2
$\begingroup$

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

Improve this question
$\endgroup$
  • $\begingroup$ Not really an answer, but if $f_k(t) = t$ then any point in the simplex is a solution, so there is no uniqueness hence it is not a function. (Of course in this instance there exists a continuous function that is a solution.) $\endgroup$ – copper.hat Jul 8 '17 at 17:13
  • $\begingroup$ True. However, note that linear functions are not strictly convex. $\endgroup$ – innerproduct Jul 8 '17 at 17:38
  • $\begingroup$ Even if strictly convex, the solution need not be unique. If all $f_k$ are the same, then the solutions can be permuted. So, it may be the case that there exists a continuous function that is a solution for all $b$, but one cannot speak of the optimal solution. It is an interesting problem. $\endgroup$ – copper.hat Jul 8 '17 at 17:40
  • 1
    $\begingroup$ In the case you pointed out, all $f_i$ identical, the solution is $x_i = \frac{b}{k}$, where $k$ is the number of variables. In this case, permuting the variables doesn't produce a different solution. For example, minimize $x^2 + y^2$ subject to $x+y = b$, for non-negative $x,y$. $\endgroup$ – innerproduct Jul 8 '17 at 17:50
2
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\begingroup$ Nice! I am a big fan of sequential arguments and now I wish I'd found this proof myself. Nice use of the uniqueness of $x(b^*)$. $\endgroup$ – innerproduct Jul 8 '17 at 18:39
  • $\begingroup$ I often find that sequential arguments are quick & terse but obscure the essence of the proof. $\endgroup$ – copper.hat Jul 8 '17 at 18:41
  • $\begingroup$ Now I want to extend and generalize this fact. Baby steps: first for the case of more general bounds on $x_i$ (should be easy), then maybe $k$ linear constraints for $k \le n$, where $n$ is the number of variables (perhaps it is enough to have some $k \times k$ submatrix of the coefficients being nonsingular), then for an arbitrary number of linear constraints, $\dots$, and finally to the non-strictly convex case where one just wants a continuous selection from the set-valued map $X(\bar{b})$. $\endgroup$ – innerproduct Jul 8 '17 at 18:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.