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]

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]

Songqiang Qiu, Zhongwen Chen. An adaptively regularized sequential quadratic programming method for equality constrained optimization. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-14. doi: 10.3934/jimo.2019075
[16]

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

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

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

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

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

2018 Impact Factor: 1.025

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences