Doubly nonnegative relaxation method for solving multiple objective quadratic programming problems

Previous Article
Manifold relaxations for integer programming
JIMO Home
This Issue
Next Article
Inexact restoration and adaptive mesh refinement for optimal control

April 2014, 10(2): 543-556. doi: 10.3934/jimo.2014.10.543

Doubly nonnegative relaxation method for solving multiple objective quadratic programming problems

Yanqin Bai ^1, and Chuanhao Guo ^1,

1.	Department of Mathematics, Shanghai University, Shanghai 200444, China, China

Received October 2012 Revised August 2013 Published October 2013

Abstract
Related Papers

Multicriterion optimization and Pareto optimality are fundamental tools in economics. In this paper we propose a new relaxation method for solving multiple objective quadratic programming problems. Exploiting the technique of the linear weighted sum method, we reformulate the original multiple objective quadratic programming problems into a single objective one. Since such single objective quadratic programming problem is still nonconvex and NP-hard in general. By using the techniques of lifting and doubly nonnegative relaxation, respectively, this single objective quadratic programming problem is transformed to a computable convex doubly nonnegative programming problem. The optimal solutions of this computable convex problem are (weakly) Pareto optimal solutions of the original problem under some mild conditions. Moreover, the proposed method is tested with two examples and a practical portfolio selection example. The test examples are solved by CVX package which is a solver for convex optimization. The numerical results show that the proposed method is effective and promising.

Keywords: linear weighted sum method, Multiple objective programming, quadratic programming, completely positive programming., copositive programming.

Mathematics Subject Classification: Primary: 90C29, 90C26; Secondary: 49M2.

Citation: 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

References:

[1]	E. E. Ammar, On solutions of fuzzy random multiobjective quadratic programming with applications in portfolio problem, Inform. Sci., 178 (2008), 468-484. doi: 10.1016/j.ins.2007.03.029.
[2]	E. E. Ammar, On fuzzy random multiobjective quadratic programming, European J. Oper. Res., 193 (2009), 329-341. doi: 10.1016/j.ejor.2007.11.031.
[3]	Y. Q. Bai, and C. H. Guo and L. M. Sun, A new algorithm for solving nonconvex quadratic programming over an ice cream cone, Pac. J. Optim., 8 (2012), 651-665.
[4]	A. Berman and N. Shaked-Monderer, Completely Positive Matrices, World Scientific Publishing Co., Inc., River Edge, NJ, 2003. doi: 10.1142/9789812795212.
[5]	H. Bonnel and N. S. Pham, Nonsmooth optimization over the (weakly or properly) Pareto set of a linear-quadratic multi-objective control problem: Explicit optimality conditions, J. Ind. Manag. Optim., 7 (2011), 789-809. doi: 10.3934/jimo.2011.7.789.
[6]	I. M. Bomze, Copositive optimization-recent developments and applications, European J. Oper. Res., 216 (2012), 509-520. doi: 10.1016/j.ejor.2011.04.026.
[7]	S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, Cambridge, 2004.
[8]	S. Burer, On the copositive representation of binary and continuous nonconvex quadratic programs, Math. Program., 210 (2009), 479-495. doi: 10.1007/s10107-008-0223-z.
[9]	S. Burer, Optimizing a polyhedral-semidefinite relaxation of completely positive programs, Math. Program. Comput., 2 (2010), 1-19. doi: 10.1007/s12532-010-0010-8.
[10]	O. Dandekar, W. Plishker, S. Bhattacharyya and R. Shekhar, Multi-objective optimization for reconfigurable implementation of medical image registration, International Journal of Reconfigurable Computing, 2008 (2009), 1-17.
[11]	P. H. Diananda, On non-negative forms in real variables some or all of which are non-negative, Proc. Cambridge Philos. Soc., 58 (1962), 17-25. doi: 10.1017/S0305004100036185.
[12]	P. Dickinson and L. Gijben, On the Computational Complexity of Membership Problems for the Completely Positive Cone and its Dual, Technical Report, Johann Bernoulli Institute for Mathematics and Computer Science, University of Groningen, The Netherlands, 2011.
[13]	M. Grant and S. Boyd, CVX: Matlab Software for Disciplined Convex Programming, version 1.21, April, 2011. Available from: http://cvxr.com/cvx.
[14]	Y. Hu, Efficiency Theory of Multiobjective Programming, Shanghai Scientific and Technical Publishers, 1994.
[15]	P. Korhonen and G. Y. Yu, A reference direction approach to multiple objective quadratic-linear programming, European Journal of Operational Research, 102 (1997), 601-610. doi: 10.1016/S0377-2217(96)00245-7.
[16]	C. Lu, S.-C. Fang, Q. W. Jin, Qingwei, Z. B. Wang and W. X. Xing, KKT solution and conic relaxation for solving quadratically constrained quadratic programming problems, SIAM J. Optim., 21 (2011), 1475-1490. doi: 10.1137/100793955.
[17]	R. T. Marler and J. S. Arora, The weighted sum method for multi-objective optimization: New insights, Struct. Multidiscip. Optim., 41 (2010), 853-862. doi: 10.1007/s00158-009-0460-7.
[18]	J. P. Xu and J. Li, A class of stochastic optimization problems with one quadratic & several linear objective functions and extended portfolio selection model, J. Comput. Appl. Math., 146 (2002), 99-113. doi: 10.1016/S0377-0427(02)00421-1.
[19]	J. P. Xu and J. Li, Multiple Objective Decision Making Theory and Methods, Tsinghua University Press, 2005.
[20]	B. R. Ye and L. H. Yu, Generating noninferior set of a multi-objective quadratic programming and application, Water Resources and Power, 9 (1991), 102-110.

