• Previous Article
    Optimal pension decision under heterogeneous health statuses and bequest motives
  • JIMO Home
  • This Issue
  • Next Article
    A mixed-integer linear programming model for optimal vessel scheduling in offshore oil and gas operations
October  2017, 13(4): 1625-1640. doi: 10.3934/jimo.2017010

On subspace properties of the quadratically constrained quadratic program

School of Mathematical Sciences, and MOE-LSC, Shanghai Jiao Tong University, 800 Dongchuan Road, Shanghai 200240, China

* Corresponding author: Jinyan Fan

Received  April 2016 Revised  October 2016 Published  December 2016

Fund Project: The authors are partially supported by NSFC 11171217 and 11571234.

In this paper, we study subspace properties of the quadratically constrained quadratic program (QCQP). We prove that, if an appropriate subspace is chosen to satisfy subspace properties, then the solution of the QCQP lies in that subspace. So, we can solve the QCQP in that subspace rather than solve it in the original space. The computational cost could be reduced significantly if the dimension of the subspace is much smaller. We also show how to construct such subspaces and investigate their dimensions.

Citation: Xin Zhao, Jinyan Fan. On subspace properties of the quadratically constrained quadratic program. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1625-1640. doi: 10.3934/jimo.2017010
References:
[1]

F. A. Al-Khayyal, Generalized bilinear programming: Part Ⅰ. Models, applications and linear programming relaxation, European Journal of Operational Research, 60 (1992), 306-314.  doi: 10.1016/0377-2217(92)90082-K.  Google Scholar

[2]

K. M. Anstreicher, Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming, Journal of Global Optimization, 43 (2009), 471-484.  doi: 10.1007/s10898-008-9372-0.  Google Scholar

[3]

G. N. GrapigliaJ. Y. Yuan and Y. Yuan, A Subspace version of the Powell-Yuan trust-region algorithm for equality constrained optimization, Journal of the Operations Research Society of China, 1 (2013), 425-451.  doi: 10.1007/s40305-013-0029-4.  Google Scholar

[4]

M. S. LoboL. VandenbergheS. Boyd and H. Lebret, Applications of second-order cone programming, Linear Algebra and its Applications, 284 (1998), 193-228.  doi: 10.1016/S0024-3795(98)10032-0.  Google Scholar

[5]

E. Phan-huy-Hao, Quadratically constrained quadratic programming: Some applications and a method for solution, Zeitschrift für Operations Research, 26 (1982), 105-119.   Google Scholar

[6]

U. Raber, Nonconvex all-quadratic global optimization problems: Solution methods, application and related topics, 1999. Google Scholar

[7]

H. D. Sherali and W. P. Adams, A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems, Kluwer Academic Publishers, Dordrecht, 1999. doi: 10.1007/978-1-4757-4388-3.  Google Scholar

[8]

N. Z. Shor, Dual estimates in multiextremal problems, Journal of Global Optimization, 2 (1992), 411-418.  doi: 10.1007/BF00122430.  Google Scholar

[9]

L. Vandenberghe and S. Boyd, Semidefinite programming, SIAM Review, 38 (1996), 49-95.  doi: 10.1137/1038003.  Google Scholar

[10]

Z. H. Wang and Y. X. Yuan, A subspace implementation of quasi-Newton trust region methods for unconstrained optimization, Numerische Mathematik, 104 (2006), 241-269.  doi: 10.1007/s00211-006-0021-6.  Google Scholar

[11]

A. Weintraub and J. Vera, A cutting plane approach for chance constrained linear programs, Operations Research, 39 (1991), 776-785.  doi: 10.1287/opre.39.5.776.  Google Scholar

[12]

Y. X. Yuan, Subspace techniques for nonlinear optimization, in Some Topics in Industrial and Applied Mathematics(eds. R. Jeltsch, D. Q. Li and I. H. Sloan), Higher Education Press, 8 (2007), 206-218 doi: 10.1142/9789812709356_0012.  Google Scholar

[13]

Y. X. Yuan, Subspace methods for large scale nonlinear equations and nonlinear least squares, Optimization and Engineering, 10 (2009), 207-218.  doi: 10.1007/s11081-008-9064-0.  Google Scholar

[14]

