An accelerated method for solving constrained multi-objective optimization

Document Type : Research Article

Authors

1 Department of Mathematics, Faculty of Mathematical Sciences and Computer, Shahid Chamran University of Ahvaz, Ahvaz, Iran

2 Department of Mathematics, University of Hormozgan, Bandarabbas, Iran

Abstract

A novel non-parametric algorithm is introduced for solving constrained multi-objective optimization problems. At each iteration, a convex sub-problem is solved to determine the search direction, while a non-monotone line search technique is used to determine the step size. An adaptive acceleration term, computed from changes in the search directions, is incorporated to scale the step and dynamically enhance convergence performance. The algorithm’s effectiveness relies on a diverse set of initial feasible solutions to accurately approximate the non-dominated boundary. Benchmark tests validate the approach, with Pareto fronts compared to those obtained using the Zoutendijk method. Numerical evaluations demonstrate superior performance in terms of convergence rate and solution quality. The algorithm is also applied to a real-world engineering design problem involving speed reduction, highlighting its computational efficiency and robustness in practical applications.

Keywords

Main Subjects


[1] M. Ahookhosh, K. Amini, S. Bahrami, A class of nonmonotone Armijo-type line search method for unconstrained optimization, Optimization 61 (2012) 387–404.
[2] M. Anitescu, A superlinearly convergent sequential quadratically constrained quadratic programming algorithm for degenerate nonlinear programming, SIAM J. Optim. 12 (2002) 949–978.
[3] M.A.T. Ansary, G. Panda, A modified quasi-Newton method for vector optimization problem, Optimization 64 (2015) 2289–2306.
[4] M.A.T. Ansary, G. Panda, A sequential quadratic programming method for constrained multiobjective optimization problems, J. Appl. Math. Comput. 64 (2020) 379–397.
[5] M.A.T. Ansary, G. Panda, A globally convergent SQCQP method for multiobjective optimization problems, SIAM J. Optim. 31 (2021) 91–113.
[6] S. Azarm, W.C. Li, Optimality and constrained derivatives in two-level design optimization, J. Mech. Des. 112 (1990) 563–568.
[7] H. Basirzadeh, V. Morovati, A. Sayadi, A quick method to calculate the super-efficient point in multi-objective assignment problems, J. Math. Comput. Sci. 10 (2014) 157–162.
[8] A. Beck, M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci. 2 (2009) 183–202.
[9] T. Binh, A multiobjective evolutionary algorithm: The study cases, Technical report, Institute for Automation and Communication, Barleben, Germany, 1999.
[10] G. Cabrera-Guerrero, M. Ehrgott, A.J. Mason, A. Raith, Biobjective optimisation over a set of convex sub-problems, Ann. Oper. Res. 319 (2022) 1507–1532.
[11] E. Carrizosa, J.B.G. Frenk, Dominating sets for convex functions with some applications, J. Optim. Theory Appl. 96 (1998) 281–295.
[12] X. Chen, M.M. Kostreva, Methods of feasible directions: A review, in: X. Yang, A.I. Mees, M. Fisher, L. Jennings (Eds.), Progress in Optimization, Applied Optimization, vol. 39, Springer, Boston, MA, 2000.
[13] Y. Collette, P. Siarry, Multiobjective Optimization: Principles and Case Studies, Springer Science and Business Media, 2013.
[14] K. Deb, A. Pratap, T. Meyarivan, Constrained test problems for multi-objective evolutionary optimization, Lect. Notes Comput. Sci. (1993) 284–298.
[15] K. Deb, Multi-objective genetic algorithms: Problem difficulties and construction of test problems, Evol. Comput. 7 (1999) 205–230.
[16] K. Deb, L. Thiele, M. Laumanns, E. Zitzler, Scalable test problems for evolutionary multiobjective optimization, in: A. Abraham, L. Jain, R. Goldberg (Eds.), Evolutionary Multiobjective Optimization, Advanced Information and Knowledge Processing, Springer, London, 2005.
[17] M. De Santis, G. Eichfelder, J. Niebling, S. Rocktäschel, Solving multiobjective mixed integer convex optimization problems, SIAM J. Optim. 30 (2020) 3122–3145.
[18] G. Eichfelder, Adaptive Scalarization Methods in Multiobjective Optimization, Springer, Berlin, 2008.
[19] G. Eichfelder, An adaptive scalarization method in multiobjective optimization, SIAM J. Optim. 19 (2009) 1694–1718.
[20] G. Eichfelder, O. Stein, L. Warnow, A solver for multiobjective mixed-integer convex and nonconvex optimization, J. Optim. Theory Appl. 203 (2024) 1736–1766.
[21] M. El Moudden, A. El Mouatasim, Accelerated diagonal steepest descent method for unconstrained multiobjective optimization, J. Optim. Theory Appl. 188 (2021) 220–242.
[22] M. Ehrgott, Multicriteria Optimization, Springer, Berlin, 2005.
[23] Z. Fan, W. Li, X. Cai, H. Li, C. Wei, Q. Zhang, K. Deb, E. Goodman, Difficulty adjustable and scalable constrained multiobjective test problem toolkit, Evol. Comput. 28 (2020) 339–378.
[24] J. Fliege, L.M.G. Drummond, B.F. Svaiter, Newton's method for multiobjective optimization, SIAM J. Optim. 20 (2009) 602–626.
[25] J. Fliege, B.F. Svaiter, Steepest descent methods for multicriteria optimization, Math. Methods Oper. Res. 51 (2000) 479–494.
[26] J. Fliege, A.I. Vaz, A method for constrained multiobjective optimization based on SQP techniques, SIAM J. Optim. 26 (2016) 2091–2119.
[27] M. Fukushima, Z.Q. Luo, P. Tseng, A sequential quadratically constrained quadratic programming method for differentiable convex minimization, SIAM J. Optim. 13 (2003) 1098–1119.
[28] J. Golinski, Investigation of a certain stray process applied to the optimum synthesis problems, Computing 6 (1970) 139–160.
[29] L. Grippo, F. Lampariello, S. Lucidi, A nonmonotone line search technique for Newton's method, SIAM J. Numer. Anal. 23 (1986) 707–716.
[30] C.L. Hwang, A.S.M. Masud, Multiple Objective Decision Making Methods and Applications, Lecture Notes in Economics and Mathematical Systems, vol. 164, Springer, Berlin, 1979.
[31] H. Kita, Y. Yabumoto, N. Mori, Y. Nishikawa, Multi-objective optimization by means of the thermodynamical genetic algorithm, in: Parallel Problem Solving from Nature – PPSN IV, Proceedings 4, Springer, Berlin, 1996, pp. 504–512.
[32] T. Maeda, Constraint qualifications in multiobjective optimization problems: Differentiable case, J. Optim. Theory Appl. 80 (1994) 483–500.
[33] S. Menon, J. Karl, K. Wignaraja, Handbook on planning, monitoring and evaluating for development results, UNDP Evaluation Office, New York, 68 (2009) 10.
[34] K.M. Miettinen, Nonlinear Multiobjective Optimization, Kluwer, Boston, 1999.
[35] S.H. Mirzaie, A. Ashrafi, Incorporating non-monotone trust region algorithm with line search method for unconstrained optimization, J. Math. Model. 13 (2025) 219–233.
[36] K. Mita, E.H. Fukuda, N. Yamashita, Nonmonotone line searches for unconstrained multiobjective optimization problems, J. Global Optim. 75 (2019) 63–90.
[37] V. Morovati, L. Pourkarimi, H. Basirzadeh, Barzilai and Borwein's method for multiobjective optimization problems, Numer. Algorithms 72 (2016) 539–604.
[38] V. Morovati, L. Pourkarimi, Extension of Zoutendijk method for solving constrained multiobjective optimization problems, European J. Oper. Res. 273 (2019) 44–57.
[39] S. Mostaghim, J. Branke, H. Schmeck, Multi-objective particle swarm optimization on computer grids, in: Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation, ACM, New York, 2007, pp. 869–875.
[40] Y.E. Nesterov, A method of solving a convex programming problem with convergence rate O(1/k^2), Dokl. Akad. Nauk 269 (1983) 543–547.
[41] J. Nocedal, S.J. Wright, Numerical Optimization, Springer, New Delhi, India, 2006.
[42] V.M. Panin, Some methods of solving convex programming problems, USSR Comput. Math. Math. Phys. 21 (1981) 57–72.