Advanced Search
Article Contents
Article Contents

Quadratic optimization over one first-order cone

Abstract Related Papers Cited by
  • 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.
    Mathematics Subject Classification: Primary: 90C20, 90C26; Secondary: 15B48, 65Y20.


    \begin{equation} \\ \end{equation}
  • [1]

    F. Alizadeh and D. Goldfarb, Second-order cone programming, Mathematical Programming, 95 (2003), 3-51.doi: 10.1007/s10107-002-0339-5.


    E. D. Andersen, C. Roos and T. Terlaky, Notes on duality in second order and $p$-order cone optimization, Optimization, 51 (2002), 627-643.doi: 10.1080/0233193021000030751.


    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-2793. Available from: http://www.optimization-online.org/DB_FILE/2012/08/3563.pdf.doi: 10.1016/j.dam.2013.05.017.


    A. Ben-Tal and A. Nemirovski, Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications, MPS/SIAM Series on Optimization, SIAM, Philadelphia, PA, 2001.doi: 10.1137/1.9780898718829.


    E. Bishop and R. R. Phelps, The support functionals of a convex set, in Proceedings of Symposia in Pure Mathematics, Vol. VII, Amer. Math. Soc., Providence, R.I., 1963, 27-35.


    S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, Cambridge, 2004.


    S. Burer, On the copositive representation of binary and continous nonconvex quadratic programs, Mathematical Programming, 120 (2009), 479-495.doi: 10.1007/s10107-008-0223-z.


    S. Burer and K. M. Anstreicher, Second-order-cone constraints for extended trust-region subproblems, SIAM Journal on Optimization, 23 (2013), 432-451.doi: 10.1137/110826862.


    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-28.doi: 10.1016/j.ejor.2013.02.031.


    G. Eichfelder and J. Povh, On reformulations of nonconvex quadratic programs over convex cones by set-semidefinite constraints, preprint, 2010. Available from: http://www.optimization-online.org/DB_FILE/2010/12/2843.pdf.


    Q. Jin, Quadratically Constrained Quadratic Programming Problems and Extensions, Ph.D thesis, North Carolina State University, 2011.


    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-134.doi: 10.1007/s40305-013-0009-8.


    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.


    M. W. Margaret, Advances in cone-based preference modeling for decision making with multiple criteria, Decision Making in Manufacturing and Services, 1 (2007), 153-173.


    Y. Nesterov and A. Nemirovsky, Interior-point Polynomial Methods in Convex Programming, SIAM, Philadelphia, PA, 1994.doi: 10.1137/1.9781611970791.


    R. T. Rockafellar, Convex Analysis, 2nd edition, Princeton University Press, Princeton, NJ, 1972.


    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-653.doi: 10.1080/10556789908805766.


    J. F. Sturm and S. Z. Zhang, On cones of nonnegative quadratic functions, Mathematics of Operations Research, 28 (2003), 246-267.doi: 10.1287/moor.


    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-721.doi: 10.3934/jimo.2013.9.703.


    S. A. Vavasis, Nonlinear Optimization: Complexity Issues, International Series of Monographs on Computer Science, 8, The Clarendon Press, Oxford University Press, New York, 1991.


    Y. Ye and S. Zhang, New results on quadratic minimization, SIAM Journal on Optimization, 14 (2003), 245-267.doi: 10.1137/S105262340139001X.

  • 加载中

Article Metrics

HTML views() PDF downloads(83) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint