4
$\begingroup$

I need to solve the quadratic programming problem $$ \text{minimize}\,\, \sum_{j=1}^{n}(x_{j})^{2} \\ \text{subject to}\,\,\, \sum_{j=1}^{n}x_{j}=1,\\ 0 \leq x_{j}\leq u_{j}, \, \, j=1,\cdots , n $$

I know that the first thing I need to do is form the Lagrangian.

Now, for a problem in standard form (note that below, $\overline{x}$, $\overline{\lambda}$, $\overline{\mu}$ denote vectors): $$ \text{minimize} \, \, f_{0}(\overline{x}) \\ \text{subject to} \,\,\, f_{i}(\overline{x}), \,\,\, i=1,\cdots, m \\ h_{i}(\overline{x}), \,\,\, i = 1,\cdots, p $$ the Lagrangian looks like this: $\displaystyle L(\overline{x},\overline{\lambda}, \overline{\mu}) = f_{0}(x) + \sum_{i=1}^{m}\lambda_{i}f_{i}(\overline{x}) + \sum_{i=1}^{p}\mu_{i}h_{i}(\overline{x})$

In this case, I am being thrown off by the fact that my sole $h_{i}(\overline{x})$ happens to be a sum that adds up to $1$, and if I want my $f_{i}(\overline{x})$'s to be $\leq 0$, I'm going to need to rewrite the last line of constraints as $x_{j} - u_{j} \leq 0$, $j = 1,\cdots , n$ and $-x_{j} \leq 0$, $j = 1, \cdots, n$.

Then, would my Lagrangian be $\displaystyle L(\overline{x},\overline{\lambda}, \overline{\mu}) = \sum_{j=1}^{n}(x_{j})^{2} + \sum_{j=1}^{n}\lambda_{i}(x_{j}-u_{j}) + \sum_{j=1}^{n}\nu_{i} (-x_{i}) + \mu\left[\left(\sum_{j=1}^{n}x_{j} \right)-1\right]$ ?

And then, how would I go about completing the problem? I've never done a problem with this many Lagrange variables in it before, nor with this many constraints, and so I'm finding it a little overwhelming...

Thank you ahead of time for your time and patience!

$\endgroup$
  • $\begingroup$ You missed $n$ inequality constraints: $-x_j \le 0$. $\endgroup$ – Math Lover Dec 17 '17 at 21:53
  • $\begingroup$ @MathLover where? I thought that would have been included in the $x_{j}-u_{j}$'s... $\endgroup$ – ALannister Dec 17 '17 at 21:54
  • $\begingroup$ What does $0 \le x_j \le u_j$ mean? $\endgroup$ – Math Lover Dec 17 '17 at 21:55
  • $\begingroup$ It means that $\forall j$, $u_{j} \geq x_{j}$, and since $x_{j} \geq 0$ $\forall j$, if I subtract from each $x_{j}$ its corresponding $u_{j}$, I will get constraints that are $\leq 0$, like I need in order for this problem to be of standard form. I understand what you mean by having $- x_{j} \leq 0$, but doing this does not take into account that each $x_{j}$ is bounded above by something. Is that unimportant? $\endgroup$ – ALannister Dec 17 '17 at 21:58
  • 1
    $\begingroup$ @MathLover: the inequalities do not go into the Lagrangian. The boundaries of the inequalities form new constraints for a lower dimensional Lagrangian. $\endgroup$ – robjohn Dec 24 '17 at 6:01
3
+100
$\begingroup$

Basic Variational Approach

Since $$ \sum_{j=1}^nx_j=1\tag1 $$ any variation of the $x_j$'s must satisfy $$ \sum_{j=1}^n\delta x_j=0\tag2 $$ At an interior critical point of $$ \sum_{j=1}^nx_j^2\tag3 $$ we will have $$ \sum_{j=1}^n2x_j\delta x_j=0\tag4 $$ At an interior critical point, any change that maintains $(1)$ should not change $(3)$. That is, for any $\delta x_j$ that satisfies $(2)$, $\delta x_j$ should satisfy $(4)$.

Note that $(2)$ says that $(\delta x_1,\delta x_2, \delta x_3,\dots,\delta x_n)$ is perpendicular to $(1,1,1,\dots,1)$, and that is the only restriction on $\delta x_j$, unless $x_j=0$ or $x_j=u_j$ (the edge cases). Furthermore, $(4)$ is satisfied when $(\delta x_1,\delta x_2, \delta x_3,\dots,\delta x_n)$ is perpendicular to $(x_1,x_2,x_3,\dots,x_n)$. This means that any $(\delta x_j)$ that is perpendicular to $(1,1,1,\dots,1)$ is perpendicular to $(x_1,x_2,x_3,\dots,x_n)$. That is, $(1,1,1,\dots,1)$ is parallel to $(x_1,x_2,x_3,\dots,x_n)$.

Thus, the only interior critical points happen when $$ x_1=x_2=x_3=\dots=x_n=\lambda\tag5 $$ In light of $(1)$, this means that $$ (x_1,x_2,x_3,\dots,x_n)=\tfrac1n\left(1,1,1,\dots,1\right)\tag6 $$ We also need to check the edge cases where some $x_j=0$ or some $x_j=u_j$. In those cases, we still have the analog of $(5)$ for the interior $x_j$; that is, those for which $0\lt x_j\lt u_j$.


Lagrangian Approach

The Lagrangian would be $$ \mathcal{L}(x_1,x_2,x_3,\dots,x_n,\lambda)=\sum_{j=1}^nx_j^2-\lambda\left(\sum_{j=1}^nx_j-1\right)\tag7 $$ Taking the gradient this locates the interior critical points $$ \begin{align} 0 &=\nabla\mathcal{L}(x_1,x_2,x_3,\dots,x_n,\lambda)\\ &=\left(2x_1-\lambda,2x_2-\lambda,2x_3-\lambda,\dots,2x_n-\lambda,\sum_{j=1}^nx_j-1\right)\tag8 \end{align} $$ which we can solve to get $(6)$.

There are $2n$ $n-1$ dimensional edges, where $x_j=0$ and $x_j=u_j$, and a number of corners, etc. that need to be considered separately. They are not handled in the $n$-dimensional Lagrangian, though we can consider separate $n-1$ dimensional Lagrangians.

$\endgroup$
  • $\begingroup$ I think your answer is useful, but it would be more useful contextualized within the framework of the work I did on my own in my original post. Nobody has done that so far, which is really what I am looking for in order to accept and award. More importantly though it's what I need in order to finally understand! $\endgroup$ – ALannister Dec 23 '17 at 20:55
  • $\begingroup$ I have to admit to you that I still don't have this problem completely figured out. I was able to form the $n-1$ dimensional Lagrangian and find the general form for critical points when some of the $x_{j}=0$ (they would not be optimal though, because the more indices where the $x$'s $=0$, the larger the value of the objective function. How do I approach it in the case where some of the $x_{j} = u_{j}$? As in, how do I form the $n-1$ dimensional Lagrangian for it and find the critical points? $\endgroup$ – ALannister Jan 7 '18 at 20:55
  • $\begingroup$ @ALannister: It's just the same as the case when some of the $x_j=0$. For example, if $x_1=u_1$ and $x_2=u_2$, then the problem becomes to minimize $$\sum_{j=3}^nx_j^2$$ under the constraint $$\sum_{j=3}^nx_j=1-u_1-u_2$$ $\endgroup$ – robjohn Jan 7 '18 at 21:03
  • $\begingroup$ I'm going to have to work through that case. You know, originally, when I was given this problem to work on, I was told as a hint: "use duality", but I honestly cannot see how duality can help us. Also, the way we're doing it here, are the cases where some of the $x_{j}=u_{j}$ also not going to be optimal? $\endgroup$ – ALannister Jan 7 '18 at 21:07
  • $\begingroup$ @ALannister: the Lagrangian method only finds internal extrema. The boundary extrema have to be checked separately. It may be that the extremum we want is an internal one and none of the edge cases are what we want. However, we still need to check them or account for them some other way. $\endgroup$ – robjohn Jan 7 '18 at 21:28
1
$\begingroup$

The primal problem is $\inf_x \sup_{\mu, \lambda \ge 0, \nu \ge 0 } L(x,\lambda, \nu, \mu)$, the dual is $ \sup_{\mu, \lambda \ge 0, \nu \ge 0 }\inf_x L(x,\lambda, \nu, \mu)$.

Since ${\partial L(x,\lambda, \nu, \mu) \over \partial x} = 2x + \lambda - \nu + \mu e$, where $e=(1,1,...)^T$, we can compute an explicit expression for the minimising $x$ and so compute a formula for $\inf_x L(x,\lambda, \nu, \mu)$.

