Lagrange Multipliers

Consider a problem of the following form:

Define the Lagrange multiplier method to solve the problem

𝕨
  • 's are called the Lagrange multipliers
  • Then Solve the problem by
    • set partial derivative to 0,

Duality

In optimization theory, duality means that optimization problems may be viewed from either of two perspectives, the primal problem or the dual problem.

The solution to the dual problem provides a lower bound to the solution of the primal (minimization) problem. 

If you have a minimization problem, you can also see it as a maximization problem.  And when you find the maximum of this problem, it will be a lower bound to the solution of the minimization problem.

General Form

Consider a generalized constrained optimization problem which contains inequality as well as equality constraints.:

Also called primal problem. To solve it, we start by defining the generalized Lagrangian:

  • Here, the ′s and  ′ s are the Lagrange multipliers or dual variables

  • objective is augmented with weighted sum of constraint functions

Consider the quantity

  • stands for "primal". Let be given; if violates any of the primal constraints, then ; if the constraints are indeed satisfied for a particular value of , then .

Hence,

Hence, consider the minimization problem

  • It is the same as our original, primal problem. Let the optimal value of the primal problem be .

Now, let’s look at a slightly different problem:

  • The new problem is optimizing (maximizing) with respect to , which are minimized with respect to .

Then, we can have the dual optimization problem:

  • This is exactly the same as our primal problem shown above, except that the order of the "max" and the "min" are now exchanged.

Let

  • The solution to the dual problem provides a lower bound to the solution of the primal (minimization) problem.

Now, we can solve the dual problem in lieu of the primal problem:

  • Easier for computation
  • Kernel functions

Under the condition that and are convex functions and are affine, and constraints of are strictly feasible:

  • There exists , so that is the solution to the primal problem and are the solution to the dual problem, and .
  • Moreover, satisfy the KKT conditions.

KKT conditions are as follows:

Table Of Contents
Lagrange Multipliers
Duality
General Form