A New Infeasible-Interior-Point Algorithm Based on Wide Neighborhoods for Symmetric Cone Programming
- PDF / 521,174 Bytes
- 19 Pages / 439.37 x 666.142 pts Page_size
- 59 Downloads / 249 Views
A New Infeasible-Interior-Point Algorithm Based on Wide Neighborhoods for Symmetric Cone Programming Chang-He Liu1 · Dan Wu1 · You-Lin Shang1
Received: 26 June 2015 / Revised: 24 October 2015 / Accepted: 6 January 2016 / Published online: 3 March 2016 © Operations Research Society of China, Periodicals Agency of Shanghai University, Science Press, and Springer-Verlag Berlin Heidelberg 2016
Abstract In this paper, we present an infeasible-interior-point algorithm, based on a new wide neighborhood for symmetric cone programming. We treat the classical Newton direction as the sum of two other directions, and equip them with different step sizes. We prove the complexity bound of the new algorithm for the Nesterov-Todd (NT) direction, and the xs and sx directions. The complexity bounds obtained here are the same as small neighborhood infeasible-interior-point algorithms over symmetric cones. Keywords Infeasible-interior-point algorithm · Wide neighborhood · Symmetric cone programming · Euclidean Jordan algebra · Polynomial complexity Mathematics Subject Classification 90C51 · 90C05 · 90C25
This work was partially supported by the National Natural Science Foundation of China (Nos. 11471102, 11426091, and 61179040), the Natural Science Foundation of Henan University of Science and Technology (No. 2014QN039) and Key Basic Research Foundation of the Higher Education Institutions of Henan Province (No. 16A110012).
B
You-Lin Shang [email protected] Chang-He Liu [email protected] Dan Wu [email protected]
1
Department of Applied Mathematics, Henan University of Science and Technology, Luoyang 471023, Henan, China
123
148
C.-H. Liu et al.
1 Introduction Linear programming over cone K, or simply cone programming problem is defined as minimizing a linear objective function subject to linear constraints and over cone K, which is a closed, pointed, convex cone with a nonempty interior in Rn . In this paper, we are interested in the interior-point-methods (IPMs) of the cone programming where cone K is a symmetric cone, that is K is self-dual and its automorphism group acts transitively on its interior. Symmetric cones are intimately related to Euclidean Jordan algebras (see [1] and [2], etc), and these algebras provide us a basic toolbox to carry out our analysis. It is well known that symmetric cone programming (SCP) includes linear programming (LP), semidefinite programming (SDP), and second-order cone programming (SOCP) as special cases. Thus, more and more attention has been focused on the optimization problems over symmetric cones. Nesterov and Todd [3–5] provided a theoretical foundation of the primal-dual IPMs on a special class of conic programming, where the associated cone is so-called self-scaled cone. Güler [2] observed that the self-scaled cones are precisely symmetric cones, which have been studied much in other areas of mathematical sciences (see, for example, [1]). Faybusovich [6,7] first analyzed the IPMs over symmetric cones by using Euclidean Jordan algebraic tools. Schmieta and Alizadeh [8] proved polyn
Data Loading...
