• 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 and 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.

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

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

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

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

[6]

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

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

[8]

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

[9]

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

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

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

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

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

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

[15]

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

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.

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

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

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

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

[6]

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

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

[8]

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

[9]

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

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

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

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

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

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

[15]

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

[1]

Ernst M. Gabidulin, Pierre Loidreau. Properties of subspace subcodes of Gabidulin codes. Advances in Mathematics of Communications, 2008, 2 (2) : 147-157. doi: 10.3934/amc.2008.2.147

[2]

Antonio Cossidente, Sascha Kurz, Giuseppe Marino, Francesco Pavese. Combining subspace codes. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021007

[3]

Michael Kiermaier, Reinhard Laue. Derived and residual subspace designs. Advances in Mathematics of Communications, 2015, 9 (1) : 105-115. doi: 10.3934/amc.2015.9.105

[4]

Heide Gluesing-Luerssen, Carolyn Troha. Construction of subspace codes through linkage. Advances in Mathematics of Communications, 2016, 10 (3) : 525-540. doi: 10.3934/amc.2016023

[5]

Daniel Heinlein, Ferdinand Ihringer. New and updated semidefinite programming bounds for subspace codes. Advances in Mathematics of Communications, 2020, 14 (4) : 613-630. doi: 10.3934/amc.2020034

[6]

Haixia Liu, Jian-Feng Cai, Yang Wang. Subspace clustering by (k,k)-sparse matrix factorization. Inverse Problems and Imaging, 2017, 11 (3) : 539-551. doi: 10.3934/ipi.2017025

[7]

Qiao-Fang Lian, Yun-Zhang Li. Reducing subspace frame multiresolution analysis and frame wavelets. Communications on Pure and Applied Analysis, 2007, 6 (3) : 741-756. doi: 10.3934/cpaa.2007.6.741

[8]

Daniel Heinlein, Sascha Kurz. Binary subspace codes in small ambient spaces. Advances in Mathematics of Communications, 2018, 12 (4) : 817-839. doi: 10.3934/amc.2018048

[9]

Thomas Honold, Michael Kiermaier, Sascha Kurz. Constructions and bounds for mixed-dimension subspace codes. Advances in Mathematics of Communications, 2016, 10 (3) : 649-682. doi: 10.3934/amc.2016033

[10]

Lori Badea, Marius Cocou. Approximation results and subspace correction algorithms for implicit variational inequalities. Discrete and Continuous Dynamical Systems - S, 2013, 6 (6) : 1507-1524. doi: 10.3934/dcdss.2013.6.1507

[11]

Gustavo Terra Bastos, Reginaldo Palazzo Júnior, Marinês Guerreiro. Abelian non-cyclic orbit codes and multishot subspace codes. Advances in Mathematics of Communications, 2020, 14 (4) : 631-650. doi: 10.3934/amc.2020035

[12]

Guojun Gan, Kun Chen. A soft subspace clustering algorithm with log-transformed distances. Big Data & Information Analytics, 2016, 1 (1) : 93-109. doi: 10.3934/bdia.2016.1.93

[13]

Hua Huang, Weiwei Wang, Chengwu Lu, Xiangchu Feng, Ruiqiang He. Side-information-induced reweighted sparse subspace clustering. Journal of Industrial and Management Optimization, 2021, 17 (3) : 1235-1252. doi: 10.3934/jimo.2020019

[14]

Qiao Liang, Qiang Ye. Deflation by restriction for the inverse-free preconditioned Krylov subspace method. Numerical Algebra, Control and Optimization, 2016, 6 (1) : 55-71. doi: 10.3934/naco.2016.6.55

[15]

Xin Zhang, Jie Wen, Qin Ni. Subspace trust-region algorithm with conic model for unconstrained optimization. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 223-234. doi: 10.3934/naco.2013.3.223

[16]

Abdeslem Hafid Bentbib, Smahane El-Halouy, El Mostafa Sadek. Extended Krylov subspace methods for solving Sylvester and Stein tensor equations. Discrete and Continuous Dynamical Systems - S, 2022, 15 (1) : 41-56. doi: 10.3934/dcdss.2021026

[17]

Huimin Lao, Hao Chen. New constant dimension subspace codes from multilevel linkage construction. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022039

[18]

Antonio Cossidente, Francesco Pavese, Leo Storme. Optimal subspace codes in $ {{\rm{PG}}}(4,q) $. Advances in Mathematics of Communications, 2019, 13 (3) : 393-404. doi: 10.3934/amc.2019025

[19]

Hannes Bartz, Antonia Wachter-Zeh. Efficient decoding of interleaved subspace and Gabidulin codes beyond their unique decoding radius using Gröbner bases. Advances in Mathematics of Communications, 2018, 12 (4) : 773-804. doi: 10.3934/amc.2018046

[20]

Anton S. Zadorin. Exact travelling solution for a reaction-diffusion system with a piecewise constant production supported by a codimension-1 subspace. Communications on Pure and Applied Analysis, 2022, 21 (5) : 1567-1580. doi: 10.3934/cpaa.2022030

2021 Impact Factor: 1.411

Metrics

  • PDF downloads (172)
  • HTML views (439)
  • Cited by (0)

Other articles
by authors

[Back to Top]