Method of centers for minimizing generalized eigenvalues.

*(English)*Zbl 0781.65051Authors’ abstract: We consider the problem of minimizing the largest generalized eigenvalue of a pair of symmetric matrices, each of which depends affinely on the decision variables. Although this problem may appear specialized, it is in fact quite general, and includes for example all linear, quadratic and linear fractional programs. Many problems arising in control theory can be cast in this form. The problem is non- differentiable but quasi-convex, so methods such as the cutting-plane algorithm of J. E. Kelley Jr. [J. Soc. Indust. Appl. Math. 8, 703- 712 (1960; Zbl 0098.12104)] or the ellipsoid algorithm of N. Z. Shor [Minimization methods for non-differentiable functions (1985; Zbl 0561.90058)] and A. S. Nemirovskij and D. B. Yudin [Problem complexity and method efficiency in optimization (1979; Zbl 0501.90061)] are guaranteed to minimize it.

In this paper we describe relevant background material and a simple interior-point method that solves such problems more efficiently. The algorithm is a variation on the method of centers by P. Huard [Resolution of mathematical programming with nonlinear constraints by the method of centres (1967; Zbl 0157.497)], using a self-concordant barrier for matrix inequalities developed by Yu. Nesterov and A. Nemirovsky [An interior point method for generalized linear-fractional programming. Math. Programming, Ser. B (to appear)]. (Nesterov and Nemirovsky have also extended their potential reduction methods to handle the same problem.)

Since the problem is quasi-convex but not convex, devising a non- heuristic stopping criterion (i.e. one that guarantees given accuracy) is more difficult than in the convex case. We describe several non-heuristic stopping criteria that are based on the dual of a related convex problem and a new ellipsoidal approximation that is slightly sharper, in some cases, than a more general result due to Nesterov and Nemirovsky [loc. cit.]. The algorithm is demonstrated on an example: determining the quadratic Lyapunov function that optimizes a decay-rate estimate for a differential inclusion.

In this paper we describe relevant background material and a simple interior-point method that solves such problems more efficiently. The algorithm is a variation on the method of centers by P. Huard [Resolution of mathematical programming with nonlinear constraints by the method of centres (1967; Zbl 0157.497)], using a self-concordant barrier for matrix inequalities developed by Yu. Nesterov and A. Nemirovsky [An interior point method for generalized linear-fractional programming. Math. Programming, Ser. B (to appear)]. (Nesterov and Nemirovsky have also extended their potential reduction methods to handle the same problem.)

Since the problem is quasi-convex but not convex, devising a non- heuristic stopping criterion (i.e. one that guarantees given accuracy) is more difficult than in the convex case. We describe several non-heuristic stopping criteria that are based on the dual of a related convex problem and a new ellipsoidal approximation that is slightly sharper, in some cases, than a more general result due to Nesterov and Nemirovsky [loc. cit.]. The algorithm is demonstrated on an example: determining the quadratic Lyapunov function that optimizes a decay-rate estimate for a differential inclusion.

Reviewer: D.Kershaw (Lancaster)

##### MSC:

65K05 | Numerical mathematical programming methods |

65F15 | Numerical computation of eigenvalues and eigenvectors of matrices |

90C25 | Convex programming |

##### Keywords:

minimizing the largest generalized eigenvalue; symmetric matrices; cutting-plane algorithm; ellipsoid algorithm; interior-point method; method of centers; quasi-convex; stopping criterion##### Software:

QDES
PDF
BibTeX
XML
Cite

\textit{S. Boyd} and \textit{L. El Ghaoui}, Linear Algebra Appl. 188--189, 63--111 (1993; Zbl 0781.65051)

Full Text:
DOI

**OpenURL**

##### References:

[1] | Alizadeh, F., Combinatorial optimization with interior point methods and semidefinite matrices, () |

[2] | Alizadeh, F., Combinatorial optimization with semidefinite matrices, () |

[3] | Alizadeh, F., Optimization over the positive-definite cone: interior point methods and combinatorial applications, () · Zbl 0814.90071 |

[4] | Allwright, J., On maximizing the minimum eigenvalue of a linear combination of symmetric matrices, SIAM J. matrix anal. appl., 10, 347-382, (1989) · Zbl 0685.15015 |

[5] | Boyd, S.; Barratt, C., Linear controller design: limits of performance, (1991), Prentice-Hall · Zbl 0748.93003 |

