A Relaxed Version of the Cutting Method with Approximation of the Constraint Region
https://doi.org/10.26907/2541-7746.2023.2.143-152
Abstract
A cutting method was proposed for solving the convex programming problem. The method assumes that the constraint region of the problem is embedded into some polyhedral sets for constructing iteration points. It involves the construction of a sequence of approximations that belongs to the admissible set and is relaxed, as well as implies that the ε-solution of the initial problem is fixed after a finite number of steps. The method also allows to obtain mixed convergent algorithms by using, if desired, any known or new relaxation algorithms for constructing the main iteration points.
Keywords
convex programming,
sequence of approximation,
relaxation,
convergence,
approximation,
generalized support vector,
subdifferential,
cutting plane
Supporting agencies: This study was supported by the Kazan Federal University Strategic Academic Leadership Program (PRIORITY-2030).
About the Authors
I. Ya. Zabotin
Kazan Federal University
Russian Federation
Russian Federation
Kazan, 420008
O. N. Shulgina
Kazan Federal University
Russian Federation
Russian Federation
Kazan, 420008
R. S. Yarullin
Kazan Federal University
Russian Federation
Russian Federation
Kazan, 420008
References
1. Bulatov V.P. Metody pogruzheniya v zadachakh optimizatsii [Imbedding Methods in Optimization Problems]. Novosibirsk, Nauka, 1977. 158 p. (In Russian)
2. Bulatov V.P., Khamisov O.V. Cutting methods in En+1 for global optimization of a class of functions. Comput. Math. Math. Phys., 2007, vol. 47, no. 11, pp. 1756–1767. URL: https://doi.org/10.1134/S0965542507110036.
3. Dem’yanov V.F., Vasil’ev L.V. Nedifferentsiruemaya optimizatsiya [Nondifferentiable Optimization]. Moscow, Nauka, 1981. 384 p. (In Russian)
4. Zabotin I.Ya., Yarullin R.S. One approach to constructing cutting algorithms with dropping of cutting planes. Russ. Math., 2013, vol. 57, no. 3, pp. 60–64. URL: https://doi.org/10.3103/S1066369X13030092.
5. Zabotin I.Ya., Yarullin R.S. Cutting-plane method based on epigraph approximation with discarding the cutting planes. Autom. Remote Control, 2015, vol. 76, no. 11, pp. 1966– 1975. URL: https://doi.org/10.1134/S0005117915110065.
6. Nesterov Yu.E. Vvedenie v vypukluyu optimizatsiyu [Introduction to Convex Optimization]. Moscow, MTsNMO, 2010. 278 p. (In Russian)
7. Nurminskii E.A. The separating planes method with bounded memory for convex nonsmooth optimization problems. Vychisl. Metody Program., 2006, vol. 7, no. 1, pp. 133–137. (In Russian)
8. Volkonskii V.A., Eganyan G.K., Pomanskii A.B. Set of efficient points in linear multicriteria problems. Sib. Math. J., 1983, vol. 24, no. 2, pp. 159–167. URL: https://doi.org/10.1007/BF00968733.
9. Polyak B.T. Vvedenie v optimizatsiyu [Introduction to Optimization]. Moscow, Nauka, 1983. 384 p. (In Russian)
10. Zabotin I.Ya. Some embedding-cutting algorithms for mathematical programming problems. Izv. Irkutsk. Gos. Univ. Ser. Mat., 2011, vol. 4, no. 2, pp. 91–101. (In Russian)
11. Vasil’ev F.P. Metody optimizatsii [Optimization Methods]. Book 1. Moscow, MTsNMO, 2011. 624 p. (In Russian)
12. Zabotin Ya.I., Fukin I.A. One modification of the penalty shifting method for problems of nonlinear programming. Russ. Math. (Izv. Vyssh. Uchebn. Zaved.), 2000, vol. 44, no. 12, pp. 47–52.
13. Pshenichnyi B.N. Vypuklyi analiz i ekstremal’nye zadachi [Convex Analysis and Extremal Problems]. Moscow, Nauka, 1980. 320 p. (In Russian)
Review
For citations:
Zabotin I.Ya., Shulgina O.N., Yarullin R.S. A Relaxed Version of the Cutting Method with Approximation of the Constraint Region. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki. 2023;165(2):143–152. (In Russ.) https://doi.org/10.26907/2541-7746.2023.2.143-152
Views:
139
Email this article 