.st0{fill:#FFFFFF;}

Nonlinear constrained optimization using MATLAB’s fmincon 

 May 20, 2022

By  Anuradha Viswanathan

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,

 \Delta f(x) = f(x^* +\Delta x)-f(x^*)= \nabla f(x^*)^T\Delta x+\frac{1}{2}\Delta x^T\nabla^{2} f(x^*)\Delta x

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

\Delta f(x) = f(x^* +\Delta x)-f(x^*) \geq 0

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

 \nabla f(x^*) = 0

which makes the equation as,

\Delta f(x) = f(x^* + \Delta x)-f(x^*)= \frac{1}{2}\Delta x^T\nabla^{2} f(x^*)\Delta x \geq 0

which means that \nabla^{2} f(x^*) is positive-semidefinite (2nd order necessary condition)

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

  \Delta f(x) = f(x^* + \Delta x)-f(x^*)= \frac{1}{2}\Delta x^T\nabla^{2} f(x^*)\Delta x> 0


Maximum and minumum

                          Maximum and minimum

 Local and global maxima and minima

         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 –

 \min_{X} f(X)

where

 X =\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}

 LB \leq X \leq UB

 A_{eq} X = b_{eq}

 AX \leq b

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

 C_{eq}(X) is a vector-valued function with all the non-linear equality constraints

Such that

 C(X)\leq 0

 C_{eq}(X)= 0

NLP problems are iterative, which implies that it starts with an initial guess as a starting point  X_{0} 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

                           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,

 f(x) = f(x_{k}) + \nabla f(x_{k})^T(x-x_{k})+\frac{1}{2}(x-x_{k})^T\nabla^{2} f(x_{k})(x-x_{k})

By the 1st order necessary condition,

 \nabla f(x) = 0, which gives

 \nabla f(x) = \nabla f(x_{k})+\nabla^{2}f(x_{k})(x-x_{k}) = 0

 -\nabla f(x_{k}) = \nabla^{2}f(x_{k})(x-x_{k})

 x=x_{k} - [\nabla^{2}f(x_{k})]^{-1}\nabla f(x_{k})

where  [\nabla^{2}f(x_{k})]^{-1} is the inverse of the Hessian and

p_{k} = [\nabla^{2}f(x_{k})]^{-1}\nabla f(x_{k}) is the descent direction from which  x_{k+1} is found as,

  x_{k+1} = x_{k} - p_{k}
Feasible Region with constraint with gradient of f and gradient of g

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

\min_X f(x)

s.t   h_j(x) = 0 , j= 1,2...n

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

 L(x,\nu ) = f(x) +\sum_{j=1}^{n}\nu_{j}h_{j}(x)

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

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

KKT conditions for inequality constraints

              KKT conditions for example constraints

Gradient of objective function is antiparallel to gradient of constraint function

The gradient of the objective function is antiparallel to the gradient of the constraint function

Gradient of the objective function is antiparallel to the gradient of the constraint function

Gradient of the objective function is antiparallel to the gradient of the constraint function

Then the equations \nabla_{x}L(x,\nu ) = 0 and h(x) = 0 are solved. h(x) = 0 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

 \min_X f(x)

s.t   g_i(x) \leq 0

KKT Dual feasibility condition:

 \lambda_i \geq 0 for all  i=1,2...n

KKT Complementary slackness condition:

\lambda_{i}g(x^*) = 0 for all  i=1,2...n

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 -

L(x,\lambda ,\nu ) = f(x) +  \sum_{i=1}^{n}\lambda_{i}g_{i}(x) + \sum_{j=1}^{m}\nu_{j}h_{j}(x)

Example of active constraint

                        Example of active constraint

Example of inactive constraint

                        Example of inactive constraint

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

\nabla L(x^{*},\nu^{*}) = 0 at the optimal solution.

The steps p_{k} and q_{k} are obtained with Newton’s method for solving the unconstrained optimization as –

 \begin{bmatrix}\nabla_{xx}^{2}L(x_{k},\nu_{k})&\nabla h(x_{k})^{T}\\ \nabla h(x_{k})& 0 \\ \end{bmatrix} * \begin{bmatrix}p_{k} \\ q_{k} \\\end{bmatrix} =\begin{bmatrix}\nabla_{x}L(x_{k},\nu_{k}) \\-h(x_{k})\end{bmatrix} - (1)