Y. X. Yuan, Recent advances in numerical methods for nonlinear equations and nonlinear least squares, Numerical Algebra, Control and Optimization, 1 (2011), 15-34.  doi: 10.3934/naco.2011.1.15.  Google Scholar

[15]

X. Zhao and J. Y. Fan, Subspace choices for the Celis-Dennis-Tapia problem, Science China Mathematics, Accepted. Google Scholar

show all references

References:
[1]

F. A. Al-Khayyal, Generalized bilinear programming: Part Ⅰ. Models, applications and linear programming relaxation, European Journal of Operational Research, 60 (1992), 306-314.  doi: 10.1016/0377-2217(92)90082-K.  Google Scholar

[2]

K. M. Anstreicher, Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming, Journal of Global Optimization, 43 (2009), 471-484.  doi: 10.1007/s10898-008-9372-0.  Google Scholar

[3]

G. N. GrapigliaJ. Y. Yuan and Y. Yuan, A Subspace version of the Powell-Yuan trust-region algorithm for equality constrained optimization, Journal of the Operations Research Society of China, 1 (2013), 425-451.  doi: 10.1007/s40305-013-0029-4.  Google Scholar

[4]

M. S. LoboL. VandenbergheS. Boyd and H. Lebret, Applications of second-order cone programming, Linear Algebra and its Applications, 284 (1998), 193-228.  doi: 10.1016/S0024-3795(98)10032-0.  Google Scholar

[5]

E. Phan-huy-Hao, Quadratically constrained quadratic programming: Some applications and a method for solution, Zeitschrift für Operations Research, 26 (1982), 105-119.   Google Scholar

[6]

U. Raber, Nonconvex all-quadratic global optimization problems: Solution methods, application and related topics, 1999. Google Scholar

[7]

H. D. Sherali and W. P. Adams, A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems, Kluwer Academic Publishers, Dordrecht, 1999. doi: 10.1007/978-1-4757-4388-3.  Google Scholar

[8]

N. Z. Shor, Dual estimates in multiextremal problems, Journal of Global Optimization, 2 (1992), 411-418.  doi: 10.1007/BF00122430.  Google Scholar

[9]

L. Vandenberghe and S. Boyd, Semidefinite programming, SIAM Review, 38 (1996), 49-95.  doi: 10.1137/1038003.  Google Scholar

[10]

Z. H. Wang and Y. X. Yuan, A subspace implementation of quasi-Newton trust region methods for unconstrained optimization, Numerische Mathematik, 104 (2006), 241-269.  doi: 10.1007/s00211-006-0021-6.  Google Scholar

[11]

A. Weintraub and J. Vera, A cutting plane approach for chance constrained linear programs, Operations Research, 39 (1991), 776-785.  doi: 10.1287/opre.39.5.776.  Google Scholar

[12]

Y. X. Yuan, Subspace techniques for nonlinear optimization, in Some Topics in Industrial and Applied Mathematics(eds. R. Jeltsch, D. Q. Li and I. H. Sloan), Higher Education Press, 8 (2007), 206-218 doi: 10.1142/9789812709356_0012.  Google Scholar

[13]

Y. X. Yuan, Subspace methods for large scale nonlinear equations and nonlinear least squares, Optimization and Engineering, 10 (2009), 207-218.  doi: 10.1007/s11081-008-9064-0.  Google Scholar

[14]

Y. X. Yuan, Recent advances in numerical methods for nonlinear equations and nonlinear least squares, Numerical Algebra, Control and Optimization, 1 (2011), 15-34.  doi: 10.3934/naco.2011.1.15.  Google Scholar

[15]

X. Zhao and J. Y. Fan, Subspace choices for the Celis-Dennis-Tapia problem, Science China Mathematics, Accepted. Google Scholar

[1]

Nicolas Rougerie. On two properties of the Fisher information. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020049

[2]

Andreu Ferré Moragues. Properties of multicorrelation sequences and large returns under some ergodicity assumptions. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020386

[3]

Christian Beck, Lukas Gonon, Martin Hutzenthaler, Arnulf Jentzen. On existence and uniqueness properties for solutions of stochastic fixed point equations. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020320

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (110)
  • HTML views (429)
  • Cited by (0)

Other articles
by authors

[Back to Top]