This article is cited in 1 scientific paper (total in 1 paper)
An algorithm for linearizing convex extremal problems
E. S. Gorskaya
M. V. Lomonosov Moscow State University, Faculty of Mechanics and Mathematics
This paper suggests a method of approximating the solution of minimization problems for convex functions of several variables under convex constraints is suggested. The main idea of this approach is the approximation of a convex function by a piecewise linear function, which results in replacing the problem of convex programming by a linear programming problem. To carry out such an approximation, the epigraph of a convex function is approximated by the projection of a polytope of greater dimension. In the first part of the
paper, the problem is considered for functions of one variable. In this case, an algorithm for approximating the epigraph of a convex function by a polygon is presented, it is shown that this algorithm is optimal with respect to the number of vertices of the polygon, and exact bounds for this number are obtained. After this, using an induction procedure, the algorithm is generalized to certain classes of functions of several variables. Applying the suggested method, polynomial algorithms for an approximate calculation of the $L_p$-norm of a matrix and of the minimum of the entropy function on a polytope are obtained.
Bibliography: 19 titles.
convex problems, piecewise linear functions, approximation of functions,
evaluation of operator norms.
PDF file (551 kB)
Sbornik: Mathematics, 2010, 201:4, 471–492
MSC: 90C05, 90C25, 52A27
E. S. Gorskaya, “An algorithm for linearizing convex extremal problems”, Mat. Sb., 201:4 (2010), 3–24; Sb. Math., 201:4 (2010), 471–492
Citation in format AMSBIB
\paper An algorithm for linearizing convex extremal problems
\jour Mat. Sb.
\jour Sb. Math.
Citing articles on Google Scholar:
Related articles on Google Scholar:
This publication is cited in the following articles:
Gorskaya E.S., “Priblizhenie vypuklykh funktsii proektsiyami mnogogrannikov”, Vestn. Mosk. un-ta. Ser. 1. Matem. Mekh., 2010, no. 5, 20–27.
|Number of views:|