American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Subgradient-based neural network for nonconvex optimization problems in support vector machines with indefinite kernels
  • JIMO Home
  • This Issue
  • Next Article
    A novel discriminant minimum class locality preserving canonical correlation analysis and its applications
January  2016, 12(1): 269-283. doi: 10.3934/jimo.2016.12.269

Quadratic optimization over a polyhedral cone

Ye Tian 1, , Qingwei Jin 2, and  Zhibin Deng 3,

1. 

School of Business Administration, Southwestern University of Finance and Economics, Chengdu, 611130
2. 

Department of Management Science and Engineering, Zhejiang University, Hangzhou, Zhejiang 310058
3. 

School of Management, University of Chinese Academy of Sciences, Beijing, 100190, China

Received  August 2014 Revised  January 2015 Published  April 2015

In this paper, we study the polyhedral cone constrained homogeneous quadratic programming problem and provide an equivalent linear conic reformulation. Based on a union of second-order cones which covers the polyhedral cone, a sequence of computable linear conic programming problems are constructed to approximate the linear conic reformulation. The convergence of the sequential solutions is guaranteed as the number of second-order cones increases such that the union of the second-order cones gets close to the polyhedral cone. In order to relieve the computational burden and improve the efficiency, an adaptive scheme and valid inequalities derived by the reformulation-linearization technique are added to the proposed algorithm. Finally, the numerical results demonstrate the effectiveness of the algorithm.
Keywords: cone of nonnegative quadratic forms, linear conic programming approximation, adaptive scheme., polyhedral cone, Quadratic optimization.
Mathematics Subject Classification: Primary: 90C26, 90C59, 90C22; Secondary: 30E1.
Citation: Ye Tian, Qingwei Jin, Zhibin Deng. Quadratic optimization over a polyhedral cone. Journal of Industrial & Management Optimization, 2016, 12 (1) : 269-283. doi: 10.3934/jimo.2016.12.269
References:
[1]

L. Angulo-Meza and M. Lins, Review of methods for increasing discrimination in data envelopment analysis,, Annals of Operations Research, 116 (2002), 225.  doi: 10.1023/A:1021340616758.  Google Scholar

[2]

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

[3]

A. Ben-Tal and A. Nemirovski, Lectures on Modern Convex Optimization Analysis, Algorithms and Engineering Applications,, SIAM, (2001).  doi: 10.1137/1.9780898718829.  Google Scholar

[4]

S. Boyd and L. Vandenberghe, Convex Optimization,, Cambridge University Press, (2004).  doi: 10.1017/CBO9780511804441.  Google Scholar

[5]

S. Burer, On the copositive representation of binary and continuous nonconvex quadratic programs,, Mathematical Programming, 120 (2009), 479.  doi: 10.1007/s10107-008-0223-z.  Google Scholar

[6]

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

[7]

M. Grant and S. Boyd, CVX: matlab Software for Disciplined Programming,, version 1.2, (2010).   Google Scholar

[8]

X. Guo, Z. Deng, S.-C. Fang and W. Xing, Quadratic optimization over one first-order cone,, Journal of Industrial and Management Optimization, 10 (2014), 945.  doi: 10.3934/jimo.2014.10.945.  Google Scholar

[9]

P. Hansen, B. Jaumard, M. Ruiz and J. Xiong, Global minimization of indefinite quadratic functions subject to box constraints,, Naval Research Logistics, 40 (1993), 373.  doi: 10.1002/1520-6750(199304)40:3<373::AID-NAV3220400307>3.0.CO;2-A.  Google Scholar

[10]

J. Hiriat-Urruty and C. Lemaréchal, Fundamentals of Convex Analysis,, Springer-Berlag, (2001).  doi: 10.1007/978-3-642-56468-0.  Google Scholar

[11]

H. Jiang, M. Fukushima, L. Qi and D. Sun, A trust region method for solving generalized complementarity problem,, SIAM Journal on Optimization, 8 (1998), 140.  doi: 10.1137/S1052623495296541.  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, S.-C. Fang, Q. Jin, Z. Wang and W. Xing, KKT solution and conic relaxation for solving quadratically constrained quadratic programming problems,, SIAM Journal on Optimization, 21 (2010), 1475.  doi: 10.1137/100793955.  Google Scholar

[14]

H. Kunze and D. Siegel, A graph theoretic approach to strong monotonicity with respect to polyhedral cones,, Positivity, 6 (2002), 95.  doi: 10.1023/A:1015290601993.  Google Scholar

[15]

F. Ma, G. Sheng and Y. Yin, A superlinearly convergent method for the generalized complementarity problem over a polyhedral cone,, Journal of Applied Mathematics, (2013).  doi: 10.1155/2013/671402.  Google Scholar

[16]

R. Rockafellar, Convex Analysis,, Princeton University Press, (1997).   Google Scholar

[17]

