A new quasi-Newton algorithm for constructing the Pareto front of multiobjective optimization problems by implementing warm-start strategies

Articles in Press

Document Type : Original paper

Authors

1 Faculty of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran

2 Faculty of Mathematical Sciences, Shahrood University of Technology, Shahrood, Iran

Abstract

Many numerical procedures for finding efficient solutions of multiobjective optimization problems are variants of Newton method, that utilize the Hessian matrix of second derivatives. Quasi-Newton methods are used for situations in which the calculation of the Hessian matrix or its inverse is difficult or expensive. In the quasi-Newton methods, only first derivatives are utilized to build an approximation of the actual Hessian matrix over a number of iterations. One of the weaknesses of Newton and quasi-Newton methods is choosing the proper starting points. In fact, the starting points should be close enough to the nondominated solution to have at least quadratic convergence. Therefore, in this study, by applying the convex hull of the individual minimums (CHIMs), we present a procedure for selecting an appropriate starting point for the quasi-Newton method with the BFGS (Broyden, Fletcher, Goldfarb and Shanno) approximation. Moreover, a new algorithm for constructing a uniform approximation of the Pareto front is presented, which can produce more than one efficient point located on the Pareto front in each iteration. To comprehensively compare the proposed algorithm with existing algorithms, three indices are considered: purity metric, measures of coverage, and spacing metric. Extensive numerical experiments show the significant advantage of the proposed algorithm. Moreover, the obtained boundary approximation follows an almost uniform distribution.

Keywords

Main Subjects

References

