On Eigenvalue Optimization
SIAM Journal on OptimizationPublished 1 August 1995
Alexander Shapiro, Michael K.H. Fan
Citations109
SJR quartileQ1
SJR score1.39
SNIP1.79
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A general framework for a smooth (differentiable) approach to optimization problems involving eigenvalues of symmetric matrices is presented, based on the concept of transversality borrowed from differential geometry.
Abstract
In this paper we study optimization problems involving eigenvalues of symmetric matrices. One of the difficulties with numerical analysis of such problems is that the eigenvalues, considered as functions of a symmetric matrix, are not differentiable at those points where they coalesce. We present a general framework for a smooth (differentiable) approach to such problems. It is based on the concept of transversality borrowed from differential geometry. In that framework we discuss first- and second-order optimality conditions and rates of convergence of the corresponding second-order algorithms. Finally we present some results on the sensitivity analysis of such problems.
Keywords
Computer ScienceMathematics
SIAM Journal on OptimizationA Version of the Bundle Idea for Minimizing a Nonsmooth Function: Conceptual Idea, Convergence Analysis, Numerical Results
476 Citations1992Helga Schramm, Jochem Zowe
By adding some features of the trust region philosophy to the bundle concept, the end result is a distinguished member of the bundle family with a more stable behaviour than some other bundle versions.
PsychometrikaOrthogonal Procrustes Rotation for Two or More Matrices
326 Citations1977Jos M. F. ten Berge
SIAM Journal on OptimizationLarge-Scale Optimization of Eigenvalues
207 Citations1992Michael L. Overton
A continuously differentiable symmetric matrix function of real parameters is constructed that obeys the inequality of the following type: For α ≥ 1, β ≥ 1 using LaSalle's inequality.
SIAM Journal on Matrix Analysis and ApplicationsOn Minimizing the Maximum Eigenvalue of a Symmetric Matrix
205 Citations1988Michael L. Overton
Mathematical ProgrammingOptimality conditions and duality theory for minimizing sums of the largest eigenvalues of symmetric matrices
188 Citations1993Michael L. Overton, Robert S. Womersley
The sum of the largest eigenvalues of a symmetric matrix is a nonsmooth convex function of the matrix elements, giving a concise characterization of the subdifferential in terms of a dual matrix.
SIAM Journal on Control and OptimizationSensitivity Analysis of Nonlinear Programs and Differentiability Properties of Metric Projections
135 Citations1988Alexander Shapiro
AutomaticaNondifferentiable optimization algorithm for designing control systems having singular value inequalities
131 Citations1982E. Polak, Y. Wardi
This paper presents an optimization algorithm which permits all the constraints of control system design requirements to be considered, involving the singular values of a system or return difference transfer function matrix.
SIAM Journal on Control and OptimizationSemi-Definite Matrix Constraints in Optimization
127 Citations1985R. Fletcher
Modifications of various iterative schemes in nonlinear programming are considered in order to develop an effective algorithm for the educational testing problem, and comparative numerical experiments are described.
Mathematical programming studiesThe minimization of certain nondifferentiable sums of eigenvalues of symmetric matrices
124 Citations1975Jane Cullum, W. E. Donath +1 more
SIAM Journal on Matrix Analysis and ApplicationsSecond Derivatives for Optimizing Eigenvalues of Symmetric Matrices
92 Citations1995Michael L. Overton, Robert S. Womersley
The main idea is to minimize the maximum eigen value subject to a constraint that this eigenvalue has a certain multiplicity, and the manifold $\Omega$ of matrices with such multiple eigenvalues is parameterized using a matrix exponential representation, leading to the definition of an appropriate Lagrangian function.
Mathematical ProgrammingNewton's method for constrained optimization
45 Citations1985Jonathan Goodman
A quadratically convergent algorithm for minimizing a nonlinear function subject to nonlinear equality constraints is derived and an extension of Kantorovich's theorem shows that the algorithm maintains quadratic convergence even if the basis of the tangent space changes abruptly from iteration to iteration.
Linear Algebra and its ApplicationsExtremal problems on the set of nonnegative definite matrices
42 Citations1985Alexander Shapiro
The duality result of Olkin and Pukelsheim (1982) is extended to a wide class of problems of minimizing a real-valued function of certain elements of a symmetric matrix subject to this matrix being nonnegative definite.
Linear Algebra and its ApplicationsA quadratically convergent local algorithm on minimizing the largest eigenvalue of a symmetric matrix
28 Citations1993Michael K.H. Fan
Mathematical ProgrammingDirectional derivatives for the value-function in semi-infinite programming
25 Citations1987Peter Zencke, R. Hettich
To compute these directional derivatives a min-max-formula, well-known in convex programming, is derived and it is shown that derivatives can be obtained more easily by a limit-process using only convergent selections of solutions of P(λn), λn → $$bar \lambda $$ and their duals.
Mathematics of Operations ResearchOn Lipschitzian Stability of Optimal Solutions of Parametrized Semi-Infinite Programs
25 Citations1994Alexander Shapiro
It is shown that under certain second-order sufficient conditions, optimal solutions of the semi-infinite programs are Lipschitzian stable provided a regularity assumption related to a linearization of the considered programs is satisfied.
SIAM Journal on Matrix Analysis and ApplicationsDual Algorithm for Orthogonal Procrustes Rotations
16 Citations1988Alexander Shapiro, J.D. Botha
It will be shown that under certain conditions ensuring differentiability of the obtained function at the minimum, this method gives the global solution of the Procrustes problem.
IMA Journal of Numerical AnalysisAn Algorithm for Optimal ℓ<sub>2</sub> Scaling of Matrices
11 Citations1991G. A. Watson
Linear Algebra and its ApplicationsOn the unsolvability of inverse eigenvalues problems almost everywhere
11 Citations1983Alexander Shapiro
SIAM Journal on Matrix Analysis and ApplicationsAlgorithms for Minimum Trace Factor Analysis
10 Citations1992G. A. Watson
In this paper, some recent developments in methods for working with constraints of this kind are exploited to provide methods which are second-order independent of the eigenvalue multiplicities.
Computational Optimization and ApplicationsA quadratically convergent local algorithm on minimizing sums of the largest eigenvalues of a symmetric matrix
3 Citations1993Batool Nekooie, Michael K.H. Fan