Quadratic Optimization over a Second-Order Cone with Linear Equality Constraints
- PDF / 766,916 Bytes
- 22 Pages / 439.37 x 666.142 pts Page_size
- 23 Downloads / 178 Views
Quadratic Optimization over a Second-Order Cone with Linear Equality Constraints Xiao-ling Guo · Zhi-bin Deng · Shu-Cherng Fang · Zhen-bo Wang · Wen-xun Xing
Received: 3 November 2013 / Revised: 28 November 2013 / Accepted: 2 December 2013 © Operations Research Society of China, Periodicals Agency of Shanghai University, and Springer-Verlag Berlin Heidelberg 2013
Abstract This paper studies the nonhomogeneous quadratic programming problem over a second-order cone with linear equality constraints. When the feasible region is bounded, we show that an optimal solution of the problem can be found in polynomial time. When the feasible region is unbounded, a semidefinite programming (SDP) reformulation is constructed to find the optimal objective value of the original problem in polynomial time. In addition, we provide two sufficient conditions, under which, if the optimal objective value is finite, we show the optimal solution of SDP reformulation can be decomposed into the original space to generate an optimal solution of the original problem in polynomial time. Otherwise, a recession direction can be identified in polynomial time. Numerical examples are included to illustrate the effectiveness of the proposed approach. Keywords Quadratic programming · Linear conic programming · Second-order cone · Cone of nonnegative quadratic functions Mathematics Subject Classification (2010) 90C20 · 90C26 · 15B48
Fang was supported by the US National Science Foundation (No. DMI-0553310). Guo, Wang and Xing were supported by the National Natural Science Foundation of China (Nos. 11171177 and 11371216). Deng was supported by the Edward P. Fitts Fellowship at North Carolina State University. X.-l. Guo · Z.-b. Wang · W.-x. Xing Department of Mathematical Sciences, Tsinghua University, Beijing 100084, China
B
Z.-b. Deng ( ) · S.-C. Fang Industrial and Systems Engineering Department, North Carolina State University, Raleigh, NC 27695, USA e-mail: [email protected]
X.-l. Guo et al.
1 Introduction Consider the following nonhomogeneous quadratic optimization problem over a second-order cone with linear equality constraints (QP-SOC in short): VQP-SOC := min F (x) = x T Qx + 2cT x s.t.
Ax = b,
(QP-SOC)
x ∈ L, where Q ∈ Rn×n is a symmetric matrix which is not necessary to be positive semidef√ inite, c ∈ Rn , A ∈ Rm×n , b ∈ Rm and L = {x ∈ Rn | x T H x f T x} is a general second-order cone with H ∈ Rn×n being a symmetric positive definite matrix and f ∈ Rn (see [22]). The second-order cone is a special Bishop–Phelps cone, which has been proven to be useful in functional analysis and vector optimization [4, 9]. A class of cardinalityconstrained portfolio selection problems can also be reformulated as a second-order cone constrained quadratic optimization problem [7, 18]. Some studies of optimization problems over L can be found in [1–3, 6]. Recently, linear conic programming has received much attention for solving quadratic optimization problems [5]. Sturm and Zhang introduced cones of nonnegative quadratic functions and reformulated
Data Loading...
