Need help setting up and solving dual problem

Solution 1:

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.

Solution 2:

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.

Solution 3:

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