A revised sequential quadratic semidefinite programming method for nonlinear semidefinite optimization

Kosuke Okabe; Yuya Yamakawa; Ellen Hidemi Fukuda

doi:10.3934/jimo.2023019

Article Contents

2023, Volume 19, Issue 10: 7777-7794. Doi: 10.3934/jimo.2023019

This issue Previous Article A variance-reduced stochastic gradient tracking algorithm for decentralized optimization with orthogonality constraints Next Article Optimal contracts to a principal-agent model with a diffusion coefficient affected by firm size

A revised sequential quadratic semidefinite programming method for nonlinear semidefinite optimization

Graduate School of Informatics, Kyoto University, Japan

^*Corresponding author: Yuya Yamakawa
^*Corresponding author: Yuya Yamakawa

Received: April 2022

Revised: January 2023

Early access: February 27, 2023

Published online: February 27, 2023

The second and third authors are supported by the Japan Society for the Promotion of Science KAKENHI for 21K17709 and 19K11840, respectively.

Abstract / Introduction Full Text(HTML) Figure(0) / Table(1) Related Papers Cited by

Abstract

In 2020, Yamakawa and Okuno proposed a stabilized sequential quadratic semidefinite programming (SQSDP) method for solving, in particular, degenerate nonlinear semidefinite optimization problems. The algorithm is shown to converge globally without a constraint qualification, and it has some nice properties, including the feasible subproblems, and their possible inexact computations. In particular, the convergence was established for approximate-Karush-Kuhn-Tucker (AKKT) and trace-AKKT conditions, which are two sequential optimality conditions for the nonlinear conic contexts. However, recently, complementarity-AKKT (CAKKT) conditions were also considered, as an alternative to the previous mentioned ones, that is more practical. Since few methods are shown to converge to CAKKT points, at least in conic optimization, and to complete the study associated to the SQSDP, here we propose a revised version of the method, maintaining the good properties. We modify the previous algorithm, prove the global convergence in the sense of CAKKT, and show some preliminary numerical experiments.

Keywords:

Mathematics Subject Classification: Primary: 90C22, 90C55; Secondary: 90C46.

Citation:

Full Text(HTML)

Table 1. Performance for the degenerated problem

	$ p = 5 $	$ p = 10 $	$ p=20 $
Average iterations	$ 200.0 $	$ 177.9 $	$ 200 $
Average $ r $	$ 3.95 \times 10^{-3} $	$ 1.24 \times 10^{-3} $	$ 2.88 \times 10^{-3} $
Maximum $ r $	$ 8.24 \times 10^{-3} $	$ 3.66 \times 10^{-3} $	$ 8.25 \times 10^{-3} $
Minimum $ r $	$ 9.52 \times 10^{-4} $	$ 2.32 \times 10^{-4} $	$ 1.04 \times 10^{-3} $

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	R. Andreani, E. H. Fukuda, G. Haeser, D. O. Santos and L. D. Secchin, Optimality conditions for nonlinear second-order cone programming and symmetric cone programming, Submitted, (2019).
[2]	R. Andreani, E. H. Fukuda, G. Haeser, D. O. Santos and L. D. Secchin, On the use of Jordan algebras for improving global convergence of an augmented Lagrangian method in nonlinear semidefinite programming, Computational Optimization and Applications, 79 (2021), 633-648. doi: 10.1007/s10589-021-00281-8.
[3]	R. Andreani, G. Haeser and J. M. Martínez, On sequencial optimality conditions for smooth constrained optimization, Optimization, 60 (2011), 627-641. doi: 10.1080/02331930903578700.
[4]	R. Andreani, G. Haeser and D. S. Viana, Optimality conditions and global convergence for nonlinear semidefinite programming, Mathematical Programming, 180 (2018), 203-235. doi: 10.1007/s10107-018-1354-5.
[5]	R. Andreani, J. M. Martínez and B. F. Svaiter, A new sequential optimality condition for constrained optimization and algorithmic consequences, SIAM Journal on Optimization, 20 (2010), 3533-3554. doi: 10.1137/090777189.
[6]	P. Apkarian, D. Noll and H. D. Tuan, Fixed-order ${H}_\infty$ control design via a partially augmented Lagrangian method, International Journal of Robust and Nonlinear Control, 13 (2003), 1137-1148. doi: 10.1002/rnc.807.
[7]	R. Correa and H. Ramírez C., A global algorithm for nonlinear semidefinite programming, SIAM Journal on Optimization, 15 (2004), 303-318. doi: 10.1137/S1052623402417298.
[8]	B. Fares, P. Apkarian and D. Noll, An augmented Lagrangian method for a class of LMI-constrained problems in robust control theory, International Journal of Control, 74 (2001), 348-360. doi: 10.1080/00207170010010605.
[9]	B. Fares, D. Noll and P. Apkarian, Robust control via sequential semidefinite programming, SIAM Journal on Control and Optimization, 40 (2002), 1791-1820. doi: 10.1137/S0363012900373483.
[10]	E. H. Fukuda and B. F. Lourenço, Exact augmented Lagrangian functions for nonlinear semidefinite programming, Computational Optimization and Applications, 71 (2018), 457-482. doi: 10.1007/s10589-018-0017-z.
[11]	P. E. Gill and D. P. Robinson, A globally convergent stabilized SQP method, SIAM Journal on Optimization, 23 (2013), 1983-2010. doi: 10.1137/120882913.
[12]	R. A. Horn and C. R. Johnson, Topics in Matrix Analysis, Cambridge University Press, Cambridge, 1991. doi: 10.1017/CBO9780511840371.
[13]	F. Jarre, An interior method for nonconvex semidefinite programs, Optimization and Engineering, 1 (2000), 347-372. doi: 10.1023/A:1011562523132.
[14]	Y. Kanno and I. Takewaki, Sequential semidefinite program for maximum robustness design of structures under load uncertainty, Journal of Optimization Theory and Applications, 130 (2006), 265-287. doi: 10.1007/s10957-006-9102-z.
[15]	C. Kanzow, C. Nagel, H. Kato and M. Fukushima, Successive linearization methods for nonlinear semidefinite programs, Computational Optimization and Applications, 31 (2005), 251-273. doi: 10.1007/s10589-005-3231-4.
[16]	M. Kočvara and M. Stingl, Solving nonconvex SDP problems of structural optimization with stability control, Optim. Methods Softw., 19 (2004), 595-609. doi: 10.1080/10556780410001682844.
[17]	H. Konno, N. Kawadai and D. Wu, Estimation of failure probability using semi-definite logit model, Computational Management Science, 1 (2003), 59-73. doi: 10.1007/s10287-003-0001-6.
[18]	D. Sun, J. Sun and L. Zhang, The rate of convergence of the augmented Lagrangian method for nonlinear semidefinite programming, Mathematical Programming, 114 (2008), 349-391. doi: 10.1007/s10107-007-0105-9.
[19]	K. C. Toh, M. J. Todd and R. H. Tutuncu, SDPT3 – A Matlab software package for semidefinite programming, Optim. Methods Softw., 11 (1999), 545-581. doi: 10.1080/10556789908805762.
[20]	R. H. Tütüncü, K. C. Toh and M. J. Todd, Solving semidefinite-quadratic-linear programs using SDPT3, Mathematical Programming, 95 (2003), 189-217. doi: 10.1007/s10107-002-0347-5.
[21]	S. J. Wright, Superlinear convergence of a stabilized SQP method to a degenerate solution, Computational Optimization and Applications, 11 (1998), 253-275. doi: 10.1023/A:1018665102534.
[22]	Y. Yamakawa and T. Okuno, A stabilized sequential quadratic semidefinite programming method for degenerate nonlinear semidefinite programs, Computational Optimization and Applications, 83 (2022), 1027-1064. doi: 10.1007/s10589-022-00402-x.
[23]	H. Yamashita and H. Yabe, Local and superlinear convergence of a primal-dual interior point method for nonlinear semidefinite programming, Mathematical Programming, 132 (2012), 1-30. doi: 10.1007/s10107-010-0354-x.
[24]	H. Yamashita and H. Yabe, A survey of numerical methods for nonlinear semidefinite programming, Journal of the Operations Research Society of Japan, 58 (2015), 24-60. doi: 10.15807/jorsj.58.24.
[25]	H. Yamashita, H. Yabe and K. Harada, A primal-dual interior point method for nonlinear semidefinite programming, Mathematical Programming, 135 (2012), 89-121. doi: 10.1007/s10107-011-0449-z.
[26]	Q. Zhao and Z. Chen, On the superlinear local convergence of a penalty-free method for nonlinear semidefinite programming, Journal of Computational and Applied Mathematics, 308 (2016), 1-19. doi: 10.1016/j.cam.2016.05.007.
[27]	Q. Zhao and Z. Chen, A line search exact penalty method for nonlinear semidefinite programming, Computational Optimization and Applications, 75 (2020), 467-491. doi: 10.1007/s10589-019-00158-x.