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

Quadratic optimization over a polyhedral cone

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

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

[3]

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

[4]

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

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

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

[7]

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

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

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

[10]

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

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

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

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

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

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

[16]

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

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

[18]

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

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

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

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

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

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

[24]

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

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.

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

[3]

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

[4]

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

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

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

[7]

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

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

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

[10]

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

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

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

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

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

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

[16]

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

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

[18]

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

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

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

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

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

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

[24]

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

[1]

Ye Tian, Shu-Cherng Fang, Zhibin Deng, Wenxun 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 & Management Optimization, 2013, 9 (3) : 703-721. doi: 10.3934/jimo.2013.9.703

[2]

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

[3]

Shrikrishna G. Dani. Simultaneous diophantine approximation with quadratic and linear forms. Journal of Modern Dynamics, 2008, 2 (1) : 129-138. doi: 10.3934/jmd.2008.2.129

[4]

Yanqin Bai, Xuerui Gao, Guoqiang Wang. Primal-dual interior-point algorithms for convex quadratic circular cone optimization. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 211-231. doi: 10.3934/naco.2015.5.211

[5]

Yanqin Bai, Lipu Zhang. A full-Newton step interior-point algorithm for symmetric cone convex quadratic optimization. Journal of Industrial & Management Optimization, 2011, 7 (4) : 891-906. doi: 10.3934/jimo.2011.7.891

[6]

Fengming Ma, Yiju Wang, Hongge Zhao. A potential reduction method for the generalized linear complementarity problem over a polyhedral cone. Journal of Industrial & Management Optimization, 2010, 6 (1) : 259-267. doi: 10.3934/jimo.2010.6.259

[7]

Jing Zhou, Dejun Chen, Zhenbo Wang, Wenxun Xing. A conic approximation method for the 0-1 quadratic knapsack problem. Journal of Industrial & Management Optimization, 2013, 9 (3) : 531-547. doi: 10.3934/jimo.2013.9.531

[8]

Yi Zhang, Yong Jiang, Liwei Zhang, Jiangzhong Zhang. A perturbation approach for an inverse linear second-order cone programming. Journal of Industrial & Management Optimization, 2013, 9 (1) : 171-189. doi: 10.3934/jimo.2013.9.171

[9]

Shiyun Wang, Yong-Jin Liu, Yong Jiang. A majorized penalty approach to inverse linear second order cone programming problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 965-976. doi: 10.3934/jimo.2014.10.965

[10]

Yanqin Bai, Chuanhao Guo. Doubly nonnegative relaxation method for solving multiple objective quadratic programming problems. Journal of Industrial & Management Optimization, 2014, 10 (2) : 543-556. doi: 10.3934/jimo.2014.10.543

[11]

Cheng Lu, Zhenbo Wang, Wenxun Xing, Shu-Cherng Fang. Extended canonical duality and conic programming for solving 0-1 quadratic programming problems. Journal of Industrial & Management Optimization, 2010, 6 (4) : 779-793. doi: 10.3934/jimo.2010.6.779

[12]

Piotr Pokora, Tomasz Szemberg. Minkowski bases on algebraic surfaces with rational polyhedral pseudo-effective cone. Electronic Research Announcements, 2014, 21: 126-131. doi: 10.3934/era.2014.21.126

[13]

Yafeng Li, Guo Sun, Yiju Wang. A smoothing Broyden-like method for polyhedral cone constrained eigenvalue problem. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 529-537. doi: 10.3934/naco.2011.1.529

[14]

Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial & Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177

[15]

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

[16]

Liping Tang, Xinmin Yang, Ying Gao. Higher-order symmetric duality for multiobjective programming with cone constraints. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-12. doi: 10.3934/jimo.2019033

[17]

Anish Ghosh, Dubi Kelmer. A quantitative Oppenheim theorem for generic ternary quadratic forms. Journal of Modern Dynamics, 2018, 12: 1-8. doi: 10.3934/jmd.2018001

[18]

Z.Y. Wu, H.W.J. Lee, F.S. Bai, L.S. Zhang. Quadratic smoothing approximation to $l_1$ exact penalty function in global optimization. Journal of Industrial & Management Optimization, 2005, 1 (4) : 533-547. doi: 10.3934/jimo.2005.1.533

[19]

Ye Tian, Cheng Lu. Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1027-1039. doi: 10.3934/jimo.2011.7.1027

[20]

Behrouz Kheirfam. A weighted-path-following method for symmetric cone linear complementarity problems. Numerical Algebra, Control & Optimization, 2014, 4 (2) : 141-150. doi: 10.3934/naco.2014.4.141

2017 Impact Factor: 0.994

Metrics

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

Other articles
by authors

[Back to Top]