A cutting-plane method with internal iteration points for the general convex programming problem
https://doi.org/10.26907/2541-7746.2023.3.208-218
Abstract
A cutting method for solving the problem of convex programming was proposed. The method calculates iteration points based on approximation by polyhedral sets of the constraint region and the epigraph of the objective function. Its distinguishing feature is that the main sequence of approximations is constructed within the admissible region. At each step, it is also possible to assess how close the current value of the function is to the optimal value. The convergence of the method was proved. A few of its implementations were outlined.
About the Authors
I. Ya. Zabotin
Kazan Federal University
Russian Federation
Russian Federation
Kazan, 420008
K. E. Kazaeva
Kazan Federal University
Russian Federation
Russian Federation
Kazan, 420008
O. N. Shulgina
Kazan Federal University
Russian Federation
Russian Federation
Kazan, 420008
References
1. Bulatov V.P. Metody pogruzheniya v zadachakh optimizatsii [Embedding Methods in Optimization Problems]. Novosibirsk, Nauka, 1977. 161 p. (In Russian)
2. 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)
3. Zabotin I.Ya., Yarullin R.S. A cutting plane algorithm with an approximation of an epigraph. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Naukii, 2013, vol. 155, no. 4, pp. 48–54. (In Russian)
4. Polyak B.T. Vvedenie v optimizatsiyu [Introduction to Optimization]. Moscow, Nauka, 1983. 384 p. (In Russian)
5. Zabotin I.Ya., Yarullin R.S. One approach to constructing cutting algorithms with dropping of cutting planes. Russ. Math. (Izv. Vyssh. Uchebn. Zaved.), 2013, vol. 57, no. 3, pp. 60–64. https://doi.org/10.3103/S1066369X13030092.
6. Zabotin I.Ya., Yarullin R.S. A cutting-plane method without inclusions of approximating sets for conditional minimization. Lobachevskii J. Math., 2015, vol. 36, no. 2, pp. 132–138. https://doi.org/10.1134/S1995080215020195.
7. 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. https://doi.org/10.1134/S0005117915110065.
8. Demyanov V. F., Vasilev L. V. Nedifferentsiruemaya optimizatsiya [Nondifferentiable Optimization]. Moscow, Nauka, 1981. 384 p. (In Russian)
9. Zabotin I., Shulgina O., Yarullin R. A minimization algorithm with approximation of an epigraph of the objective function and a constaint set. CEUR Workshop Proc. Vol. 1623: Proc. 9th Int. Conf. on Discrete Optimization and Operations Research and Scientific School (DOOR-SUP 2016). Vladivostok, 2016, pp. 321–324.
10. Zabotin I.Y, Shul’gina O.N, Yarullin R.S. A minimization method with approximation of feasible set and epigraph of objective function. Russ. Math. (Izv. Vyssh. Uchebn. Zaved.), 2016, vol. 60, no. 11, pp. 78–81. https://doi.org/10.3103/S1066369X16110098.
11. Shulgina O.N., Yarullin R.S., Zabotin I.Ya. A cutting method with approximation of a constraint region and an epigraph for solving conditional minimization problems. Lobachevskii J. Math., 2018, vol. 39, no. 6, pp. 847–854. https://doi.org/10.1134/S1995080218060197.
Review
For citations:
Zabotin I.Ya., Kazaeva K.E., Shulgina O.N. A cutting-plane method with internal iteration points for the general convex programming problem. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki. 2023;165(3):208-218. (In Russ.) https://doi.org/10.26907/2541-7746.2023.3.208-218
Views:
126
Email this article 