Dual of quadratic program with linear objective

Question

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.

Answer 1

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