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






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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

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

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
Received: 23.06.2009

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}


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

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    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.  mathnet  mathscinet  zmath  elib
  • Математический сборник Sbornik: Mathematics (from 1967)
    Number of views:
    This page:584
    Full text:127
    References:36
    First page:16

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2021