Optimization in Practice with MATLAB for Engineering Students and Professionals (2015)

R	x1 *	x2 *	f*	g1 (x)	g2 (x)
1	1.366	1.866	4.134	-1.000	-1.366
0.1	1.048	0.198	3.102	-0.100	-1.048
0.01	1.005	0.020	3.010	-0.010	-1.005
0.001	1.000	0.002	3.001	-0.001	-1.000
0.0001	1.000	0.000	3.000	0.000	-1.000

13.5 Karush-Kuhn-Tucker Conditions

For constrained nonlinear optimization, the Lagrangian function and the Lagrange multiplier are used to provide a strategy for finding and validating the optimum of a function subject to constraints. Consider the minimization of a nonlinear optimization problem subject to equality constraints.

(13.40)

subject to

	(13.41)

The Lagrangian function converts the constrained problem into an unconstrained problem, as given by

(13.42)

The unspecified constants, ν_j, are the Lagrange multipliers. There are no sign restrictions on the values of ν_j. Suppose the minimum for the unconstrained problem L(x,ν) is x^*, and x^*satisfies h _j(x) = 0. For all values of x that satisfyh_j(x) = 0, the minimum of L(x,ν) is the minimum of f(x) subject to h_j(x) = 0. Then x^*minimizes the constrained optimization problem.

The following example shows us how to solve an optimization problem with equality constraints using the Lagrangian function.

Example: Minimize the following two variable function with a single equality constraint.

(13.43)

subject to

	(13.44)

The Lagrangian function of the problem is given by

(13.45)

The gradient of L(x,ν) with respect to x is equal to zero at the minimum.

(13.46)

(13.47)

The Hessian matrix of L(x,ν) with respect to x is given by

The Hessian is positive definite, implying that the optimal point is a minimum of the objective function.

From the above two functions of gradients and the equality constraint function, the point of the minimum is found to be x₁^* = 0.8 and x₂^* = 1.6. The Lagrange multiplier is ν = −1.6. The minimum value of the objective function is8.2.

The steps to solve constrained optimization problems with equality constraints using the Lagrangian function include

1. Construct the Lagrangian function L(x,ν) using the objective function and the equality constraints.

2. Solve ∇_xL(x,ν) = 0 and h(x) = 0.

The same method can be used to solve optimization problems with inequality constraints. The Lagrangian function in that case is constructed as

(13.48)

However, there are sign restrictions on the Lagrange multipliers for inequality constraints. They should satisfy λ_i ≥ 0. Additionally, the following functions should also be satisfied at the minimum.

(13.49)

(13.50)

A new concept known as the active set should be introduced before the discussion of this method. The active set at any feasible point x is comprised of the equality constraints and the inequality constraints for which g_i(x) = 0.

An inequality constraint, at the minimum point x^*in the feasible region, can be classified into the following two cases.

Case I: The inequality constraint is inactive at the minimum point x^*, which implies g_i(x^*) < 0. Since the minimum point x^*satisfies λ_i^*g _i(x^*) = 0, the Lagrange multiplier is λ_i^* = 0. Then L(x^*,λ) = f(x^*).

Case II: The inequality constraint is active at the minimum point x^*, which implies g_i(x^*) = 0. Then L(x^*,λ) = f(x^*).

At the minimum point x^*, ∇_xL(x^*,λ) = 0.

The following example explains the above process.

Example: Minimize the following two-variable function with a single inequality constraint.

(13.51)

subject to

	(13.52)

The Lagrangian function is given by

(13.53)

The gradient of L(x,λ) satisfies the following two equations:

(13.54)

(13.55)

The following two equations are satisfied:

(13.56)

(13.57)

(13.58)

Since λ = 0 does not satisfy ∇_xL = 0, λ is greater then zero. From Eq. 13.56, it is derived that (x₁² +x ₂² −1) = 0.

From Eq. 13.54 and 13.55, it is derived that x₁ = x₂.

Since λ > 0, it is derived from Eq. 13.54 and 13.55 that x₁ < 0 and x₂ < 0.

Solving (x₁² +x ₂² −1) = 0, the minimum point is found to be located at (−,−). The optimal value of the objective function is −.

The Lagrangian function for an optimization problem with multiple constraints is expressed as

(13.59)

At the feasible point x, if the gradients of the constraints in the active set are linearly independent, the Linear Independence Constraint Qualification (LICQ) holds.

Suppose there are two inequality constraints as given by

(13.60)

(13.61)

In that case, the only feasible point is (1, 0), as shown by Fig. 13.4. At (1, 0), the gradients of the two constraints are given by

(13.62)

(13.63)

Equations 13.62 and 13.63 are not linearly independent. Therefore, the LICQ does not hold at that point. The Karush-Kuhn-Tucker (KKT) conditions are necessary for a solution to be a local minimum.