$\endgroup$
  • $\begingroup$ I don't understand how that can be the partial w.r.t. $x$. What about all the summations? Where did they go? Unless this is the partial w.r.t. $x_{i}$ for some $i$? Then, the derivatives of the other ones would equal $0$? $\endgroup$ – ALannister Dec 18 '17 at 3:55
  • 1
    $\begingroup$ The summations didn't go away. If you prefer, compute ${\partial L(x,\lambda, \nu, \mu) \over \partial x_k}$ instead. Since $x \mapsto L(x,\lambda, \nu, \mu) $ is a (positive definite) quadratic, the function has a unique minimiser at the value of $x$ for which the derivative is zero. $\endgroup$ – copper.hat Dec 18 '17 at 4:19
  • $\begingroup$ okay, so $\frac{\partial L(x ,\lambda, \nu,\mu)}{\partial x_{k}} = 2x_{k}+\lambda_{k}-\nu_{k}+\mu$, and then $\nabla_{x}L(x,\lambda, \nu, \mu) = 2x + \lambda - \nu + \mu e$, where $e = \begin{pmatrix} 1 \\ 1 \\ 1 \\ \vdots \\ 1 \end{pmatrix}$. Then, $2x + \lambda - \nu + \mu e = 0$ implies that $x = \frac{1}{2}\nu - \frac{1}{2}\lambda - \frac{1}{2}\mu e$. So, how do I substitute this into my Lagrangian so that I can obtain the dual problem? Also, since $0 \leq x_{j}$ $\forall j$, does $x = \frac{1}{2}\nu - \frac{1}{2}\lambda - \frac{1}{2}\mu e$ imply that $\lambda + \mu e \leq\nu$? $\endgroup$ – ALannister Dec 18 '17 at 4:38
  • $\begingroup$ okay, if I can't finish figuring this out by myself today, tomorrow I'll post a bounty. $\endgroup$ – ALannister Dec 18 '17 at 18:18
  • 1
    $\begingroup$ Hi @ALannister: First, if the $u_i$'s are large, then the solution is $\tfrac{1}{n}\mathbf{e}_n$, where $\mathbf{e}_n$ is the vector of all $1$'s in $\mathbb{R}^n$. Second, view your problem as a projection problem: you want to project the origin onto the intersection of the box with the hyperplane with normal vector $\mathbf{e}_n$ and offset value $1$. $\endgroup$ – max_zorn Dec 23 '17 at 6:51
1
$\begingroup$

I ran into space limitations, so here is what I wanted as a comment:

Hi @ALannister:

1] if the $u_i$'s are large, then the solution is $\tfrac{1}{n}\mathbf{e}_n$, where $\mathbf{e}_n$ is the vector of all $1$'s in $\mathbb{R}^n$.

2] view your problem as a projection problem: you want to project the origin onto the intersection of the box with the hyperplane with normal vector $\mathbf{e}_n$ and offset value $1$.

3] For notational convenience, assume $u_1\leq u_2\leq\cdots\leq u_n$.

4] As you blow up the ball (intersected with the nonnegative orthant), it will either hit first the hyperplane or the boundary of the box you are given.

5] If it hits the hyperplane first, then you are done (the problem is really unconstrained).

6] If you hit the box boundary first, you will hit it at $x_1=u_1$. This value is now fixed.

7] The remaining variables $x_2,\ldots x_n$ are now in a box of one less dimension, and the hyperplane has now normal vector $\mathbf{e}_{n-1}$, the all-ones in $\mathbb{R}^{n-1}$, and the offset is $1-u_1$.

8] Repeat this argument until you are done. This leads to your solution.

I suspect this is known. Is this a homework in a book? If so, please let us know from where this problem comes from, it is neat.

$\endgroup$
  • $\begingroup$ it's homework, but it's not from a book. These comments are interesting, and essentially are spoilers as to what the final answer is, but it's not really what I was looking for. I was looking for something to help me bridge the gap between $L(\frac{1}{2}\left( \nu - \lambda - \mu e \right), \lambda, \nu, \mu)$ and the final answer. For one thing, once I have this expression for $L$, I don't know what the dual is. I need to express that explicitly. $\endgroup$ – ALannister Dec 23 '17 at 7:04
  • $\begingroup$ can you give me any pointers in that regard? $\endgroup$ – ALannister Dec 23 '17 at 7:05
  • $\begingroup$ I suggest you look at the proof of how one projects onto the $r$-simplex, which corresponds to the case when $u_i\equiv +\infty$ but the hyperplane offset if $=r$. In Lange's book MM Optimization Algorithms, Example 5.3.2, you find this done with Lagrange multipliers, you find the solution and the values of the multipliers. You can regard this as a "subproblem" of what I outlined and adjust accordingly. I would still think this is known and published somewhere, please report back once you get the solution. Thanks and good luck! $\endgroup$ – max_zorn Dec 23 '17 at 7:16
  • $\begingroup$ PS: Lange points to a paper by Duchi, Shalev-Shwartz, Singer and Chandra from 2002 entitled "Efficient projection onto the $\ell_1$-ball for learning in high dimensions." $\endgroup$ – max_zorn Dec 23 '17 at 7:19
  • $\begingroup$ that's very interesting, but I don't it's going to help me. Thanks anyway. $\endgroup$ – ALannister Dec 23 '17 at 7:19

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.