3.3 Quadratic Programming

A convex quadratic with linear constraints. SVM is the running example.

These notes walk through the lecture slides. The original deck is unchanged; use (slides) on the course hub if you want that PDF.

The notes follow Deisenroth, Faisal, and Ong, Mathematics for Machine Learning.

1. Quadratic cost, linear constraints

A quadratic program keeps linear inequalities and lets the objective be quadratic. That is the next step past an LP: nonlinear models whose cost is a bowl, plus the same polyhedron as before.

This is also how regularization enters: a quadratic penalty on $θ$ is still a QP when the constraints stay linear. Soft-margin SVM is the example this course cares about.

{min}_{θ \in ℝ^{d}} \frac{1}{2} θ^{⊤} Q θ + 𝐜^{⊤} θ subject to A θ \leq 𝐛,

with $A \in ℝ^{m \times d}$ , $𝐛 \in ℝ^{m}$ , $𝐜 \in ℝ^{d}$ , and $Q \in ℝ^{d \times d}$ symmetric positive definite. Then the objective is convex, so a local min is the unique global min. Still $d$ variables and $m$ linear constraints.

2. Dual

Lagrangian

ℒ (θ; λ) = \frac{1}{2} θ^{⊤} Q θ + 𝐜^{⊤} θ + λ^{⊤} (A θ - 𝐛) .

Stationarity in $θ$ :

Q θ + (𝐜 + A^{⊤} λ) = 0 .

If $Q$ is invertible,

θ = - Q^{- 1} (𝐜 + A^{⊤} λ) .

Substitute back. The dual Lagrangian is the concave quadratic

D (λ) = - \frac{1}{2} (𝐜 + A^{⊤} λ)^{⊤} Q^{- 1} (𝐜 + A^{⊤} λ) - λ^{⊤} 𝐛 .

The dual problem is therefore

{max}_{λ \in ℝ^{m}} - \frac{1}{2} (𝐜 + A^{⊤} λ)^{⊤} Q^{- 1} (𝐜 + A^{⊤} λ) - λ^{⊤} 𝐛 subject to λ \geq 0 .

Week 5 does the same substitution for the SVM dual, then replaces inner products by a kernel.

3. Why SVM is a QP

Soft-margin SVM:

{min}_{θ \in ℝ^{l}} & \frac{1}{2} ‖ θ ‖^{2} + C \sum_{n = 1}^{N} ξ_{n} subject to & y_{n} (x_{n}^{⊤} θ + b) \geq 1 - ξ_{n}, ξ_{n} \geq 0 .

$θ$ : hyperplane weights.
$C$ : trade-off between margin size and slack.
$ξ_{n}$ : slack; a point may sit on the wrong side of the margin, at a linear cost.

Quadratic objective, linear inequalities: a QP, not an LP, because of $‖ θ ‖^{2}$ .

4. Practice

Why is a soft-margin SVM a quadratic program?
What does $Q$ positive definite buy you that a general quadratic objective does not?
After $θ = - Q^{- 1} (𝐜 + A^{⊤} λ)$ , what variables does the dual still optimize, and what constraint remains on them?

Ahmad Mousavi

1. Quadratic cost, linear constraints

2. Dual

3. Why SVM is a QP

4. Practice