Doubly nonnegative relaxation method for solving multiple objective quadratic programming problems

Yanqin Bai; Chuanhao Guo

doi:10.3934/jimo.2014.10.543

Article Contents

2014, Volume 10, Issue 2: 543-556. Doi: 10.3934/jimo.2014.10.543

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

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

Received: September 30, 2012

Revised: July 31, 2013

Published: March 2014

Abstract Related Papers Cited by

Abstract

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:

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

Citation:

Related Papers

Cited by

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.