The space decomposition method for the sum of nonlinear convex maximum eigenvalues and its applications

Ming Huang; Cong Cheng; Yang Li; Zun Quan Xia

doi:10.3934/jimo.2019034

Article Contents

2020, Volume 16, Issue 4: 1885-1905. Doi: 10.3934/jimo.2019034

This issue Previous Article Higher-order symmetric duality for multiobjective programming with cone constraints Next Article Sparse signal reconstruction via the approximations of

$ \ell_{0} $

quasinorm

The space decomposition method for the sum of nonlinear convex maximum eigenvalues and its applications

1.
School of Science, Dalian Maritime University, Dalian 116026, China
2.
School of Control Science and Engineering, Dalian University of Technology, Dalian 116024, China
3.
School of Economics and Management, Hebei University of Technology, Tianjin 300401, China
4.
College of Science, Dalian Minzu University, Dalian 116600, China
5.
School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, China

* Corresponding author
* Corresponding author

Early access: May 2019

Published: May 2020

The research is supported by the National Natural Science Foundation of China under Projects No.11701063, 11501080, 11626053, 71831002; the Innovative Research Groups of the National Natural Science Foundation of China No.71621061 and the 111 Project No.B16009; the Project funded by China Postdoctoral Science Foundation under No.2016M601296; the Fundamental Research Funds for the Central Universities under Projects No.3132017053, 3132018215, 3132019179, 3132019501 and 3132019502; the Program for Innovative Research Team in University No.IRT-17R13.

Abstract Full Text(HTML) Related Papers Cited by

Abstract

In this paper, we mainly consider optimization problems involving the sum of largest eigenvalues of nonlinear symmetric matrices. One of the difficulties with numerical analysis of such problems is that the eigenvalues, regarded as functions of a symmetric matrix, are not differentiable at those points where they coalesce. The $\mathcal {U}$-Lagrangian theory is applied to the function of the sum of the largest eigenvalues, with convex matrix-valued mappings, which doesn't need to be affine. Some of the results generalize the corresponding conclusions for linear mapping. In the approach, we reformulate the first- and second-order derivatives of ${\mathcal U}$-Lagrangian in the space of decision variables $R^m$ under some mild conditions in terms of $\mathcal{VU}$-space decomposition. We characterize smooth trajectory, along which the function has a second-order expansion. Moreover, an algorithm framework with superlinear convergence is presented. Finally, an application of $\mathcal{VU}$-decomposition derivatives shows that $\mathcal{U}$-Lagrangian possesses proper execution in matrix variable.

Keywords:

Mathematics Subject Classification: Primary: 15A18, 49J52; Secondary: 52A41, 65K10.

Citation:

Full Text(HTML)

Related Papers

Cited by

References

