Quadratic optimization over a polyhedral cone

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

Abstract
Related Papers

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

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

[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 and 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 and 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 and 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 and 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 and Management Optimization, 2010, 6 (1) : 259-267. doi: 10.3934/jimo.2010.6.259
[7]	Yi Zhang, Yong Jiang, Liwei Zhang, Jiangzhong Zhang. A perturbation approach for an inverse linear second-order cone programming. Journal of Industrial and Management Optimization, 2013, 9 (1) : 171-189. doi: 10.3934/jimo.2013.9.171
[8]	Shiyun Wang, Yong-Jin Liu, Yong Jiang. A majorized penalty approach to inverse linear second order cone programming problems. Journal of Industrial and Management Optimization, 2014, 10 (3) : 965-976. doi: 10.3934/jimo.2014.10.965
[9]	Jing Zhou, Dejun Chen, Zhenbo Wang, Wenxun Xing. A conic approximation method for the 0-1 quadratic knapsack problem. Journal of Industrial and Management Optimization, 2013, 9 (3) : 531-547. doi: 10.3934/jimo.2013.9.531
[10]	Yanqin Bai, Chuanhao Guo. Doubly nonnegative relaxation method for solving multiple objective quadratic programming problems. Journal of Industrial and 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 and 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 and Optimization, 2011, 1 (3) : 529-537. doi: 10.3934/naco.2011.1.529
[14]	Songqiang Qiu, Zhongwen Chen. An adaptively regularized sequential quadratic programming method for equality constrained optimization. Journal of Industrial and Management Optimization, 2020, 16 (6) : 2675-2701. doi: 10.3934/jimo.2019075
[15]	Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial and Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177
[16]	Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial and Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[17]	Liping Tang, Xinmin Yang, Ying Gao. Higher-order symmetric duality for multiobjective programming with cone constraints. Journal of Industrial and Management Optimization, 2020, 16 (4) : 1873-1884. doi: 10.3934/jimo.2019033
[18]	Arezu Zare, Mohammad Keyanpour, Maziar Salahi. On fractional quadratic optimization problem with two quadratic constraints. Numerical Algebra, Control and Optimization, 2020, 10 (3) : 301-315. doi: 10.3934/naco.2020003
[19]	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
[20]	Behrouz Kheirfam. A weighted-path-following method for symmetric cone linear complementarity problems. Numerical Algebra, Control and Optimization, 2014, 4 (2) : 141-150. doi: 10.3934/naco.2014.4.141

2020 Impact Factor: 1.801

Tools

Metrics

Other articles
by authors

on AIMS
Ye Tian Qingwei Jin Zhibin Deng
on Google Scholar
Ye Tian Qingwei Jin Zhibin Deng

[Back to Top]