Journal
IEEE TRANSACTIONS ON AUTOMATIC CONTROL
Volume 54, Issue 11, Pages 2545-2559Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TAC.2009.2031207
Keywords
Probabilistic robustness; randomized algorithms; statistical learning theory; uncertain systems
Funding
- MCYT-Spain
- European Commission [DPI2007-66718-C04-01, FP7-223866]
Ask authors/readers for more resources
In this paper, we study two general semi-infinite programming problems by means of a randomized strategy based on statistical learning theory. The sample size results obtained with this approach are generally considered to be very conservative by the control community. The first main contribution of this paper is to demonstrate that this is not necessarily the case. Utilizing as a starting point one-sided results from statistical learning theory, we obtain bounds on the number of required samples that are manageable for reasonable values of probabilistic confidence and accuracy. In particular, we show that the number of required samples grows with the accuracy parameter epsilon as 1/epsilon in 1/epsilon, and this is a significant improvement when compared to the existing bounds which depend on 1/epsilon(2) ln 1/epsilon(2). Secondly, we present new results for optimization and feasibility problems involving Boolean expressions consisting of polynomials. In this case, when the accuracy parameter is sufficiently small, an explicit bound that only depends on the number of decision variables, and on the confidence and accuracy parameters is presented. For convex optimization problems, we also prove that the required sample size is inversely proportional to the accuracy for fixed confidence. Thirdly, we propose a randomized algorithm that provides a probabilistic solution circumventing the potential conservatism of the bounds previously derived.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available