[1]	R. Abraham, J. E. Marsden and T. Ratiu, Manifolds, Tensor Analysis, and Applications, Applied Mathematical Sciences Volume 75, Springer-Verlag, 1988. doi: 10.1007/978-1-4612-1029-0.
[2]	P. Apkarian, D. Noll, J.-B. Thevenet and H. D. Tuan, A spectral quadratic-SDP method with applications to fixed-order $H_2$ and $H_{\infty}$ synthesis, European Journal of Control, 10 (2004), 527-538. doi: 10.3166/ejc.10.527-538.
[3]	J. F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems, Springer-Verlag, New York, 2000. doi: 10.1007/978-1-4612-1394-9.
[4]	S. Cox and R. Lipton, Extremal eigenvalue problems for two-phase conductors, Archive for Rational Mechanics and Analysis, 136 (1996), 101-117. doi: 10.1007/BF02316974.
[5]	J. Cullum, W. E. Donath and P. Wolfe, The minimization of certain nondifferentiable sums of eigenvalues of symmetric matrices, Mathematical Programming Study, 3 (1975), 35-55. doi: 10.1007/bfb0120698.
[6]	A. R. Díaz and N. Kikuchi, Solutions to shape and topology eigenvalue optimization problems using a homogenization method, International Journal for Numerical Methods in Engineering, 35 (1992), 1487-1502. doi: 10.1002/nme.1620350707.
[7]	R. Fletcher, Semi-definite matrix constraints in optimization, SIAM Journal on Control and Optimization, 23 (1985), 493-513. doi: 10.1137/0323032.
[8]	C. Helmberg, F. Rendl and R. Weismantel, A semidefinite programming approach to the quadratic knapsack problem, Journal of Combinatorial Optimization, 4 (2000), 197-215. doi: 10.1023/A:1009898604624.
[9]	C. Helmberg, M. L. Overton and F. Rendl, The spectral bundle method with second-order information, Optimization Methods and Software, 29 (2014), 855-876. doi: 10.1080/10556788.2013.858155.
[10]	J.-B. Hiriart-Urruty and C. Lemaréchal, Convex Analysis and Minimization Algorithms I-II, Springer-Verlag, Berlin, 1993. doi: 10.1007/978-3-662-02796-7.
[11]	J.-B. Hiriart-Urruty and D. Ye, Sensitivity analysis of all eigenvalues of a symmetric matrix, Numerische Mathematik, 70 (1995), 45-72. doi: 10.1007/s002110050109.
[12]	M. Huang, L. P. Pang and Z. Q. Xia, The space decomposition theory for a class of eigenvalue optimizations, Computational Optimization and Applications, 58 (2014), 423-454. doi: 10.1007/s10589-013-9624-x.
[13]	M. Huang, L. P. Pang, X. J. Liang and Z. Q. Xia, The space decomposition theory for a class of semi-infinite maximum eigenvalue optimizations, Abstract and Applied Analysis, 2014 (2014), Article ID 845017, 12 pages. doi: 10.1155/2014/845017.
[14]	M. Huang, L. P. Pang, X. J. Liang and F. Y. Meng, A second-order bundle method based on $\mathcal UV$-decomposition strategy for a special class of eigenvalue optimizations, Numerical Functional Analysis and Optimization, 37 (2016), 554-582. doi: 10.1080/01630563.2016.1138969.
[15]	M. Huang, X. J. Liang, L. P. Pang and Y. Lu, The bundle scheme for solving arbitrary eigenvalue optimizations, Journal of Industrial and Management Optimization, 13 (2017), 659-680. doi: 10.3934/jimo.2016039.
[16]	M. Huang, L. P. Pang, Y. Lu and Z. Q. Xia, A fast space-decomposition scheme for nonconvex eigenvalue optimization, Set-Valued and Variational Analysis, 25 (2017), 43-67. doi: 10.1007/s11228-016-0365-8.
[17]	M. Huang, Y. Lu, L. P. Pang and Z. Q. Xia, A space decomposition scheme for maximum eigenvalue functions and its applications, Mathematical Methods of Operations Research, 85 (2017), 453-490. doi: 10.1007/s00186-017-0579-z.
[18]	C. Kan and W. Song, Second-order conditions for existence of augmented lagrange multipliers for eigenvalue composite optimization problems, Journal of Global Optimization, 63 (2015), 77-97. doi: 10.1007/s10898-015-0273-8.
[19]	C. Lemaréchal, F. Oustry and C. Sagastizábal, The ${\mathcal U}$-Lagrangian of a convex function, Transactions of the American Mathematical Society, 352 (2000), 711-729. doi: 10.1090/S0002-9947-99-02243-6.
[20]	A. S. Lewis and M. L. Overton, Eigenvalue optimization, Acta Numerica, 5 (1996), 149-190. doi: 10.1017/S0962492900002646.
[21]	X. Liu, X. Wang, Z. Wen and Y. Yuan, On the Convergence of the Self-Consistent Field Iteration in Kohn-Sham Density Functional Theory, SIAM Journal on Matrix Analysis and Applications, 35 (2014), 546-558. doi: 10.1137/130911032.
[22]	X. Liu, Z. Wen, X. Wang, M. Ulbrich and Y. Yuan, On the analysis of the discretized kohn-sham density functional theory, SIAM Journal on Numerical Analysis, 53 (2015), 1758-1785. doi: 10.1137/140957962.
[23]	R. Mifflin and C. Sagastizábal, A $\mathcal {VU}$-algorithm for convex minimization, Mathematical Programming Ser.B, 104 (2005), 583-608. doi: 10.1007/s10107-005-0630-3.
[24]	D. Noll and P. Apkarian, Spectral bundle method for nonconvex maximum eigenvalue functions: Second-order methods, Mathematical Programming Ser. B, 104 (2005), 729-747. doi: 10.1007/s10107-005-0635-y.
[25]	D. Noll, M. Torki and P. Apkarian, Partially augmented Lagrangian method for matrix inequality constraints, SIAM Journal on Optimization, 15 (2004), 161-184. doi: 10.1137/S1052623402413963.
[26]	F. Oustry, The ${\mathcal U}$-Lagrangian of the maximum eigenvalue functions, SIAM Journal on Optimization, 9 (1999), 526-549. doi: 10.1137/S1052623496311776.
[27]	M. L. Overton, Large-scale optimization of eigenvalues, SIAM Journal on Optimization, 2 (1992), 88-120. doi: 10.1137/0802007.
[28]	M. L. Overton and R. S. Womersley, Optimality conditions and duality theory for minimizing sums of the largest eigenvalues of symmetric matrices, Mathematical Programming, 62 (1993), 321-357. doi: 10.1007/BF01585173.
[29]	M. L. Overton and R. S. Womersley, Second derivatives for optimizing eigenvalues of symmetric matrices, SIAM Journal on Matrix Analysis and Applications, 16 (1995), 697-718. doi: 10.1137/S089547989324598X.
[30]	M. L. Overton and X. Ye, Towards second-order methods for structured nonsmooth optimization, In: S. Gomez, J.-P. Hennart eds., Advances in Optimization and Numerical Analysis, 97–109, Volume 275 of the series Mathematics and Its Applications, Kluwer Academic Publishers, Norwell, MA, 1994. doi: 10.1007/978-94-015-8330-5_7.
[31]	G. Pataki, On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues, Mathematics of Operations Research, 23 (1998), 339-358. doi: 10.1287/moor.23.2.339.
[32]	R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, NJ, 1997.
[33]	A. Shapiro and M. K. H. Fan, On eigenvalue optimization, SIAM Journal on Optimization, 5 (1995), 552-569. doi: 10.1137/0805028.
[34]	A. Shapiro, First and second order analysis of nonlinear semidefinite programs, Mathematical Programming, 77 (1997), 301-320. doi: 10.1007/BF02614439.
[35]	M. Torki, First- and second-order epi-differentiability in eigenvalue optimization, Journal of Mathematical Analysis and Applications, 234 (1999), 391-416. doi: 10.1006/jmaa.1999.6320.
[36]	M. Torki, Second-order directional derivatives of all eigenvalues of a symmetric matrix, Nonlinear Analysis. Theory, Methods & Applications, 46 (2001), 1133-1150. doi: 10.1016/S0362-546X(00)00165-6.
[37]	L. Vandenberghe and S. Boyd, Semidefinite programming, SIAM Review, 38 (1996), 49-95. doi: 10.1137/1038003.
[38]	Z. Wen, C. Yang, X. Liu and Y. Zhang, Trace-penalty minimization for large-scale eigenspace computation, J. Sci. Comput., 66 (2016), 1175-1203. doi: 10.1007/s10915-015-0061-0.
[39]	Z. Zhao, B. Braams, M. Fukuda, M. Overton and J. Percus, The reduced density matrix method for electronic structure calculations and the role of three-index representability conditions, Journal of Chemical Physics, 120 (2004), 2095-2104. doi: 10.1063/1.1636721.