Max-min eigenvalue problems, primal-dual interior point algorithms, and trust region subproblems

Franz Rendl; Robert J. Vanderbei; Henry Wolkowicz

doi:10.1080/10556789508805599

Max-min eigenvalue problems, primal-dual interior point algorithms, and trust region subproblems

Franz Rendl
, Robert J. Vanderbei
, Henry Wolkowicz

Research output: Contribution to journal › Article › peer-review

19 Scopus citations

Abstract

Two Primal-dual interior point algorithms are presented for the problem of maximizing the smallest eigenvalue of a symmetric matrix over diagonal perturbations. These algorithms prove to be simple, robust, and efficient. Both algorithms are based on transforming the problem to one with constraints over the cone of positive semidefinite matrices, i.e. Löwner order constraints. One of the algorithms does this transformation through an intermediate transformation to a trust region subproblem. This allows the removal of a dense row.

Original language	English (US)
Pages (from-to)	1-16
Number of pages	16
Journal	Optimization Methods and Software
Volume	5
Issue number	1
DOIs	https://doi.org/10.1080/10556789508805599
State	Published - Jan 1 1995

All Science Journal Classification (ASJC) codes

Software
Control and Optimization
Applied Mathematics

Keywords

1 programming
Graph bisection
Löwner partial order
Max-min eigenvalue problems
Primal-dual interior point methods
Quadratic 0
Trust region subproblems

Access to Document

10.1080/10556789508805599

Cite this

@article{8f6842f0c9f24dfb975e8a5f398b0517,

title = "Max-min eigenvalue problems, primal-dual interior point algorithms, and trust region subproblems",

abstract = "Two Primal-dual interior point algorithms are presented for the problem of maximizing the smallest eigenvalue of a symmetric matrix over diagonal perturbations. These algorithms prove to be simple, robust, and efficient. Both algorithms are based on transforming the problem to one with constraints over the cone of positive semidefinite matrices, i.e. L{\"o}wner order constraints. One of the algorithms does this transformation through an intermediate transformation to a trust region subproblem. This allows the removal of a dense row.",

keywords = "1 programming, Graph bisection, L{\"o}wner partial order, Max-min eigenvalue problems, Primal-dual interior point methods, Quadratic 0, Trust region subproblems",

author = "Franz Rendl and Vanderbei, \{Robert J.\} and Henry Wolkowicz",

note = "Funding Information: v \textasciitilde{} h ipsaper was presented at the NATO Advanced Study Institute on Algorithms for Continuous Optimization, n Ciocco, Italy, September, 1993. *Research support by Christian Doppler Laboratorium fiir Dislcrete Optimierung. +Research support by AFOSR through grant AFOSR-91-0359. \$Research support by the National Science and Engineering Research Council Canada.",

year = "1995",

month = jan,

day = "1",

doi = "10.1080/10556789508805599",

language = "English (US)",

volume = "5",

pages = "1--16",

journal = "Optimization Methods and Software",

issn = "1055-6788",

publisher = "Taylor and Francis Ltd.",

number = "1",

}

TY - JOUR

T1 - Max-min eigenvalue problems, primal-dual interior point algorithms, and trust region subproblems

AU - Rendl, Franz

AU - Vanderbei, Robert J.

AU - Wolkowicz, Henry

N1 - Funding Information: v ~ h ipsaper was presented at the NATO Advanced Study Institute on Algorithms for Continuous Optimization, n Ciocco, Italy, September, 1993. *Research support by Christian Doppler Laboratorium fiir Dislcrete Optimierung. +Research support by AFOSR through grant AFOSR-91-0359. $Research support by the National Science and Engineering Research Council Canada.

PY - 1995/1/1

Y1 - 1995/1/1

N2 - Two Primal-dual interior point algorithms are presented for the problem of maximizing the smallest eigenvalue of a symmetric matrix over diagonal perturbations. These algorithms prove to be simple, robust, and efficient. Both algorithms are based on transforming the problem to one with constraints over the cone of positive semidefinite matrices, i.e. Löwner order constraints. One of the algorithms does this transformation through an intermediate transformation to a trust region subproblem. This allows the removal of a dense row.

AB - Two Primal-dual interior point algorithms are presented for the problem of maximizing the smallest eigenvalue of a symmetric matrix over diagonal perturbations. These algorithms prove to be simple, robust, and efficient. Both algorithms are based on transforming the problem to one with constraints over the cone of positive semidefinite matrices, i.e. Löwner order constraints. One of the algorithms does this transformation through an intermediate transformation to a trust region subproblem. This allows the removal of a dense row.

KW - 1 programming

KW - Graph bisection

KW - Löwner partial order

KW - Max-min eigenvalue problems

KW - Primal-dual interior point methods

KW - Quadratic 0

KW - Trust region subproblems

UR - https://www.scopus.com/pages/publications/0029425729

UR - https://www.scopus.com/pages/publications/0029425729#tab=citedBy

U2 - 10.1080/10556789508805599

DO - 10.1080/10556789508805599

M3 - Article

AN - SCOPUS:0029425729

SN - 1055-6788

VL - 5

SP - 1

EP - 16

JO - Optimization Methods and Software

JF - Optimization Methods and Software

IS - 1

ER -

Max-min eigenvalue problems, primal-dual interior point algorithms, and trust region subproblems

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this