[6] | Balakrishnan, V.; Feron, E.; Boyd, S.; El Ghaoui, L., Computing bounds for the structured singular value via an interior point algorithm, Proceedings of the American control conference, 2195-2196, (1992), Chicago |

[7] | S. Boyd, L. El Ghaoui, E. Feron, and V. Balakrishnan, Linear matrix inequalities in systems and control theory, monograph in preparation. · Zbl 0816.93004 |

[8] | Bland, R.G.; Goldfarb, D.; Todd, M.J., The ellipsoid method: A survey, Oper. res., 29, 6, 1039-1091, (1981) · Zbl 0474.90056 |

[9] | Boyd, S.; Yang, Q., Structured and simultaneous Lyapunov functions for system stability problems, Internat. J. control, 49, 6, 2215-2240, (1989) · Zbl 0683.93057 |

[10] | Cullum, J.; Donath, W.; Wolfe, P., The minimization of certain nondifferentiable sums of eigenvalues of symmetric matrices, Math. programming study, 3, 35-55, (1975) · Zbl 0355.90054 |

[11] | Craven, B.; Mond, B., Linear programming with matrix variables, Linear algebra appl., 38, 73-80, (1981) · Zbl 0464.90052 |

[12] | Dikin, I., Iterative solution of problems of linear and quadratic programming, Soviet math. dokl., 8, 3, 674-675, (1967) · Zbl 0189.19504 |

[13] | El Ghaoui, L.; Balakrishnan, V.; Feron, E.; Boyd, S., On maximizing a robustness measure for structured nonlinear perturbations, Proceedings of the American control conference, 2923-2924, (1992), Chicago |

[14] | M. Fan, A quadratically convergent algorithm on minimizing the largest eigenvalue of a symmetric matrix, Linear Algebra Appl., submitted for publication. · Zbl 0781.65023 |

[15] | Feron, E.; Balakrishnan, V.; Boyd, S., Design of stabilizing state feedback for delay systems via convex optimization, Proceedings of the IEEE conference on decision and control, (1992), Tucson, Ariz. |

[16] | Feron, E.; Balakrishnan, V.; Boyd, S.; El Ghaoui, L., Numerical methods for H2 related problems, Proceedings of the American control conference, 2921-2922, (1992), Chicago |

[17] | Fletcher, R., Semidefinite matrix constraints in optimization, SIAM J. control optim., 23, 493-513, (1985) · Zbl 0567.90088 |

[18] | Fiacco, A.; McCormick, G., Nonlinear programming: sequential unconstrained minimization techniques, Classics appl. math., (1990), SIAM Philadelphia · Zbl 0713.90043 |

[19] | Fan, M.; Nekooie, B., On minimizing the largest eigenvalue of a symmetric matrix, Proceedings of the IEEE conference on decision and control, 134-139, (1992) |

[20] | Friedland, S.; Nocedal, J.; Overton, M., The formulation and analysis of numerical methods for inverse eigenvalue problems, SIAM J. numer. anal., 24, 3, 634-667, (1987) · Zbl 0622.65030 |

[21] | Gács, P.; Lovász, L., Khachiyan’s algorithm for linear programming, Math. program. stud., 14, 61-68, (1981) · Zbl 0463.90066 |

[22] | Goh, C.; Teo, D., On minimax eigenvalue problems via constrained optimization, J. optim. theory appl., 57, 1, 59-68, (1988) · Zbl 0619.90067 |

[23] | Haeberly, J., On shape optimizing the ratio of the first two eigenvalues of the Laplacian, () |

[24] | Huard, P., Resolution of mathematical programming with nonlinear constraints by the method of centers, (1967), North Holland Amsterdam · Zbl 0157.49701 |

[25] | Jarre, F., An interior-point method for minimizing the maximum eigenvalue of a linear combination of matrices, Technical report 91-8, (1991), SIAM J. Control Optim., to appear. |

[26] | F. Jarre, Interior-point methods for convex programming, Appl. Math. Optim., to appear. · Zbl 0767.90063 |

[27] | Karmarkar, N., A new polynomial-time algorithm for linear programming, Combinatorica, 4, 4, 373-395, (1984) · Zbl 0557.90065 |

[28] | Kelley, J.E., The cutting-plane method for solving convex programs, J. soc. indust. appl. math., 8, 4, 703-712, (1960) · Zbl 0098.12104 |

[29] | Khachiyan, L., A polynomial algorithm in linear programming, Soviet math. dokl., 20, 191-194, (1979) · Zbl 0409.90079 |

[30] | Kortanek, K.; Potra, F.; Ye, Y., On some efficient interior point methods for nonlinear convex programming, Linear algebra appl., 152, 169-189, (1991) · Zbl 0741.65052 |

[31] | Lieu, B.; Huard, P., La méthode des centres dans un espace topologique, Numer. math., 8, 56-67, (1965) · Zbl 0171.40802 |

[32] | Nesterov, Yu.; Nemirovsky, A., General approach to polynomial-time algorithm design for convex programming, (1988), Central Economic Mathematical Inst., USSR Academy of Sciences Moscow, Technical Report |

[33] | Nesterov, Yu.; Nemirovsky, A., Optimization over positive semidefinite matrices: mathematical background and User’s manual, (1990), USSR Academy of Sciences, Central Economic and Mathematical Inst 32 Krasikova St., Moscow 117418, USSR |

[34] | Nesterov, Yu.; Nemirovsky, A., Self-concordant functions and polynomial time methods in convex programming, (1990), Central Economic and Mathematical Inst., USSR Academy of Sciences Moscow, Technical Report |

[35] | Nesterov, Yu.; Nemirovsky, A., Conic formulation of a convex programming problem and duality, () |

[36] | Yu. Nesterov and A. Nemirovsky, An interior point method for generalized linear-fractional programming, Math. Programming Ser B, submitted for publication. · Zbl 0754.90042 |

[37] | Nesterov, Yu.; Nemirovsky, A., Interior point polynomial methods in convex programming: theory and applications, (1993), SIAM |

[38] | Nemirovsky, A.; Yudin, D., Problem complexity and method efficiency in optimization, (1983), Wiley |

[39] | Overton, M., On minimizing the maximum eigenvalue of a symmetric matrix, SIAM J. matrix anal. appl., 9, 2, 256-268, (1988) · Zbl 0647.65044 |

[40] | Overton, M., Large-scale optimization of eigenvalues, SIAM J. optim., 88-120, (1992) · Zbl 0757.65072 |

[41] | Overton, M.; Womersley, R., On the sum of the largest eigenvalues of a symmetric matrix, SIAM J. matrix anal. appl., 41-45, (1992) · Zbl 0747.15005 |

[42] | M. Overton and R. Womersley, Optimality conditions and duality theory for minimizing sums of the largest eigenvalues of symmetric matrices, Math. Programming, to appear. · Zbl 0806.90114 |

[43] | Panier, E., On the need for special purpose algorithms for minimax eigenvalue problems, Journal optim. theory appl., 62, 2, 279-287, (1989) · Zbl 0652.49010 |

[44] | Pyatnitskii, E.S.; Skorodinskii, V.I., Numerical method of construction of Lyapunov functions and absolute stability criteria in the form of numerical procedures, Automat. remote control, 44, 11, 1427-1437, (1983) · Zbl 0547.93020 |

[45] | Polak, E.; Wardi, Y., A nondifferentiable optimization algorithm for the design of control systems subject to singular value inequalities over a frequency range, Automatica, 18, 3, 267-283, (1982) · Zbl 0532.49017 |

[46] | Ringertz, U.T., Optimal design of nonlinear shell structures, () · Zbl 0868.73058 |

[47] | Shapiro, A., Extremal problems on the set of nonnegative definite matrices, Linear algebra appl., 67, 7-18, (1985) · Zbl 0565.90056 |

[48] | Shor, N.Z., Minimization methods for non-differentiable functions, () · Zbl 0524.49002 |

[49] | Sonnevend, G., An “analytical centre” for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming, (), 866-878 |

[50] | Sonnevend, G., New algorithms in convex programming based on a notion of “centre” (for systems of analytic inequalities) and on rational extrapolation, Internat. ser. numer. math., 84, 311-326, (1988) |

[51] | Sonnevend, G.; Golub, G.; Van Dooren, P., Applications of analytic centers, Numerical linear algebra, digital signal processing, and parallel algorithms, NATO adv. sci. inst. ser. F comput. systems sci., F70, 617-632, (1991) · Zbl 0742.65052 |

[52] | L. Vandenberghe and S. Boyd, Primal-dual potential reduction method for problems involving matrix inequalities, Math. Programming, submitted for publication. · Zbl 0857.90104 |

[53] | Wright, M., Interior methods for constrained optimization, Acta numer., 1, (1992) · Zbl 0766.65053 |

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.