On the Expected Probability of Constraint Violation in Sampled Convex Programs

G. C. Calafiore ()
Additional contact information
G. C. Calafiore: Politecnico di Torino

Journal of Optimization Theory and Applications, 2009, vol. 143, issue 2, No 11, 405-412

Abstract: Abstract In this note, we derive an exact expression for the expected probability V of constraint violation in a sampled convex program (see Calafiore and Campi in Math. Program. 102(1):25–46, 2005; IEEE Trans. Autom. Control 51(5):742–753, 2006 for definitions and an introduction to this topic): $$V=\frac{\mbox{expected number of support constraints}}{1+\mbox{number of constraints}}.$$ This result (Theorem 2.1) is obtained using a simple technique based on cardinality count. In the note, we also use a Chernoff bounding technique on the upper tail violation probability expression derived in (Campi and Garatti in SIAM J. Optim. 19(3):1211–1230, 2008) to obtain one of the tightest available explicit bounds on the sample complexity of sampled convex programs (Proposition 2.1).

Keywords: Sampled convex programs; Scenario optimization; Randomized methods; Robust convex optimization; Probabilistic robustness; Semi-infinite programming; Constraint violation probability (search for similar items in EconPapers)
Date: 2009
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-009-9579-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:143:y:2009:i:2:d:10.1007_s10957-009-9579-3

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-009-9579-3

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().