show all references

References:

[1]	E. E. Ammar, On solutions of fuzzy random multiobjective quadratic programming with applications in portfolio problem, Inform. Sci., 178 (2008), 468-484. doi: 10.1016/j.ins.2007.03.029.
[2]	E. E. Ammar, On fuzzy random multiobjective quadratic programming, European J. Oper. Res., 193 (2009), 329-341. doi: 10.1016/j.ejor.2007.11.031.
[3]	Y. Q. Bai, and C. H. Guo and L. M. Sun, A new algorithm for solving nonconvex quadratic programming over an ice cream cone, Pac. J. Optim., 8 (2012), 651-665.
[4]	A. Berman and N. Shaked-Monderer, Completely Positive Matrices, World Scientific Publishing Co., Inc., River Edge, NJ, 2003. doi: 10.1142/9789812795212.
[5]	H. Bonnel and N. S. Pham, Nonsmooth optimization over the (weakly or properly) Pareto set of a linear-quadratic multi-objective control problem: Explicit optimality conditions, J. Ind. Manag. Optim., 7 (2011), 789-809. doi: 10.3934/jimo.2011.7.789.
[6]	I. M. Bomze, Copositive optimization-recent developments and applications, European J. Oper. Res., 216 (2012), 509-520. doi: 10.1016/j.ejor.2011.04.026.
[7]	S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, Cambridge, 2004.
[8]	S. Burer, On the copositive representation of binary and continuous nonconvex quadratic programs, Math. Program., 210 (2009), 479-495. doi: 10.1007/s10107-008-0223-z.
[9]	S. Burer, Optimizing a polyhedral-semidefinite relaxation of completely positive programs, Math. Program. Comput., 2 (2010), 1-19. doi: 10.1007/s12532-010-0010-8.
[10]	O. Dandekar, W. Plishker, S. Bhattacharyya and R. Shekhar, Multi-objective optimization for reconfigurable implementation of medical image registration, International Journal of Reconfigurable Computing, 2008 (2009), 1-17.
[11]	P. H. Diananda, On non-negative forms in real variables some or all of which are non-negative, Proc. Cambridge Philos. Soc., 58 (1962), 17-25. doi: 10.1017/S0305004100036185.
[12]	P. Dickinson and L. Gijben, On the Computational Complexity of Membership Problems for the Completely Positive Cone and its Dual, Technical Report, Johann Bernoulli Institute for Mathematics and Computer Science, University of Groningen, The Netherlands, 2011.
[13]	M. Grant and S. Boyd, CVX: Matlab Software for Disciplined Convex Programming, version 1.21, April, 2011. Available from: http://cvxr.com/cvx.
[14]	Y. Hu, Efficiency Theory of Multiobjective Programming, Shanghai Scientific and Technical Publishers, 1994.
[15]	P. Korhonen and G. Y. Yu, A reference direction approach to multiple objective quadratic-linear programming, European Journal of Operational Research, 102 (1997), 601-610. doi: 10.1016/S0377-2217(96)00245-7.
[16]	C. Lu, S.-C. Fang, Q. W. Jin, Qingwei, Z. B. Wang and W. X. Xing, KKT solution and conic relaxation for solving quadratically constrained quadratic programming problems, SIAM J. Optim., 21 (2011), 1475-1490. doi: 10.1137/100793955.
[17]	R. T. Marler and J. S. Arora, The weighted sum method for multi-objective optimization: New insights, Struct. Multidiscip. Optim., 41 (2010), 853-862. doi: 10.1007/s00158-009-0460-7.
[18]	J. P. Xu and J. Li, A class of stochastic optimization problems with one quadratic & several linear objective functions and extended portfolio selection model, J. Comput. Appl. Math., 146 (2002), 99-113. doi: 10.1016/S0377-0427(02)00421-1.
[19]	J. P. Xu and J. Li, Multiple Objective Decision Making Theory and Methods, Tsinghua University Press, 2005.
[20]	B. R. Ye and L. H. Yu, Generating noninferior set of a multi-objective quadratic programming and application, Water Resources and Power, 9 (1991), 102-110.

