Nonconvex robust programming via value-function optimization

Ying Cui, Ziyu He, Jong Shi Pang

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

Convex programming based robust optimization is an active research topic in the past two decades, partially because of its computational tractability for many classes of optimization problems and uncertainty sets. However, many problems arising from modern operations research and statistical learning applications are nonconvex even in the nominal case, let alone their robust counterpart. In this paper, we introduce a systematic approach for tackling the nonconvexity of the robust optimization problems that is usually coupled with the nonsmoothness of the objective function brought by the worst-case value function. A majorization-minimization algorithm is presented to solve the penalized min-max formulation of the robustified problem that deterministically generates a “better” solution compared with the starting point (that is usually chosen as an unrobustfied optimal solution). A generalized saddle-point theorem regarding the directional stationarity is established and a game-theoretic interpretation of the computed solutions is provided. Numerical experiments show that the computed solutions of the nonconvex robust optimization problems are less sensitive to the data perturbation compared with the unrobustfied ones.

Original languageEnglish (US)
Pages (from-to)411-450
Number of pages40
JournalComputational Optimization and Applications
Volume78
Issue number2
DOIs
StatePublished - Mar 2021

Bibliographical note

Funding Information:
J.-S. Pang and Z. He was based on research supported by the National Science Foundation under Grant IIS-1632971 and by the Air Force Office of Scientific Research under Grant Number FA9550-18-1-0382.

Publisher Copyright:
© 2020, Springer Science+Business Media, LLC, part of Springer Nature.

Keywords

  • Nonconvex
  • Nonsmooth
  • Robust optimization
  • Value function

Fingerprint

Dive into the research topics of 'Nonconvex robust programming via value-function optimization'. Together they form a unique fingerprint.

Cite this