Figure 13.4. The LICQ Does Not Hold

Theorem (Karush-Kuhn-Tucker Conditions)
Suppose that x^* is a local minimum solution of f(x) subject to constraints g_i(x) ≤ 0 (i = 1, ...,m) and h_j(x) = 0 (j = 1, ...,n). The objective function, f (x), and the constraints, g_i(x) and h_j(x), are continuously differentiable. The LICQ holds at x^*. Then there are Lagrange multipliers λ^*and ν^*, such that the following conditions are satisfied at (x^*,λ^*,ν^*).

	(13.64)
	(13.65)
	(13.66)
	(13.67)
	(13.68)
	(13.69)

The following example is used to illustrate how to use the KKT conditions to solve an optimization problem.

Example: Minimize the following two variable function with two inequality constraints.

(13.70)

subject to

	(13.71)
	(13.72)

This optimization problem can be solved using the graphical approach. The feasible region and the optimal point are plotted in Fig. 13.5.

Figure 13.5. Using the KKT Conditions to Solve an Optimization Problem

The Lagrangian function is formulated as

(13.73)

This problem can be solved using the KKT conditions as follows.

(13.74)

(13.75)

(13.76)

(13.77)

(13.78)

(13.79)

(13.80)

(13.81)

Based on Eqs. 13.74 — 13.81, the four possible cases for different values of λ₁ and λ₂ are discussed below.

Case I: λ₁ = 0 and λ₂ = 0.

If λ₁ = 0 and λ₂ = 0, Eq. 13.74 and 13.75 cannot be equal to 0.

Case II: λ₁ > 0 and λ₂ = 0.

From Eq. 13.74 and 13.75, it is found that x₁ = x₂ and they should be negative.

From Eq. 13.78, x₁ = x₂ = −. However, they do not satisfy Eq. 13.81.

Case III: λ₁ = 0 and λ₂ > 0.

Equation 13.75 is not satisfied.

Case IV: λ₁ > 0 and λ₂ > 0.

From Eq. 13.79, it is found that x₁ = −. From Eq. 13.75, x₂ < 0. From Eq. 13.78, x₂ = −. All the other equations are satisfied. The values of λ₁ and λ₂ are and (1 −).

Therefore, the minimum point is found to be (x₁,x₂) = (−,−), using the KKT conditions.

13.6 Sequential Linear Programming

In Chapter 11, we determined that certain algorithms can be used to efficiently and reliably solve linear programming problems. We note here that nonlinear optimization problems can be converted to approximate linearoptimization problems. These converted problems are only partially equivalent to the original problem, and only in a certain neighborhood of the design space — near the operating point. Subsequently, in the neighborhood of the operating point, the problems can be solved using linear programming techniques.

The sequential linear programming method linearizes the objective function and constraints of an optimization problem, and expresses them as linear functions using Taylor series expansions. A Taylor series expansion at the point, x_k, is given by

(13.82)

The higher order terms, O( x−x_k )², are ignored and only the linear term is retained. The linearization form of f (x) at x_k is given by

(13.83)

The most direct use of sequential linear programming is to replace a nonlinear problem with a complete linearization of the constituent functions at a sequential set of points that are intended to lead to the solution. This method can also be applied to a linearly constrained problem with a nonlinear objective function. A linearly constrained nonlinear programming problem has the following form.

(13.84)

subject to

	(13.85)
	(13.86)

The objective function, f(x), is linearized at a feasible point, x_k, and the problem is reformulated as follows.

(13.87)

subject to

	(13.88)
	(13.89)

Assuming the feasible region is bounded, the above problem will possess an optimal solution, _k^*, at a feasible corner point. The optimal solution, _k^*, is not guaranteed to be improved over the current point, x_k. Since the feasible region is a polyhedron and since _k^*is a corner point of the feasible region, any point on the line between _k^* and x_k is feasible. Since (_k^*; x _k) < f(x_k), the vector (_k^*− x _k) is a descent direction. A line search on this descent direction can lead to an improvement in f (x). The formulated line search problem is stated as follows:

(13.90)

subject to

	(13.91)

The line search will find a feasible point, x_k+1, that satisfies f (x_k+1) < f(x_k). The new point, x_k+1, is used as a linearization point for the next linear approximation, and a new line search is then performed. After successive iterations of approximations and line searches, the process is expected to converge to the optimal point of the nonlinear problem. For nonlinear programming problems with linear constraints, the solution steps, using sequential linear programming, are:

1. Set an initial guess x₀. Specify the convergence tolerance > 0.

2. Calculate the gradient of f (x_k). If the gradient is ∇f_k ≤ , stop.

3. Approximate the original objective function at x_k using the Taylor expansion.

4. Solve the linearized problem to find the optimal solution, _k^*.

5. Perform a line search for the original objective function between the points x_k and x_k^* to find an improved point x_k+1.

6.Set k = k + 1. Go to Step 2.

A general nonlinear optimization problem can involve nonlinear constraints, as defined by

	(13.92)

subject to

	(13.93)
	(13.94)
	(13.95)

Using the Taylor expansions for the objective function and the constraints at the point x_k, the linearized approximation problem is constructed as

	(13.96)

subject to

	(13.97)
	(13.98)
	(13.99)

Solving the above linear programming problem, a new point, x_k+1, is obtained in the feasible region of the linear constraints. A series of points can be generated through iterations. At each iteration, the solution to the previous linear approximate problem is used as the linearization point, and a new linear programming problem is constructed and solved. However, there is no assurance that the solution to the approximate linear programming problem lies within the feasible region of the original problem. In order to attain convergence to the true optimal solution of the nonlinear programming problem, at each iteration, an improvement in both the objective function and the constraintfeasibility should be made. One way to achieve a satisfactory approximation of the linearization is to impose limits on the allowable increments in the variables, in order to keep the solution to the linear programming problem within a reasonably small neighborhood of the linearization point. The limits can be stated as

(13.100)

The steps to solve a general nonlinear programming problem using the sequential linear programming method are:

1. Set an initial guess x₀. Specify the convergence tolerance > 0.

2. Calculate the gradient of f (x_k). If the gradient ∇f_k ≤ , stop.

3. Approximate the original nonlinear functions at x_k using the Taylor expansion.

4. Impose increment limits. −δ ≤ x − x_k ≤ δ, δ > 0.

5. Solve the linearized problem to find the optimal solution, x_k+1.

6.Set k = k + 1. Go to Step 2.

The optimization problem in the following example is a quadratic problem. It can be solved using the sequential linear programming method without imposing increment limits.

Example: Solve the following minimization problem.

(13.101)

subject to

	(13.102)
	(13.103)
	(13.104)
	(13.105)

The feasible region lies on the curve h₁(x) = 0 between the point (1, 4) determined by the linear bound 1 ≤ x₁ and the point (2, 3) determined by the constraint g₁(x) ≤ 0. The linearized approximation of the problem is constructedat the point (2, 4) as shown below.

(13.106)

subject to

	(13.107)
	(13.108)
	(13.109)
	(13.110)

The solution to the approximate optimization problem is found to be (1.8889, 3.2222). At this point, the optimization can be relinearized and solved. After several iterations, the minimum solution to the original problem is found to be (2, 3). The estimated minimum value of the objective function is 2.

13.7 Sequential Quadratic Programming

Sequential quadratic programming (SQP) is a highly effective method to solve constrained optimization problems involving smooth nonlinear functions. This approach solves a series of quadratic subproblems.

A nonlinear optimization problem without inequality constraints is defined as

(13.111)

subject to

	(13.112)

The Lagrangian function for the above problem is expressed as

(13.113)

The KKT conditions require that ∇L(x^*,ν^*) = 0 at the optimal point. The Newton method for unconstrained minimization can be expressed as

(13.114)

In Equation 13.114, the step p_k and q_k are obtained as the solution to the following linear function.

(13.115)

Equation 13.115 can also be expressed as

(13.116)

Equation 13.116 represents the first-order optimality conditions for the following optimization problem.

(13.117)

subject to

	(13.118)

In Equation 13.114, q_k represents the Lagrange multiplier, ν_k, in the above formulation.

At each iteration, a quadratic problem is solved to obtain [p_k,q_k]^T. These values are used to update [x_k,ν_k] using Eq. 13.114.

A nonlinear optimization problem with both equality and inequality constraints is defined as

(13.119)

subject to

	(13.120)
	(13.121)

The above optimization problem can be reformulated as

(13.122)

subject to

	(13.123)
	(13.124)

Example: Apply the SQP method to solve the following problem involving an equality constraint.

(13.125)

subject to

	(13.126)

Considering the initial values of x and ν as X₀ = [1,−1]^T and ν₀ = 1, we get

(13.127)

(13.128)

(13.129)

(13.130)

(13.131)

(13.132)

(13.133)

Using the first-order optimality conditions, the solution to [p₀,q₀]^T can be obtained from the following equation.

(13.134)

From Eq. 13.134, the values of steps p₀ and q₀ are given by

(13.135)

(13.136)

The values of x and ν can then be updated for the next iteration as

(13.137)

(13.138)

The above equations represent the process for the first iteration. The values of x and ν are updated by the same procedure. The minimum point for this problem is found to be [0.6633,−0.7483]^T. The minimum function value is estimated as 0.1764.

13.8 Comparison of Computational Issues

In this chapter, the methods used to solve nonlinear programming problems with constraints were presented, including the elimination method, penalty methods, the sequential linear programming method, and the sequentialquadratic programming method.

The elimination method is limited in its application. It can be useful for solving optimization problems involving equality constraints. It requires solving systems of equations, making it challenging to convert this method into numerical algorithms. This method is not practical for solving large scale problems.

The penalty methods solve a sequence of subproblems with updated penalty parameters. These methods require a large number of iterations. If the constraints values span several orders of magnitude, the penalty method may face scaling issues.

The sequential linear programming method is efficient for optimization problems with mild nonlinearities. This method is not well-suited for optimization problems involving highly nonlinear functions.

The sequential quadratic programming method is one of the most effective methods used to solve constrained nonlinear optimization problems. It can be leveraged to solve both small scale and large scale problems, as well as problems with significant nonlinearities. This method has been implemented in many optimization solvers and commercial software packages and has a wide applicability.

13.9 Summary

This Chapter delved further into the theory and application of nonlinear programming (NLP), with the description of the characteristics of constrained NLP, and introductions to the major approaches used for solving constrainedNLP problems. The structure of constrained NLP problems is first presented, the general formulation of which includes inequality and equality constraints. Basic methods for solving constrained NLP, such as Elimination methodsand Penalty methods, are then introduced. This was followed by the introduction of the Karush-Kuhn Tucker conditions, which are of paramount importance in NLP, both as a set of optimality criteria and as a means of solving simpler constrained NLP problems. Advanced methods for solving constrained NLP problems are also presented in this chapter, specifically including Sequential Linear Programming and Sequential Quadratic Programming. Thechapter concluded with a comparative discussion of the computational capabilities and limitations of the different classes of constrained NLP methods.

13.10 Problems

Warm-up Problems

13.1Consider the following optimization problem:

(13.139)

subject to

	(13.140)

1.Find all the points that satisfy the KKT condition using Lagrange multipliers.

2.Use the variable elimination method to solve the problem (eliminate x₁). Compare the solutions obtained using the variable elimination method with those obtained in Question 1.

13.2Use the Lagrange multiplier method to solve the following problem:

(13.141)

subject to

	(13.142)
	(13.143)

Intermediate Problems

13.3Consider the following optimization problem:

	(13.144)

subject to

	(13.145)
	(13.146)
	(13.147)
	(13.148)
	(13.149)
	(13.150)

1.Write down the Karush-Kuhn Tucker (KKT) necessary conditions for this problem

2.You are given that constraints g₁ and g₄ are active, and the other constraints are inactive. Given this information, simplify the KKT conditions found in No. 1.

3.Find all the possible KKT points using the simplified KKT conditions from No. 2.

13.4Solve the constrained optimization problem below using the inverse penalty method.

(13.151)

subject to

	(13.152)

1.Perform four unconstrained optimizations using the following values for the penalty parameter: R = 1, 0.1, 0.01, and 0.001.

2.For each R, prepare a table that provides the value of the penalty parameter, the values of the design variables, objective function and the constraint.

3.Can you guess where the constrained minimum might be?

13.5Consider the following problem:

(13.153)

subject to

	(13.154)

1.Solve the above optimization problem using the bracket operator penalty method.

2.Check your answer using fminsearch.

3.Plot contours of the objective function, and the path of the intermediate solutions as the optimal point is reached.

13.6Let f (x) = 2x³−3x²−12x+1. Answer the following questions:

(a)Determine the minimum of f (x) by hand. Report the values of the optimum x and the function value at this point.

(b)This sub-problem is a simple demonstration of how constrained optimization is sometimes performed. Let us add another component to the above function. The function now takes the form f (x) = 2x³ − 3x² − 12x + 1 +R(x− 6)², where R is a constant. Plot this new function for R = 0,R = 1,R = 10,R = 100, and R = 1, 000 for 0 ≤ x ≤ 8 on the same figure. Use different colors for each R. Keep your vertical axis limits between −100 and 800.

(c)By looking at the plot in Part (b), can you tell what the minimum of the new function is for the different values of R? Indicate these minima on the plot, and compare them with the minimum of the original function in Part (a). What is the minimum of the new function if R = ∞∞?

(d)Explain how this problem shows you one way to solve constrained optimization problems.

BIBLIOGRAPHY OF CHAPTER 13

[1] J. Johannes. Introduction to the Theory of Nonlinear Optimization. Springer, 3rd edition, 2007.

[2] I. Griva, S. G. Nash, and A. Sofer. Linear and Nonlinear Optimization. SIAM, 2nd edition, 2009.

[3]M. S. Bazaraa, H. D. Sherali, and C. M. Shetty. Nonlinear Programming: Theory and Algorithms. John Wiley and Sons, 3rd edition, 2013.

[4]A. Ravindran, G. V. Reklaitis, and K. M. Ragsdell. Engineering Optimization: Methods and Applications. John Wiley and Sons, 2006.