Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-23T00:22:50.542Z Has data issue: false hasContentIssue false
  • English
  • Français

Eigenvalue optimization

Published online by Cambridge University Press:  07 November 2008

Adrian S. Lewis  and
Michael L. Overton
Adrian S. Lewis
Affiliation:
Department of Combinatorics and OptimizationUniversity of WaterlooOntario N2L 3G1, Canada E-mail: [email protected]:http://orion.uwaterloo.ca/~aslewis
Michael L. Overton
Affiliation:
Computer Science Department Courant Institute of Mathematical Sciences New York University New York, NY 10012-1110, USA E-mail: [email protected]:http://cs.nyu.edu/cs/faculty/overton
Get access Rights & Permissions [Opens in a new window]

Extract

Optimization problems involving eigenvalues arise in many different mathematical disciplines. This article is divided into two parts. Part I gives a historical account of the development of the field. We discuss various applications that have been especially influential, from structural analysis to combinatorial optimization, and we survey algorithmic developments, including the recent advance of interior-point methods for a specific problem class: semidefinite programming. In Part II we primarily address optimization of convex functions of eigenvalues of symmetric matrices subject to linear constraints. We derive a fairly complete mathematical theory, some of it classical and some of it new. Using the elegant language of conjugate duality theory, we highlight the parallels between the analysis of invariant matrix norms and weakly invariant convex matrix functions. We then restrict our attention further to linear and semidefinite programming, emphasizing the parallel duality theory and comparing primal-dual interior-point methods for the two problem classes. The final section presents some apparently new variational results about eigenvalues of nonsymmetric matrices, unifying known characterizations of the spectral abscissa (related to Lyapunov theory) and the spectral radius (as an infimum of matrix norms).

