×
Mengi, Emre

A support function based algorithm for optimization with eigenvalue constraints. (English) Zbl 1359.65094

SIAM J. Optim. 27, No. 1, 246-268 (2017).
Summary: Optimization of convex functions subject to eigenvalue constraints is intriguing because of peculiar analytical properties of eigenvalue functions and is of practical interest because of a wide range of applications in fields such as structural design and control theory. Here we focus on the optimization of a linear objective subject to a constraint on the smallest eigenvalue of an analytic and Hermitian matrix-valued function. We propose a numerical approach based on quadratic support functions that overestimate the smallest eigenvalue function globally. The quadratic support functions are derived by employing variational properties of the smallest eigenvalue function over a set of Hermitian matrices. We establish the local convergence of the algorithm under mild assumptions and deduce a precise rate of convergence result by viewing the algorithm as a fixed point iteration. The convergence analysis reveals that the algorithm is immune to the nonsmooth nature of the smallest eigenvalue. We illustrate the practical applicability of the algorithm on the pseudospectral functions.

Cited in 2 Documents

MSC:

65K05 Numerical mathematical programming methods
90C26 Nonconvex programming, global optimization

Keywords:

nonsmooth optimization; analytical properties of eigenvalues; support functions; Karush-Kuhn-Tucker conditions; fixed point theory; pseudospectra; local convergence; algorithm; Hermitian matrices

Software:

Eigtool; PSAPSR
PDF BibTeX XML Cite
\textit{E. Mengi}, SIAM J. Optim. 27, No. 1, 246--268 (2017; Zbl 1359.65094)
Full Text: DOI arXiv Link
  • logo of hbz
  • logo of WorldCat

References:

[1] W. Achtziger and M. Kocvara, Structural topology optimization with eigenvalues, SIAM J. Optim., 18 (2007), pp. 1129–1164. · Zbl 1149.74044
[2] V. Blondel, M. Gevers, and A. Lindquist, Survey on the state of systems and control, Eur. J. Control, 1 (1995), pp. 5–23. · Zbl 1177.93001
[3] J. M. Borwein and A. S. Lewis, Convex and Nonlinear Optimization, Springer-Verlag, Berlin, 2000. · Zbl 0953.90001
[4] S. Boyd and L. Vandenberghe, Convex Optimization, 7th ed., Cambridge University Press, New York, 2009. · Zbl 1058.90049
[5] J. V. Burke, A. S. Lewis, and M. L. Overton, Robust stability and a criss-cross algorithm for pseudospectra, IMA J. Numer. Anal., 23 (2003), pp. 359–375. · Zbl 1042.65060
[6] E. W. Cheney and A. A. Goldstein, Newton’s method for convex programming and Tchebycheff approximation, Numer. Math., 1 (1959), pp. 253–268. · Zbl 0113.10703
[7] F. H. Clarke, Generalized gradients and applications, Trans. Amer. Math. Soc., 205 (1975), pp. 247–262. · Zbl 0307.26012
[8] F. H. Clarke, Optimization and Nonsmooth Analysis, SIAM, Philadelphia, 1990. · Zbl 0696.49002
[9] S. J. Cox and M. L. Overton, On the optimal design of columns against buckling, SIAM J. Math. Anal., 23 (1992), pp. 287–325. · Zbl 0793.73070
[10] N. Guglielmi and M. L. Overton, Fast algorithms for the approximation of the pseudospectral abscissa and pseudospectral radius of a matrix, SIAM J. Matrix Anal. Appl., 32 (2011), pp. 1166–1192. · Zbl 1248.65034
[11] W. Hare and C. Sagastizabal, A redistributed proximal bundle method for nonconvex optimization, SIAM J. Optim., 20 (2010), pp. 2442–2473. · Zbl 1211.90183
[12] R. A. Horn and C. A. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, UK, 1990. · Zbl 0704.15002
[13] J. E. Kelley, The cutting-plane method for solving convex programs, J. SIAM, 8 (1960), pp. 703–712, . · Zbl 0098.12104
[14] K. C. Kiwiel, Methods of Descent for Nondifferentiable Optimization, Lecture Notes in Math. 1133, Springer-Verlag, New York, 1985. · Zbl 0561.90059
[15] P. Lancaster, On eigenvalues of matrices dependent on a parameter, Numer. Math., 6 (1964), pp. 377–387. · Zbl 0133.26201
[16] C. Lemaréchal, A. Nemirovskii, and Y. Nesterov, New variants of bundle methods, Math. Program., 69 (1995), pp. 111–147. · Zbl 0857.90102
[17] M. Mäkelä, Survey of bundle methods for nonsmooth optimization, Optim. Methods Softw., 17 (2002), pp. 1–29, .
[18] E. Mengi and M. L. Overton, Algorithms for the computation of the pseudospectral radius and the numerical radius of a matrix, IMA J. Numer. Anal., 25 (2005), pp. 648–669. · Zbl 1082.65043
[19] E. Mengi, E. A. Yildirim, and M. Kilic, Numerical optimization of eigenvalues of Hermitian matrix functions, SIAM J. Matrix Anal. Appl., 35 (2014), pp. 699–724. · Zbl 1307.65043
[20] J. E. Mitchell, Cutting Plane Methods and Subgradient Methods, INFORMS Tutorials in Operations Research, INFORMS, 2009.
[21] F. Rellich, Perturbation Theory of Eigenvalue Problems, Gordon and Breach, London, 1969. · Zbl 0181.42002
[22] J. Shen and J. Lam, On static output-feedback stabilization for multi-input multi-output positive systems, Internat. J. Robust Nonlinear Control, 25 (2015), pp. 3154–3162, . · Zbl 1327.93318
[23] L. N. Trefethen and M. Embree, Spectra and Pseudospectra. The Behavior of Nonnormal Matrices and Operators, Princeton University Press, Princeton, NJ, 2005. · Zbl 1085.15009
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.