Lagrange Multiplier - Handling Multiple Constraints - Multiple Constraints

Multiple Constraints

For more than one constraint, the same reasoning applies. If two or more constraints are active together, each constraint contributes a direction that will violate it. Together, these “violation directions” form a “violation space”, where infinitesimal movement in any direction within the space will violate one or more constraints. Thus, to satisfy multiple constraints we can state (using this new terminology) that at the stationary points, the direction that changes f is in the “violation space” created by the constraints acting jointly.

The violation space created by the constraints consists of all points that can be reached by adding any linear combination of violation direction vectors—in other words, all the points that are “reachable” when we use the individual violation directions as the basis of the space. Thus, we can succinctly state that v is in the space defined by if and only if there exists a set of “multipliers” such that:

which for our purposes, translates to stating that the direction that changes f at p is in the “violation space” defined by the constraints if and only if:

As before, we now add simultaneous equation to guarantee that we only perform this test when we are at a point that satisfies every constraint, we end up with simultaneous equations that when solved, identify all constrained stationary points:

\begin{align} g_1(p) & = 0 && \text{these mean the point satisfies all constraints} \\ g_2(p)& =0 \\ & \ \ \vdots \\ g_M(p) &= 0 \\ & \\ \nabla f(p) - \sum_{k=1}^M {\lambda_k \, \nabla g_k (p)} & = 0 && \text{this means the point is a stationary point}. \\ \end{align}

The method is complete now (from the standpoint of solving the problem of finding stationary points) but as mathematicians delight in doing, these equations can be further condensed into an even more elegant and succinct form. Lagrange must have cleverly noticed that the equations above look like partial derivatives of some larger scalar function L that takes all the and all the as inputs. Next, he might then have noticed that setting every equation equal to zero is exactly what one would have to do to solve for the unconstrained stationary points of that larger function. Finally, he showed that a larger function L with partial derivatives that are exactly the ones we require can be constructed very simply as below:

\begin{align} & {} \quad L\left( x_1, x_2, \ldots, x_N, \lambda_1, \lambda_2, \ldots, \lambda _M \right) \\ & = f\left( x_1, x_2, \ldots, x_N \right) - \sum\limits_{k=1}^M {\lambda_k g_k\left( x_1, x_2, \ldots, x_N \right)}. \end{align}

Solving the equation above for its unconstrained stationary points generates exactly the same stationary points as solving for the constrained stationary points of f under the constraints .

In Lagrange’s honor, the function above is called a Lagrangian, the scalars are called Lagrange Multipliers and this optimization method itself is called The Method of Lagrange Multipliers.

The method of Lagrange multipliers is generalized by the Karush–Kuhn–Tucker conditions, which can also take into account inequality constraints of the form h(x) ≤ c.

Read more about this topic:  Lagrange Multiplier, Handling Multiple Constraints

Famous quotes containing the words multiple and/or constraints:

    “Combining paid employment with marriage and motherhood creates safeguards for emotional well-being. Nothing is certain in life, but generally the chances of happiness are greater if one has multiple areas of interest and involvement. To juggle is to diminish the risk of depression, anxiety, and unhappiness.”
    —Faye J. Crosby (20th century)

    “Play is a major avenue for learning to manage anxiety. It gives the child a safe space where she can experiment at will, suspending the rules and constraints of physical and social reality. In play, the child becomes master rather than subject.... Play allows the child to transcend passivity and to become the active doer of what happens around her.”
    —Alicia F. Lieberman (20th century)