# American Institute of Mathematical Sciences

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

## Quadratic optimization over one first-order cone

 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

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.
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. Google Scholar [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. Google Scholar [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. Google Scholar [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. Google Scholar [5] E. Bishop and R. R. Phelps, The support functionals of a convex set,, in Proceedings of Symposia in Pure Mathematics, (1963), 27. Google Scholar [6] S. Boyd and L. Vandenberghe, Convex Optimization,, Cambridge University Press, (2004). Google Scholar [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. Google Scholar [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. Google Scholar [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. Google Scholar [10] G. Eichfelder and J. Povh, On reformulations of nonconvex quadratic programs over convex cones by set-semidefinite constraints,, preprint, (2010). Google Scholar [11] Q. Jin, Quadratically Constrained Quadratic Programming Problems and Extensions,, Ph.D thesis, (2011). Google Scholar [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. Google Scholar [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). Google Scholar [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. Google Scholar [15] Y. Nesterov and A. Nemirovsky, Interior-point Polynomial Methods in Convex Programming,, SIAM, (1994). doi: 10.1137/1.9781611970791. Google Scholar [16] R. T. Rockafellar, Convex Analysis,, 2nd edition, (1972). Google Scholar [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. Google Scholar [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. Google Scholar [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. Google Scholar [20] S. A. Vavasis, Nonlinear Optimization: Complexity Issues,, International Series of Monographs on Computer Science, (1991). Google Scholar [21] Y. Ye and S. Zhang, New results on quadratic minimization,, SIAM Journal on Optimization, 14 (2003), 245. doi: 10.1137/S105262340139001X. Google Scholar

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. Google Scholar [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. Google Scholar [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. Google Scholar [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. Google Scholar [5] E. Bishop and R. R. Phelps, The support functionals of a convex set,, in Proceedings of Symposia in Pure Mathematics, (1963), 27. Google Scholar [6] S. Boyd and L. Vandenberghe, Convex Optimization,, Cambridge University Press, (2004). Google Scholar [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. Google Scholar [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. Google Scholar [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. Google Scholar [10] G. Eichfelder and J. Povh, On reformulations of nonconvex quadratic programs over convex cones by set-semidefinite constraints,, preprint, (2010). Google Scholar [11] Q. Jin, Quadratically Constrained Quadratic Programming Problems and Extensions,, Ph.D thesis, (2011). Google Scholar [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. Google Scholar [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). Google Scholar [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. Google Scholar [15] Y. Nesterov and A. Nemirovsky, Interior-point Polynomial Methods in Convex Programming,, SIAM, (1994). doi: 10.1137/1.9781611970791. Google Scholar [16] R. T. Rockafellar, Convex Analysis,, 2nd edition, (1972). Google Scholar [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. Google Scholar [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. Google Scholar [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. Google Scholar [20] S. A. Vavasis, Nonlinear Optimization: Complexity Issues,, International Series of Monographs on Computer Science, (1991). Google Scholar [21] Y. Ye and S. Zhang, New results on quadratic minimization,, SIAM Journal on Optimization, 14 (2003), 245. doi: 10.1137/S105262340139001X. Google Scholar

2018 Impact Factor: 1.025

## Metrics

• HTML views (0)
• Cited by (2)

• on AIMS