Smooth convex approximation to the maximum eigenvalue function. (English) Zbl 1066.90081
Summary: In this paper, we consider smooth convex approximations to the maximum eigenvalue function. To make it applicable to a wide class of applications, the study is conducted on the composite function of the maximum eigenvalue function and a linear operator mapping \(\mathbb R^{m}\) to \(\mathcal S_n\), the space of \(n\)-by-\(n\) symmetric matrices. The composite function in turn is the natural objective function of minimizing the maximum eigenvalue function over an affine space in \(\mathcal S_n\). This leads to a sequence of smooth convex minimization problems governed by a smoothing parameter. As the parameter goes to zero, the original problem is recovered. We then develop a computable Hessian formula of the smooth convex functions, matrix representation of the Hessian, and study the regularity conditions which guarantee the nonsingularity of the Hessian matrices. The study on the well-posedness of the smooth convex function leads to a regularization method which is globally convergent.
References:
| [1] | Auslender, A. (1999), Penalty and barrier methods: a unified framework, SIAM J. Optimization 10, 211-230. · Zbl 0953.90045 · doi:10.1137/S1052623497324825 |
| [2] | Ben-Tal, A. and Teboulle, M. (1989), A smoothing technique for nondifferentiable optimization problems. In: Optimization, 1-11. Fifth French German Conference, Lecture Notes in Math. 1405, Springer, New York. · Zbl 0683.90078 |
| [3] | Bertsekas, D.P. (1982), Constrained Optimization and Lagrangian Multiplier Methods, Academic Press, New York. · Zbl 0572.90067 |
| [4] | Chang, P.-L. (1980), A minimax approach t nonlinear programming, Doctoral Dissertation, University of Washington, Department of Mathematics. |
| [5] | Chen, X. and Tseng, P. (2003), Non-interior continuation methods for solving semidefinite complementarity problems, Mathematical Programming 95, 431-474. · Zbl 1023.90046 · doi:10.1007/s10107-002-0306-1 |
| [6] | Dontchev, A.L. and Zolezzi, T. (1993), Well-posed optimization problems. In: Lecture Notes in Mathematics, 1543. Springer, Berlin. · Zbl 0797.49001 |
| [7] | Facchinei, F. (1998), Structural and stability properties of P 0 nonlinear complementarity problems, Mathematics of Operations Research 23, 735-745. · Zbl 0977.90059 · doi:10.1287/moor.23.3.735 |
| [8] | Facchinei, F. and Kanzow, C. (1999), Beyond monotonicity in regularization methods for nonlinear complementarity problems, SIAM J. Control and Optimization 37, 1150-1161. · Zbl 0997.90085 · doi:10.1137/S0363012997322935 |
| [9] | Goldstein, A.A. (1997), Chebyshev approximation and linear inequalities via exponentials, Report, Department of Mathematics, University of Washington, Seattle. |
| [10] | Golub, G.H. and Val Loan, C.F. (1996), Matrix Computations, 3rd ed., Johns Hopkins University Press, Baltimore, MD. · Zbl 0865.65009 |
| [11] | Horn, R.A. and Johnson, C.R. (1985), Matrix Analysis, Cambridge Press, Cambridge, United Kingdom. · Zbl 0576.15001 |
| [12] | Lewis, A.S. (1996), Derivatives of spectral functions, Mathematics of Operations Research 21, 576-588. · Zbl 0860.49017 · doi:10.1287/moor.21.3.576 |
| [13] | Lewis, A.S. and Overton, M.L. (1996), Eigenvalue optimization, Acta Numerica 5, 149-190. · Zbl 0870.65047 · doi:10.1017/S0962492900002646 |
| [14] | Lewis, A.S. and Sendov, H.S. (2001), Twice differentiable spectral functions, SIAM J. Matrix Analysis and Application 23, 368-386. · Zbl 1053.15004 · doi:10.1137/S089547980036838X |
| [15] | Li, X.-S. (1991), An aggregation function method for nonlinear programming, Science in China (Series A) 34, 1467-1473. · Zbl 0752.90069 |
| [16] | Oustry, F. (1999), The U-Lagrangian of the maximum eigenvalue function, SIAM J. Optimization 9, 526-549. · Zbl 0961.65059 · doi:10.1137/S1052623496311776 |
| [17] | Oustry, F. (2000), A second-order bundle method to minimize the maximum eigenvalue function, Mathematical Programming 89, 1-33. · Zbl 1033.90080 · doi:10.1007/PL00011388 |
| [18] | Overton, M.L. and Womersley, R.S. (1995), Second derivatives for optimizing eigenvalues of symmetric matrices, SIAM J. Matrix Analysis and Application 16, 667-718. · Zbl 0832.65036 |
| [19] | Peng, J.-M. and Lin, Z.-H. (1999), A non-interior continuation method for generalized linear complementarity problems, Mathematical Programming 86, 533-563. · Zbl 0987.90081 · doi:10.1007/s101070050104 |
| [20] | Qi, H.-D. (1999), Tikhonov regularization methods for variational inequality problems, J. Optimization Theory and Application 102, 193-201. · Zbl 0939.90019 · doi:10.1023/A:1021802830910 |
| [21] | Qi, H.-D. (2000), A regularized smoothing Newton method for box constrained variational inequality problems with P 0-functions, SIAM J. Optimization 10, 315-330. · Zbl 0955.90136 · doi:10.1137/S1052623497324047 |
| [22] | Qi, H.-D. and Liao, L.-Z. (1999), A smoothing Newton method for extended vertical linear complementarity problems, SIAM J. Matrix Analysis and Application 21, 45-66. · Zbl 1017.90114 · doi:10.1137/S0895479897329837 |
| [23] | Qi L. and Tseng, P. (2002), An analysis of piecewise smooth functions and almost smooth functions, Department of Applied Mathematics, The Hong Kong Polytechnic University. |
| [24] | Ravindran, G. and Gowda, M.S. (2000), Regularization of P 0-functions in box variational inequality problems, SIAM J. Optimization 11, 748-760. · Zbl 1010.90083 · doi:10.1137/S1052623497329567 |
| [25] | Shapiro, A. and Fan, M.K.H. (1995), On eigenvalue optimization, SIAM J. Optimization 5, 552-568. · Zbl 0838.90115 · doi:10.1137/0805028 |
| [26] | Stewart, G.W. and Sun, J.-G. (1990), Matrix Perturbation Theory, Academic Press, New York. · Zbl 0706.65013 |
| [27] | Sun, D. (1990), A regularization Newton method for solving nonlinear complementarity problems, Applied Mathematics and Optimization 40, 315-339. · Zbl 0937.90110 · doi:10.1007/s002459900128 |
| [28] | Tang, H. and Zhang, L. (1994), A maximum entropy method for convex programming, Chinese Science Bulletin 39, 682-684. |
| [29] | Tseng, P. and Bertsekas, D.P. (1993), On the convergence f the exponential multiplier method for convex programming, Mathematical Programming 60, 1-19. · Zbl 0783.90101 · doi:10.1007/BF01580598 |
| [30] | Zhang, L. and Tang, H. (1998), A further study on a penalty function of Bertsekas. Advances in nonlinear programming (Beijing, 1996), Appl. Optim., 14, Kluwer Academic Publishers, Dordrecht, pp. 345-351. · Zbl 0910.90250 |
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.
