An algorithm for linearizing convex extremal problems

E. S. Gorskaya

Sbornik. Mathematics, Tome 201 (2010) no. 4, pp. 471-492

Résumé

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.

Détail

Keywords: convex problems, piecewise linear functions, approximation of functions, evaluation of operator norms.

Bibliographie

[1] S. Boyd, L. Vandenberghe, Convex optimization, Cambridge Univ. Press, Cambridge, 2004 | MR | Zbl

[2] Yu. Nesterov, A. Nemirovskii, Interior-point polynomial algorithms in convex programming, SIAM Stud. Appl. Math., 13, SIAM, Philadelphia, PA, 1994 | MR | Zbl

[3] Yu. Nesterov, Introductory lectures on convex optimization, Appl. Optim., 87, Kluwer Acad. Publishers, Boston, MA, 2004 | MR | Zbl

[4] P. M. Gruber, “Error of asymptotic formulae for volume approximation of convex bodies in $\mathbb E^d$”, Monatsh. Math., 135:4 (2002), 279–304 | DOI | MR | Zbl

[5] C. Schütt, E. Werner, “Random polytopes with vertices on the boundary of a convex body”, C. R. Acad. Sci. Paris Sér. I Math., 331:9 (2000), 697–701 | DOI | MR | Zbl

[6] R. Schneider, “Polyhedral approximation of smooth convex bodies”, J. Math. Anal. Appl., 128:2 (1987), 470–474 | DOI | MR | Zbl

[7] M. Ludwig, C. Schütt, E. Werner, “Approximation of the Euclidean ball by polytopes”, Studia Math., 173:1 (2006), 1–18 | DOI | MR | Zbl

[8] L. Chen, “New analysis of the sphere covering problems and optimal polytope approximation of convex bodies”, J. Approx. Theory, 133:1 (2005), 134–145 | DOI | MR | Zbl

[9] J. Bourgain, J. Lindenstrauss, V. Milman, “Approximation of zonoids by zonotopes”, Acta Math., 162:1 (1989), 73–141 | DOI | MR | Zbl

[10] V. Yu. Protasov, “The generalized joint spectral radius. A geometric approach”, Izv. Math., 61:5 (1997), 995–1030 | DOI | MR | Zbl

[11] M. A. Lopez, Sh. Reisner, “Hausdorff approximation of convex polygons”, Comput. Geom., 32:2 (2005), 139–158 | DOI | MR | Zbl

[12] J. S. Müller, “Step by step approximation of plane convex bodies”, Arch. Math. (Basel), 58:6 (1992), 606–610 | DOI | MR | Zbl

[13] R. Schneider, “Affine-invariant approximation by convex polytopes”, Studia Sci. Math. Hungar., 21:3–4 (1986), 401–408 | MR | Zbl

[14] D. E. McClure, R. A. Vitale, “Polygonal approximation of plane convex bodies”, J. Math. Anal. Appl., 51:2 (1975), 326–358 | DOI | MR | Zbl

[15] V. Yu. Protasov, “Sovmestnyi spektralnyi radius i invariantnye mnozhestva lineinykh operatorov”, Fundament. i prikl. matem., 2:1 (1996), 205–231 | MR | Zbl

[16] A. A. Ligun, V. F. Storchai, “On the best choice of nodes for approximation by splines in the metric of $L_p$”, Math. Notes, 20:4 (1976), 899–903 | DOI | MR | Zbl | Zbl

[17] A. D. Ioffe, V. M. Tihomirov, Theory of extremal problems, Stud. Math. Appl., 6, North-Holland, Amsterdam–New York, 1979 | MR | MR | Zbl | Zbl

[18] D. S. Watkins, Fundamentals of matrix computations, Pure Appl. Math. (N. Y.), Wiley, New York, 2002 | MR | Zbl

[19] G. H. Golub, Ch. F. Van Loan, Matrix computations, Johns Hopkins Stud. Math. Sci., Johns Hopkins Univ. Press, Baltimore, MD, 1996 | MR | Zbl