A Cutting Method with Approximation of a Constraint Region and an Epigraph for Solving Conditional Minimization Problems

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.