Doubly nonnegative relaxation method for solving multiple objective quadratic programming problems

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

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

Doubly nonnegative relaxation method for solving multiple objective quadratic programming problems

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 & 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. 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. 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.
[4]	A. Berman and N. Shaked-Monderer, Completely Positive Matrices,, World Scientific Publishing Co., (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. doi: 10.3934/jimo.2011.7.789.
[6]	I. M. Bomze, Copositive optimization-recent developments and applications,, European J. Oper. Res., 216 (2012), 509. doi: 10.1016/j.ejor.2011.04.026.
[7]	S. Boyd and L. Vandenberghe, Convex Optimization,, Cambridge University Press, (2004).
[8]	S. Burer, On the copositive representation of binary and continuous nonconvex quadratic programs,, Math. Program., 210 (2009), 479. 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. 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.
[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. 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, (2011).
[13]	M. Grant and S. Boyd, CVX: Matlab Software for Disciplined Convex Programming,, version 1.21, (2011).
[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. 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. 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. 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. 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.

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. 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. 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.
[4]	A. Berman and N. Shaked-Monderer, Completely Positive Matrices,, World Scientific Publishing Co., (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. doi: 10.3934/jimo.2011.7.789.
[6]	I. M. Bomze, Copositive optimization-recent developments and applications,, European J. Oper. Res., 216 (2012), 509. doi: 10.1016/j.ejor.2011.04.026.
[7]	S. Boyd and L. Vandenberghe, Convex Optimization,, Cambridge University Press, (2004).
[8]	S. Burer, On the copositive representation of binary and continuous nonconvex quadratic programs,, Math. Program., 210 (2009), 479. 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. 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.
[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. 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, (2011).
[13]	M. Grant and S. Boyd, CVX: Matlab Software for Disciplined Convex Programming,, version 1.21, (2011).
[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. 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. 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. 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. 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.

[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 & 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 & 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 & 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 & Management Optimization, 2014, 10 (2) : 397-412. doi: 10.3934/jimo.2014.10.397
[5]	Charles Fefferman. Interpolation by linear programming I. Discrete & Continuous Dynamical Systems - A, 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 & Management Optimization, 2013, 9 (3) : 703-721. doi: 10.3934/jimo.2013.9.703
[7]	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
[8]	Yue Zheng, Zhongping Wan, Shihui Jia, Guangmin Wang. A new method for strong-weak linear bilevel programming problem. Journal of Industrial & Management Optimization, 2015, 11 (2) : 529-547. doi: 10.3934/jimo.2015.11.529
[9]	Yanqun Liu. An exterior point linear programming method based on inclusive normal cones. Journal of Industrial & Management Optimization, 2010, 6 (4) : 825-846. doi: 10.3934/jimo.2010.6.825
[10]	Ram U. Verma. General parametric sufficient optimality conditions for multiple objective fractional subset programming relating to generalized $(\rho,\eta,A)$ -invexity. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 333-339. doi: 10.3934/naco.2011.1.333
[11]	Tien-Fu Liang, Hung-Wen Cheng. Multi-objective aggregate production planning decisions using two-phase fuzzy goal programming method. Journal of Industrial & Management Optimization, 2011, 7 (2) : 365-383. doi: 10.3934/jimo.2011.7.365
[12]	Sigurdur Hafstein, Skuli Gudmundsson, Peter Giesl, Enrico Scalas. Lyapunov function computation for autonomous linear stochastic differential equations using sum-of-squares programming. Discrete & Continuous Dynamical Systems - B, 2018, 23 (2) : 939-956. doi: 10.3934/dcdsb.2018049
[13]	Jiani Wang, Liwei Zhang. Statistical inference of semidefinite programming with multiple parameters. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-12. doi: 10.3934/jimo.2019015
[14]	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 & Management Optimization, 2006, 2 (4) : 373-385. doi: 10.3934/jimo.2006.2.373
[15]	Zhiqing Meng, Qiying Hu, Chuangyin Dang. A penalty function algorithm with objective parameters for nonlinear mathematical programming. Journal of Industrial & Management Optimization, 2009, 5 (3) : 585-601. doi: 10.3934/jimo.2009.5.585
[16]	Yanqun Liu. Duality in linear programming: From trichotomy to quadrichotomy. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1003-1011. doi: 10.3934/jimo.2011.7.1003
[17]	Ruotian Gao, Wenxun Xing. Robust sensitivity analysis for linear programming with ellipsoidal perturbation. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-16. doi: 10.3934/jimo.2019041
[18]	Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353
[19]	James Anderson, Antonis Papachristodoulou. Advances in computational Lyapunov analysis using sum-of-squares programming. Discrete & Continuous Dynamical Systems - B, 2015, 20 (8) : 2361-2381. doi: 10.3934/dcdsb.2015.20.2361
[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

2017 Impact Factor: 0.994

American Institute of Mathematical Sciences