Type
Research Article
Information
Acta Numerica , Volume 5 , January 1996 , pp. 149 - 190
Copyright
Copyright © Cambridge University Press 1996

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Alizadeh, F. (1991), Combinatorial Optimization with Interior Point Methods and Semidefinite Matrices, PhD thesis, University of Minnesota.Google Scholar
Alizadeh, F. (1995), ‘Interior point methods in semidefinite programming with applications to combinatorial optimization’, SIAM J. Optim. 5, 13–51.Google Scholar
Alizadeh, F., Haeberly, J.-P. A. and Overton, M. L. (1996 a), ‘Complementarity and nondegeneracy in semidefinite programming’, Mathematical Programming (Series B). To appear.Google Scholar
Alizadeh, F., Haeberly, J.-P. A. and Overton, M. L. (1996 b), Primal-dual interior-point methods for semidefinite programming: convergence rates, stability, and numerical results. In preparation.Google Scholar
Arazy, J. (1981), ‘On the geometry of the unit ball of unitary matrix spaces’, Integral Equations and Operator Theory 4, 151–171.CrossRefGoogle Scholar
Ashbaugh, M. S. and Benguria, R. D. (1991), ‘Proof of the Payne–Pólya–Weinberger conjecture’, Bulletin of the American Math Society 25, 19–29.CrossRefGoogle Scholar
Barbara, A. and Crouzeix, J.-P. (1994), ‘Concave gauge functions and applications’, ZOR – Mathematical Methods of Operations Research 40, 43–74.CrossRefGoogle Scholar
Baumgärtel, H. (1985), Analytic Perturbation Theory for Matrices and Operators, Birkhäuser, Boston.Google Scholar
Bellman, R. and Fan, K. (1963), On systems of linear inequalities in Hermitian matrix variables, in Convexity, American Mathematical Society, Providence, pp. 1–11. Proceedings of Symposia in Pure Mathematics VII.Google Scholar
Boyd, S., Ghaoui, L. E., Feron, E. and Balakrishnan, V. (1994), Linear Matrix Inequalities in System and Control Theory, SIAM, Philadelphia.Google Scholar
Burke, J. V. and Overton, M. L. (1994), ‘Differential properties of the spectral abscissa and the spectral radius for analytic matrix–valued mappings’, Nonlinear Analysis, Theory, Methods and Applications 23, 467–488.Google Scholar
Clarke, F. H. (1983), Optimization and Nonsmooth Analysis, Wiley, New York. Reprinted by SIAM, Philadelphia, 1990.Google Scholar
Cox, S. J. (1992), ‘The shape of the ideal column’, Mathematical Intelligencer 14, 16–31.Google Scholar
Cox, S. J. (1993), ‘Steven Cox responds’, Mathematical Intelligencer 15, 68.Google Scholar
Cox, S. J. and Maddocks, J. H. (1996), Optimal design of the nonlinear elastica. In preparation.Google Scholar
Cox, S. J. and Overton, M. L. (1992), ‘The optimal design of columns against buckling’, SIAM J. Math. Anal. 23, 287–325.Google Scholar
Cox, S. J. and Overton, M. L. (1996), ‘Perturbing the critically damped wave equation’, SIAM J. Math. Anal. To appear.CrossRefGoogle Scholar
Craven, B. D. and Mond, B. (1981), ‘Linear programming with matrix variables’, Linear Algebra and its Applications 38, 73–80.Google Scholar
Cullum, J., Donath, W. E. and Wolfe, P. (1975), ‘The minimization of certain nondifferentiable sums of eigenvalues of symmetric matrices’, Mathematical Programming Study 3, 35–55.Google Scholar
Dantzig, G. B. (1991), Linear programming, in History of Mathematical Programming: A Collection of Personal Reminiscences (Lenstra, J. K., Rinnooy Kan, A. H. G. and Schrijver, A., eds), North-Holland, Amsterdam, pp. 19–31.Google Scholar
Davis, C. (1957), ‘All convex invariant functions of Hermitian matrices’, Archiv der Mathematik 8, 276–278.Google Scholar
de Sá, E. M. (1994 a), ‘Exposed faces and duality for symmetric and unitarily invariant norms’, Linear Algebra and its Applications 197,198, 429–450.CrossRefGoogle Scholar
de Sá, E. M. (1994 b), ‘Faces and traces of the unit ball of a symmetric gauge function’, Linear Algebra and its Applications 197,198, 349–395.Google Scholar
de Sá, E. M. (1994 c), ‘Faces of the unit ball of a unitarily invariant norm’, Linear Algebra and its Applications 197,198, 451–493.Google Scholar
Deville, R., Godefroy, G. and Zizler, V. (1993), Smoothness and Renormings in Banach Spaces, Longman, Harlow, UK.Google Scholar
Donath, W. E. and Hoffman, A. J. (1973), ‘Lower bounds for the partitionings of graphs’, IBM Journal of Research and Development 17, 420–425.Google Scholar
Fiedler, M. (1973), ‘Algebraic connectivity of graphs’, Czech. Math. Journal 23, 298–305.Google Scholar
Fletcher, R. (1985), ‘Semi-definite constraints in optimization’, SIAM J. Control Optim. 23, 493–513.Google Scholar
Fletcher, R. (1991), ‘A new variational result for quasi-Newton formulae’, SIAM J. Optim. 1, 18–21.Google Scholar
Friedland, S. (1981), ‘Convex spectral functions’, Linear and multilinear algebra 9, 299–316.Google Scholar
Friedland, S., Nocedal, J. and Overton, M. L. (1987), ‘The formulation and analysis of numerical methods for inverse eigenvalue problems’, SIAM J. Numer. Anal. 24, 634–667.CrossRefGoogle Scholar
Goemans, M. X. and Williamson, D. P. (1996), ‘Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming’, J. Assoc. Comput. Mach. To appear.Google Scholar
Gonzaga, C. C. (1992), ‘Path-following methods for linear programming’, SIAM Review 34, 167–224.CrossRefGoogle Scholar
Grötschel, M., Lovász, L. and Schriver, A. (1988), Geometric Algorithms and Combinatorial Optimization, Springer, New York.CrossRefGoogle Scholar
Helmberg, C. (1994), An Interior Point Method for Semidefinite Programming and Max-Cut Bounds, PhD thesis, Technische Universitát Graz, Austria.Google Scholar
Helmberg, C., Rendl, F., Vanderbei, R. and Wolkowicz, H. (1996), ‘An interior-point method for semidefinite programming’, SIAM J. Optim. To appear.Google Scholar
Hirriart-Urruty, J.-B. and Ye, D. (1995), ‘Sensitivity analysis of all eigenvalues of a symmetric matrix’, Numer. Math. 70, 45–72.CrossRefGoogle Scholar
Horn, R. A. and Johnson, C. R. (1985), Matrix Analysis, Cambridge University Press, UK.Google Scholar
Horn, R. A. and Johnson, C. R. (1991), Topics in Matrix Analysis, Cambridge University Press, UK.Google Scholar
Karmarkar, N. (1984), ‘A new polynomial time algorithm for linear programming’, Combinatorica 4, 373–395.Google Scholar
Karmarkar, N. and Thakur, S. (1992), An interior-point approach to a tensor optimization problem with application to upper bounds in integer quadratic optimization problems, in Integer Programming and Combinatorial Optimization (Balas, E., Cornuejils, G. and Kannan, R., eds), pp. 406–419. Proceedings of a conference held at Carnegie Mellon University by the Math. Programming Society.Google Scholar
Kirmser, P. G. and Hu, K.-K. (1993), ‘The shape of the ideal column reconsidered’, Mathematical Intelligencer 15, 62–67.Google Scholar
Kojima, M., Mizuno, S. and Yoshise, A. (1989), A primal-dual interior point method for linear programming, in Progress in Mathematical Programming, Interior-Point and Related Methods (Megiddo, N., ed.), Springer, New York, pp. 29–47.Google Scholar
Kojima, M., Shindoh, S. and Hara, S. (1994), Interior-point methods for the monotone linear complementarity problem in symmetric matrices. Technical Report B-282, Department of Information Sciences, Tokyo Inst. of Technology.Google Scholar
Lewis, A. S. (1995 a), ‘The convex analysis of unitarily invariant functions’, J. Convex Anal. 2, 173–183.Google Scholar
Lewis, A. S. (1995 b), Eigenvalue-constrained faces. Technical Report CORR 95–22, University of Waterloo. Submitted to Linear Algebra and its Applications.Google Scholar
Lewis, A. S. (1995 c), Von Neumann‘s lemma and a Chevalley-type theorem for convex functions on Cartan subspaces. Technical Report CORR 95–19, University of Waterloo. Submitted to Transactions of the American Mathematical Society.Google Scholar
Lewis, A. S. (1996 a), ’Convex analysis on the Hermitian matrices‘, SIAM J. Optim. 6, 164–177.Google Scholar
Lewis, A. S. (1996 b), ’Derivatives of spectral functions‘, Mathematics of Operations Research. To appear.Google Scholar
Lewis, A. S. (1996 c), ‘Group invariance and convex matrix analysis’, SIAM J. Matrix Anal. Appl. To appear.CrossRefGoogle Scholar
Lustig, I. J., Marsten, R. E. and Shanno, D. F. (1994), ‘Interior point methods for linear programming: Computational state of the art’, ORSA Journal on Computing 6, 1–14.CrossRefGoogle Scholar
Marshall, A. W. and Olkin, I. (1979), Inequalities: Theory of Majorization and its Applications, Academic Press, New York.Google Scholar
Martínez-Legaz, J.-E. (1995), On convex and quasi-convex spectral functions. Technical report, Universitat Autònoma de Barcelona.Google Scholar
McLinden, L. (1980), ‘An analogue of Moreau's proximation theorem with applications to nonlinear complementarity problems’, Pacific Journal of Mathematics pp. 101–161.CrossRefGoogle Scholar
Megiddo, N. (1989), Pathways to the optimal set in linear programming, in Progress in Mathematical Programming, Interior-Point and Related Methods (Megiddo, N., ed.), Springer, New York, pp. 131–158.Google Scholar
Mohar, B. and Poljak, S. (1993), Eigenvalues in combinatorial optimization, in Combinatorial and graph-theoretic problems in linear algebra (Brualdi, R., Friedland, S. and Klee, V., eds), Vol. 50, Springer. IMA Volumes in Mathematics and its Applications.Google Scholar
Monteiro, R. and Adler, I. (1989), ‘Interior path-following primal-dual algorithms: Part I: Linear programming’, Mathematical Programming 44, 27–41.Google Scholar
Moro, J., Burke, J. V. and Overton, M. L. (1995), On the Lidskii–Vishik–Lyusternik perturbation theory for eigenvalues of matrices with arbitrary Jordan structure. Technical Report 710, NYU Comp. Sci. Dept. Submitted to SIAM J. Matr. Anal. Appl.Google Scholar
Nesterov, Y. and Nemirovskii, A. (1994), Interior Point Polynomial Methods in Convex Programming, SIAM, Philadelphia.Google Scholar
Nesterov, Y. and Todd, M. (1996), ‘Self-scaled barriers and interior-point methods for convex programming’, Mathematics of Operations Research. To appear.Google Scholar
Olhoff, N. and Rasmussen, S. (1977), ‘On single and bimodal optimum buckling loads of clamped columns’, Int. J. Solids Struct. 9, 605–614.Google Scholar
Ortega, J. M. (1972), Numerical Analysis: A Second Course, Academic Press, New York and London. Reprinted by SIAM, Philadelphia, 1990.Google Scholar
Overton, M. L. (1988), ‘On minimizing the maximum eigenvalue of a symmetric matrix’, SIAM J. Matrix Anal. Appl. 9, 256–268.Google Scholar
Overton, M. L. (1992), ‘Large-scale optimization of eigenvalues’, SIAM J. Optim. 2, 88–120.Google Scholar
Overton, M. L. and Womersley, R. S. (1988), ‘On minimizing the spectral radius of a nonsymmetric matrix function – optimality conditions and duality theory’, SIAM J. Matrix Anal. Appl. 9, 473–498.Google Scholar
Overton, M. L. and Womersley, R. S. (1993), ‘Optimality conditions and duality theory for minimizing sums of the largest eigenvalues of symmetric matrices’, Mathematical Programming 62, 321–357.CrossRefGoogle Scholar
Overton, M. L. and Womersley, R. S. (1995), ‘Second derivatives for optimizing eigenvalues of symmetric matrices’, SIAM J. Matrix Anal. Appl. 16, 697–718.Google Scholar
Pataki, G. (1995), On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues. Technical Report MSRR-604 (revised), Graduate School of Industrial Administration, Carnegie–Mellon University. Submitted to Math. of Operations Research.Google Scholar
Payne, L. E., Pólya, G. and Weinberger, H. F. (1956), ‘On the ratio of consecutive eigenvalues’, Journal of Mathematics and Physics 35, 289–298.Google Scholar
Poljak, S. and Tuza, Z. (1993), Max-cut problem – a survey. Technical report, Charles University, Prague.Google Scholar
Pothen, A. (1996), Graph partitioning algorithms in scientific computing, in Parallel Numerical Algorithms (Keyes, D., Sameh, A. and Venkatakrishnan, V., eds), Kluwer. To appear.Google Scholar
Rendl, F. and Wolkowicz, H. (1992), ‘Applications of parametric programming and eigenvalue maximization to the quadratic assignment problem’, Mathematical Programming 53, 63–78.Google Scholar
Ringertz, U. T. (1995), ‘An algorithm for optimization of nonlinear shell structures’, International Journal for Numerical Methods in Engineering 38, 299–314.Google Scholar
Ringertz, U. T. (1996), Eigenvalues in optimum structural design, in Proceedings of an IMA workshop on Large-Scale Optimization (Conn, A. R., Biegler, L. T., Coleman, T. F. and Santosa, F., eds). To appear.Google Scholar
Rockafellar, R. T. (1970), Convex Analysis, Princeton University Press, Princeton University.Google Scholar
Schramm, H. and Zowe, J. (1992), ‘A version of the bundle idea for minimizing a nonsmooth function: conceptual idea, convergence analysis, numerical results’, SIAM J. Optim. 2, 121–152.CrossRefGoogle Scholar
Seeger, A. (1996), ‘Convex analysis of spectrally-defined matrix functions’, SIAM J. Optim. To appear.Google Scholar
Shapiro, A. (1996), ‘First and second order analysis of nonlinear semidefinite programs’, Mathematical Programming (Series B). To appear.Google Scholar
Shapiro, A. and Fan, M. K. H. (1995), ‘On eigenvalue optimization’, SIAM J. Optim. 3, 552–568.Google Scholar
Tadjbakhsh, I. and Keller, J. B. (1962), ‘Strongest columns and isoperimetric inequalities for eigenvalues’, J. Appl. Mech. 29, 159–164.Google Scholar
Theobald, C. M. (1975), ‘An inequality for the trace of the product of two symmetric matrices’, Mathematical Proceedings of the Cambridge Philosophical Society 77, 265–266.Google Scholar
Tsing, N.-K., Fan, M. K. H. and Verriest, E. I. (1994), ‘On analyticity of functions involving eigenvalues’, Linear Algebra and its Applications 207, 159–180.Google Scholar
Tunçel, L. (1995). Private communication.Google Scholar
Vandenberghe, L. and Boyd, S. (1995), ‘Primal-dual potential reduction method for problems involving matrix inequalities’, Mathematical Programming (Series B) 69, 205–236.Google Scholar
Vandenberghe, L. and Boyd, S. (1996), ‘Semidefinite programming’, SIAM Review 38, 49–95.Google Scholar
Watson, G. A. (1992), ‘Characterization of the subdifferential of some matrix norms’, Linear Algebra and its Applications 170, 33–45.Google Scholar
Wright, M. H. (1992), Interior methods for constrained optimization, in Acta Numerica, Cambridge University Press, UK, pp. 341–407.Google Scholar
Wright, S. J. (1995), ‘Stability of linear equations solvers in interior-point methods’, SIAM J. Matrix Anal. Appl. 16, 1287–1307.Google Scholar
Zhang, Y. and Tapia, R. A. (1993), ‘A superlinearly convergent polynomial primal-dual interior-point algorithm for linear programming’, SIAM J. Optim. 3, 118–133.CrossRefGoogle Scholar
Zhang, Y., Tapia, R. A. and Dennis, J. E. (1992), ‘On the superlinear and quadratic convergence of primal-dual interior point linear programming algorithms’, SIAM J. Optim. 2, 304–324.Google Scholar
Ziȩtak, K. (1988), ‘On the characterization of the extremal points of the unit sphere of matrices’, Linear Algebra and its Applications 106, 57–75.Google Scholar
Ziȩtak, K. (1993), ‘Subdifferentials, faces and dual matrices’, Linear Algebra and its Applications 185, 125–141.Google Scholar