Problem

Given a minimization problem with constraints, we want to find optimal parameters. The problem is formulated as follows:

Classes

There are two main problem classes that fit into this generalization.

We start with the augmented Lagrangian

where and are Lagrange multipliers with constraints and .

Then, observe that

since if a constraint was violated, setting or to would make the whole value .

Let be the optimal solution, with the given constraints. Following from above,

Let the Lagrange dual be

and optimal .

The weak duality theorem states

and the strong duality theorem states that if , , and are convex and there exists for all , we have

In many cases, the dual solution is easier to solve for. Thus, if the strong duality requirements are met, we can optimize for the dual instead.

If we solve the problem, we have the following KKT conditions. Let , , and be optimal, and , . Then, and , and