# Dual of quadratic program with linear objective

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

• 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$. Aug 6, 2021 at 13:31