Cutting-plane method with embedding of epigraphs of auxiliary functions

摘要

We propose a method of conditional minimization of convex functions from the class of cutting methods. The method based on using of the exterior penalty functions. The iteration points are found by solving linear programming problems. In this case, the admissible set and the epigraph of each auxiliary function are embedded into polyhedral sets. A set, that approximates the epigraph of the next auxiliary function, is constructed on the basis of the previous set by cutting off the iteration point from it. The method's convergence is proved.