Using the solution for p_{k} and q_{k} , the next iteration step of x_{k+1} and \nu_{k+1} are obtained as

 \begin{pmatrix}x_{k+1}\\\nu_{k+1}\end{pmatrix}=\begin{pmatrix}x_{k}\\\nu_{k}\end{pmatrix}+\begin{pmatrix}p_{k}\\q_{k}\end{pmatrix}

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

\min  p^{T}\nabla L(x_{k},\nu_{k})+\frac{1}{2}p^{T}\nabla_{xx}^{2}L(x_{k},\nu_{k})p =0

 s.t  \nabla h(x_{k})^{T}p+h(x_{k})=0

At each iteration, a quadratic program sub-problem needs to be solved to find the steps  [p_{k},q_{k}] which will be necessary to update[x_{k},v_{k}]

  x_{1}[/latex]= 1,  x_{2} = 2,  \lambda_{1} = 1,  s_{2}^2= 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 x_{1} and x_{2}, 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 –

\min_{X} x_{1}^2 - x_{2}

s.t x_{2} - 2x_{1} \leq 0

1 - x_{1} - x_{2} \leq 0

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

x_{2} - 2x_{1} = - s_{1}^2

x_{2} - 2x_{1} + s_{1}^2 = 0

For the second constraint,

1 - x_{1} - x_{2} = -s_{2}^2

1 - x_{1} - x_{2} + s_{2}^2 = 0

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

\lambda_{i}^*g_{i}(x^{*}) = 0 for all i = 1..m

The Lagrangian for this problem is given by –

 L = x_{1}^2-x_{2}+\lambda_{1}(x_{2}-2x_{1}+s_{1}^2)+ \lambda_{2}(1-x_{1}-x_{2}+s_{2}^{2})

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

\nabla_{x_{1}}L=0=2x_{1}-2\lambda_{1}-\lambda_{2} - (1)

 \nabla_{x_{2}}L=0=-1+\lambda_{1}-\lambda_{2} - (2)

 \nabla_{\lambda_{1}}L=0=x_{2}-2x_{1}+s_{1}^2 - (3)

 \nabla_{\lambda_{2}}L=0=1-x_{1}-x_{2}+s_{2}^2 - (4)

\nabla_{s_{1}}L=0=\lambda_{1}s_{1} – (5)

 \nabla_{s_{2}}L=0=\lambda_{2}s_{2} – (6)

  \lambda_{1} \geq 0,\lambda_{2} \geq 0,

The last two equations are complementary slackness conditions.

These indicate that the \lambda is zero or s is zero.

If   s_{1} is zero, then the constraint-1 is active. If  \lambda_{1} 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:  \lambda_{1}=  \lambda_{2} = 0

Equation 2 is violated.

Case 2:  s_{1} = 0,  s_{2} = 0,

  • Gives negative Lagrange multipliers

Case 3:  \lambda_{1}= 0,  s_{2} = 0,

  • gives negative Lagrange multipliers

Case 4:  \lambda_{2}= 0,  s_{1} = 0,

Gives a valid solution as, x_{1}= 1,  x_{2} = 2,  \lambda_{1} = 1,  s_{2}^2= 2 indicates that constraint-1 is active and constraint-2 is inactive

MATLAB Implementation of nonlinear constrained optimization with equality and inequality constraints

Get Access to
Codes & Report!

Learn how to solve nonlinearities in modeling practical objective functions and constraints using the fmincon solver and graphically interpret the optimal solutions; Developed in MATLAB R2022a with Optimization Toolbox

i. Code for equality constrained SQP nonlinear optimization problem

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
main_optimization_equality.m

% This script contains the graphical as well as the numerical solution for the
% non-linear optimization problem with linear/non-linear equality constraints

% Topic: Non-linear constrained optimization with MATLAB's fmincon
% function(main function)
% Website: https://matlabhelper.com
% Date: 09-04-2022

clc
clear all
close all

global fcount;
lb = [];
ub = [];

% Creates a mesh grid with variables x1 and x2
[x1, x2] = meshgrid(-5:.01:25,-5:.01:25);
% Evaluates the objective function on the grid
z = (x1.^2) - 8*x1 + x2.^2 - 12.*x2 ;


