In this note we derive an exact expression for the expected probability V of constraint violation in a sampled convex program (see [1], [2] for definitions and an introduction to this topic): V = expected number of support constraints/1 + number of constraints. This result (Theorem 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 to obtain one of the tightest available explicit bounds on the sample complexity of sampled convex programs (Proposition 3).

A note on the expected probability of constraint violation in sampled convex programs / Calafiore, Giuseppe Carlo. - STAMPA. - (2009), pp. 1788-1791. (Intervento presentato al convegno IEEE Multi-conference on Systems and Control tenutosi a St. Petersburg, Russia nel July 8-10, 2009) [10.1109/CCA.2009.5281097].

A note on the expected probability of constraint violation in sampled convex programs

CALAFIORE, Giuseppe Carlo
2009

Abstract

In this note we derive an exact expression for the expected probability V of constraint violation in a sampled convex program (see [1], [2] for definitions and an introduction to this topic): V = expected number of support constraints/1 + number of constraints. This result (Theorem 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 to obtain one of the tightest available explicit bounds on the sample complexity of sampled convex programs (Proposition 3).
2009
9781424446018
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11583/2284915
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo