3
$\begingroup$

Consider the following quadratic program

$$\begin{align*}&\text{min } \frac{1}{2}b^TDb+d^Tb\\ &\text{s.t. } Ab\le b_0\end{align*}$$ where $D$ is a positive semidefinite matrix.

The Lagrangian dual function is written as follows

$$\begin{align*}L(b,\lambda)&=\frac{1}{2}b^TDb+d^Tb+\lambda^T(Ab-b_0)\\ &=\frac{1}{2}b^TDb+(d^T+\lambda^TA)b-\lambda^Tb_0 \end{align*}$$

Then I got stuck on finding the dual of the problem.

Similar background problem:

$\endgroup$
1
$\begingroup$

Informally, the approach is to swap the $\inf$, $\sup$ to convert from the primal to the dual.

With the Lagrangian above, the primal is $P: \ \inf_b \sup_{\lambda \ge 0} L(b,\lambda)$, hence we go ahead and swap the $\inf$, $\sup$ to get the dual, that is $D:\ \sup_{\lambda \ge 0} \inf_b L(b,\lambda)$.

Note that $\inf_b L(b,\lambda)$ is finite iff the convex function $b \mapsto L(b,\lambda)$ has a (global) minimiser iff there is some $b$ such that $Db + d +A^T \lambda = 0$, hence we can write $D:\ \sup_{\lambda \ge 0} \inf_{\{b | Db + d +A^T \lambda = 0\}} | L(b,\lambda)$.

The expression $L(b,\lambda)$ can be simplified using the pseudo inverse of $D$ and the fact that if $Db + d +A^T \lambda = 0$, then $b = - D^\dagger (A^T \lambda + d)$. This results in semi definite quadratic program.

$\endgroup$
  • $\begingroup$ how do you then from the dual function formulate the dual problem? I'm working on this problem here: math.stackexchange.com/questions/2550644/… which is looking like it might be the exact same question the OP asked here. $\endgroup$ – ALannister Dec 4 '17 at 15:43
  • $\begingroup$ actually, I just realized that the question I linked to is not regarding the same exact problem. My problem is a little different, and so if you could take a look and offer some help, I would be most appreciative! You always give such instructive answers. $\endgroup$ – ALannister Dec 4 '17 at 15:54

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.