../

2026-10-08 CVXOPT Scribe

Review of last week’s contents

Suppose you had any optimization problem (not necessarily convex) $$\text{minimize } f_o(x)$$ $$\text{subject to } f_i(x) \le 0, i=1,\ldots,m$$ $$h_j(x) = 0, j=1,\ldots,m$$

Lagrangian

We can define a Lagrangian for this as follows

$$\mathcal{L}(x, \lambda, \nu) = f_0(x) + \sum_i \lambda_i f_i (x) + \sum_j \nu_j h_j (x)$$

TODO(dbk): We saw that the gradients are parallel

Lagrangian Dual function

If you have a Lagrangian, you can define a new function which eliminates the original variable $x$ as

$$g(\lambda, \nu) = \inf_{x\in\mathbf{dom}f_o} { L(x, \lambda, \nu) }$$

Lagrange Dual Optimization Problem

$g$ is always concave in $\lambda, \nu$, regardless of $f$. This is because it is a point-wise minimum over a bunch of affine functions.

We form an optimization problem on the Lagrangian dual as follows

$$\text{maximize}\quad g(\lambda, \nu)$$ $$\text{subject to}\quad \lambda \succeq 0$$

We call this a dual because, maximizing this is equivalent* to minimizing the original function $f$

We don’t have to put any constraints on $\nu$ as any optimal solution would have to be feasible rendering $\nu$’s multiplicative pair 0 which allows $\nu$ to unconstrained.

We call $(\lambda^, \nu^)$ the optimal lagrange mulipliers

Lower Bounding Property

If $p^$ is the minimal value of the primal problem, then we can say that $$p^ \ge d^$$ i.e $$f_0(x^) \ge g(\lambda^, \nu^)$$ Moreover For any $\lambda, \nu$, we have $$g(\lambda, \nu)\le p^*$$

We call this property as weak duality. This holds for any optimization problem.

The difference $p^* - d^*$ is called the duality gap and when the gap is 0, we call it strong duality

Strong Duality

Strong duality is so good to have. If you have strong duality then you can solve the problem very easily by maximizing the Lagrangian dual (by virtue of being concave is efficiently solvable). But most problems don’t have strong duality. But for convex functions the duality most often holds. We will see the condition for when they hold. You can write entire textbooks about the conditions when strong duality holds, we will just see the most popular ones.

Slater’s Constraint Qualifications

Theorm 1: Slater’s Constraint Qualifications

  1. Primal is Convex
  2. $\exists \tilde{x}$ such that $f_i(x) \lt 0, \forall i$ and $h_j(x) = 0, \forall j$. This essentially says that there exists an $x$ that is strictly feasible
  3. If $f_i(x)$ is affine i.e $c_i^T x + d \le 0$, then we don’t care about strict inequality

That’s it. This may seem very weak and that is the point. If a function is convex then strong duality holds almost all the time.

Examples: Linear Program

Primal

$$\text{minimize } c^Tx$$ $$\text{subject to } Ax = b$$ $$x \succeq 0$$

Dual

$$\text{maximize } g(\lambda, \nu) = \text{maximize } b^T\nu $$ $$\text{subject to } c + A^T\nu \succeq 0$$

Though this is not in the standard form, you can easily convert it to be.

Strong duality?

  1. Primal is feasible $\implies Ax-b = 0 \implies b \in Ra(A)$
  2. We have any inequalities.

Hence we have strong duality if $b$ is in the column space of $A$

Example: Least Norm Solution of a Linear System

$$\text{minimize }\frac{1}{2}x^Tx$$ subject to $$Ax - b = 0$$