Quadratic optimization over one first-order cone

Previous Article
Finite-time optimal consensus control for second-order multi-agent systems
JIMO Home
This Issue
Next Article
A majorized penalty approach to inverse linear second order cone programming problems

July 2014, 10(3): 945-963. doi: 10.3934/jimo.2014.10.945

Quadratic optimization over one first-order cone

Xiaoling Guo ^1, , Zhibin Deng ^2, , Shu-Cherng Fang ^2, and Wenxun Xing ^1,

1.	Department of Mathematical Sciences, Tsinghua University, Beijing, 100084, China
2.	Industrial and Systems Engineering Department, North Carolina State University, Raleigh, NC 27695-7906, United States, United States

Received February 2013 Revised June 2013 Published November 2013

Abstract
Related Papers

This paper studies the first-order cone constrained homogeneous quadratic programming problem. For efficient computation, the problem is reformulated as a linear conic programming problem. A union of second-order cones are designed to cover the first-order cone such that a sequence of linear conic programming problems can be constructed to approximate the conic reformulation. Since the cone of nonnegative quadratic forms over a union of second-order cones has a linear matrix inequalities representation, each linear conic programming problem in the sequence is polynomial-time solvable by applying semidefinite programming techniques. The convergence of the sequence is guaranteed when the union of second-order cones gets close enough to the first-order cone. In order to further improve the efficiency, an adaptive scheme is adopted. Numerical experiments are provided to illustrate the efficiency of the proposed approach.

Keywords: first-order cone, linear conic programming, adaptive scheme., cone of nonnegative quadratic forms, Quadratic programming.

Mathematics Subject Classification: Primary: 90C20, 90C26; Secondary: 15B48, 65Y2.

Citation: Xiaoling Guo, Zhibin Deng, Shu-Cherng Fang, Wenxun Xing. Quadratic optimization over one first-order cone. Journal of Industrial & Management Optimization, 2014, 10 (3) : 945-963. doi: 10.3934/jimo.2014.10.945

References:

[1]	F. Alizadeh and D. Goldfarb, Second-order cone programming,, Mathematical Programming, 95 (2003), 3. doi: 10.1007/s10107-002-0339-5.
[2]	E. D. Andersen, C. Roos and T. Terlaky, Notes on duality in second order and $p$-order cone optimization,, Optimization, 51 (2002), 627. doi: 10.1080/0233193021000030751.
[3]	P. Belotti, J. C. Góez, I. Pólik, T. K. Ralphs and T. Terlaky, On families of quadratic surfaces having fixed intersections with two hyperplanes,, Discrete Applied Mathematics, 161 (2013), 2778. doi: 10.1016/j.dam.2013.05.017.
[4]	A. Ben-Tal and A. Nemirovski, Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications,, MPS/SIAM Series on Optimization, (2001). doi: 10.1137/1.9780898718829.
[5]	E. Bishop and R. R. Phelps, The support functionals of a convex set,, in Proceedings of Symposia in Pure Mathematics, (1963), 27.
[6]	S. Boyd and L. Vandenberghe, Convex Optimization,, Cambridge University Press, (2004).
[7]	S. Burer, On the copositive representation of binary and continous nonconvex quadratic programs,, Mathematical Programming, 120 (2009), 479. doi: 10.1007/s10107-008-0223-z.
[8]	S. Burer and K. M. Anstreicher, Second-order-cone constraints for extended trust-region subproblems,, SIAM Journal on Optimization, 23 (2013), 432. doi: 10.1137/110826862.
[9]	Z. Deng, S.-C. Fang, Q. Jin and W. Xing, Detecting copositivity of a symmetric matrix by an adaptive ellipsoid-based approximation scheme,, European Journal of Operational Research, 229 (2013), 21. doi: 10.1016/j.ejor.2013.02.031.
[10]	G. Eichfelder and J. Povh, On reformulations of nonconvex quadratic programs over convex cones by set-semidefinite constraints,, preprint, (2010).
[11]	Q. Jin, Quadratically Constrained Quadratic Programming Problems and Extensions,, Ph.D thesis, (2011).
[12]	Q. Jin, Y. Tian, Z. Deng, S.-C. Fang and W. Xing, Exact computable representation of some second-order cone constrained quadratic programming problems,, Journal of Operations Research Society of China, 1 (2013), 107. doi: 10.1007/s40305-013-0009-8.
[13]	C. Lu, Q. Jin, S.-C. Fang, Z. Wang and W. Xing, An LMI based adaptive approximation scheme to cones of nonnegative quadratic functions,, working paper, (2011).
[14]	M. W. Margaret, Advances in cone-based preference modeling for decision making with multiple criteria,, Decision Making in Manufacturing and Services, 1 (2007), 153.
[15]	Y. Nesterov and A. Nemirovsky, Interior-point Polynomial Methods in Convex Programming,, SIAM, (1994). doi: 10.1137/1.9781611970791.
[16]	R. T. Rockafellar, Convex Analysis,, 2nd edition, (1972).
[17]	J. F. Sturm, Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Interior point methods,, Optimization Methods and Software, 11/12 (1999), 625. doi: 10.1080/10556789908805766.
[18]	J. F. Sturm and S. Z. Zhang, On cones of nonnegative quadratic functions,, Mathematics of Operations Research, 28 (2003), 246. doi: 10.1287/moor.28.2.246.14485.
[19]	Y. Tian, S.-C. Fang, Z. Deng and W. Xing, Computable representation of the cone of nonnegative quadratic forms over a general second-order cone and its application to completely positive programming,, Journal of Industrial and Management Optimization, 9 (2013), 703. doi: 10.3934/jimo.2013.9.703.
[20]	S. A. Vavasis, Nonlinear Optimization: Complexity Issues,, International Series of Monographs on Computer Science, (1991).
[21]	Y. Ye and S. Zhang, New results on quadratic minimization,, SIAM Journal on Optimization, 14 (2003), 245. doi: 10.1137/S105262340139001X.

show all references

References:

[1]	F. Alizadeh and D. Goldfarb, Second-order cone programming,, Mathematical Programming, 95 (2003), 3. doi: 10.1007/s10107-002-0339-5.
[2]	E. D. Andersen, C. Roos and T. Terlaky, Notes on duality in second order and $p$-order cone optimization,, Optimization, 51 (2002), 627. doi: 10.1080/0233193021000030751.
[3]	P. Belotti, J. C. Góez, I. Pólik, T. K. Ralphs and T. Terlaky, On families of quadratic surfaces having fixed intersections with two hyperplanes,, Discrete Applied Mathematics, 161 (2013), 2778. doi: 10.1016/j.dam.2013.05.017.
[4]	A. Ben-Tal and A. Nemirovski, Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications,, MPS/SIAM Series on Optimization, (2001). doi: 10.1137/1.9780898718829.
[5]	E. Bishop and R. R. Phelps, The support functionals of a convex set,, in Proceedings of Symposia in Pure Mathematics, (1963), 27.
[6]	S. Boyd and L. Vandenberghe, Convex Optimization,, Cambridge University Press, (2004).
[7]	S. Burer, On the copositive representation of binary and continous nonconvex quadratic programs,, Mathematical Programming, 120 (2009), 479. doi: 10.1007/s10107-008-0223-z.
[8]	S. Burer and K. M. Anstreicher, Second-order-cone constraints for extended trust-region subproblems,, SIAM Journal on Optimization, 23 (2013), 432. doi: 10.1137/110826862.
[9]	Z. Deng, S.-C. Fang, Q. Jin and W. Xing, Detecting copositivity of a symmetric matrix by an adaptive ellipsoid-based approximation scheme,, European Journal of Operational Research, 229 (2013), 21. doi: 10.1016/j.ejor.2013.02.031.
[10]	G. Eichfelder and J. Povh, On reformulations of nonconvex quadratic programs over convex cones by set-semidefinite constraints,, preprint, (2010).
[11]	Q. Jin, Quadratically Constrained Quadratic Programming Problems and Extensions,, Ph.D thesis, (2011).
[12]	Q. Jin, Y. Tian, Z. Deng, S.-C. Fang and W. Xing, Exact computable representation of some second-order cone constrained quadratic programming problems,, Journal of Operations Research Society of China, 1 (2013), 107. doi: 10.1007/s40305-013-0009-8.
[13]	C. Lu, Q. Jin, S.-C. Fang, Z. Wang and W. Xing, An LMI based adaptive approximation scheme to cones of nonnegative quadratic functions,, working paper, (2011).
[14]	M. W. Margaret, Advances in cone-based preference modeling for decision making with multiple criteria,, Decision Making in Manufacturing and Services, 1 (2007), 153.
[15]	Y. Nesterov and A. Nemirovsky, Interior-point Polynomial Methods in Convex Programming,, SIAM, (1994). doi: 10.1137/1.9781611970791.
[16]	R. T. Rockafellar, Convex Analysis,, 2nd edition, (1972).
[17]	J. F. Sturm, Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Interior point methods,, Optimization Methods and Software, 11/12 (1999), 625. doi: 10.1080/10556789908805766.
[18]	J. F. Sturm and S. Z. Zhang, On cones of nonnegative quadratic functions,, Mathematics of Operations Research, 28 (2003), 246. doi: 10.1287/moor.28.2.246.14485.
[19]	Y. Tian, S.-C. Fang, Z. Deng and W. Xing, Computable representation of the cone of nonnegative quadratic forms over a general second-order cone and its application to completely positive programming,, Journal of Industrial and Management Optimization, 9 (2013), 703. doi: 10.3934/jimo.2013.9.703.
[20]	S. A. Vavasis, Nonlinear Optimization: Complexity Issues,, International Series of Monographs on Computer Science, (1991).
[21]	Y. Ye and S. Zhang, New results on quadratic minimization,, SIAM Journal on Optimization, 14 (2003), 245. doi: 10.1137/S105262340139001X.

