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

[1]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

[2]

Jean-François Biasse. Improvements in the computation of ideal class groups of imaginary quadratic number fields. Advances in Mathematics of Communications, 2010, 4 (2) : 141-154. doi: 10.3934/amc.2010.4.141

[3]

Marcelo Messias. Periodic perturbation of quadratic systems with two infinite heteroclinic cycles. Discrete & Continuous Dynamical Systems - A, 2012, 32 (5) : 1881-1899. doi: 10.3934/dcds.2012.32.1881

[4]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023

[5]

Caifang Wang, Tie Zhou. The order of convergence for Landweber Scheme with $\alpha,\beta$-rule. Inverse Problems & Imaging, 2012, 6 (1) : 133-146. doi: 10.3934/ipi.2012.6.133

[6]

Rabiaa Ouahabi, Nasr-Eddine Hamri. Design of new scheme adaptive generalized hybrid projective synchronization for two different chaotic systems with uncertain parameters. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2361-2370. doi: 10.3934/dcdsb.2020182

[7]

Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327

[8]

Meiqiao Ai, Zhimin Zhang, Wenguang Yu. First passage problems of refracted jump diffusion processes and their applications in valuing equity-linked death benefits. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021039

[9]

Zhihua Zhang, Naoki Saito. PHLST with adaptive tiling and its application to antarctic remote sensing image approximation. Inverse Problems & Imaging, 2014, 8 (1) : 321-337. doi: 10.3934/ipi.2014.8.321

[10]

Murat Uzunca, Ayşe Sarıaydın-Filibelioǧlu. Adaptive discontinuous galerkin finite elements for advective Allen-Cahn equation. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 269-281. doi: 10.3934/naco.2020025

[11]

Alexandre B. Simas, Fábio J. Valentim. $W$-Sobolev spaces: Higher order and regularity. Communications on Pure & Applied Analysis, 2015, 14 (2) : 597-607. doi: 10.3934/cpaa.2015.14.597

[12]

Wolf-Jüergen Beyn, Janosch Rieger. The implicit Euler scheme for one-sided Lipschitz differential inclusions. Discrete & Continuous Dynamical Systems - B, 2010, 14 (2) : 409-428. doi: 10.3934/dcdsb.2010.14.409

[13]

Alina Chertock, Alexander Kurganov, Mária Lukáčová-Medvi${\rm{\check{d}}}$ová, Șeyma Nur Özcan. An asymptotic preserving scheme for kinetic chemotaxis models in two space dimensions. Kinetic & Related Models, 2019, 12 (1) : 195-216. doi: 10.3934/krm.2019009

[14]

Qian Liu. The lower bounds on the second-order nonlinearity of three classes of Boolean functions. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020136

[15]

Diana Keller. Optimal control of a linear stochastic Schrödinger equation. Conference Publications, 2013, 2013 (special) : 437-446. doi: 10.3934/proc.2013.2013.437

[16]

Guillaume Bal, Wenjia Jing. Homogenization and corrector theory for linear transport in random media. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1311-1343. doi: 10.3934/dcds.2010.28.1311

[17]

Nizami A. Gasilov. Solving a system of linear differential equations with interval coefficients. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2739-2747. doi: 10.3934/dcdsb.2020203

[18]

Tomáš Roubíček. An energy-conserving time-discretisation scheme for poroelastic media with phase-field fracture emitting waves and heat. Discrete & Continuous Dynamical Systems - S, 2017, 10 (4) : 867-893. doi: 10.3934/dcdss.2017044

[19]

Chih-Chiang Fang. Bayesian decision making in determining optimal leased term and preventive maintenance scheme for leased facilities. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020127

[20]

Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Linear nonbinary covering codes and saturating sets in projective spaces. Advances in Mathematics of Communications, 2011, 5 (1) : 119-147. doi: 10.3934/amc.2011.5.119

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (46)
  • HTML views (0)
  • Cited by (2)

[Back to Top]