A. Sinha, P. Korhonen, J. Wallenius and K. Deb, An interactive evolutionary multi-objective optimization method based on polyhedral cones,, Learning and Intelligent Optimization, 6073 (2010), 318.  doi: 10.1007/978-3-642-13800-3_33.  Google Scholar

[18]

J. Stoer and C. Witzgall, Convexity and Optimization In Finite Dimensions,, Springer-Berlag Berlin, (1970).   Google Scholar

[19]

J. Sturm, SeDuMi 1.02, a matlab tool box for optimization over symmetric cones,, Optimization Methods and Software, 11 & 12 (1999), 625.  doi: 10.1080/10556789908805766.  Google Scholar

[20]

J. Sturm and S. Zhang, On cones of nonnegative quadratic functions,, Mathematics of Operations Research, 28 (2003), 246.  doi: 10.1287/moor.28.2.246.14485.  Google Scholar

[21]

H. Sun and Y. Wang, Further discussion on the error bound for generalized linear complementarity problem over a polyhedral cone,, Journal of Optimization and Theory Application, 159 (2013), 93.  doi: 10.1007/s10957-013-0290-z.  Google Scholar

[22]

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 positiv programming,, Journal of Industrial and Management Optimization, 9 (2013), 703.  doi: 10.3934/jimo.2013.9.703.  Google Scholar

[23]

Y. Wang, F. Ma and J. Zhang, A nonsmooth L-M method for solving the generalized nonlinear complementarity problem over a polyhedral cone,, Applied Mathematics and Optimization, 52 (2005), 73.  doi: 10.1007/s00245-005-0823-4.  Google Scholar

[24]

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]

L. Angulo-Meza and M. Lins, Review of methods for increasing discrimination in data envelopment analysis,, Annals of Operations Research, 116 (2002), 225.  doi: 10.1023/A:1021340616758.  Google Scholar

[2]

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

[3]

A. Ben-Tal and A. Nemirovski, Lectures on Modern Convex Optimization Analysis, Algorithms and Engineering Applications,, SIAM, (2001).  doi: 10.1137/1.9780898718829.  Google Scholar

[4]

S. Boyd and L. Vandenberghe, Convex Optimization,, Cambridge University Press, (2004).  doi: 10.1017/CBO9780511804441.  Google Scholar

[5]

S. Burer, On the copositive representation of binary and continuous nonconvex quadratic programs,, Mathematical Programming, 120 (2009), 479.  doi: 10.1007/s10107-008-0223-z.  Google Scholar

[6]

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

[7]

M. Grant and S. Boyd, CVX: matlab Software for Disciplined Programming,, version 1.2, (2010).   Google Scholar

[8]

X. Guo, Z. Deng, S.-C. Fang and W. Xing, Quadratic optimization over one first-order cone,, Journal of Industrial and Management Optimization, 10 (2014), 945.  doi: 10.3934/jimo.2014.10.945.  Google Scholar

[9]

P. Hansen, B. Jaumard, M. Ruiz and J. Xiong, Global minimization of indefinite quadratic functions subject to box constraints,, Naval Research Logistics, 40 (1993), 373.  doi: 10.1002/1520-6750(199304)40:3<373::AID-NAV3220400307>3.0.CO;2-A.  Google Scholar

[10]

J. Hiriat-Urruty and C. Lemaréchal, Fundamentals of Convex Analysis,, Springer-Berlag, (2001).  doi: 10.1007/978-3-642-56468-0.  Google Scholar

[11]

H. Jiang, M. Fukushima, L. Qi and D. Sun, A trust region method for solving generalized complementarity problem,, SIAM Journal on Optimization, 8 (1998), 140.  doi: 10.1137/S1052623495296541.  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, S.-C. Fang, Q. Jin, Z. Wang and W. Xing, KKT solution and conic relaxation for solving quadratically constrained quadratic programming problems,, SIAM Journal on Optimization, 21 (2010), 1475.  doi: 10.1137/100793955.  Google Scholar

[14]

H. Kunze and D. Siegel, A graph theoretic approach to strong monotonicity with respect to polyhedral cones,, Positivity, 6 (2002), 95.  doi: 10.1023/A:1015290601993.  Google Scholar

[15]

F. Ma, G. Sheng and Y. Yin, A superlinearly convergent method for the generalized complementarity problem over a polyhedral cone,, Journal of Applied Mathematics, (2013).  doi: 10.1155/2013/671402.  Google Scholar

[16]

R. Rockafellar, Convex Analysis,, Princeton University Press, (1997).   Google Scholar

[17]

A. Sinha, P. Korhonen, J. Wallenius and K. Deb, An interactive evolutionary multi-objective optimization method based on polyhedral cones,, Learning and Intelligent Optimization, 6073 (2010), 318.  doi: 10.1007/978-3-642-13800-3_33.  Google Scholar

[18]

J. Stoer and C. Witzgall, Convexity and Optimization In Finite Dimensions,, Springer-Berlag Berlin, (1970).   Google Scholar

