For $w_i\ge 0$ and some constants $\alpha_i , i=1,...,n$, what is the maximum and minimum of $\sum_{i=1}^{n}\alpha_i w_i$ subjected to $\sum_{i=1}^{n}w_i=1$? Intuitively, I put all weight on the maximum and minimum among $\alpha_i$ to get the maximum and minimum of the weighted sum respectively. That is, $$\max_{w_i} \sum_{i=1}^{n}\alpha_i w_i = \max_{i}(\alpha_i)$$ and $$\min_{w_i} \sum_{i=1}^{n}\alpha_i w_i = \min_{i}(\alpha_i)$$

However, I cannot give the rigorous proof for this. I have tried Lagrange multiplier method on $\sum_{i=1}^{n}w_i=1$ but how about the $w_i\ge 0, i=1,...,n$? What is the rigorous way to prove this question?


Lagrange multipliers work on the interior of regions. This is a linear function on the region $$ \left\{(w_k):\sum_kw_k=1,w_k\ge0\right\} $$ The extremes occur on the boundary of this region. Depending on the dimension. In the usual case, you should try Lagrange multipliers on the lower dimensional "faces", then "edges" of the region (places where one or more of the $w_k=0$). However, again, this would be a linear function on those lower dimensional regions; in the end, the extremes are going to occur at one of the vertices with all but one of the $w_k=0$. That is at the maximum and minimum $\alpha_k$.

Alternate Approach

Note that since $w_k\ge0$ and $\sum\limits_kw_k=1$, $$ \begin{align} \left(\sum_k\alpha_kw_k\right)-\alpha_\text{min} &=\sum_k(\alpha_k-\alpha_\text{min})w_k\\ &\ge0 \end{align} $$ and $$ \begin{align} \alpha_\text{max}-\sum_k\alpha_kw_k &=\sum_k(\alpha_\text{max}-\alpha_k)w_k\\ &\ge0 \end{align} $$


Here's the Lagrange multiplier argument (and switching to $x$ instead of $w$): The problem is standard linear programming: $$ \min \alpha^T x $$ subject to simplex constraints $x \ge 0$ and $\mathbf{1}^T x = 1$. The Lagrangian is $$ L(x, \lambda, \nu) = \alpha^T x - \lambda^T x + \nu (\mathbf{1}^T x - 1) = -\nu + (\alpha - \lambda + \nu \mathbf{1})^Tx $$ Minimizing w.r.t to $x$ gives the dual function $$ g(\lambda, \nu) = \inf_x L(x, \lambda, \nu) = -\nu $$ if $\nu \mathbf{1} - \lambda + \alpha=0$, otherwise unbounded below, since $L$ is a linear function of $x$. The dual problem is therefore $$ \max g(\lambda, \nu) = -\nu $$ subject to $\lambda = \nu \mathbf{1} + \alpha \ge 0 $, where I've plugged in dual feasibility condition $\nu \mathbf{1} - \lambda + \alpha=0$.

Note the dual constraint $\nu \mathbf{1} + \alpha \ge 0 $, or $ -\nu \mathbf{1} \le \alpha$, is a vector inequality, equivalent to $\forall \alpha_i, -\nu \le \alpha_i$, in other words $-\nu \leq \min_i \alpha_i$, so the dual solution is found at the smallest coordinate of $\alpha$.

The argument for $\max \alpha^T x$ follows similarly.


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.