An inexact primal-dual algorithm for semi-infinite programming
| Autor: | William B. Haskell, Sixiang Zhao, Bo Wei |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
0209 industrial biotechnology
Primal dual algorithm 021103 operations research Sample complexity General Mathematics Constraint violation Monte Carlo method 0211 other engineering and technologies 02 engineering and technology Management Science and Operations Research Regularization (mathematics) Semi-infinite programming 020901 industrial engineering & automation Rate of convergence Optimization and Control (math.OC) FOS: Mathematics Applied mathematics Monte Carlo integration Mathematics - Optimization and Control Software Mathematics |
| Zdroj: | Mathematical Methods of Operations Research. 91:501-544 |
| ISSN: | 1432-5217 1432-2994 |
| DOI: | 10.1007/s00186-019-00698-2 |
| Popis: | This paper considers an inexact primal-dual algorithm for semi-infinite programming (SIP) for which it provides general error bounds. We create a new prox function for nonnegative measures for the dual update, and it turns out to be a generalization of the Kullback-Leibler divergence. We show that, with a tolerance for small errors (approximation and regularization error), this algorithm achieves an $${\mathcal {O}}(1/\sqrt{K})$$ rate of convergence in terms of the optimality gap and constraint violation, where K is the total number of iterations. We then use our general error bounds to analyze the convergence and sample complexity of a specific primal-dual SIP algorithm based on Monte Carlo sampling. Finally, we provide numerical experiments to demonstrate the performance of this algorithm. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
| Nepřihlášeným uživatelům se plný text nezobrazuje | K zobrazení výsledku je třeba se přihlásit. |