American Institute of Mathematical Sciences

Advanced
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

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

[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.  Google Scholar

[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.   Google Scholar

[4]

A. Berman and N. Shaked-Monderer, Completely Positive Matrices,, World Scientific Publishing Co., (2003).  doi: 10.1142/9789812795212.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[7]

S. Boyd and L. Vandenberghe, Convex Optimization,, Cambridge University Press, (2004).   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[12]

P. Dickinson and L. Gijben, On the Computational Complexity of Membership Problems for the Completely Positive Cone and its Dual,, Technical Report, (2011).   Google Scholar

[13]

M. Grant and S. Boyd, CVX: Matlab Software for Disciplined Convex Programming,, version 1.21, (2011).   Google Scholar

[14]

Y. Hu, Efficiency Theory of Multiobjective Programming,, Shanghai Scientific and Technical Publishers, (1994).   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[19]

J. P. Xu and J. Li, Multiple Objective Decision Making Theory and Methods,, Tsinghua University Press, (2005).   Google Scholar

[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.   Google Scholar

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

[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.  Google Scholar

[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.   Google Scholar

[4]

A. Berman and N. Shaked-Monderer, Completely Positive Matrices,, World Scientific Publishing Co., (2003).  doi: 10.1142/9789812795212.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[7]

S. Boyd and L. Vandenberghe, Convex Optimization,, Cambridge University Press, (2004).   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[12]

P. Dickinson and L. Gijben, On the Computational Complexity of Membership Problems for the Completely Positive Cone and its Dual,, Technical Report, (2011).   Google Scholar

[13]

M. Grant and S. Boyd, CVX: Matlab Software for Disciplined Convex Programming,, version 1.21, (2011).   Google Scholar

[14]

Y. Hu, Efficiency Theory of Multiobjective Programming,, Shanghai Scientific and Technical Publishers, (1994).   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[19]

J. P. Xu and J. Li, Multiple Objective Decision Making Theory and Methods,, Tsinghua University Press, (2005).   Google Scholar

[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.   Google Scholar

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

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

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

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

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

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

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

Jiani Wang, Liwei Zhang. Statistical inference of semidefinite programming with multiple parameters. Journal of Industrial & Management Optimization, 2020, 16 (3) : 1527-1538. doi: 10.3934/jimo.2019015
[15]

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

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

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

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

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

Ruotian Gao, Wenxun Xing. Robust sensitivity analysis for linear programming with ellipsoidal perturbation. Journal of Industrial & Management Optimization, 2020, 16 (4) : 2029-2044. doi: 10.3934/jimo.2019041

2018 Impact Factor: 1.025

Tools

Metrics

  • PDF downloads (49)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences