We consider a variant of the successive concessions method for solving a multi-objective optimization problem. The proposed variant differs from the well-known method by the general way of specifying concessions. In the proposed variant, the concessions are defined in such a way that the solutions of the particular problems of two adjacent stages can differ from each other both in the optimal value of the objective functions and in the distance by values not exceeding specified ones. We propose the implementation of the method for the case where all particular problems are convex programming problems. The implementation is based on the developed algorithm of conditional minimization of non-differentiable functions. This algorithm belongs to the class of cutting methods and is characterized by the fact that it uses approximation by polyhedral sets of both the constraint region and the epigraph of the objective function of the problem, and iteration points are constructed as belonging to the feasible set.
Keywords: multi-objective optimization, non-differentiable optimization, cutting-plane methods, approximations sequence, convergence, approximating set, cutting plane
Received May 13, 2025
Revised May 26, 2025
Accepted June 1, 2025
Published online June 30, 2025
Funding Agency: This study was supported by the Kazan Federal University Strategic Academic Leadership Program (PRIORITY-2030).
Igor’ Yarolslavich Zabotin, Dr. Phys.-Math. Sci., Prof., Institute of Computer Mathematics and Information Technologies of Kazan (Volga region) Federal University, Kazan, 420008 Russia, e-mail: iyazabotin@mail.ru
Oksana Nikolaevna Shul’gina, Cand. Sci. (Phys.-Math.), Institute of Computer Mathematics and Information Technologies of Kazan (Volga region) Federal University, Kazan, 420008 Russia, e-mail: onshul@mail.ru
Rashid Samatovich Yarullin, Cand.Sci. (Phys.-Math.), Institute of Computer Mathematics and Information Technologies of Kazan (Volga region) Federal University, Kazan, 420008 Russia, e-mail: yarullinrs@gmail.com
REFERENCES
1. Keeney R.L., Raiffa H. Decisions with multiple objectives: preferences and value trade-offs. NY, Wiley, 1976, 569 p. ISBN: 0471465100 . Translated to Russian under the title Prinyatiye resheniy pri mnogikh kriteriyakh: predpochteniya i zameshcheniya, Moscow, Radio i svyaz’, 1981, 560 p.
2. Lotov A.V., Pospelova I.I. Mnogokriterial’nyye zadachi prinyatiya resheniy: uchebnoye posobiye [Multicriteria decision making problems: tutorial]. Moscow, MAKS Press, 2008. 197 p. http://www.ccas.ru/mmes/mmeda/L&P2008.pdf
3. Nelyubin A.P., Podinovski A.P. Multicriteria problems with importance-ordered criteria groups. Autom. Remote Control, 2022, vol. 83, no. 7, pp. 1108–1122. https://doi.org/10.1134/S0005117922070074
4. Klamroth K., Stiglmayr M., Totzeck C. Consensus-based optimization for multi-objective problems: a multi-swarm approach. J. Glob. Optim., 2024, vol. 89, pp. 745–776. https://doi.org/10.1007/s10898-024-01369-1
5. Bulatov V.P. Metody pogruzheniya v zadachakh optimizatsii [Embedding methods in optimization problems]. Novosibirsk, Nauka Publ., 1977, 164 p.
6. Khamisov O.V. Development optimization methods in investigations of V. P. Bulatov. Izv. Irkutsk. Gos. Un-ta. Ser. Matematika, 2011, vol. 5, no. 2, pp. 6–15 (in Russian).
7. Zabotin I.Ya., Shulgina O.N., Yarullin R.S. A minimization method with approximation of feasible set and epigraph of objective function. Russian Math. (Iz. VUZ), 2016, vol. 60, no. 11, pp. 78–81. https://doi.org/10.3103/S1066369X16110098
8. Demyanov V.F., Vasil’ev L.V. Nedifferentsiruyemaya optimizatsiya [Nondifferentiable optimization]. Moscow, Nauka Publ., 1981, 384 p.
9. Zabotin I.Ya. On the several algorithms of immersion-severances for the problem of mathematical programming. Izv. Irkutsk. Gos. Un-ta. Ser. Matematika. 2011, vol. 4, no. 2, pp. 91–101 (in Russian).
10. Vasil’ev F.P. Metody optimizatsii. Tom 1 [Optimization methods. Vol. 1]. Moscow, MCNMO, 2011, 620 p. ISBN: 978-5-94057-707-2 .
Cite this article as: I.Ya. Zabotin, O.N. Shulgina, R.S. Yarullin. A variant of the successive concessions method and its implementation based on cutting procedures. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2025, vol. 31, no. 3, pp. 138–149.
