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

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

Pablo Neme, Jorge Oviedo. A note on the lattice structure for matching markets via linear programming. Journal of Dynamics & Games, 2020  doi: 10.3934/jdg.2021001

[2]

Ke Su, Yumeng Lin, Chun Xu. A new adaptive method to nonlinear semi-infinite programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021012

[3]

Tengfei Yan, Qunying Liu, Bowen Dou, Qing Li, Bowen Li. An adaptive dynamic programming method for torque ripple minimization of PMSM. Journal of Industrial & Management Optimization, 2021, 17 (2) : 827-839. doi: 10.3934/jimo.2019136

[4]

Ali Mahmoodirad, Harish Garg, Sadegh Niroomand. Solving fuzzy linear fractional set covering problem by a goal programming based solution approach. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020162

[5]

Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020054

[6]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102

[7]

Mahdi Karimi, Seyed Jafar Sadjadi. Optimization of a Multi-Item Inventory model for deteriorating items with capacity constraint using dynamic programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021013

[8]

Haoyu Li, Zhi-Qiang Wang. Multiple positive solutions for coupled Schrödinger equations with perturbations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020294

[9]

Alain Bensoussan, Xinwei Feng, Jianhui Huang. Linear-quadratic-Gaussian mean-field-game with partial observation and common noise. Mathematical Control & Related Fields, 2021, 11 (1) : 23-46. doi: 10.3934/mcrf.2020025

[10]

Lars Grüne, Roberto Guglielmi. On the relation between turnpike properties and dissipativity for continuous time linear quadratic optimal control problems. Mathematical Control & Related Fields, 2021, 11 (1) : 169-188. doi: 10.3934/mcrf.2020032

[11]

Jingrui Sun, Hanxiao Wang. Mean-field stochastic linear-quadratic optimal control problems: Weak closed-loop solvability. Mathematical Control & Related Fields, 2021, 11 (1) : 47-71. doi: 10.3934/mcrf.2020026

[12]

Qiang Fu, Xin Guo, Sun Young Jeon, Eric N. Reither, Emma Zang, Kenneth C. Land. The uses and abuses of an age-period-cohort method: On the linear algebra and statistical properties of intrinsic and related estimators. Mathematical Foundations of Computing, 2020  doi: 10.3934/mfc.2021001

[13]

Lin Jiang, Song Wang. Robust multi-period and multi-objective portfolio selection. Journal of Industrial & Management Optimization, 2021, 17 (2) : 695-709. doi: 10.3934/jimo.2019130

[14]

Peng Luo. Comparison theorem for diagonally quadratic BSDEs. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020374

[15]

Xiyou Cheng, Zhitao Zhang. Structure of positive solutions to a class of Schrödinger systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020461

[16]

Kung-Ching Chang, Xuefeng Wang, Xie Wu. On the spectral theory of positive operators and PDE applications. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3171-3200. doi: 10.3934/dcds.2020054

[17]

Paul E. Anderson, Timothy P. Chartier, Amy N. Langville, Kathryn E. Pedings-Behling. The rankability of weighted data from pairwise comparisons. Foundations of Data Science, 2021  doi: 10.3934/fods.2021002

[18]

Huu-Quang Nguyen, Ya-Chi Chu, Ruey-Lin Sheu. On the convexity for the range set of two quadratic functions. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020169

[19]

Wei-Chieh Chen, Bogdan Kazmierczak. Traveling waves in quadratic autocatalytic systems with complexing agent. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020364

[20]

Elvio Accinelli, Humberto Muñiz. A dynamic for production economies with multiple equilibria. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021002

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (67)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]