Nonlinear constrained optimization using MATLAB’s fmincon

May 20, 2022

By Anuradha Viswanathan

Table of Contents

1

Description and foundation of nonlinear optimization

2

1st and 2nd order optimality conditions

3

Formulation of the optimization problem

Formulation of the NLP problem

Newton's method

4

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

5

Nonlinear problem with inequality constraints - KKT conditions

6

Equality-constrained Sequential Quadratic Programming problem

7

Inequality-constrained Sequential Quadratic Programming problem with the example

8

MATLAB Implementation of nonlinear constrained optimization with equality and inequality constraints

i. Code for equality constrained SQP nonlinear optimization problem

ii. Code for inequality constrained SQP nonlinear optimization problem

9

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

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

10

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.

Be a Brand Representative

Join Training Modules

Participate in Online Quiz

Get Research Assistance

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

Buy & Download Now

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.

Get instant access to the code, model, or application of the video or article you found helpful! Simply purchase the specific title, if available, and receive the download link right away! #MATLABHelper #CodeMadeEasy

Ready to take your MATLAB skills to the next level? Look no further! At MATLAB Helper, we've got you covered. From free community support to expert help and training, we've got all the resources you need to become a pro in no time. If you have any questions or queries, don't hesitate to reach out to us. Simply post a comment below or send us an email at [email protected].

And don't forget to connect with us on LinkedIn, Facebook, and Subscribe to our YouTube Channel! We're always sharing helpful tips and updates, so you can stay up-to-date on everything related to MATLAB. Plus, if you spot any bugs or errors on our website, just let us know and we'll make sure to fix it ASAP.

Ready to get started? Book your expert help with Research Assistance plan today and get personalized assistance tailored to your needs. Or, if you're looking for more comprehensive training, join one of our training modules and get hands-on experience with the latest techniques and technologies. The choice is yours – start learning and growing with MATLAB Helper today!

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

good and useful information

Need Urgent Help?

Our experts assist in all MATLAB & Simulink fields with communication options from live sessions to offline work.

Book Expert Help

testimonials

Philippa E. / PhD Fellow

I STRONGLY recommend MATLAB Helper to EVERYONE interested in doing a successful project & research work! MATLAB Helper has completely surpassed my expectations. Just book their service and forget all your worries.

Yogesh Mangal / Graduate Trainee

MATLAB Helper provide training and internship in MATLAB. It covers many topics of MATLAB. I have received my training from MATLAB Helper with the best experience. It also provide many webinar which is helpful to learning in MATLAB.

Research Assistance

Training Programs

Online Courses

USEFUL resources