Worst-Case Violation of Sampled Convex Programs for Optimization with Uncertainty

Takafumi Kanamori () and Akiko Takeda ()
Additional contact information
Takafumi Kanamori: Nagoya University
Akiko Takeda: Keio University

Journal of Optimization Theory and Applications, 2012, vol. 152, issue 1, No 10, 197 pages

Abstract: Abstract A deterministic approach called robust optimization has been recently proposed to deal with optimization problems including inexact data, i.e., uncertainty. The basic idea of robust optimization is to seek a solution that is guaranteed to perform well in terms of feasibility and near-optimality for all possible realizations of the uncertain input data. To solve robust optimization problems, Calafiore and Campi have proposed a randomized approach based on sampling of constraints, where the number of samples is determined so that only a small portion of the original constraints is violated by the randomized solution. Our main concern is not only the probability of violation, but also the degree of violation, i.e., the worst-case violation. We derive an upper bound of the worst-case violation for the sampled convex programs and consider the relation between the probability of violation and the worst-case violation. The probability of violation and the degree of violation are simultaneously bounded by a prescribed value when the number of random samples is large enough. In addition, a confidence interval of the optimal value is obtained when the objective function includes uncertainty. Our method is applicable to not only a bounded uncertainty set but also an unbounded one. Hence, the scope of our method includes random sampling following an unbounded distribution such as the normal distribution.

Keywords: Uncertainty; Sampled convex programs; Worst-case violation; Violation probability; Uniform lower bound (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10957-011-9923-2 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:152:y:2012:i:1:d:10.1007_s10957-011-9923-2

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

DOI: 10.1007/s10957-011-9923-2

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 ().