[19]

J. Sturm, SeDuMi 1.02, a matlab tool box for optimization over symmetric cones,, Optimization Methods and Software, 11 & 12 (1999), 625.  doi: 10.1080/10556789908805766.  Google Scholar

[20]

J. Sturm and S. Zhang, On cones of nonnegative quadratic functions,, Mathematics of Operations Research, 28 (2003), 246.  doi: 10.1287/moor.28.2.246.14485.  Google Scholar

[21]

H. Sun and Y. Wang, Further discussion on the error bound for generalized linear complementarity problem over a polyhedral cone,, Journal of Optimization and Theory Application, 159 (2013), 93.  doi: 10.1007/s10957-013-0290-z.  Google Scholar

[22]

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 positiv programming,, Journal of Industrial and Management Optimization, 9 (2013), 703.  doi: 10.3934/jimo.2013.9.703.  Google Scholar

[23]

Y. Wang, F. Ma and J. Zhang, A nonsmooth L-M method for solving the generalized nonlinear complementarity problem over a polyhedral cone,, Applied Mathematics and Optimization, 52 (2005), 73.  doi: 10.1007/s00245-005-0823-4.  Google Scholar

[24]

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

[1]

Hua Chen, Yawei Wei. Multiple solutions for nonlinear cone degenerate elliptic equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020272
[2]

Alain Bensoussan, Xinwei Feng, Jianhui Huang. Linear-quadratic-Gaussian mean-field-game with partial observation and common noise. Mathematical Control & Related Fields, 2021, 11 (1) : 23-46. doi: 10.3934/mcrf.2020025
[3]

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
[4]

Jingrui Sun, Hanxiao Wang. Mean-field stochastic linear-quadratic optimal control problems: Weak closed-loop solvability. Mathematical Control & Related Fields, 2021, 11 (1) : 47-71. doi: 10.3934/mcrf.2020026
[5]

Peng Luo. Comparison theorem for diagonally quadratic BSDEs. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020374
[6]

Huu-Quang Nguyen, Ya-Chi Chu, Ruey-Lin Sheu. On the convexity for the range set of two quadratic functions. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020169
[7]

Wei-Chieh Chen, Bogdan Kazmierczak. Traveling waves in quadratic autocatalytic systems with complexing agent. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020364
[8]

Gui-Qiang Chen, Beixiang Fang. Stability of transonic shock-fronts in three-dimensional conical steady potential flow past a perturbed cone. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 85-114. doi: 10.3934/dcds.2009.23.85
[9]

Ke Su, Yumeng Lin, Chun Xu. A new adaptive method to nonlinear semi-infinite programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021012
[10]

Tengfei Yan, Qunying Liu, Bowen Dou, Qing Li, Bowen Li. An adaptive dynamic programming method for torque ripple minimization of PMSM. Journal of Industrial & Management Optimization, 2021, 17 (2) : 827-839. doi: 10.3934/jimo.2019136
[11]

Djamel Aaid, Amel Noui, Özen Özer. Piecewise quadratic bounding functions for finding real roots of polynomials. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 63-73. doi: 10.3934/naco.2020015
[12]

Peter Frolkovič, Karol Mikula, Jooyoung Hahn, Dirk Martin, Branislav Basara. Flux balanced approximation with least-squares gradient for diffusion equation on polyhedral mesh. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 865-879. doi: 10.3934/dcdss.2020350
[13]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102
[14]

Pablo Neme, Jorge Oviedo. A note on the lattice structure for matching markets via linear programming. Journal of Dynamics & Games, 2020  doi: 10.3934/jdg.2021001
[15]

Klemens Fellner, Jeff Morgan, Bao Quoc Tang. Uniform-in-time bounds for quadratic reaction-diffusion systems with mass dissipation in higher dimensions. Discrete & Continuous Dynamical Systems - S, 2021, 14 (2) : 635-651. doi: 10.3934/dcdss.2020334
[16]

Norman Noguera, Ademir Pastor. Scattering of radial solutions for quadratic-type Schrödinger systems in dimension five. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021018
[17]

Haodong Yu, Jie Sun. Robust stochastic optimization with convex risk measures: A discretized subgradient scheme. Journal of Industrial & Management Optimization, 2021, 17 (1) : 81-99. doi: 10.3934/jimo.2019100
[18]

Mahdi Karimi, Seyed Jafar Sadjadi. Optimization of a Multi-Item Inventory model for deteriorating items with capacity constraint using dynamic programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021013
[19]

Ali Mahmoodirad, Harish Garg, Sadegh Niroomand. Solving fuzzy linear fractional set covering problem by a goal programming based solution approach. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020162
[20]

Chaman Kumar. On Milstein-type scheme for SDE driven by Lévy noise with super-linear coefficients. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1405-1446. doi: 10.3934/dcdsb.2020167

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (109)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences