- Introduction
- Analytical Methods without Constraints
- Analytical Methods Applicable for Constraints
- Necessary and Sufficient Conditions for Constrained Problems
- Closure
- References
- Problems
The
necessary conditions have been developed by Kuhn and Tucker (14) for a
general nonlinear optimization problem with equality and inequality constraints.
This optimization problem written in terms of minimizing y(
where y(
Any value of where the x The necessary conditions for a constrained minimum are given by the following theorem (7,8,10,14).
Examining these conditions, the first one is setting the first partial
derivatives of the Lagrangian function with respect to the independent
variables x For the problem
of maximizing y(
These conditions are the same as the ones for minimizing given by equation (2-45), except the inequality is reversed for the Lagrange Multipliers in the fifth condition. Also, the inequality constraints are written as less than or equal to zero for convenience in the subsequent discussion on sufficient conditions. The following example illustrates the Kuhn-Tucker necessary conditions for a simple problem.
Locate the five Kuhn-Tucker points of the following problem, and determine their character, i.e., maximum, minimum, or saddle point.
A diagram of the above equations is given in Figure 2-6. The function being optimized is the classic saddle point function which in constrained by planes. The first step
in the procedure is to locate the stationary points by ignoring the inequality
constraints, i.e., l The Kuhn-Tucker
point is The point Proceeding to
step two, one constraint equation at a time is selected, and the character
of the Kuhn-Tucker point is determined. Beginning with the first constraint
equation as an equality, i.e., l Solving gives:
The sign of the Lagrange Multiplier is negative, and by the Kuhn-Tucker necessary conditions, the point can be a maximum, since the other constraint equations are satisfied as inequalities. The procedure is repeated for the other three constraint equations, each considered individually as an equality. The results for the Kuhn-Tucker points are summarized in the following table:
Character: max min max min saddle The character of each of the stationary points is based on the Kuhn-Tucker necessary conditions. By examining Figure 2-5, we confirm their character. However, constraint qualifications and sufficient conditions are needed to give a general method, and this is discussed next.
In the theorems developed by Kuhn and Tucker (14), the constraint equations
must satisfy certain conditions at the Kuhn-Tucker points, and these conditions
are called
These do not
satisfy this condition at point x The same concepts used for unconstrained problems are followed to develop the sufficient conditions for constrained problems. This involves expanding the Lagrangian function in a Taylor series about the Kuhn-Tucker point located using the necessary conditions. The Taylor series is simplified by neglecting third and higher order terms to give a function that contains only terms involving second partial derivatives evaluated at the Kuhn-Tucker point. This gives a differential quadratic form, and a test similar to the one for the unconstrained problem is obtained to determine if the Kuhn-Tucker point is a maximum, minimum, or saddle. The sufficient conditions for the case of both inequality and equality constraints are more elaborate than if only equality constraints are involved. We have space to give only the appropriate theorems and describe their development and use. Further details are given by Avriel(10), Bazaraa and Shetty(15) and Reklaitis, et. al.(17). Considering the case of only equality constraints first, the Lagrangian function for n independent variables and m equality constraint equations is given by the following equation. Expanding the
Lagrangian function in a Taylor series about the Kuhn-Tucker point This equation
is comparable to equation (2-8), and subscripts x As previously,
we need to determine if the term in the brackets remains positive (minimum),
remains negative (maximum) or changes sign (saddle point) for small feasible
changes in To determine
if the quadratic form is always positive or always negative, results comparable
to those given by equation (2-7) are required, with the extension that
the constraints also be satisfied, i.e., for feasible values of
The proof of
this theorem is given by Avriel (10), and follows the discussion of the
concepts given above. The comparable result for a strict maxima is obtained
by changing (-1)
Consider the following problem.
Forming the Lagrangian
function and differentiating with respect to x
Solving the above equation set simultaneously gives the following values for the Kuhn-Tucker point.
From the necessary conditions of equations (2-45) or (2-49), the Lagrange multipliers are unrestricted in sign, and the value of the determinants from the theorem on sufficiency conditions is required to determine the character of this point. The partial derivatives needed for this evaluation are:
The determinant is (m = 2, n = 3, p = 3, only one in this case): The value of
D The sufficient conditions for problems with equality and inequality constraints, equations (2-41), (2-42), and (2-43), are summarized in the following theorem. There are a number of mathematical concepts and theorems required to obtain this result. These are given in some detail by Avriel (10), Bazaraa and Shetty (15) and Reklaitis, et. al.(17); it is not feasible to describe them in the space available here.
The following example illustrates the application of this theorem.
Consider the following problem after Reklaitis et. al.(17).
Applying the theorem gives:
Solving this
set of equations gives x
However, for
all finite values of In summary, the necessary and sufficient conditions for nonlinear programming problems have been described and illustrated with examples. References have been given for more details for this theory.
An important special case is when the economic model is concave, and all
of the constraint equation are convex and are inequalities. This is known
as
The necessary
and sufficient conditions for the maximum of concave function y( The theorem from Cooper(7) that establishes the above result is:
The proof of this theorem uses the definition of convex and concave functions and the fact that the Lagrangian function can be formulated as the sum of concave functions, which is concave. These concepts and results for the Kuhn-Tucker conditions and those given previously will be valuable in our discussion of modern optimization procedures in the following chapters. Those interested in further theoretical results are referred to the references at the end of the chapter and Chapter 6. Also, in industrial practice we will see that the concepts from the Kuhn-Tucker conditions are used in computer programs for advanced multivariable search methods to optimize economic and process models which are too elaborate for the algebraic manipulations required to use these theories directly. |