2
$\begingroup$

Given the set $T_{\alpha}=\{x\in\mathbb{R}^n:\sum x_i=1,0\leq x_i\leq \alpha\}$
For which $\alpha$ the set is non-empty?
Find a dual problem with one dual decision variable to the problem of finding the orthogonal projection of a given vector $y ∈\mathbb{R}^n$ onto $T_α$.

I found that $\alpha\geq1/n$ and when i tried to calculate the dual function I did the following.
$\min$ $||x-y||^2$
s.t
$\sum x_i=1$
$0\leq x_i\leq\alpha\to X=\{x:0\leq x_i\leq\alpha\}$
Setting the lagrangian to be $L(x,\lambda)=||x-y||^2+2\lambda(\sum x_i-1)$,we would like to minimize the lagrangian w.r.t x then :
$$\underset{x\in X}{\min}L(x,\lambda)=\sum x_i^2+2(\lambda-y_i)x_i+||y||^2-2\lambda$$
$$\frac{\partial L}{\partial x_i}=2x_i+2(\lambda-y_i)=0\to x_i^*=\left\{\begin{array}{rcl} y_i-\lambda&0\leq y_i-\lambda\leq\alpha\\ \alpha&y_i-\lambda>\alpha\\ 0&y_i-\lambda<0\end{array}\right.$$
and the dual function is $q(\lambda)=-2\lambda+||y||^2+\left\{\begin{array}{rcl}n\alpha^2+2n\alpha\lambda-2\alpha\sum y_i&y_i-\lambda>\alpha\\ -\sum [y_i-\lambda]_+^2&\mbox{else}\end{array}\right.$ and the derivative of $q$ is:
$$q'(\lambda)=-2+\left\{\begin{array}{rcl}2n\alpha &y_i-\lambda>\alpha\\ 2\sum[y_i-\lambda]_+^2&\mbox{else}\end{array}\right.$$

I'm not sure if I've found the right dual function and if I've found the right derivative and write matlab code that solves the dual and finds the projection of $y$

$\endgroup$
7
  • $\begingroup$ I am curious where this problem came from? $\endgroup$ – copper.hat Jan 5 at 4:22
  • 1
    $\begingroup$ "introduction to nonlinear optimization amir beck" question 12.22 $\endgroup$ – convxy Jan 5 at 5:18
  • $\begingroup$ I am probably wrong here, but it seems unlikely to me that there is a 'nice' one dual variable problem corresponding to this. $\endgroup$ – copper.hat Jan 5 at 6:57
  • $\begingroup$ Maybe you're right but I think I found the right one (maybe it's not a nice one tho)and after I find the dual problem I need to solve the dual with matlab but thats afterwards.@copper.hat $\endgroup$ – convxy Jan 5 at 7:04
  • $\begingroup$ Practically, I think I would project on to $e^T x = 1$ first, then onto $0 \le x_k \le 1$ and then onto $0 \le x_k \le \alpha$. But that does not really help you. $\endgroup$ – copper.hat Jan 5 at 7:06
1
$\begingroup$

This is basically Projection onto the Simplex with some modifications.
The problem is given by:

$$ \begin{alignat*}{3} \arg \min_{x} & \quad & \frac{1}{2} \left\| x - y \right\|_{2}^{2} \\ \text{subject to} & \quad & 0 \leq {x}_{i} \leq \alpha \\ & \quad & \boldsymbol{1}^{T} x = 1 \end{alignat*} $$

The problem is valid for $ \alpha \geq \frac{1}{n} $ otherwise the constraint $ \boldsymbol{1}^{T} x = 1 $ isn't feasible.
For $ \alpha \geq 1 $ the problem matches the Projection onto the Simplex as the upper boundary can not be an active constraint (Well it is for 1, but then it is equivalent for the equality constraint and the non negativity).

The Lagrangian in that case is given by:

$$ \begin{align} L \left( x, \mu \right) & = \frac{1}{2} {\left\| x - y \right\|}^{2} + \mu \left( \boldsymbol{1}^{T} x - 1 \right) && \text{} \\ \end{align} $$

The trick is to leave non negativity constrain implicit.
Hence the Dual Function is given by:

$$ \begin{align} g \left( \mu \right) & = \inf_{0 \leq {x}_{i} \leq \alpha} L \left( x, \mu \right) && \text{} \\ & = \inf_{0 \leq {x}_{i} \leq \alpha} \sum_{i = 1}^{n} \left( \frac{1}{2} { \left( {x}_{i} - {y}_{i} \right) }^{2} + \mu {x}_{i} \right) - \mu && \text{Component wise form} \end{align} $$

Taking advantage of the Component Wise form the solution is given:

$$ \begin{align} {x}_{i}^{\ast} = { \left( {y}_{i} - \mu \right) }_{0 \leq \cdot \leq \alpha} \end{align} $$

Where the solution includes the inequality constrains by Projecting onto the box $ \mathcal{B} = \left\{ x \mid 0 \leq {x}_{i} \leq \alpha \right\} $.

The solution is given by finding the $ \mu $ which holds the constrain (Pay attention, since the above was equality constrain, $ \mu $ can have any value and it is not limited to non negativity as $ \lambda $).

The objective function (From the KKT) is given by:

$$ \begin{align} 0 = h \left( \mu \right) = \sum_{i = 1}^{n} {x}_{i}^{\ast} - 1 & = \sum_{i = 1}^{n} { \left( {y}_{i} - \mu \right) }_{0 \leq \cdot \leq \alpha} - 1 \end{align} $$

The above is a Piece Wise linear function of $ \mu $.

Since the function is continuous yet it is not differentiable due to its piece wise property theory says we must use derivative free methods for root finding. One could use the Bisection Method for instance.

MATLAB Code

I wrote a MATLAB code which implements the method with Bisection Root Finding. I verified my implementation vs. CVX. The MATLAB Code which is accessible in my StackExchange Mathematics Q3972913 GitHub Repository.

$\endgroup$
3
  • $\begingroup$ Thanks,So I see that is more or less they way I've done :),and could you see why the code here doesn't give the right answer?github.com/ronkurman/matlab $\endgroup$ – convxy Jan 5 at 15:43
  • $\begingroup$ I added a reference code. You may have a look. Please keep +1 answers which are valuable to you. $\endgroup$ – Royi Jan 5 at 23:50
  • $\begingroup$ Which part of it looks non differnetiable? $\endgroup$ – Royi Jan 8 at 18:24
0
$\begingroup$

Adding to @Royi 's answer,

The Lagrangian is: $$\mathcal L(\mu) = \sum_{i=1}^n ({\left( {y}_{i}-\mu \right)}_{0 \leq \cdot \leq \alpha}^2 -2(y_i-\mu){\left( {y}_{i}-\mu \right)}_{0 \leq \cdot \leq \alpha}) + ||y||_2^2-2\mu $$

From duality, we know this function is concave. It is also $\to -\infty$ as $\mu \to \infty$ (sum becomes zero, and $-2\mu\to -\infty$) and as $\mu \to -\infty$ (square in the sum is finite;$||y||_2^2$ is finite; we end up with $\mu(2\alpha n-2)$ but since $\alpha > \frac{1}{n}$ then $2\alpha n-2>0$). It is continuous. The question is - is it differentiable?

We note that while $[x]_{0 \leq \cdot \leq \alpha}^2$ is not differentiable, $[x]_{0 \leq \cdot \leq \alpha}^2 - 2x[x]_{0 \leq \cdot \leq \alpha}$ surprisingly is! For $x < 0$ the term is $=0$ and so the derivative is $0$. For $x>\alpha$ we get $\alpha^2-2\alpha x$, whose derivative is $-2\alpha$. For $0 < x < \alpha$ we get $x^2-2x^2=-x^2$, whose derivative is $-2x$. This goes to $0$ as $x\to 0$ and goes to $-2\alpha$ as $x\to \alpha$. Hence the Lagrangian is also differentiable! And the derivative is $- 2[x]_{0 \leq \cdot \leq \alpha}$.

So the dual problem is to find the maximum of the Lagrangian, under $\mu\in\mathbb R$ (as it is an equality constraint). From all of the above, if we differentiate and equate to zero we will find the maximum of this dual problem. Differentiating and equating to zero, we get: $$\mathcal L' = \sum_{i=1}^n -2{\left( {y}_{i}-\mu \right)}_{0 \leq \cdot \leq \alpha}(-1) -2 = 0 \Rightarrow \sum_{i=1}^n {\left( {y}_{i}-\mu \right)}_{0 \leq \cdot \leq \alpha} -1 = 0 $$

Which is the h function in Royi's answer.

$\endgroup$

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.