# Lagrange duality

This page just lists the basic properties for reference, and does not give any intuition or proofs. This is based on chapter 5 of Boyd and Vandenberghe’s (outstanding) Convex Optimization. I have emphasized the terminology here because this is necessary to read most work using Lagrange duality.

Take an optimization problem:

minimize

subject to ,

The **Lagrangian** is

The **Lagrange dual function** is

.

The Lagrange dual function gives lower bounds on the optimal value of the original problem.

(This is very easy to check: if is a feasible solution to the original problem, observe that )

Whenever we bound some quantity with regards to some adjustable parameters, the obvious idea is to adjust the parameters so as to make the bound as good as possible. This is the **Lagrange dual problem**.

maximize

subject to .

Call the optimal value of the Lagrange dual problem . It is obvious that

always, called **weak duality**. When is , i.e. when does **strong duality** hold? The answer is that is usually does when the original problem is convex. (i.e. convex, linear).

**Slater’s theorem** removes the “usually”. Strong duality holds if the original problem is convex, and there exists a **strictly feasible** point, i.e. there exists an such that the inequalities are strictly satisfied:

.

Actually, a slightly stronger result holds: if some are affine, only is necessary for those constraints.

### Like this:

Like Loading...