An accelerated active-set algorithm for a quadratic semidefinite program with general constraints
- PDF / 3,055,103 Bytes
- 42 Pages / 439.37 x 666.142 pts Page_size
- 38 Downloads / 157 Views
An accelerated active‑set algorithm for a quadratic semidefinite program with general constraints Chungen Shen1 · Yunlong Wang2 · Wenjuan Xue3 · Lei‑Hong Zhang4 Received: 9 September 2019 / Accepted: 12 September 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract In this paper, we are concerned with efficient algorithms for solving the least squares semidefinite programming which contains many equalities and inequalities constraints. Our proposed method is built upon its dual formulation and is a type of active-set approach. In particular, by exploiting the nonnegative constraints in the dual form, our method first uses the information from the Barzlai–Borwein step to estimate the active/inactive sets, and within an adaptive framework, it then accelerates the convergence by switching the L-BFGS iteration and the semi-smooth Newton iteration dynamically. We show the global convergence under mild conditions, and furthermore, the local quadratic convergence under the additional nondegeneracy condition. Various types of synthetic as well as real-world examples are tested, and preliminary but promising numerical experiments are reported. Keywords Semidefinite programs · Active set · Barzlai–Borwein step · L-BFGS · Semi-smooth Newton Mathematics Subject Classification 65K05 · 95C55 · 90C30 Wenjuan Xue: The work of this author was supported in part by the National Natural Science Foundation of China NSFC-11601318. Lei-Hong Zhang: The work of this author was supported in part by the National Natural Science Foundation of China (NSFC-11671246, NSFC-12071332), the National Key R&D Program of China (No. 2018YFB0204404) and Double Innovation Program of Jiangsu Province, Year 2018. * Chungen Shen [email protected] Lei‑Hong Zhang [email protected] 1
College of Science, University of Shanghai for Science and Technology, Shanghai 200093, China
2
Antai College of Economics and Management, Shanghai Jiao Tong University, Shanghai 200030, China
3
School of Mathematics and Physics, Shanghai University of Electric Power, Shanghai 200090, China
4
School of Mathematical Sciences, Soochow University, Suzhou 215006, Jiangsu, China
13
Vol.:(0123456789)
C. Shen et al.
1 Introduction Let Sn+ be the cone of positive semidefinite matrices in the space Sn of n × n symmetric matrices, and ⟨A, B⟩ ∶= tr(AT B) with A, B ∈ Sn . In this paper, we consider the least squares semidefinite programming (LSSDP) [2, 10, 12, 17, 27] of the following form
1 ‖X − G‖2F 2 s.t. ⟨Ai , X⟩ = bi , ⟨Ai , X⟩ ≥ bi , X ∈ Sn+ ,
min
i = 1, … , p, i = p + 1, … , m,
(1.1)
where b = (b1 , … , bm )T ∈ ℝm , and G, Ai ∈ Sn for i = 1, … , m are all given. To solve the problem (1.1) numerically, in the literature, a couple of methods have been proposed and can be used in different situations. For instance, for small- to medium-size n and m, interior point methods implemented in, for example, SeDuMi [31] and SDPT3 [34], can solve efficiently the dual problem (1.2)
min t s.t. ⟨Ai , X⟩ = bi , i = 1, … , p, ⟨Ai , X⟩ ≥ bi
Data Loading...
