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)$?


1 Answer 1


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^*)$$


$$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.

  • $\begingroup$ 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. $\endgroup$
    – msantama
    Commented May 1 at 0:24
  • $\begingroup$ 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)$? $\endgroup$
    – Harry556
    Commented May 5 at 7:36
  • $\begingroup$ Oh I assumed $f$, $g_1$, and $g_2$ are convex. Is that not necessarily the case? $\endgroup$
    – msantama
    Commented May 5 at 14:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .