# Distributed Robust Optimization

Consider the following constrained optimization problem $\mathcal{P}$.

$$\min_{x \in X \subseteq \mathbb{R}^n} f(x) \ \text{sub. to: } g(x,y) \leq 0 \ \forall y \in Y \subseteq \mathbb{R}^m$$

Functions $f$ and $g$ are continuous and convex. Sets $X, Y$ are compact and convex.

Note that the constraint "$g(x,y) \leq 0 \ \forall y \in Y$" is infinite dimensional.

Assume that both the optimal value of $\mathcal{P}$ and its optimizer $x^* \in X$ (supposed unique) exist and are bounded.

Suppose we can solve the following "sub-problems" $\mathcal{P}_1$, $\mathcal{P}_2$.

$$\min_{x \in X} f(x) \ \text{sub. to: } g(x,y) \leq 0 \ \forall y \in Y_1 \subset Y$$

$$\min_{x \in X} f(x) \ \text{sub. to: } g(x,y) \leq 0 \ \forall y \in Y_2 \subset Y$$

where $Y_1 \cap Y_2 = \varnothing$ and $Y_1 \cup Y_2 = Y$. Namely, we know the unique optimizers $x_1^*$ and $x_2^*$ of $\mathcal{P}_1$ and $\mathcal{P}_2$, respectively, and hence the optimal values $f(x_1^*)$ and $f(x_2^*)$.

Question: can we compute $x^*$ from the knowledge of $x_1^*$ and $x_2^*$, under one of the following assumptions?

1. $f$ and $g$ are linear, i.e. $f(x) := c^\top x$ and $g(x,y) := Ax + By$.
2. $f$ is quadratic, i.e. $f(x) := x^\top C x + c^\top x$ with $C$ positive definite, and $g$ is linear.

3. No additional assumptions on $f$ and $g$.

Comments. I think this problem is very interesting because would tell how to subdivide a "difficult" optimization problem into two "less difficult" ones. I have looked into the literature of Distributed Robust Optimization to solve this. There actually are convergent algorithms which mainly address the problem whenever the sets $Y_1$ and $Y_2$ (in general, more than $2$ sub-problems are considered) have overlappings. In the latter case, the "solvers" have to communicate to finally "agree" about $x^*$. But I guess that if $Y_1$ and $Y_2$ do not overlap, something better can be done, at least in the linear, or quadratic, case.

I can't comment because I just made this account. But wouldn't $x^*$ in the linear case just be the first point of the convex combination form $\alpha x_1^* + (1 - \alpha) x_2^*$ when $f(x_1^*) < f(x_2^*)$? Or the smallest $\alpha$ such that that convex combination point $\in X_2$. I don't know about the quadratic case. Would have to give it more thought.
• What do you mean by "first point"? By the way, why $x^*$ is supposed to be in the convex combination of $x_1^*$ and $x_2^*$? Apr 1 '13 at 20:18
• Actually, I take it all back. $f(x) is linear$. If $f ( x_1^*) < f(x_2^*)$ and $X_1$ and $X_2$ are convex then $x_2^*$ is the minimizer of $\text{min} f(x) \text{s.t} x \in X_1 x \in X_2$. Since the function is linear $f(x) = \nabla f(x_1^*) * (x-x_1^*)$ You might have to prove this on your own but because its linear $f(x) \forall x \in X_1 uninary minus X_2 <= f(y) \forall y \in X_2$ $x_2^*$ is the minimizer of $f(x) x \in X_1$ therefore the minimizer of the internsection should be $x_2$. Apr 1 '13 at 20:34