# Composition of two convex optimization problems

Suppose I have two optimization problems with the same objective function but different constraints: \begin{align*} F_1(a)=&\min_x f(x)\\ &\text{s.t.}~ g_1(x)\leq a, \end{align*} \begin{align*} F_2(b)=&\min_x f(x)\\ &\text{s.t.}~ g_2(x)\leq b. \end{align*} The optimal value as a function of the constraint parameters $$F_1(a)$$ and $$F_2(b)$$ are both convex functions.

Now consider the composed optimization problem \begin{align*} F(a,b)=\min_x &f(x)\\ \text{s.t.}~ &g_1(x)\leq a,\\ &g_2(x)\leq b. \end{align*} What can I say about the function $$F(a,b)$$? Is it also convex over $$(a,b)$$?

Consider arbitrary $$c_1 := \begin{bmatrix} a_1 \\ b_1 \end{bmatrix}$$ and $$c_2 := \begin{bmatrix} a_2 \\ b_2 \end{bmatrix}$$ and define $$g(x) := \begin{bmatrix} g_1(x) \\ g_2(x) \end{bmatrix}$$.

I proceed under the assumption that both $$F(c_1)$$ and $$F(c_2)$$ are bounded and therefore have at least one minimizer.

$$x_1^* \in \underset{x}{\arg \min} \; f(x) \text{ subject to } g(x) \leq c_1 \implies F(c_1) = f(x_1^*)$$ $$x_2^* \in \underset{x}{\arg \min} \; f(x) \text{ subject to } g(x) \leq c_2 \implies F(c_2) = f(x_2^*)$$

and observe

$$t \in [0, 1] \implies t F(c_1) + (1 - t) F(c_2) = tf(x_1^*) + (1-t)f(x_2^*) \geq f(t x_1^* + (1 - t) x_2^*)$$

Furthermore

$$g(t x_1^* + (1 - t) x_2^*) \leq t g(x_1^*) + (1 - t) g(x_2^*) \leq t c_1 + (1 - t) c_2$$

so $$t x_1^* + (1 - t) x_2^*$$ is feasible for $$\min_x f(x) \text{ subject to } g(x) \leq t c_1 + (1 - t) c_2$$. We can then conclude

$$t \in [0, 1] \implies t F(c_1) + (1 - t) F(c_2) \geq f(t x_1^* + (1 - t) x_2^*) \geq F(t c_1 + (1 - t) c_2)$$

which shows $$F$$ is convex.

• The unbounded case is simple actually. Consider sequences of feasible points in $F(c_1)$ and $F(c_2)$. Then convex combinations of these points are feasible in $F(t c_1 + (1 - t) c_2)$ and you can show the objective is unbounded. Commented May 1 at 0:24
• Thanks! But why can we get $g(tx_1^*+(1-t)x_2^*)\leq tg(x_1^*)+(1-t)g(x_2^*)$? Does the convexity of $F_1(a)$ imply the convexity of $g_1(x)$? Commented May 5 at 7:36
• Oh I assumed $f$, $g_1$, and $g_2$ are convex. Is that not necessarily the case? Commented May 5 at 14:07