Continuity of the optimal solution when the objective function is convex and separable

1k Views Asked by At

I have a very simple class of optimization problems. The objective function is separable with each part being strictly (or even strongly) convex. Furthermore, there's a solitary linear constraint: the sum of the variables is $b$. The variables must all be non-negative.

Can we say that the optimal solution, denoted $x(b)$, is a continuous function of the scalar $b$?

minimize $\sum f_i(x_i)$

subject to: $\sum x_i = b$

with: $x_i \ge 0.$

If necessary, assume that there exists $m>0$ such that $f_i''(t) > m$ for all $i$ and for all $t \ge 0$.

1

There are 1 best solutions below

3
On BEST ANSWER

I am not a fan of the following style of proof, but one not based on sequences escapes me.

Note that convexity of $\phi$ as such plays no part in the argument below, the main characteristics needed are continuity of $\phi$ and uniqueness of the minimiser.

Let $\Sigma_b = \{x | \sum_k x_k =b , x_k \ge 0 \}$.

Suppose $\phi$ is strictly convex, then the solution to $\min \{ \phi(x) | x \in \Sigma_b \}$ is unique. Let the solution be $x(b)$.

It is clear from continuity that if $b_k \to 0$ then $x(b_k) \to x(0)$ (regardless of $\phi$).

So, suppose $b_k \to b^* \neq 0$. We would like to show that $x(b_k) \to x(b^*)$.

Note that if $x \in \Sigma_{b^*} $ then ${b_k \over b^* } x \in \Sigma_{b_k} $.

Hence $\phi(x(b_k)) \le \phi({b_k \over b^* } x)$ for all $x \in \Sigma_{b^*} $.

Suppose $x^*$ is an accumulation point of $x(b_k)$ then the previous statement shows that $\phi(x^*) \le \phi(x) $ for all $x \in \Sigma_{b^*} $ and so $x^* = x(b^*)$. Since the $x(b_k)$ all lie in some compact set it follows that $x(b_k) \to x(b^*)$ and so $b \mapsto x(b)$ is continuous.