×

Spectral bundle methods for non-convex maximum eigenvalue functions: second-order methods. (English) Zbl 1124.90035

Summary: We study constrained and unconstrained optimization programs for nonconvex maximum eigenvalue functions. We show how second order techniques may be introduced as soon as it is possible to reliably guess the multiplicity of the maximum eigenvalue at a limit point. We examine in which way standard and projected Newton steps may be combined with a nonsmooth first-order method to obtain a globally convergent algorithm with a fair chance to local superlinear or quadratic convergence.

MSC:

90C30 Nonlinear programming
49J52 Nonsmooth analysis
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Apkarian, P., Noll, D.: Nonsmooth Hsynthesis. Submitted
[2] Apkarian, P., Noll, D.: Controller design via nonsmooth multi-directional search. SIAM Journal on Control and Optimization · Zbl 1139.93012
[3] Apkarian, P., Noll, D.: Nonsmooth optimization for multidisk Hsynthesis. Submitted · Zbl 1293.93310
[4] Arnold, V.I.: On matrices depending on parameters. Russ. Math. Surveys 26, 29–43 (1971) · Zbl 0259.15011 · doi:10.1070/RM1971v026n02ABEH003827
[5] Bonnans, J.F.: Local analysis of Newton-type methods for variational inequalities and nonlinear programming. Appl. Math. Opt. 29, 161–186 (1994) · Zbl 0809.90115 · doi:10.1007/BF01204181
[6] Bonnans, J.F., Panier, E., Tits, A.L., Zhou, J.L.: Avoiding the Maratos effect by means of a nonmonotone line search II: Inequality problems - feasible iterates. SIAM J. Num. Anal., vol. 29 (4), 1187–1202 (1992) · Zbl 0763.65042 · doi:10.1137/0729072
[7] Bui Trong Lieu, Huard, P.: La méthode des centres dans un espace topologique. Numerische Mathematik, vol. 8, 56–67 (1966) · Zbl 0171.40802 · doi:10.1007/BF02165238
[8] Clarke, F.H.: Optimization and Nonsmooth Analysis. John Wiley, New York, 1983 · Zbl 0582.49001
[9] Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust-Region Methods. MPS/SIAM Series on Optimization, 2000 · Zbl 0958.65071
[10] Cullum, J., Donath, W.E., Wolfe, P.: The minimization of certain nondifferential sums of eigenvalues of symmetric matrices. Math. Progr. Stud., vol. 3, 35–55 (1975) · Zbl 0355.90054
[11] Dennis jun, J.E., Schnabel, R.B.: Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Prentice Hall Series in Computational Mathematics, 1983 · Zbl 0579.65058
[12] Fletcher, R.: Semidefinite constraints in optimization. SIAM J. Control Optim. 23, 493–513 (1985) · Zbl 0567.90088 · doi:10.1137/0323032
[13] Fletcher, R.: Practical methods of optimization. John Wiley & Sons, Chichester, 2nd ed. 1987 · Zbl 0905.65002
[14] Fletcher, R., Leyffer, S.: A bundle filter method for nonsmooth nonlinear optimization. University of Dundee, Report NA/195, 1999
[15] Fletcher, R., Leyffer, S.: Nonlinear programming without a penalty function. Math. Programming, vol. 91, 239–269 (2002) · Zbl 1049.90088 · doi:10.1007/s101070100244
[16] Fuduli, A., Gaudioso, M., Giallombardo, G.: Minimizing nonconvex nonsmooth functions via cutting planes and proximity control. SIAM J. on Optim., vol. 14 (3), 743–756 (2005) · Zbl 1079.90105 · doi:10.1137/S1052623402411459
[17] Hare, W.L., Lewis, A.S.: Identifying active constraints via partial smoothness and prox-regularity. Journal of Convex Ananlysis, vol. 11, 251–266 (2004) · Zbl 1178.90314
[18] Helmberg, C., Oustry, F.: Bundle methods to minimize the maximum eigenvalue function. In: L. Vandenberghe, R. Saigal, H. Wolkowitz, (eds.), Handbook of Semidefinite Programming · Zbl 0957.90513
[19] Hiriart-Urruty, J.-B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms, part II, Springer Verlag, Berlin, 1993
[20] Huard, P.: Resolution of mathematical programming with nonlinear constraints by the method of centers. Nonlinear programming, P. Abadie (ed.), North Holland, 1967, pp. 209–219 · Zbl 0157.49701
[21] Kato, T.: Perturbation Theory for Linear Operators. Springer Verlag, 1984 · Zbl 0531.47014
[22] Kiwiel, K.C.: Methods of descent for nondifferentiable optimization. Lect. Notes in Math. vol. 1133, Springer Verlag, Berlin, 1985 · Zbl 0561.90059
[23] Kiwiel, K.C.: Proximity control in bundle methods for convex nondifferentiable optimization. Math. Programming 46, 105–122 (1990) · Zbl 0697.90060 · doi:10.1007/BF01585731
[24] Lemaréchal, C.: Extensions diverses des méthodes de gradient et applications. Thèse d’Etat, Paris, 1980
[25] Lemaréchal, C.: Bundle methods in nonsmooth optimization. In: Nonsmooth Optimization, Proc. IIASA Workshop 1977, C. Lemaréchal, R. Mifflin (eds.), Pergamon Press, 1978 · Zbl 0828.90124
[26] Lemaréchal, C.: Nondifferentiable Optimization. chapter VII. In: Handbooks in Operations Research and Management Science. vol. 1, Optimization, G.L. Nemhauser, A.H.G. Rinnooy Kan, M.J. Todd (eds.), North Holland, 1989 · Zbl 0683.90079
[27] Lemaréchal, C., Nemirovskii, A., Nesterov, Y.: New variants of bundle methods. Math. Programming, 69, 111–147 (1995) · Zbl 0857.90102
[28] Lemaréchal, C., Oustry, F.: Nonsmooth algorithms to solve semidefinite programs. In: L. El Ghaoui, L. Niculescu (eds.), Advances in LMI Methods in Control, SIAM Series: Advances in Design and Control, 2000 · Zbl 0955.90098
[29] Lemaréchal, C., Oustry, F., Sagastizábal, C.: The -Lagrangian of a convex function. Trans. Amer. Math. Soc. 352, 2000 · Zbl 0939.49014
[30] Mifflin, R., Sagastizábal, C.: VU-smoothness and proximal point results for some nonconvex functions. Optimization Methods and Software, 2004, to appear · Zbl 1097.90059
[31] Noll, D., Apkarian, P.: Spectral bundle methods for nonconvex maximum eigenvalue functions: first-order methods. Mathematical Programming Series B 104, 701–727 (2005) · Zbl 1124.90034 · doi:10.1007/s10107-005-0634-z
[32] Overton, M.L.: On minimizing the maximum eigenvalue of a symmetric matrix. SIAM J. Matrix Anal. Appl. vol. 9 (2), 256–268 (1988) · Zbl 0647.65044 · doi:10.1137/0609021
[33] Overton, M.L.: Large-scale optimization of eigenvalues. SIAM J. Optim. vol. 2 (1), 88–120 (1992) · Zbl 0757.65072 · doi:10.1137/0802007
[34] Overton, M.L., Womersley, R.S.: Optimality conditions and duality theory for minimizing sums of the largest eigenvalues of symmetric matrices. Math. Programming 62, 321–357 (1993) · Zbl 0806.90114 · doi:10.1007/BF01585173
[35] Overton, M.L., Womersley, R.S.: Second derivatives for optimizing eigenvalues of symmetric matrices. SIAM J. Matrix Anal. Appl. vol. 16 (3), 697–718 (1995) · Zbl 0832.65036 · doi:10.1137/S089547989324598X
[36] Haeberly, J.-P.A., Overton, M.L.: A hybrid algorithm for optimizing eigenvalues of symmetric definite pencils. SIAM J. Matrix Anal. Appl. 15, 1141–1156 (1994) · Zbl 0808.65036 · doi:10.1137/S0895479893244833
[37] Oustry, F.: Vertical development of a convex function. J. Convex Analysis 5, 153–170 (1998) · Zbl 0915.49012
[38] Oustry, F.: The -Lagrangian of the maximum eigenvalue function. SIAM J. Optim., vol. 9 (2), 526–549 (1999) · Zbl 0961.65059 · doi:10.1137/S1052623496311776
[39] Oustry, F.: A second-order bundle method to minimize the maximum eigenvalue function. Math. Programming Series A vol. 89 (1), 1–33 (2000) · Zbl 1033.90080 · doi:10.1007/PL00011388
[40] Polak, E.: Optimization. Algorithms and Consistent Approximations. Springer Series in Applied Mathematical Sciences vol. 124, Springer Verlag, 1997 · Zbl 0899.90148
[41] Polak, E., Wardi, Y.: Nondifferentiable optimization algorithm for designing control systems having singular value inequalities. Automatica, vol. 18 (3), 267–283 (1982) · Zbl 0532.49017 · doi:10.1016/0005-1098(82)90087-5
[42] Scherer, C.: A full block S-procedure with applications. Proc. IEEE Conf. on Decision and Control, San Diego, USA, 1997, pp. 2602–2607
[43] Scherer, C.: Robust mixed control and linear parameter-varying control with full block scalings. In: L. El Ghaoui, S.I. Niculescu (eds.), Advances in Linear Matrix Inequality Methods in Control, SIAM Series, 2000 · Zbl 0952.93025
[44] Shapiro, A.: Extremal problems on the set of nonnegative matrices. Lin. Algebra and its Appl. 67, 7–18 (1985) · Zbl 0565.90056 · doi:10.1016/0024-3795(85)90182-X
[45] Shapiro, A.: First and second-order analysis of nonlinear semidefinite programs. Math. Programming Series B 77, 301–320 (1997) · Zbl 0888.90127
[46] Shapiro, A., Fan, M.K.H.: On eigenvalue optimization. SIAM J. Optim. vol. 5 (3), 552 – 569 (1995) · Zbl 0838.90115 · doi:10.1137/0805028
[47] Torki, M.: First- and second-order epi-differentiability in eigenvalue optimization. J. Math. Anal. Appl. 234, 391 – 416 (1999) · Zbl 1016.90061 · doi:10.1006/jmaa.1999.6320
[48] Wolfe, Ph.: A method of conjugate subgradients for minimizing nondifferentiable convex functions. Math. Programming Studies 3, 145 – 173 (1975)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.