A redistributed cutting plane bundle-type algorithm for multiobjective nonsmooth optimization

Jia-Tong Li; Jia-Tong Li

doi:10.3934/math.2022710

AIMS Mathematics

2022, Volume 7, Issue 7: 12827-12841. doi: 10.3934/math.2022710

Previous Article Next Article

Research article

A redistributed cutting plane bundle-type algorithm for multiobjective nonsmooth optimization

Jia-Tong Li ^,

College of Science, Northeast Forestry University, Harbin 150040, China

Received: 08 January 2022 Revised: 16 April 2022 Accepted: 21 April 2022 Published: 05 May 2022
MSC : 49J52, 65K10, 90C26, 90C29

I construct a new cutting-plane model for approximating nonsmooth nonconvex functions in multiobjective optimization and propose a new bundle-type method with the help of an improvement function. The presented bundle method possesses three features. Firstly, the objective and constraint functions are approximated by a new cutting-plane model, which is a local convexification of the corresponding functions, instead of the entire approximation for the functions, as most bundle methods do. Secondly, the subgradients and values of the objective and constraint functions are computed approximately. In other words, approximate calculation is applied to the method, and the proposed algorithm is doubly approximate to some extent. Thirdly, the introduction of the improvement function eliminates the necessity of employing any scalarization, which is the usual method when dealing with multiobjective optimization. Under reasonable conditions satisfactory convergence results are obtained.
- multiobjective nonsmooth optimization,
- cutting-plane model,
- redistributed bundle method,
- approximate calculation,
- subgradient
Citation: Jia-Tong Li. A redistributed cutting plane bundle-type algorithm for multiobjective nonsmooth optimization[J]. AIMS Mathematics, 2022, 7(7): 12827-12841. doi: 10.3934/math.2022710

Related Papers:

Abstract

I construct a new cutting-plane model for approximating nonsmooth nonconvex functions in multiobjective optimization and propose a new bundle-type method with the help of an improvement function. The presented bundle method possesses three features. Firstly, the objective and constraint functions are approximated by a new cutting-plane model, which is a local convexification of the corresponding functions, instead of the entire approximation for the functions, as most bundle methods do. Secondly, the subgradients and values of the objective and constraint functions are computed approximately. In other words, approximate calculation is applied to the method, and the proposed algorithm is doubly approximate to some extent. Thirdly, the introduction of the improvement function eliminates the necessity of employing any scalarization, which is the usual method when dealing with multiobjective optimization. Under reasonable conditions satisfactory convergence results are obtained.

References

[1]	J. Outrata, M. Kocvara, J. Zowe, Nonsmooth approach to optimization problems with equilibrium constraints: Theory, applications and numerical results, Springer Science & Business Media, 1998.
[2]	J. J. Moreau, P. D. Panagiotopoulos, G. Strang (Eds.), Topics in nonsmooth mechanics, Basel: Birkhauser Verlag, 1988.
[3]	K. M. Miettinen, Nonlinear multiobjective optimization, Springer Science & Business Media, 1999.
[4]	K. Miettinen, M. M. Makela, Interactive bundle-based method for nondifferentiable multiobjective optimization: NIMBUS, Optimization, 34 (2007), 231–246. https://doi.org/10.1080/02331939508844109 doi: 10.1080/02331939508844109
[5]	H. Mukai, Algorithms for multicriterion optimization, IEEE transactions on automatic control, 25 (1980), 177–186. https://doi.org/10.1109/TAC.1980.1102298 doi: 10.1109/TAC.1980.1102298
[6]	R. E. Steuer, Multiple criteria optimization: Theory, computation and applications, 1986.
[7]	K. H. Han, J. H. Kim, Genetic quantum algorithm and its application to combinatorial optimization problem, In: Proceedings of the 2000 congress on evolutionary computation. CEC00 (Cat. No.00TH8512), 2002. https://doi.org/10.1109/CEC.2000.870809
[8]	L. Banchi, J. Pereira, S. Lloyd, S. Pirandola, Convex optimization of programmable quantum computers, NPJ Quantum Inf., 6 (2020), 42. https://doi.org/10.1038/s41534-020-0268-2 doi: 10.1038/s41534-020-0268-2
[9]	C. Lemaréchal, Lagrangian relaxation, In: Computational combinatorial optimization, Berlin: Springer, 2001. https://doi.org/10.1007/3-540-45586-8_4
[10]	C. Sagastizábal, Divide to conquer: Decomposition methods for energy optimization, Math. Program., 134 (2012), 187–222. https://doi.org/10.1007/s10107-012-0570-7 doi: 10.1007/s10107-012-0570-7
[11]	C. Sagastizábal, M. Solodov, An infeasible bundle method for nonsmooth convex constrained optimization without a penalty function or a filter, SIAM J. Optim., 16 (2005), 146–169. https://doi.org/10.1137/040603875 doi: 10.1137/040603875
[12]	K. C. Kiwiel, A linearization algorithm for nonsmooth minimization, Math. Oper. Res., 10 (1985), 185–194. https://doi.org/10.1287/moor.10.2.185 doi: 10.1287/moor.10.2.185
[13]	M. M. Makela, P. Neittaanmaki, Nonsmooth optimization: Analysis and algorithms with applications to optimal control, World Scientific, 1992.
[14]	K. C. Kiwiel, Restricted step and Levenberg-Marquardt techniques in proximal bundle methods for nonconvex nondifferentiable optimization, SIAM J. Optim., 6 (1996), 227–249. https://doi.org/10.1137/0806013 doi: 10.1137/0806013
[15]	L. Luksan, J. Vlcek, A bundle Newton method for nonsmooth unconstrained minimization, Math. Program., 83 (1998), 373–391. https://doi.org/10.1007/BF02680566 doi: 10.1007/BF02680566
[16]	J. Vlcek, L. Luksan, Globally convergent variable metric method for nonconvex nondifferentiable unconstrained minimization, J. Optimiz. Theory App., 111 (2001), 407–430. https://doi.org/10.1023/A:1011990503369 doi: 10.1023/A:1011990503369
[17]	A. Fudili, M. Gaudioso, G. Giallombardo, Minimizing nonconvex nonsmooth functions via cutting plane and proximity control, SIAM J. Optim., 14 (2003), 743–756. https://doi.org/10.1137/S1052623402411459 doi: 10.1137/S1052623402411459
[18]	A. Fudili, M. Gaudioso, G. Giallombardo, A DC piecewise affine model and a bundling technique in nonconvex nonsmooth minimization, Optim. Method. Softw., 19 (2004), 89–102. https://doi.org/10.1080/10556780410001648112 doi: 10.1080/10556780410001648112
[19]	N. Haarala, K. Miettinen, M. M. Makela, Globally convergent limited memory bundle method for large-scale nonsmooth optimization, Math. Program., 109 (2007), 181–205. https://doi.org/10.1007/s10107-006-0728-2 doi: 10.1007/s10107-006-0728-2
[20]	W. Hare, C. Lemaréchal, A redistributed proximal bundle method for nonconvex optimization, SIAM J. Optim., 20 (2010), 2442–2473. https://doi.org/10.1137/090754595 doi: 10.1137/090754595
[21]	W. Hare, C. Lemaréchal, M. Solodov, A proximal bundle method for nonsmooth nonconvex functions with inexact information, Comput. Optim. Appl., 63 (2016), 1–28. https://doi.org/10.1007/s10589-015-9762-4 doi: 10.1007/s10589-015-9762-4
[22]	K. C. Kiwiel, An algorithm for nonsmooth convex minimization with errors, Math. Comput., 45 (1985), 173–180. https://doi.org/10.1090/S0025-5718-1985-0790650-5 doi: 10.1090/S0025-5718-1985-0790650-5
[23]	M. Hintermuller, A proximal bundle method based on approximate subgradients, Comput. Optim. Appl., 20 (2001), 245–266. https://doi.org/10.1023/A:1011259017643 doi: 10.1023/A:1011259017643
[24]	W. de. Oliveira, C. Sagastizábal, C. Lemaréchal, Convex proximal bundle methods in depth: A unified analysis for inexact oracles, Math. Program., 148 (2014), 241–27. https://doi.org/10.1007/s10107-014-0809-6 doi: 10.1007/s10107-014-0809-6
[25]	R. Correa, C. Lemaréchal, Convergence of some algorithms for convex minimization, Math. Program., 62 (1993), 261–275. https://doi.org/10.1007/BF01585170 doi: 10.1007/BF01585170
[26]	J. Shen, Z. Q. Xia, L. P. Pang, A proximal bundle method with inexact data for convex nondifferentiable minimization, Nonlinear Anal. Theor., 66 (2007), 2016–2027. https://doi.org/10.1016/j.na.2006.02.039 doi: 10.1016/j.na.2006.02.039
[27]	J. Shen, X. Q. Liu, F. F. Guo, S. X. Wang, An approximate redistributed proximal bundle method with inexact data for minimizing nonsmooth nonconvex functions, Math. Probl. Eng., 2015 (2015), 215310. https://doi.org/10.1155/2015/215310 doi: 10.1155/2015/215310
[28]	W. Hare, C. Lemaréchal, M. Solodov, A proximal bundle method for nonsmooth nonconvex functions with inexact information, Comput. Optim. Appl., 63 (2016), 1–28. https://doi.org/10.1007/s10589-015-9762-4 doi: 10.1007/s10589-015-9762-4
[29]	J. B. Jian, C. M. Tang, L. Shi, A feasible point method with bundle modification for nonsmooth convex constrained optimization, Acta Math. Appl. Sin. Engl. Ser., 34 (2018), 254–273. https://doi.org/10.1007/s10255-018-0755-9 doi: 10.1007/s10255-018-0755-9
[30]	S. Schaible, Quasiconvex, pseudoconvex, and strictly pseudoconvex quadratic functions, J. Optim. Theory Appl., 35 (1981), 303–338. https://doi.org/10.1007/BF00934906 doi: 10.1007/BF00934906
[31]	A. Daniilidis, P. Georgiev, Approximate convexity and submonotonicity. J. Math. Anal. Appl., 291 (2004), 292–301. https://doi.org/10.1016/j.jmaa.2003.11.004 doi: 10.1016/j.jmaa.2003.11.004
[32]	J. E. Springarn, Submonotone subdifferentials of Lipschitz functions, Trans. Amer. Math. Soc., 264 (1981), 77–89. https://doi.org/10.1090/S0002-9947-1981-0597868-8 doi: 10.1090/S0002-9947-1981-0597868-8
[33]	D. Noll, O. Prot, A. Rondepierre, A proximity control algorithm to minimize nonsmooth and nonconvex functions, Pac. J. Optim., 4 (2008), 569–602. https://hal.archives-ouvertes.fr/hal-00464695
[34]	M. M. Makela, N. Karmitsa, O. Wilppu, Proximal bundle method for nonsmooth and nonconvex multiobjective optimization, In: International conference for mathematical modeling and optimization in mechanics (MMOM 2014).
[35]	D. A. G. Vieira, A. C. Lisboa, A cutting-plane method to nonsmooth multiobjective optimization problems, Eur. J. Oper. Res., 275 (2019), 822–829. https://doi.org/10.1016/j.ejor.2018.12.047 doi: 10.1016/j.ejor.2018.12.047
[36]	A. Kabgani, M. Soleimani-damaneh, Semi-quasidifferentiability in nonsmooth nonconvex multiobjective optimization, Eur. J. Oper. Res., 299 (2021), 35–45. https://doi.org/10.1016/j.ejor.2021.10.063 doi: 10.1016/j.ejor.2021.10.063

Reader Comments

Your name:*

Email:*
© 2022 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)