What's wrong in this dual derivation?

169 Views Asked by At

I have a function in the form \begin{align} f(q,M)=\sup_{0\leq \alpha \leq 1} -\alpha^T (R\odot M)\alpha+\alpha^Tq \end{align} which is a dual of a minimization problem, where $R$ and $M$ are positive semidefinite matrices, and $\alpha$ and $q$ are vectors of length,$n$. Now I have a minimization problem, in the following form \begin{align} \text{minimize }_{q,M} &f(q,M)+\frac{1}{2} \Vert q \Vert^2\cr \text{s.t.} & M \succeq q q^T \end{align} I compute the lagrangian of the problem, \begin{align} \mathsf{L}=f(q,M)+\frac{1}{2} \Vert q \Vert^2-tr(\begin{bmatrix} Z,z\\z^T,v\\ \end{bmatrix}\begin{bmatrix} M,q\\q^T,1\\ \end{bmatrix}) \end{align} My question is how to derive $\frac{\partial}{\partial M}L$. Because when I want to derive it,I got the following, which is contradictory because $\alpha \alpha^T\odot R$ and $Z$ are positive semidefinite. What is wrong? \begin{align} \frac{\partial}{\partial M}L=-\alpha \alpha^T\odot R -Z = 0 \end{align} I wrote the problem in this equivalent form, \begin{align} \text{minimize }_{t,q,M} &t+\frac{1}{2} \Vert q \Vert^2\cr \text{s.t.} & M \succeq q q^T\cr &t\geq -\alpha^T (R\odot M)\alpha+\alpha^Tq \end{align} Now, The lagrangian can be written for the above problem using standard techniques, \begin{align} \mathsf{L}(t,q,M;Z,z,v,u,w,s)&=t+\frac{1}{2} \Vert q \Vert^2-tr(\begin{bmatrix} Z,z\\z^T,v\\ \end{bmatrix}\begin{bmatrix} M,q\\q^T,1\\ \end{bmatrix})+u(-\alpha^T (R\odot M)\alpha+\alpha^Tq-t)\cr &=(1-u)t+\frac{1}{2} \Vert q \Vert^2-tr((Z+u(R\odot \alpha\alpha^T))^TM)-2 z^T q -v+uq^T \alpha \end{align} Still the same problem exists.
Please notice that I want to know how to derive the dual correctly. The problem is feasible and bounded. But the above analysis suggest it's not. Also, a question similar to this but about a different problem asked here

1

There are 1 best solutions below

3
On

Note that $\alpha=0$ is feasible and gives $-\alpha^T (R\odot M)\alpha+\alpha^Tq=0$ $\quad\Rightarrow\quad$ $f(q,M)\ge 0$ $\quad\Rightarrow\quad$ $g(q,M)=f(q,M)+\frac12\|q\|^2\ge 0$ $\quad\Rightarrow\quad$ $\min\, g(q,M)\ge 0$.

Now take $q=0$ $\quad\Rightarrow\quad$ $f(0,M)=0$ $\quad\Rightarrow\quad$ $g(0,M)=0$.

Conclusion: the minimum is zero, attained at $(0,M)$ for any positive semi-definite $M$.