# What's wrong in this dual derivation?

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

• This is the form of the problem, because it is lenghty. – user85361 Jul 21 '15 at 6:49
• Your $f$ is a supremum, may be non-smooth. How come you got $\alpha$ in your derivative when $L$ does not depend on it after taking the supremum? By the way, is $\odot$ the Hadamard multiplication? – A.Γ. Jul 21 '15 at 7:49
• At first it was nested minimiziation in the form $\text{minimize}_{q,M} \text{minimize}_{\alpha}$. For some reasons, I have to first derive the dual of the inner minimization and after that derive dual of complete problem. I assumed for a single $\alpha$, in derivative of $\alpha$. I think this is wrong but I don't know how to do it. – user85361 Jul 21 '15 at 9:34
• Assume the supremum in $f$ is attained at $\alpha_0$. It depends on $M$ and $q$, i.e. $\alpha_0(M,q)$, and you have to consider derivatives of $\alpha$ in $L$ too. However, $\alpha_0$ is unlikely to be differentiable (or even continuous) due to the hyper-cube constraints. I think that derivations leads nowhere here, it is non-smooth optimization. – A.Γ. Jul 21 '15 at 11:03

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