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

$\endgroup$
4
  • $\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, 2017 at 17:13
  • $\begingroup$ True. However, note that linear functions are not strictly convex. $\endgroup$ Jul 8, 2017 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, 2017 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$ Jul 8, 2017 at 17:50

1 Answer 1

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

$\endgroup$
3
  • $\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$ Jul 8, 2017 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, 2017 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$ Jul 8, 2017 at 18:48

You must log in to answer this question.

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