A Wide Neighborhood Interior-Point Algorithm for Convex Quadratic Semidefinite Optimization
- PDF / 636,525 Bytes
- 20 Pages / 439.37 x 666.142 pts Page_size
- 101 Downloads / 190 Views
A Wide Neighborhood Interior-Point Algorithm for Convex Quadratic Semidefinite Optimization Mohammad Pirhaji1 · Maryam Zangiabadi2 · Hossien Mansouri2 · Ali Nakhaei1 · Ali Shojaeifard1 Received: 17 August 2017 / Revised: 18 August 2018 / Accepted: 30 August 2018 © Operations Research Society of China, Periodicals Agency of Shanghai University, Science Press, and Springer-Verlag GmbH Germany, part of Springer Nature 2018
Abstract In this paper, we propose an interior-point algorithm based on a wide neighborhood for convex quadratic semidefinite optimization problems. Using the Nesterov–Todd direction as the search direction, we prove the convergence analysis and obtain the polynomial complexity bound of the proposed algorithm. Although the algorithm belongs to the class of large-step interior-point algorithms, its complexity coincides with the best iteration bound for short-step interior-point algorithms. The algorithm is also implemented to demonstrate that it is efficient. Keywords Convex quadratic semidefinite optimization · Feasible interior-point method · Wide neighborhood · Polynomial complexity Mathematics Subject Classification 90C22 · 90C25 · 90C51
B
Mohammad Pirhaji [email protected] Maryam Zangiabadi [email protected] Hossien Mansouri [email protected] Ali Nakhaei [email protected] Ali Shojaeifard [email protected]
1
Department of Mathematics and Statistics, Imam Hossein Comprehensive University, Tehran, Iran
2
Department of Applied Mathematics, Shahrekord University, Shahrekord, Iran
123
M. Pirhaji et al.
1 Introduction Let S n be the vector space of all n × nreal symmetric matrices endowed with the n Sn be the cone of positive semidefinite inner product M · N = Tr(M N ) and S+ ++ (positive definite) matrices in S n . Consider the primal problem of convex quadratic n , denoted by CQSDO, in the standard form optimization (CQO) over S+ 1 X · Q(X ), 2 Ai · X = bi , i = 1, 2, · · · , m,
(P) min C · X + X 0, and its Lagrangian dual problem (D) max bT y − m
1 X · Q(X ), 2
yi Ai − Q(X ) + S = C,
i=1
S 0, where C ∈ S n and b ∈ Rm are given data, the notation denotes the positive semidefinite (positive definite) matrices, Ai ∈ S n are linearly independent matrices and Q : S n −→ S n is a self-adjoint positive semidefinite linear operator on S n , i.e., for any M, N ∈ S n , Q(M) · N = M · Q(N ) and Q(M) · M 0. The CQSDO problems are the general state of semidefinite optimization (SDO) problems. In fact these problems can be reduced to SDO problems if Q(X ) = 0. Additionally, they can also be reformulated as the semidefinite linear complementarity problems (SDLCPs). After the landmark paper of Karmarkar [1], interior-point methods (IPMs) have shown their powers and efficiency in solving the linear optimization (LO) problems and various classes of other mathematical programming such as complementarity problems (CPs), second-order cone optimization (SOCO) problems, SDO problems and CQSDO problems. In last decade, some primal-dual IPMs for LO have been suc
Data Loading...
