• 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, 2021, 14 (1) : 77-88. doi: 10.3934/krm.2020049

[2]

Yongjie Wang, Nan Gao. Some properties for almost cellular algebras. Electronic Research Archive, 2021, 29 (1) : 1681-1689. doi: 10.3934/era.2020086

[3]

Simone Göttlich, Elisa Iacomini, Thomas Jung. Properties of the LWR model with time delay. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020032

[4]

Bo Tan, Qinglong Zhou. Approximation properties of Lüroth expansions. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020389

[5]

Akbar Mahmoodi Rishakani, Seyed Mojtaba Dehnavi, Mohmmadreza Mirzaee Shamsabad, Nasour Bagheri. Cryptographic properties of cyclic binary matrices. Advances in Mathematics of Communications, 2021, 15 (2) : 311-327. doi: 10.3934/amc.2020068

[6]

Michael Winkler, Christian Stinner. Refined regularity and stabilization properties in a degenerate haptotaxis system. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 4039-4058. doi: 10.3934/dcds.2020030

[7]

Yujuan Li, Huaifu Wang, Peipei Zhou, Guoshuang Zhang. Some properties of the cycle decomposition of WG-NLFSR. Advances in Mathematics of Communications, 2021, 15 (1) : 155-165. doi: 10.3934/amc.2020050

[8]

Lisa Hernandez Lucas. Properties of sets of Subspaces with Constant Intersection Dimension. Advances in Mathematics of Communications, 2021, 15 (1) : 191-206. doi: 10.3934/amc.2020052

[9]

Nitha Niralda P C, Sunil Mathew. On properties of similarity boundary of attractors in product dynamical systems. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021004

[10]

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

[11]

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

[12]

Giulia Luise, Giuseppe Savaré. Contraction and regularizing properties of heat flows in metric measure spaces. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 273-297. doi: 10.3934/dcdss.2020327

[13]

Liping Tang, Ying Gao. Some properties of nonconvex oriented distance function and applications to vector optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (1) : 485-500. doi: 10.3934/jimo.2020117

[14]

Xiaoming Wang. Upper semi-continuity of stationary statistical properties of dissipative systems. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 521-540. doi: 10.3934/dcds.2009.23.521

[15]

Philippe Laurençot, Christoph Walker. Variational solutions to an evolution model for MEMS with heterogeneous dielectric properties. Discrete & Continuous Dynamical Systems - S, 2021, 14 (2) : 677-694. doi: 10.3934/dcdss.2020360

[16]

Helin Guo, Huan-Song Zhou. Properties of the minimizers for a constrained minimization problem arising in Kirchhoff equation. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1023-1050. doi: 10.3934/dcds.2020308

[17]

Lars Grüne, Roberto Guglielmi. On the relation between turnpike properties and dissipativity for continuous time linear quadratic optimal control problems. Mathematical Control & Related Fields, 2021, 11 (1) : 169-188. doi: 10.3934/mcrf.2020032

[18]

Simone Fiori. Error-based control systems on Riemannian state manifolds: Properties of the principal pushforward map associated to parallel transport. Mathematical Control & Related Fields, 2021, 11 (1) : 143-167. doi: 10.3934/mcrf.2020031

[19]

Qiang Fu, Xin Guo, Sun Young Jeon, Eric N. Reither, Emma Zang, Kenneth C. Land. The uses and abuses of an age-period-cohort method: On the linear algebra and statistical properties of intrinsic and related estimators. Mathematical Foundations of Computing, 2020  doi: 10.3934/mfc.2021001

[20]

Divine Wanduku. Finite- and multi-dimensional state representations and some fundamental asymptotic properties of a family of nonlinear multi-population models for HIV/AIDS with ART treatment and distributed delays. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021005

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (117)
  • HTML views (430)
  • Cited by (0)

Other articles
by authors

[Back to Top]