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$
$\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-\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 I need to write a Matlab code that solves the dual problem and afterwards returns x


1 Answer 1


I've checked my answer and it works. Here is a Matlab code that I've written.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.