A version of the penalty method with approximation of the epigraphs of auxiliary functions
I.Ya. Zabotin*, K.E. Kazaeva**
Kazan Federal University, Kazan, 420008 Russia
E-mail: *IYaZabotin@mail.ru, **k.e.kazaeva@gmail.com
Received March 11, 2019
Full text PDF
DOI: 10.26907/2541-7746.2019.2.263-273
For citation: Zabotin I.Ya., Kazaeva K.E. A version of the penalty method with approximation of the epigraphs of auxiliary functions. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2019, vol. 161, no. 2, pp. 263–273. doi: 10.26907/2541-7746.2019.2.263-273. (In Russian)
Abstract
A method for solving the convex programming problem, which is ideologically close to the known methods of external penalties, was proposed. The method uses auxiliary functions that are built on the general form of the penalty functions. In order to find approximations, the epigraphs of these auxiliary functions, as well as the original problem's domain of constraints, were immersed in certain polyhedral sets. In this regard, the problems of finding the iterative points are the linear programming problems, in which the constraints are the sets that approximate the epigraphs and a polyhedron containing an admissible set. The approximating sets were constructed using the traditional cutting of iterative points by planes. The peculiarity of the method is that it enables a periodic update of the approximating sets by discarding the cutting planes. The convergence of the proposed method was proved. Its implementation was discussed.
Keywords: conditional minimization, iterative point, convergence, penalty function, epigraph, approximating set, cutting hyperplane
References
1. Vasil'ev F.P. Metody optimizatsii [Optimization Methods]. Book 1. Moscow, MTsNMO, 2011. 620 p. (In Russian)
2. Konnov I.V. Nelineinaya optimizatsiya i variatsionnye neravenstva [Nonlinear Optimization and Variational Inequalities]. Kazan, Kazan. Univ., 2013. 508 p. (In Russian)
3. Polyak B.T. Vvedenie v optimizatsiyu [Introduction to Optimization]. Moscow, Nauka, 1983. 384p. (In Russian)
4. Bulatov V.P. Metody pogruzheniya v zadachakh optimizatsii [Embedding Methods in Optimization Problems]. Novosibirsk, Nauka, 1977. 161 p. (In Russian)
5. Bulatov V.P., Khamisov O.V. Cutting methods in for global optimization of a class of functions. Comput. Math. Math. Phys., 2007., vol. 47, no. 11, pp. 1756–1767. doi: 10.1134/S0965542507110036.
6. 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. doi: 10.1134/S0005117915110065.
7. Zabotin I., Shulgina O., Yarullin R. A minimization algorithm with approximation of an epigraph of the objective function and a constraint set. CEUR Workshop Proc., 2016, vol. 1623: Discrete Optimization and Operations Research 2016. (DOOR 2016), pp. 321–324.
8. Nurminski E.A. A separating plane algorithm with limited memory for convex nonsmooth optimization. Vychisl. Metody Programm., 2006, vol. 7, no. 1, pp. 133–137. (In Russian)
9. Zabotin I., Kazaeva K. Cutting - plane method with embedding of epigraphs of auxiliary functions. In: Constructive Nonsmooth Analysis and Related Topics (Dedicated to the Memory of V.F. Demyanov). IEEE, 2017, pp. 1–4. doi: 10.1109/CNSA.2017.7974033.
10. 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. doi: 10.1134/S1995080215020195.
11. 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., 2016, vol. 60, no. 11, pp. 78–81. doi: 10.3103/S1066369X16110098.
12. Zabotin I.Ya., Shulgina O.N., Yarullin R.S. A cutting method and construction of mixed minimization algorithms on its basis. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko - Matematicheskie Nauki, 2014, vol. 156, no. 4, pp. 14–24. (In Russian)
13. 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)
The content is available under the license Creative Commons Attribution 4.0 License.