(Rest of the code to set constraints, bounds graphically to determine the feasible region and find the optimal solution with fmincon. Two m-files for the objective function and the constraint function are created)


opts = optimoptions(@fmincon,'Display','iter-detailed','Algorithm','sqp'
[x,fval] = fmincon(@objfun_equality,x0,A,b,Aeq,beq,lb,ub,'confun_equality',opts);

ii. Code for inequality constrained SQP nonlinear optimization problem

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
main_optimization_inequality.m

% This script contains the graphical as well as the numerical solution for the
% nonlinear optimization problem with linear and/or nonlinear inequality constraints

% Topic: Non-linear constrained optimization with MATLAB's fmincon
% function(main function)
% Website: https://matlabhelper.com
% Date: 09-04-2022

clc
clear all
close all

global fcount;
lb = [];
ub = [];

% Creates a mesh grid with variables x1 and x2
[x1, x2] = meshgrid(-5:.01:5,-5:.01:5);

% Evaluates the objective function on the grid
z = (x1.^2) - x2 ;

(Rest of the code to set constraints, bounds graphically to determine the feasible region and find the optimal solution with fmincon. Two m-files for the objective function and the constraint function are created)

opts = optimoptions(@fmincon,'Display','iter-detailed','Algorithm','sqp')
[x,fval] = fmincon(@objfun_inequality,x0,A,b,Aeq,beq,lb,ub,'confun_inequality',opts);

Output

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

The variables X_{1}, X_{2} and f(X) are plotted as variables x, y and z respectively. 

The plot of the objective function vs X_{1} and X_{2} without the constraints is as follows –

Unconstrained objective function (equality constrained)

            Unconstrained objective function (equality constrained)

Upon including the constraints, the feasible region of the solution is obtained as shown here in the contour plot –

Contour plot of the objective function with equality constraint

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

 X_{0}=\begin{pmatrix}1\\1\end{pmatrix}

So, in this case, the optimum is at

 x_{1}^* = 3

 x_{2}^* = 5

 f^* = -50

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 X_{1} and X_{2} without the constraints is as follows –

Unconstrained objective function(inequality constrained problem)

Unconstrained objective function(inequality constrained problem)

Upon including the constraints, the feasible region of the solution is obtained, as shown here

Feasible region (inequality constrained problem)

                Feasible region (inequality constrained problem)

The contour plot of the objective function with the constraints is as shown,

: Contour plot of objective with inequality constraints

                      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

 X_{0}=\begin{pmatrix}1\\1\end{pmatrix}

So, in this case, the optimum is at

 x_{1}^* = 1

 x_{2}^* = 2

 f^* = -1

 The non-linear problem solution lies within the feasible region.
Graphical solution(Unconstrained optimization problem)

               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.

Did you find some helpful content from our video or article and now looking for its code, model, or application? You can purchase the specific Title, if available, and instantly get the download link.

Thank you for reading this blog. Do share this blog if you found it helpful. If you have any queries, post them in the comments or contact us by emailing your questions to [email protected]. Follow us on LinkedIn Facebook, and Subscribe to our YouTube Channel. If you find any bug or error on this or any other page on our website, please inform us & we will correct it.

If you are looking for free help, you can post your comment below & wait for any community member to respond, which is not guaranteed. You can book Expert Help, a paid service, and get assistance in your requirement. If your timeline allows, we recommend you book the Research Assistance plan. If you want to get trained in MATLAB or Simulink, you may join one of our training modules. 

If you are ready for the paid service, share your requirement with necessary attachments & inform us about any Service preference along with the timeline. Once evaluated, we will revert to you with more details and the next suggested step.

Education is our future. MATLAB is our feature. Happy MATLABing!

About the author 

Anuradha Viswanathan

MATLAB Developer at MATLAB Helper,
M.S in Telecommunications and Networking,
M.S in Physics

  • Gudaru Venkaiah Katuri says:

    good and useful information

  • {"email":"Email address invalid","url":"Website address invalid","required":"Required field missing"}

    MATLAB Helper ®

    Follow: YouTube Channel, LinkedIn Company, Facebook Page, Instagram Page

    Join Community of MATLAB Enthusiasts: Facebook Group, Telegram, LinkedIn Group

    Use Website Chat or WhatsApp at +91-8104622179

    >