Advanced Search
Article Contents
Article Contents

# Quadratic optimization over a polyhedral cone

• 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.
Mathematics Subject Classification: Primary: 90C26, 90C59, 90C22; Secondary: 30E10.

 Citation:

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

## Article Metrics

HTML views() PDF downloads(300) Cited by(0)

## Other Articles By Authors

• on this site
• on Google Scholar

### Catalog

/

DownLoad:  Full-Size Img  PowerPoint