RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Forthcoming papers Archive Impact factor Subscription Guidelines for authors License agreement Submit a manuscript Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Mat. Sb.: Year: Volume: Issue: Page: Find

 Mat. Sb., 2010, Volume 201, Number 4, Pages 3–24 (Mi msb7594)

An algorithm for linearizing convex extremal problems

E. S. Gorskaya

M. V. Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: 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.

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

DOI: https://doi.org/10.4213/sm7594

Full text: PDF file (551 kB)
References: PDF file   HTML file

English version:
Sbornik: Mathematics, 2010, 201:4, 471–492

Bibliographic databases:

UDC: 519.853.3+517.518.8+514.172.45
MSC: 90C05, 90C25, 52A27

Citation: 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
\Bibitem{Gor10} \by E.~S.~Gorskaya \paper An algorithm for linearizing convex extremal problems \jour Mat. Sb. \yr 2010 \vol 201 \issue 4 \pages 3--24 \mathnet{http://mi.mathnet.ru/msb7594} \crossref{https://doi.org/10.4213/sm7594} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=2675339} \zmath{https://zbmath.org/?q=an:1218.90110} \adsnasa{http://adsabs.harvard.edu/cgi-bin/bib_query?2010SbMat.201..471G} \elib{https://elibrary.ru/item.asp?id=19066194} \transl \jour Sb. Math. \yr 2010 \vol 201 \issue 4 \pages 471--492 \crossref{https://doi.org/10.1070/SM2010v201n04ABEH004079} \isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000279452200006} \elib{https://elibrary.ru/item.asp?id=15325127} \scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-77954798505} 

• http://mi.mathnet.ru/eng/msb7594
• https://doi.org/10.4213/sm7594
• http://mi.mathnet.ru/eng/msb/v201/i4/p3

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. Gorskaya E.S., “Priblizhenie vypuklykh funktsii proektsiyami mnogogrannikov”, Vestn. Mosk. un-ta. Ser. 1. Matem. Mekh., 2010, no. 5, 20–27.
•  Number of views: This page: 584 Full text: 127 References: 36 First page: 16