Blog | Nonlinear Constrained Optimization Using Fmincon (2024)

Since most practical engineering design problems are nonlinear, applying nonlinear programming techniques is paramount. This blog applies both graphical and numerical methods to obtain the optimal solution. The focus here will be on optimization using the advanced sequential quadratic programming (SQP) algorithm of MATLAB's fmincon solver. The theory behind Karush-Kuhn-Tucker's conditions for optimality in the cases of equality and inequality constraints is discussed.

Description and foundation of nonlinear optimization

This blog deals with an optimization problem with multiple design variables. There are different methods of solving multivariate problems, as discussed below.

Unconstrained optimization problems:

1. Zeroth order: Simplex search method, pattern search method

2. First-order: Steepest descent, Conjugate gradient

3. Second-order: Newton's method, Quasi-Newton's method, Line-search method

Constrained optimization problems:

1. Elimination method

2. Penalty methods

3. Karush-Kuhn-Tucker(KKT) conditions

4. Sequential linear programming

5. Sequential Quadratic Programming(SQP)

This blog deals with solving by the Lagrange multiplier method with KKT conditions using the sequential quadratic programming algorithm(SQP) approach.

1st and 2nd order optimality conditions

Constrained optimization problems can be reformulated as unconstrained optimization problems.

Its derivatives can obtain the local optima of an objective function, and the optimality conditions involve the gradient vector and Hessian matrices of the objective functions.

Given that a function f(x) is continuous and has first and second derivatives that are continuous, it can be expressed as a Taylor Series expansion and neglecting higher-order terms as,

with being the local optimum. Therefore, if is a local minimum then,

Therefore, the first order necessary condition that needs to be satisfied by the local minimum is,

which makes the equation as,

which means that is positive-semidefinite (2nd order necessary condition)

However an additional 2nd sufficient condition needs to be satisfied to guarantee a local minimum at which requires that the Hessian of f(x) is positive definite at the point where and hence,

Maximum and minimum

Local and global maxima and minima

Formulation of the optimization problem

Formulation of the NLP problem

A nonlinear programming problem can have a linear or nonlinear objective function with linear and/or nonlinear constraints.

The NLP solver in MATLAB uses the formulation as shown below –

where

C(X) is a vector-valued function with all the non-linear inequality constraints

is a vector-valued function with all the non-linear equality constraints

Such that

NLP problems are iterative, which implies that it starts with an initial guess as a starting point for what the optimum might be. The solver iteratively goes through from the starting point following the gradient of the objective function and the constraints to reach the point where the gradient is equal to zero. Another issue commonly encountered in nonlinear optimization is the non-convexity of the function. This implies that the solver may not be able to find the global minimum and instead finds one of many local minima. Therefore, the choice of starting point will significantly impact the solution found, and this problem will be computationally expensive for solvers, especially when the problem involves more than two variables. Additionally, the constraints can also be non-convex.

Convex and concave functions

Newton's method

In this method, the objective function is approximated by a quadratic function at each iteration, and this approximation is then minimized, and a descent direction is computed. The quadratic approximation of the function is given by,

By the 1st order necessary condition,

, which gives

where is the inverse of the Hessian and

is the descent direction from which is found as,

Feasible Region with constraint with gradient of f and gradient of g

Nonlinear problem with equality constraints - Karush-Kuhn-Tucker(KKT) conditions

Suppose we have a function to be minimized as

s.t

This problem can be converted from a constrained problem to an unconstrained problem using the Lagrange function is given by,

The above-stated equation is the KKT condition for stationarity.

The constants are the Lagrange multipliers. Suppose that the minimum for the unconstrained problem is x* , and x* satisfies the constraint equation. For all values of x which satisfy the constraint equation, the minimum of is the minimum of f(x) subject to the constraint equation.

KKT conditions for example constraints

Then the equations and are solved. is the KKT condition for primal feasibility. When there are no inequality constraints, the KKT conditions turn into the Lagrange conditions and the specified parameters are the Lagrange multipliers

Nonlinear problem with inequality constraints - KKT conditions

Suppose we have a function to be minimized as

s.t

KKT Dual feasibility condition:

for all

KKT Complementary slackness condition:

for all

For the case of inequality constraints, it is important to note that there are sign restrictions on the Lagrange multipliers as described above

The Lagrangian can also be written for multiple constraints consisting of equality and inequality constraints as -

Equality-constrained Sequential Quadratic Programming problem

Sequential quadratic programming is one of the algorithms used to solve nonlinear constrained optimization problems by converting the problem into a sequence of quadratic program sub-problems. To get a linear system of equations applying the KKT conditions, it is necessary to have a quadratic objective function and linear constraint functions. This is what you would call a quadratic programming problem. This involves approximating the problem with a quadratic objective and linear constraints and iteratively solving by updating the Hessian, gradient, and Jacobian.

For a problem with equality constraints, the KKT conditions require that

at the optimal solution.

The steps and are obtained with Newton’s method for solving the unconstrained optimization as –

- (1)

Using the solution for and , the next iteration step of and are obtained as

The 1st order optimality condition that needs to be satisfied is represented by the equation (1) above for the following optimization problem–

s.t

At each iteration, a quadratic program sub-problem needs to be solved to find the steps which will be necessary to update

x_{1}[/latex]= 1, = 2, = 1, = 2 indicates that constraint-1 is active and constraint-2 is inactiveIn MATLAB, the objective function is coded into a separate file where it takes input as the vector X containing and , and the output would be the value of the objective function. Vectors are created defining the lower and upper bounds, and the constraints are specified as empty if there are none. There must be a separate file to specify the nonlinear constraints, a function of X containing the input variables.

Inequality-constrained Sequential Quadratic Programming problem with the example

For example minimise –

s.t

It is necessary to introduce slack variables to convert inequality constraints to equality constraints as follows –

For the second constraint,

The KKT inequality constraints would include the complementary slackness condition which in the general form is given by,

for all i = 1..m

The Lagrangian for this problem is given by –

Then, the partial derivatives of the Lagrangian with respect to each of these variables are taken and set to be zero as –

- (1)

- (2)

- (3)

- (4)

– (5)

– (6)

The last two equations are complementary slackness conditions.

These indicate that the is zero or s is zero.

If is zero, then the constraint-1 is active. If is zero, then the constraint-1 is inactive. This implies that the constraint is either active or inactive. This gives four possibilities, and it is necessary to test each of the possibilities.

Case 1: = = 0

Equation 2 is violated.

Case 2: = 0, = 0,

• Gives negative Lagrange multipliers

Case 3: = 0, = 0,

• gives negative Lagrange multipliers

Case 4: = 0, = 0,

Gives a valid solution as, = 1, = 2, = 1, = 2 indicates that constraint-1 is active and constraint-2 is inactive

i. Code for equality constrained SQP nonlinear optimization problem

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Output

i. Nonlinear equality constrained problem with SQP algorithm in fmincon function

The variables , and f(X) are plotted as variables x, y and z respectively.

The plot of the objective function vs and without the constraints is as follows –

Unconstrained objective function (equality constrained)

Contour plot of the objective function with equality constraint

It is observed that the graphical solution to the minimum of the objective function is the same as that obtained using the fmincon solver with the initial guess as

So, in this case, the optimum is at

The non-linear problem solution lies on feasible region defined by the equality constraint.

ii. Nonlinear inequality constrained problem with SQP algorithm in fmincon function

The plot of the objective function vs and without the constraints is as follows –

Unconstrained objective function(inequality constrained problem)

Feasible region (inequality constrained problem)

Contour plot of objective with inequality constraints

It is observed that the graphical solution to the minimum of the objective function is the same as that obtained using the fmincon solver with the initial guess as

So, in this case, the optimum is at

The non-linear problem solution lies within the feasible region.

Graphical solution(Unconstrained optimization problem)

Conclusion

We have seen how to solve the nonlinear optimization problem by taking the case of equality constraints and inequality constraints separately. The theory of Karush-Kuhn-Tucker conditions has been presented to obtain insights into how the constrained nonlinear optimization problems are solved. The basics of the SQP algorithm used by MATLAB's fmincon solver to solve these problems have been discussed.