\`x^2+y_1+z_12^34\`
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.

    Citation:

    \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.

    [2]

    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.

    [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-2793. Available from: http://www.optimization-online.org/DB_FILE/2012/08/3563.pdf.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, SIAM, Philadelphia, PA, 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, Vol. VII, Amer. Math. Soc., Providence, R.I., 1963, 27-35.

    [6]

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

    [7]

    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.

    [8]

    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.

    [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-28.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. Available from: http://www.optimization-online.org/DB_FILE/2010/12/2843.pdf.

    [11]

    Q. Jin, Quadratically Constrained Quadratic Programming Problems and Extensions, Ph.D thesis, North Carolina State University, 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-134.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-173.

    [15]

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

    [16]

    R. T. Rockafellar, Convex Analysis, 2nd edition, Princeton University Press, Princeton, NJ, 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-653.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-267.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-721.doi: 10.3934/jimo.2013.9.703.

    [20]

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

    [21]

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

  • 加载中
SHARE

Article Metrics

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

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return