For solving constrained minimization problem propose a cutting plane method which belongs to a class of cutting methods.The designed method uses an approximation of the epigraph of the objective function. In the methods of the mentioned class for construction an iteration point on each step the epigraph of the objective function or the constrained set are embedded in some approximation polyhedral sets. Each approximating set is usually constructed on the base of the previous one by cutting of some subset which contains the current iteration point. It is difficult to realize cutting methods in practice, because during growth of iteration’s count the number of cutting planes that define approximating sets indefinitely increases. Proposed method is characterized by periodically applying procedures of updating approximating sets due to dropping of the arbitrary number of any planes constructed in the solution process. These procedures are based on the criterion inserted in this paper of the quality of approximating the epigraph of the objective function by embedding sets. Moreover, the method admits its combination with any other famous or new relaxation algorithms, allows to use parallel computations for construction iteration points, and in case of the strongly convex objective function lets to evaluate proximity of each iteration points to optimal. Prove convergence of the method. Discuss ways to specify the control parameters of the method.

1. Bulatov V. P. Embedding methods in optimization problems (in Russian). Novosibirsk, Nauka, 1977. 161 p.

2. Bulatov V. P., Khamisov O. V. Cutting methods in En+1 for global optimization of a class of functions (in Russian). Zhurn. Vychisl. Matem. i Matem. Fiz., 2007, vol. 47, no. 11, pp. 1830–1842.

3. Vasil’ev F. P. Optimization methods (in Russian). Moscow, MCCME, 2011. 620 p.

4. Zabotin I. Ya. Some embedding-cutting algorithms for mathematical programming problems (in Russian). Izv. Irkutsk. Gos. Univ., Ser. Matem., 2011, vol. 4, no. 2, pp. 91–101.

5. Zabotin I. Ya., Yarullin R. S. A cutting method with updating embedding sets and assessments of the solution’s accuracy (in Russian). Uch. Zap. Kazan. Gos. Univ.m Ser. Fiz.-Mat. Nauki., 2013, vol. 155, no. 2, pp. 54–64.

6. Kolokolov A. A. Regular partitions and cuts in integer programming (in Russian). Sib. zhurn. issled. oper., 1994, vol. 1, no. 2, pp. 18–39.

7. Konnov I. V. Nonlinear optimization and variational inequalities (in Russian). Kazan, Kazan university, 2013. 508 p.

8. Levitin E. C., Polyak B. T. Minimization methods for feasible set (in Russian). Zhurn. Vychisl. Matem. i Matem. Fiz., 1966, vol. 6, no. 5, pp. 878–823.

9. Nesterov Yu. E. Introduction to convex optimization (in Russian). Moscow, MCCME, 2010. 274 p.

10. Nurminskii E. A. Cutting method for solving non-smooth convex optimization problem with limited memory (in Russian). Vychisl. Met. i Program., 2006, vol. 7, pp. 133–137.

11. Kelley J.E. The cutting-plane method for solving convex programs SIAMJ., 1960, vol. 8, no. 4, pp. 703–712.

12. Lemarechal C., Nemirovskii A., Nesterov Yu. New variants of bundle methods Mathematical Programming, 1995, vol. 69, pp. 111–148.

13. Zabotin I.Ya., Yarullun R.S. One approach to constructing cutting algorithms with dropping of cutting planes Russian Math. (Iz. VUZ), Allerton Press Inc., 2013, vol. 57, no. 3, pp. 60–64.