Consiglio Nazionale delle Ricerche

Tipo di prodottoArticolo in rivista
TitoloA Randomized Cutting Plane Method with Probabilistic Geometric Convergence
Anno di pubblicazione2010
  • Elettronico
  • Cartaceo
Autore/iF. Dabbene, P.S. Shcherbakov, B.T. Polyak
Affiliazioni autoriF. Dabbene : CNR-IEIIT P.S. Shcherbakov, B.T. Polyak : Institute of Control Science, Russian Academy of Sciences, Moscow, Russian Federation
Autori CNR e affiliazioni
  • inglese
AbstractWe propose a randomized method for general convex optimization problems; namely, the minimization of a linear function over a convex body. The idea is to generate N random points inside the body, choose the best one, and cut the part of the body defined by the linear constraint. We analyze the convergence properties of the algorithm from a theoretical viewpoint, i.e., under the rather standard assumption that an algorithm for uniform generation of random points in the convex body is available. Under this assumption, the expected rate of convergence for such method is proved to be geometric. This analysis is based on new results on the statistical properties of the empirical minimum over a convex body that we obtained in this paper. Moreover, explicit sample size results on convergence are derived. In particular, we compute the minimum number of random points that should be generated at each step in order to guarantee that, in a probabilistic sense, the method performs better than the deterministic center-of-gravity algorithm. From a practical viewpoint, we show how the method can be implemented using hit-and-run versions of Markov-chain Monte Carlo algorithms and exemplify the performance of this implementable modification via a number of illustrative problems. A crucial notion for the hit-and-run implementation is that of boundary oracle, which is available for most optimization problems including linear matrix inequalities and many other kinds of constraints. Preliminary numerical results for semidefinite programs are presented confirming that the randomized approach might be competitive to modern deterministic convex optimization methods
Lingua abstractinglese
Altro abstract-
Lingua altro abstract-
Pagine da3185
Pagine a3207
Pagine totali-
RivistaSIAM journal on optimization (Print)
Attiva dal 1991
Editore: The Society, - Philadelphia, Pa.
Paese di pubblicazione: Stati Uniti d'America
Lingua: inglese
ISSN: 1052-6234
Titolo chiave: SIAM journal on optimization (Print)
Titolo proprio: SIAM journal on optimization (Print)
Titolo abbreviato: SIAM j. optim. (Print)
Titoli alternativi:
  • Society for Industrial and Applied Mathematics journal on optimization (Print)
  • Optimization (Print)
Numero volume della rivista20
Fascicolo della rivista6
Verificato da refereeSì: Internazionale
Stato della pubblicazione-
Indicizzazione (in banche dati controllate)
  • ISI Web of Science (WOS) (Codice:000285547100021)
  • Scopus (Codice:2-s2.0-79251528591)
Parole chiavecontrol, robust optimzation
Link (URL, URI)
Titolo parallelo-
Data di accettazione-
Note/Altre informazioni-
Strutture CNR
  • IEIIT — Istituto di elettronica e di ingegneria dell'informazione e delle telecomunicazioni
Moduli CNR
    Progetti Europei-
    • Published paper

    Dati storici
    I dati storici non sono modificabili, sono stati ereditati da altri sistemi (es. Gestione Istituti, PUMA, ...) e hanno solo valore storico.
    Area disciplinareCommunication
    Area valutazione CIVRIngegneria industriale e informatica