[1]	Zhi-Bin Deng, Ye Tian, Cheng Lu, Wen-Xun Xing. Globally solving quadratic programs with convex objective and complementarity constraints via completely positive programming. Journal of Industrial and Management Optimization, 2018, 14 (2) : 625-636. doi: 10.3934/jimo.2017064
[2]	Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 193-206. doi: 10.3934/naco.2012.2.193
[3]	Ye Tian, Shucherng Fang, Zhibin Deng, Qingwei Jin. Cardinality constrained portfolio selection problem: A completely positive programming approach. Journal of Industrial and Management Optimization, 2016, 12 (3) : 1041-1056. doi: 10.3934/jimo.2016.12.1041
[4]	Yanqun Liu, Ming-Fang Ding. A ladder method for linear semi-infinite programming. Journal of Industrial and Management Optimization, 2014, 10 (2) : 397-412. doi: 10.3934/jimo.2014.10.397
[5]	Charles Fefferman. Interpolation by linear programming I. Discrete and Continuous Dynamical Systems, 2011, 30 (2) : 477-492. doi: 10.3934/dcds.2011.30.477
[6]	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
[7]	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
[8]	Tone-Yau Huang, Tamaki Tanaka. Optimality and duality for complex multi-objective programming. Numerical Algebra, Control and Optimization, 2022, 12 (1) : 121-134. doi: 10.3934/naco.2021055
[9]	Jean Creignou, Hervé Diet. Linear programming bounds for unitary codes. Advances in Mathematics of Communications, 2010, 4 (3) : 323-344. doi: 10.3934/amc.2010.4.323
[10]	Yue Zheng, Zhongping Wan, Shihui Jia, Guangmin Wang. A new method for strong-weak linear bilevel programming problem. Journal of Industrial and Management Optimization, 2015, 11 (2) : 529-547. doi: 10.3934/jimo.2015.11.529
[11]	Yanqun Liu. An exterior point linear programming method based on inclusive normal cones. Journal of Industrial and Management Optimization, 2010, 6 (4) : 825-846. doi: 10.3934/jimo.2010.6.825
[12]	Ram U. Verma. General parametric sufficient optimality conditions for multiple objective fractional subset programming relating to generalized $(\rho,\eta,A)$ -invexity. Numerical Algebra, Control and Optimization, 2011, 1 (3) : 333-339. doi: 10.3934/naco.2011.1.333
[13]	Jiani Wang, Liwei Zhang. Statistical inference of semidefinite programming with multiple parameters. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1527-1538. doi: 10.3934/jimo.2019015
[14]	Sigurdur Hafstein, Skuli Gudmundsson, Peter Giesl, Enrico Scalas. Lyapunov function computation for autonomous linear stochastic differential equations using sum-of-squares programming. Discrete and Continuous Dynamical Systems - B, 2018, 23 (2) : 939-956. doi: 10.3934/dcdsb.2018049
[15]	Tien-Fu Liang, Hung-Wen Cheng. Multi-objective aggregate production planning decisions using two-phase fuzzy goal programming method. Journal of Industrial and Management Optimization, 2011, 7 (2) : 365-383. doi: 10.3934/jimo.2011.7.365
[16]	Bao Qing Hu, Song Wang. A novel approach in uncertain programming part II: a class of constrained nonlinear programming problems with interval objective functions. Journal of Industrial and Management Optimization, 2006, 2 (4) : 373-385. doi: 10.3934/jimo.2006.2.373
[17]	Ali Tebbi, Terence Chan, Chi Wan Sung. Linear programming bounds for distributed storage codes. Advances in Mathematics of Communications, 2020, 14 (2) : 333-357. doi: 10.3934/amc.2020024
[18]	Yanqun Liu. Duality in linear programming: From trichotomy to quadrichotomy. Journal of Industrial and Management Optimization, 2011, 7 (4) : 1003-1011. doi: 10.3934/jimo.2011.7.1003
[19]	Ruotian Gao, Wenxun Xing. Robust sensitivity analysis for linear programming with ellipsoidal perturbation. Journal of Industrial and Management Optimization, 2020, 16 (4) : 2029-2044. doi: 10.3934/jimo.2019041
[20]	Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353

2021 Impact Factor: 1.411

Tools

Metrics

Other articles
by authors

on AIMS
Yanqin Bai Chuanhao Guo
on Google Scholar
Yanqin Bai Chuanhao Guo

[Back to Top]