Quadratic Programming and Cone Programming

Conic Lifting and Duality: A Commutative View

This note studies a simple but important compatibility in convex optimization: taking the dual of a quadratic program directly, or first lifting it into a cone program and then dualizing, leads to the same result.

This reflects a deeper principle: conic duality and classical Lagrangian duality are consistent with each other. The conic formulation does not change the underlying problem, it only reorganizes its structure.

We demonstrate this through a minimal example.

The following figure shows the hierarchy of convex optimization problems, where linear programming lies at the most specialized level, while quadratic programming and second-order cone programming occupy more general levels above it.

Warning: Please verify all arguments in this blog carefully on your own before using them in your research.

---

1. The original quadratic program

Consider the problem

$$(P_1)\quad \min_x \; \|x\|_2^2 \quad \text{s.t. } Ax + b \in K$$

where:

• $x \in \mathbb{R}^n$
• $A \in \mathbb{R}^{m \times n}$
• $b \in \mathbb{R}^m$
• $K \subseteq \mathbb{R}^m$ is a convex cone

This is a quadratic program with a conic constraint.

---

Direct dual via Lagrangian

Introduce a dual variable $y \in K^*$. The Lagrangian is

$$L(x,y) = \|x\|_2^2 + y^T (Ax + b)$$

Minimizing over $x$:

$$\nabla_x L = 2x + A^T y = 0 \;\Rightarrow\; x^* = -\tfrac{1}{2} A^T y$$

Substituting back:

$$\|x^*\|_2^2 = \tfrac{1}{4} y^T A A^T y$$

$$y^T A x^* = -\tfrac{1}{2} y^T A A^T y$$

So the dual function becomes

$$g(y) = b^T y - \tfrac{1}{4} y^T A A^T y$$

and the dual problem is

$$(D_1)\quad \max_{y \in K^*} \; b^T y - \tfrac{1}{4} y^T A A^T y$$

---

2. Conic lifting (SOCP reformulation)

We now reformulate $(P_1)$ as a cone program.

Introduce a scalar variable $r$ and consider the epigraph form:

$$\min_{x,r} \; r \quad \text{s.t. } \|x\|_2^2 \le r,\;\; Ax + b \in K$$

---

SOC representation

The quadratic constraint can be written as a second-order cone constraint:

$$\|(2x,\; 1 - r)\|_2 \le 1 + r$$

This allows us to express everything using affine maps and cones.

---

Standard conic form

Define the variable

$$w = (x, r)$$

We rewrite the problem as

$$(P_2)\quad \min_w \; c^T w \quad \text{s.t. } \mathcal{A}w + \beta \in \mathcal{K}$$

---

Components

Objective:

$$c = (0, \dots, 0, 1)$$

---

Cone:

$$\mathcal{K} = \mathcal{Q}^{n+2} \times K$$

where $\mathcal{Q}$ is the second-order cone.

---

Affine map:

$$\mathcal{A} = \begin{pmatrix} \mathcal{A}_{\text{soc}} \\ \mathcal{A}_K \end{pmatrix}, \quad \beta = \begin{pmatrix} \beta_{\text{soc}} \\ b \end{pmatrix}$$

---

SOC block:

$$\mathcal{A}_{\text{soc}} = \begin{pmatrix} 0 & 1 \\ 2I & 0 \\ 0 & -1 \end{pmatrix}, \quad \beta_{\text{soc}} = \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix}$$

---

Cone $K$ block:

$$\mathcal{A}_K = (A \;\; 0)$$

---

At this point, the quadratic program has been rewritten as a standard conic program. No approximation has been made; this is an exact reformulation.

3. Conic dual of the lifted problem

We now take the dual of the conic program $(P_2)$:

$$(P_2)\quad \min_w \; c^T w \quad \text{s.t. } \mathcal{A}w + \beta \in \mathcal{K}$$

---

Conic duality

The standard dual of a cone program is

$$\max_z \; -\beta^T z \quad \text{s.t. } \mathcal{A}^T z + c = 0,\;\; z \in \mathcal{K}^*$$

---

Structure of the dual variables

Recall that

$$\mathcal{K} = \mathcal{Q}^{n+2} \times K$$

so

$$\mathcal{K}^* = \mathcal{Q}^{n+2} \times K^*$$

since the second-order cone is self-dual.

We split the dual variable as

$$z = (z^{\text{soc}},\; y)$$

with:

• $z^{\text{soc}} \in \mathcal{Q}^{n+2}$
• $y \in K^*$

---

Dual problem before simplification

The dual becomes

$$(D_2)\quad \max \; -\beta_{\text{soc}}^T z^{\text{soc}} - b^T y$$

subject to

$$\mathcal{A}_{\text{soc}}^T z^{\text{soc}} + \mathcal{A}_K^T y + c = 0$$

$$z^{\text{soc}} \in \mathcal{Q}^{n+2}, \quad y \in K^*$$

---

Eliminating the SOC variables

The constraint

$$\mathcal{A}_{\text{soc}}^T z^{\text{soc}} + c + \mathcal{A}_K^T y = 0$$

encodes two components:

• one corresponding to $x$
• one corresponding to $r$

From the $x$-part:

$$z^{\text{soc}}_{1:n} = -\tfrac{1}{2} A^T y$$

From the $r$-part, a linear relation ties together the scalar entries of $z^{\text{soc}}$.

The SOC constraint

$$z^{\text{soc}} \in \mathcal{Q}^{n+2}$$

then implies

$$\left\| \tfrac{1}{2} A^T y \right\|_2 \le s$$

for some scalar $s$, which appears in the objective.

Optimizing over $z^{\text{soc}}$ (i.e., choosing the smallest feasible $s$) yields

$$s = \left\| \tfrac{1}{2} A^T y \right\|_2$$

---

Reduced dual

Substituting back into the objective gives

$$(D_2)\quad \max_{y \in K^*} \; b^T y - \tfrac{1}{4} y^T A A^T y$$

---

4. Comparison of the two duals

We now compare:

• Direct dual from $(P_1)$:

$$(D_1)\quad \max_{y \in K^*} \; b^T y - \tfrac{1}{4} y^T A A^T y$$

• Conic dual from $(P_2)$:

$$(D_2)\quad \max_{y \in K^*} \; b^T y - \tfrac{1}{4} y^T A A^T y$$

Key observation

$$D_1 \equiv D_2$$

The two derivations produce exactly the same dual problem.

---

Conclusion

We have shown the following equivalence:

• Starting from the quadratic program $(P_1)$:
  • taking the dual directly yields $(D_1)$
• Alternatively:
  • lifting $(P_1)$ to a conic program $(P_2)$
  • then applying conic duality yields $(D_2)$

These two paths lead to the same result.

Commutative diagram

$$\begin{array}{ccc} P_1 & \xrightarrow{\text{Lagrangian dual}} & D_1 \\ \downarrow{\text{lift}} & & \uparrow{\text{equivalent}} \\ P_2 & \xrightarrow{\text{conic dual}} & D_2 \end{array}$$

Takeaway

• Lifting a quadratic program into a cone program does not change its dual.
• It only exposes the same structure through a different lens.