Let $c$ and $k$ be element-wise positive $n\times 1$ vectors and let $A$ be a element-wise positive and positive-definite matrix. Consider the optimization problem \begin{align} \max_{p\in\mathbb{R}^n}&\quad c^\top p\\ \text{s.t.}&\quad p^\top Ap-k^\top p \leq 0 \\ &\quad0\leq p \leq 1 \end{align} What is the dual program of this optimization problem? I am interested only in the dual program due to theoretical motivations.


Your primal problem is equivalent to

$$ -\min_{p \in \mathbb{R}^n}\;\; - c^\top p \quad \text{s.t.} \quad p^\top A p - k^\top p \leq 0,\; p-1 \leq 0,\; -p \leq 0 $$

Then, the lagrangian function $L : \mathbb{R}^n \times \mathbb{R} \times \mathbb{R}^n \times \mathbb{R}^n$ reads

$$ \begin{align*} L(p, \lambda, \mu, \tau) &= -c^\top p + \lambda (p^\top A p - k^\top p) + \mu^\top (p - \mathbf{1})-\tau^\top p \\ &= p^\top \lambda A p - (c+\lambda k - \mu + \tau)^\top p - \mu^\top \mathbf{1} % \end{align*} $$

Next, we need $\inf_{p \in \mathbb{R}^n} L(p, \lambda, \mu, \tau)$. Since $L$ is quadratic and convex in $p$, the first order necessary condition $$ \nabla_p L = 2\lambda A p - (c+\lambda k - \mu + \tau) = 0 $$

is sufficient. Hence, since $\lambda \geq 0$, we have $$ \tilde{p} = \frac12 (\lambda A)^{\dagger} (c+\lambda k - \mu + \tau), $$ where $(\lambda A)^{\dagger}$ denotes the Moore-Penrose pseudo inverse of $\lambda A$. Note that because $A$ is symmetric and positive definite we have $(\lambda A)^{\dagger} = \frac{1}{\lambda} A^{-1}$ for $\lambda > 0$. Consequently,

$$ \begin{align*} \inf_{p \in \mathbb{R}^n} L(p, \lambda, \mu, \tau) &= L(\tilde{p}, \lambda, \mu, \tau) \\ % &= \tilde{p}^\top \lambda A \tilde{p} - (c+\lambda k - \mu + \tau)^\top \tilde{p} - \mu^\top \mathbf{1} \\ &= -\frac{1}{2} (c+\lambda k - \mu + \tau)^\top (\lambda A)^{\dagger} (c+\lambda k - \mu + \tau) - \mathbf{1}^\top \mu, \end{align*} $$

where we used $(\lambda A)^{\dagger} (\lambda A) (\lambda A)^{\dagger} = (\lambda A)^{\dagger}$. Finally, the lagrangian dual problem reads

$$ \max_{\lambda, \mu, \tau \geq 0} \quad -\frac{1}{2} (c+\lambda k - \mu + \tau)^\top (\lambda A)^{\dagger} (c+\lambda k - \mu + \tau) - \mathbf{1}^\top \mu. $$

  • $\begingroup$ Thanks for the answer. Please see if my thought process is correct. I think the primal quadratic constraint is active which should follow from complementary slackness $\lambda(p^TAp-k^Tp)=0$ Now, if $\lambda=0$, this will imply $c=\mu-\tau$ from stationarity condition. This will end up causing contradictions for the complementary slackness conditions involving $\mu$ and $\tau$. $\endgroup$ Aug 6 at 13:31

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.