[1] F. Akbari, M. Ghaznavi, and E. Khorram, A revised pascoletti–serafini scalarization method for multiobjective optimization problems, J. Optim. Theory Appl. 178 (2018), no. 2, 560–590. https://doi.org/10.1007/s10957-018-1289-2
[2] F. Akbari, E. Khorram, and M. Ghaznavi, A comparative study of different algorithms and scalarization techniques for constructing the pareto front of multiobjective optimization problems, Optimization (2024), 1–38. https://doi.org/10.1080/02331934.2024.2369605
[3] M.A.T. Ansary, A newton-type proximal gradient method for nonlinear multiobjective optimization problems, Optim. Methods Soft. 38 (2023), no. 3, 570–590. https://doi.org/10.1080/10556788.2022.2157000
[4] S. Bandyopadhyay, S.K. Pal, and B. Aruna, Multiobjective GAs, quantitative indices, and pattern classification, IEEE Trans. Syst. Man. Cybern., Part B 34 (2004), no. 5, 2088–2099. https://doi.org/10.1109/TSMCB.2004.834438
[5] S.P. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004.
[6] Y. Cao, D. Acevedo, Z.K. Nagy, and C.D. Laird, Real-time feasible multi-objective optimization based nonlinear model predictive control of particle size and shape in a batch crystallization process, Control Eng. Pract. 69 (2017), 1–8. https://doi.org/10.1016/j.conengprac.2017.08.008
[7] G.A. Carrizo, P.A. Lotito, and M.C. Maciel, Trust region globalization strategy for the nonconvex unconstrained multiobjective optimization problem, Math. Program. 159 (2016), no. 1, 339–369. https://doi.org/10.1007/s10107-015-0962-6
[8] J. Chen, L. Tang, and X. Yang, A Barzilai-Borwein descent method for multiobjective optimization problems, Eur. J. Oper. Res. 311 (2023), no. 1, 196–209. https://doi.org/10.1016/j.ejor.2023.04.022
[9] G. Cocchi and M. Lapucci, An augmented Lagrangian algorithm for multiobjective optimization, Comput. Optim. Appl. 77 (2020), no. 1, 29–56. https://doi.org/10.1007/s10589-020-00204-z
[10] C.A. Coello Coello, G.B. Lamont, and D.A. VanVeldhuizen, Evolutionary Algorithms for Solving Multi-Objective Problems, Springer, New York, 2007.
[11] I. Das and J.E. Dennis, Normal-boundary intersection: A new method for generating the Pareto surface in nonlinear multicriteria optimization problems, SIAM J. Optim. 8 (1998), no. 3, 631–657. https://doi.org/10.1137/S1052623496307510
[12] K. Deb, Multi-Objective Optimization Using Evolutionary Algorithms, Wiley, Chichester, 2001.
[13] K. Deb, L. Thiele, M. Laumanns, and E. Zitzler, Scalable test problems for evolutionary multiobjective optimization, Tech. report, Kanpur Genetic Algorithms Lab. (KanGAL), Indian Inst. Technol., Kanpur, India, 2001.
[14] P. Dhal and C. Azad, A multi-objective feature selection method using Newton’s law based PSO with GWO, Appl. Soft Comput. 107 (2021), 107394. https://doi.org/10.1016/j.asoc.2021.107394
[15] A. Domahidi, E. Chu, and S. Boyd, ECOS: An SOCP solver for embedded systems, 2013 European Control Conference (ECC), IEEE, 2013, pp. 3071–3076. https://doi.org/10.23919/ECC.2013.6669541
[16] L.M.G. Drummond and A.N. Iusem, A projected gradient method for vector optimization problems, Comput. Optim. Appl. 28 (2004), no. 1, 5–29. https://doi.org/10.1023/B:COAP.0000018877.86161.8b
[17] M. Ehrgott, Multicriteria Optimization, Springer, Berlin, 2005.
[18] J. Fliege, L.M.G. Drummond, and B.F. Svaiter, Newton’s method for multiobjective optimization, SIAM J. Optim. 20 (2009), no. 2, 602–626. https://doi.org/10.1137/08071692X
[19] J. Fliege and B.F. Svaiter, Steepest descent methods for multicriteria optimization, Math. Oper. Res. 51 (2000), no. 3, 479–494. https://doi.org/10.1007/s001860000043
[20] J. Fliege and A.I.F. Vaz, A method for constrained multiobjective optimization based on SQP techniques, SIAM J. Optim. 26 (2016), no. 4, 2091–2119. https://doi.org/10.1137/15M1016424
[21] J. Fliege and R. Werner, Robust multiobjective optimization & applications in portfolio optimization, Eur. J. Oper. Res. 234 (2014), no. 2, 422–433. https://doi.org/10.1016/j.ejor.2013.10.028
[22] N. Ghalavand, E. Khorram, and V. Morovati, An adaptive nonmonotone line search for multiobjective optimization problems, Comput. Oper. Res. 136 (2021), 105506. https://doi.org/10.1016/j.cor.2021.105506
[23] N. Ghalavand, E. Khorram, and V. Morovati, Two adaptive nonmonotone trust-region algorithms for solving multiob-
jective optimization problems, Optimization 73 (2024), no. 9, 2953–2985. https://doi.org/10.1080/02331934.2023.2234920
[24] A. Ghane-Kanafi and E. Khorram, A new scalarization method for finding the efficient frontier in non-convex multibjective problems, Appl. Math. Model. 39 (2015), no. 23-24, 7483–7498. https://doi.org/10.1016/j.apm.2015.03.022.
[25] M. Ghaznavi, F. Akbari, and E. Khorram, Optimality conditions via a unified direction approach for (approximate) efficiency in multiobjective optimization, Optim. Methods Softw. 36 (2021), no. 2-3, 627–652. https://doi.org/10.1080/10556788.2019.1571589
[26] M. Ghaznavi and Z. Azizi, An algorithm for approximating nondominated points of convex multiobjective optimization problems, Bull. Iran. Math. Soc. 43 (2017), no. 5, 1399–1415.
[27] Y. Jin, M. Olhofer, and B. Sendhoff, Dynamic weighted aggregation for evolutionary multi-objective optimization: Why does it work and how?, Proceedings of the Genetic and Evolutionary Computation Conference, 2001, pp. 1042–1049.
[28] V.D. Joshi, M. Sharma, and J. Singh, Solving multi-choice solid stochastic multi objective transportation problem with supply, demand and conveyance capacity involving newton divided difference interpolations, J. Comput. Anal. Appl. 33
(2024), no. 1, 372–395.
[29] I.Y. Kim and O.L. De Weck, Adaptive weighted-sum method for bi-objective optimization: Pareto front generation, Struct. Multidiscip. Optim. 29 (2005), no. 2, 149–158. https://doi.org/10.1007/s00158-004-0465-1
[30] K. Kumar, D. Ghosh, A. Upadhayay, J.C. Yao, and X. Zhao, Quasi-newton methods for multiobjective optimization problems: A systematic review, Appl. Set-Valued Anal. Optim. 5 (2023), no. 2, 291–321. https://doi.org/10.23952/asvao.5.2023.2.12
[31] M. Lapucci and P. Mansueto, Improved front steepest descent for multi-objective optimization, Oper. Res. Lett. 51 (2023), no. 3, 242–247.  https://doi.org/10.1016/j.orl.2023.03.001
[32] M. Lapucci and P. Mansueto, A limited memory Quasi-Newton approach for multi-objective optimization, Comput. Optim. Appl. 85 (2023), no. 1, 33–73. https://doi.org/10.1007/s10589-023-00454-7
[33] L.R. Lucambio Pérez and L.F. Prudente, Nonlinear conjugate gradient methods for vector optimization, SIAM J. Optim. 28 (2018), no. 3, 2690–2720. https://doi.org/10.1137/17M1126588
[34] H. Meng, X. Zhang, and S. Liu, New quality measures for multiobjective programming, Advances in Natural Computation (Berlin, Heidelberg) (L. Wang, K. Chen, and Y.S. Ong, eds.), Springer Berlin Heidelberg, 2005, pp. 1044–1048.
[35] Q. Mercier, F. Poirion, and J.A. Désidéri, A stochastic multiple gradient descent algorithm, Eur. J. Oper. Res. 271 (2018), no. 3, 808–817. https://doi.org/10.1016/j.ejor.2018.05.064
[36] A. Messac and C.A. Mattson, Normal constraint method with guarantee of even representation of complete pareto frontier, AIAA J. 42 (2004), no. 10, 2101–2111.  https://doi.org/10.2514/1.8977
[37] K. Miettinen, Nonlinear Multi-objective Optimization, Kluwer Academic, Dordrecht, 1999.
[38] V. Morovati, H. Basirzadeh, and L. Pourkarimi, Quasi-Newton methods for multiobjective optimization problems, 4OR-Q J. Oper. Res. 16 (2018), no. 3, 261–294. https://doi.org/10.1007/s10288-017-0363-1
[39] V. Morovati and L. Pourkarimi, Extension of Zoutendijk method for solving constrained multiobjective optimization problems, Eur. J. Oper. Res. 273 (2019), no. 1, 44–57. https://doi.org/10.1016/j.ejor.2018.08.018
[40] V. Morovati, L. Pourkarimi, and H. Basirzadeh, Barzilai and Borwein’s method for multiobjective optimization problems, Numer. Algorithms 72 (2016), no. 3, 539–604. https://doi.org/10.1007/s11075-015-0058-7
[41] H. Mukai, Algorithms for multicriterion optimization, IEEE Trans. Autom. 25 (2003), no. 2, 177–186. https://doi.org/10.1109/TAC.1980.1102298
[42] J. Nocedal and S.J. Wright, Numerical Optimization, 2nd ed., Springer Science+Business Media, LLC, New York, 2006.
[43] A. Pascoletti and P. Serafini, Scalarizing vector optimization problems, J. Optim. Theory Appl. 42 (1984), no. 4, 499–524. https://doi.org/10.1007/BF00934564
[44] Ž. Povalej, Quasi-Newton’s method for multiobjective optimization, J. Comput. Appl. Math. 255 (2014), 765–777.
https://doi.org/10.1016/j.cam.2013.06.045
[45] M. Preuss, B. Naujoks, and G. Rudolph, Pareto set and EMOA behavior for simple multimodal multiobjective functions, Parallel Problem Solving from Nature - PPSN IX (Berlin, Heidelberg) (T.P. Runarsson, H.G. Beyer, E. Burke, J.J.
Merelo-Guerv´os, L.D. Whitley, and X. Yao, eds.), Springer Berlin Heidelberg, 2006, pp. 513–522.
[46] S. Qu, M. Goh, and F.T.S. Chan, Quasi-Newton methods for solving multiobjective optimization, Oper. Res. Lett. 39 (2011), no. 5, 397–399. https://doi.org/10.1016/j.orl.2011.07.008
[47] M.M. Rizvi, New optimality conditions for non-linear multiobjective optimization problems and new scalarization techniques for constructing pathological pareto fronts, Ph.D. thesis, University of South Australia, 2013.
[48] S. Sch¨affler, R. Schultz, and K. Weinzierl, Stochastic method for the solution of unconstrained vector optimization problems, J. Optim. Theory Appl. 114 (2002), no. 1, 209–222. https://doi.org/10.1023/A:1015472306888
[49] W. Sun and Y.X. Yuan, Optimization Theory and Methods: Nonlinear Programming, Springer, New York, 2006.
[50] D.A.G. Vieira, R.H.C. Takahashi, and R.R. Saldanha, Multicriteria optimization with a multiobjective golden section line search, Math. Program. 131 (2012), no. 1, 131–161. https://doi.org/10.1007/s10107-010-0347-9
[51] K. Witting, Numerical algorithms for the treatment of parametric multiobjective optimization problem and applications, Ph.D. thesis, Universität Paderborn, Paderborn, 2012.
[52] S. Yang, J. Wang, M. Li, and H. Yue, Research on intellectualized location of coal gangue logistics nodes based on particle swarm optimization and quasi-newton algorithm, Mathematics 10 (2022), no. 1, 162. https://doi.org/10.3390/math10010162
[53] F. YE, B. Lin, Z. Yue, P. Guo, Q. Xiao, and Y. Zhang, Multi-objective meta learning, Advances in Neural Information Processing Systems (M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J.W. Vaughan, eds.), vol. 34, Curran Associates, Inc., 2021, pp. 21338–21351.
[54] E.A. Yildirim and S.J. Wright, Warm-start strategies in interior-point methods for linear programming, SIAM J. Optim. 12 (2002), no. 3, 782–810. https://doi.org/10.1137/S1052623400369235
[55] Y. Zhu, H. Wu, Z. Zhang, C. Zong, and D. Xu, Optimal power flow research of AC–DC hybrid grid with multiple energy routers, Electr. Power Syst. Res. 228 (2024), 110090. https://doi.org/10.1016/j.epsr.2023.110090
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 10 September 2025

Files

Share

How to cite

Statistics