Convex Optimization · Problem 4.59

Duality — Boyd & Vandenberghe

Mathematics — Optimization · robust-optimization

Problem

Robust optimization. In some optimization problems there is uncertainty or variation in the objective and constraint functions, due to parameters or factors that are either beyond our control or unknown. We can model this situation by making the objective and constraint functions f0,…,fmf_0, \ldots, f_m functions of the optimization variable x∈Rnx \in \mathbf{R}^n and a parameter vector u∈Rku \in \mathbf{R}^k that is unknown, or varies. To simplify the discussion, we assume there are no equality constraints. (a) Stochastic optimization. We consider the problem minimizeE f0(x,u)subject toE fi(x,u)≤0,i=1,…,m,\begin{array}{ll} \text{minimize} & \mathbf{E}\, f_0(x, u) \\ \text{subject to} & \mathbf{E}\, f_i(x, u) \leq 0, \quad i = 1, \ldots, m, \end{array} where the expectation is with respect to uu. Show that if fif_i are convex in xx for each uu, then this stochastic optimization problem is convex. (b) Worst-case optimization. We consider the problem minimizesup⁡u∈Uf0(x,u)subject tosup⁡u∈Ufi(x,u)≤0,i=1,…,m.\begin{array}{ll} \text{minimize} & \sup_{u \in \mathcal{U}} f_0(x, u) \\ \text{subject to} & \sup_{u \in \mathcal{U}} f_i(x, u) \leq 0, \quad i = 1, \ldots, m. \end{array} Show that if fif_i are convex in xx for each uu, then this worst-case optimization problem is convex. (c) Finite set of possible parameter values. Suppose we are given the set of possible values of the parameter is finite, i.e., we have u∈{u1,…,uN}u \in \{u_1, \ldots, u_N\}. For the stochastic case, we are also given the probabilities of each value: prob(u=ui)=pi\mathbf{prob}(u = u_i) = p_i, where p∈RNp \in \mathbf{R}^N, p⪰0p \succeq 0, 1Tp=1\mathbf{1}^T p = 1. In the worst-case formulation, we simply take U∈{u1,…,uN}\mathcal{U} \in \{u_1, \ldots, u_N\}. Show how to set up the worst-case and stochastic optimization problems explicitly (i.e., give explicit expressions for sup⁡u∈Ufi\sup_{u \in \mathcal{U}} f_i and Eufi\mathbf{E}_u f_i).

Browse the problem library