Abstract
We propose a method which belongs to a class of cutting methods for solving a convex programming problem. The developed method differs from traditional algorithms of the mentioned class by the following fact. This method uses approximation of the feasible set and the epigraph of the objective function simultaneously for the solving problem. In the method cutting planes are constructed by subgradients of the objective function and functions which define the constrained set. In this case while initial approximating sets are chosen as polyhedral sets, each iteration point is found by solving a linear programming problem independently of the type of functions which define the solving problem. Moreover, unlike most the cutting methods the proposed method is characterized by possibility of updating approximating sets due to dropping accumulating constraints.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
V. P. Bulatov, Embedding Methods in Optimization Problems (Nauka, Novosibirsk, 1977) [in Russian].
V. P. Bulatov and O. V. Khamisov, “Cutting methods in En+1 for solving optimization problems in a class of functions,” Comput. Math. Math. Phys. 47, 1756–1767 (2007).
I. Ya. Zabotin, “On several algorithms of immersion-cutoff for the problem of mathematical programming,” Izv. Irkutsk. Univ., Ser. Mat. 4 (2), 91–101 (2011).
A. A. Kolokolov, “Regular partitions and cuts in integer programming,” in Discrete Analysis and Operations Research, Vol. 355 of Mathematics and Its Applications, Ed. by A. D. Korshunov (Springer, Netherland s, 1996), pp. 59–79.
Yu. E. Nesterov, Introductory Lectures on Convex Optimization (MTsMNO,Moscow, 2010) [in Russian].
E. A. Nurminski, “The separating planesmethod with bounded memory for convex nonsmooth optimization,” Vychisl. Metody Program. 7, 133–137 (2006).
B. T. Polyak, Introduction to Optimization (Nauka, Moscow, 1983) [in Russian].
J. E. Kelley, “The cutting-plane method for solving convex programs,” J. Soc. Ind. Appl. Math. 8, 703–712 (1960).
V. F. Demyanov and L. V. Vasilev, Nondifferentiable Optimization (Mir,Moscow, 1972) [in Russian].
I. Ya. Zabotin and R. S. Yarullin, “A cutting plane algorithm with an approximation of an epigraph,” Uch. Zap. Kazan. Univ., Ser. Fiz.-Mat. Nauki 155 (4), 48–54 (2013).
I. Ya. Zabotin and R. S. Yarullin, “One approach to constructing cutting algorithms with dropping of cutting planes,” Russ. Math. (Iz. VUZ) 57 (3), 60–64 (2013).
I. Ya. Zabotin and R. S. Yarullin, “A cutting method for finding discrete minimax with dropping of cutting planes,” Lobachevskii J. Math. 35 (4), 157–163 (2013).
I. Ya. Zabotin, O. N. Shulgina, and R. S. Yarullin, “A minimization method with approximation of feasible set and epigraph of objective function,” Russ. Math. (Iz. VUZ) 60 (11), 78–81 (2016).
Author information
Authors and Affiliations
Corresponding author
Additional information
Submitted by A. M. Elizarov
Rights and permissions
About this article
Cite this article
Shulgina, O.N., Yarullin, R.S. & Zabotin, I.Y. A Cutting Method with Approximation of a Constraint Region and an Epigraph for Solving Conditional Minimization Problems. Lobachevskii J Math 39, 847–854 (2018). https://doi.org/10.1134/S1995080218060197
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S1995080218060197