2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ This is the form of the problem, because it is lenghty. $\endgroup$ – user85361 Jul 21 '15 at 6:49
  • $\begingroup$ 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? $\endgroup$ – A.Γ. Jul 21 '15 at 7:49
  • $\begingroup$ 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. $\endgroup$ – user85361 Jul 21 '15 at 9:34
  • $\begingroup$ 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. $\endgroup$ – A.Γ. Jul 21 '15 at 11:03
0
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ He didn't ask for a solution, he asked for help deriving the dual. $\endgroup$ – Michael Grant Jul 21 '15 at 13:24
  • $\begingroup$ Yes. Michael is right. I just need help in deriving the dual. I just didn't put all of the problem in the question because it's lengthy. As I mentioned in the problem it is only the form of the problem. $\endgroup$ – user85361 Jul 21 '15 at 14:33
  • $\begingroup$ @MichaelGrant, Could you please help me in this question? In case there wasn't any minimization before the sup, I just convert it to a minimization by multiplying it by minus one and it seems things comes right. But In this case I don't know what to do? $\endgroup$ – user85361 Jul 21 '15 at 14:36

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.