Nonconvex robust programming via value-function optimization
- PDF / 3,351,004 Bytes
- 40 Pages / 439.37 x 666.142 pts Page_size
- 71 Downloads / 230 Views
Nonconvex robust programming via value‑function optimization Ying Cui1 · Ziyu He2 · Jong‑Shi Pang2 Received: 12 May 2020 / Accepted: 9 November 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
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 saddlepoint 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. Keywords Robust optimization · Nonconvex · Nonsmooth · Value function
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 FA955018-1-0382. * Ying Cui [email protected] Ziyu He [email protected] Jong‑Shi Pang [email protected] 1
Department of Industrial and Systems Engineering, University of Minnesota, Minneapolis, MN 55455, USA
2
Daniel J. Epstein Department of Industrial and Systems Engineering, University of Southern California, Los Angeles, CA 90089‑0193, USA
13
Vol.:(0123456789)
Y. Cui et al.
1 Introduction The presence of uncertainty, interdiction, or attack is a major impediment to the smart learning and decision making for an economic agent. Moreover, with a goal of instilling harmful disruptions and/or more serious damages, an adversary could add to such an impediment and significantly affect the decision maker’s normal operations. Anticipating and possibly without precise information, the decision maker, considered as the defender, needs to guard against such disruptions/interdictions/attacks and undertakes the planning accordingly. While this defender-attacker paradigm is classical in non-cooperative game theory and has many applications, the rigorous treatment of the resulting mathematical program can be very challenging when all components of the decision process are being perturbed/attacked/poisoned, resulting in a decision making problem that is void of the two most important properties of convexity and smoothness which are key
Data Loading...
