Approximation of Convex Functions by Projections of Polyhedra / Gorskaya E.S. // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika. 2010. ? 5. P. 20-27 [Moscow Univ. Math. Bulletin. Vol. 65, No 5, 2010. P. 196-203].

A method for approximate solution of minimization problems for multivariable convex functions with convex constraints is proposed. The main idea consists in approximation of the objective function and constraints by piecewise linear functions and subsequent reduction of the initial convex programming problem to a problem of linear programming. We present algorithms constructing approximating polygons for some classes of single variable convex functions. The many-dimensional problem is reduced to a one-dimensional one by an inductive procedure. The efficiency of the method is illustrated by numerical examples.

Key words: convex problems, projections of polyhedra, approximation, complexity of algorithms.