Quadratic optimization over a polyhedral cone

Ye Tian; Qingwei Jin; Zhibin Deng

doi:10.3934/jimo.2016.12.269

Article Contents

2016, Volume 12, Issue 1: 269-283. Doi: 10.3934/jimo.2016.12.269

This issue Previous Article A novel discriminant minimum class locality preserving canonical correlation analysis and its applications Next Article Subgradient-based neural network for nonconvex optimization problems in support vector machines with indefinite kernels

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

Received: July 31, 2014

Revised: December 31, 2014

Published: December 2015

Abstract Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 90C26, 90C59, 90C22; Secondary: 30E10.

Citation:

Related Papers

Cited by

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-242.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-484.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, Philadelphis, 2001.doi: 10.1137/1.9780898718829.
[4]	S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, Cambridge, 2004.doi: 10.1017/CBO9780511804441.
[5]	S. Burer, On the copositive representation of binary and continuous nonconvex quadratic programs, Mathematical Programming, 120 (2009), 479-495.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-28.doi: 10.1016/j.ejor.2013.02.031.
[7]	M. Grant and S. Boyd, CVX: matlab Software for Disciplined Programming, version 1.2, 2010. http://cvxr.com/cvx
[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-963.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-392.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, Berlin, 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-157.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-134.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-1490.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-113.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), Art. ID 671402, 6 pp.doi: 10.1155/2013/671402.
[16]	R. Rockafellar, Convex Analysis, Princeton University Press, Princeton, NJ, 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-332.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-653.doi: 10.1080/10556789908805766.
[20]	J. Sturm and S. Zhang, On cones of nonnegative quadratic functions, Mathematics of Operations Research, 28 (2003), 246-267.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-107.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-721.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-92.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-267.doi: 10.1137/S105262340139001X.