[1]	Ye Tian, Shu-Cherng Fang, Zhibin Deng, Wenxun Xing. Computable representation of the cone of nonnegative quadratic forms over a general second-order cone and its application to completely positive programming. Journal of Industrial & Management Optimization, 2013, 9 (3) : 703-721. doi: 10.3934/jimo.2013.9.703
[2]	Yi Zhang, Yong Jiang, Liwei Zhang, Jiangzhong Zhang. A perturbation approach for an inverse linear second-order cone programming. Journal of Industrial & Management Optimization, 2013, 9 (1) : 171-189. doi: 10.3934/jimo.2013.9.171
[3]	Shiyun Wang, Yong-Jin Liu, Yong Jiang. A majorized penalty approach to inverse linear second order cone programming problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 965-976. doi: 10.3934/jimo.2014.10.965
[4]	Liping Tang, Xinmin Yang, Ying Gao. Higher-order symmetric duality for multiobjective programming with cone constraints. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-12. doi: 10.3934/jimo.2019033
[5]	Yanqin Bai, Chuanhao Guo. Doubly nonnegative relaxation method for solving multiple objective quadratic programming problems. Journal of Industrial & Management Optimization, 2014, 10 (2) : 543-556. doi: 10.3934/jimo.2014.10.543
[6]	Ye Tian, Qingwei Jin, Zhibin Deng. Quadratic optimization over a polyhedral cone. Journal of Industrial & Management Optimization, 2016, 12 (1) : 269-283. doi: 10.3934/jimo.2016.12.269
[7]	Cheng Lu, Zhenbo Wang, Wenxun Xing, Shu-Cherng Fang. Extended canonical duality and conic programming for solving 0-1 quadratic programming problems. Journal of Industrial & Management Optimization, 2010, 6 (4) : 779-793. doi: 10.3934/jimo.2010.6.779
[8]	Xiaoni Chi, Zhongping Wan, Zijun Hao. Second order sufficient conditions for a class of bilevel programs with lower level second-order cone programming problem. Journal of Industrial & Management Optimization, 2015, 11 (4) : 1111-1125. doi: 10.3934/jimo.2015.11.1111
[9]	Jinchuan Zhou, Changyu Wang, Naihua Xiu, Soonyi Wu. First-order optimality conditions for convex semi-infinite min-max programming with noncompact sets. Journal of Industrial & Management Optimization, 2009, 5 (4) : 851-866. doi: 10.3934/jimo.2009.5.851
[10]	Ye Tian, Cheng Lu. Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1027-1039. doi: 10.3934/jimo.2011.7.1027
[11]	Shrikrishna G. Dani. Simultaneous diophantine approximation with quadratic and linear forms. Journal of Modern Dynamics, 2008, 2 (1) : 129-138. doi: 10.3934/jmd.2008.2.129
[12]	Ziye Shi, Qingwei Jin. Second order optimality conditions and reformulations for nonconvex quadratically constrained quadratic programming problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 871-882. doi: 10.3934/jimo.2014.10.871
[13]	Yanqin Bai, Pengfei Ma, Jing Zhang. A polynomial-time interior-point method for circular cone programming based on kernel functions. Journal of Industrial & Management Optimization, 2016, 12 (2) : 739-756. doi: 10.3934/jimo.2016.12.739
[14]	Yanqin Bai, Xuerui Gao, Guoqiang Wang. Primal-dual interior-point algorithms for convex quadratic circular cone optimization. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 211-231. doi: 10.3934/naco.2015.5.211
[15]	Yanqin Bai, Lipu Zhang. A full-Newton step interior-point algorithm for symmetric cone convex quadratic optimization. Journal of Industrial & Management Optimization, 2011, 7 (4) : 891-906. doi: 10.3934/jimo.2011.7.891
[16]	Shu-Cherng Fang, David Y. Gao, Ruey-Lin Sheu, Soon-Yi Wu. Canonical dual approach to solving 0-1 quadratic programming problems. Journal of Industrial & Management Optimization, 2008, 4 (1) : 125-142. doi: 10.3934/jimo.2008.4.125
[17]	Zhenbo Wang, Shu-Cherng Fang, David Y. Gao, Wenxun Xing. Global extremal conditions for multi-integer quadratic programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 213-225. doi: 10.3934/jimo.2008.4.213
[18]	Andrew E.B. Lim, John B. Moore. A path following algorithm for infinite quadratic programming on a Hilbert space. Discrete & Continuous Dynamical Systems - A, 1998, 4 (4) : 653-670. doi: 10.3934/dcds.1998.4.653
[19]	Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial & Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177
[20]	Ailing Zhang, Shunsuke Hayashi. Celis-Dennis-Tapia based approach to quadratic fractional programming problems with two quadratic constraints. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 83-98. doi: 10.3934/naco.2011.1.83

2017 Impact Factor: 0.994

American Institute of Mathematical Sciences