Nonlinear Programming (NLP)

What is NLP?

Nonlinear programming refers to the an optimization scenario in which: the objective function is possibly nonlinear, and there are equality and/or inequality constraints which are possibly nonlinear.

My interest is in applying it to optimal control problems, which can have quite complicated nonlinear dynamics and constraints.

The Math:

The nonlinear, in/equality constrained optimization problem can be written as:

minxf(x)

subject to h(x)=0

g(x)≤0

Where x is a vector of length n, f(x) returns a scalar, h(x) is a vector of length t, and g(x) is a vector of length m

How to solve this?

 First, look at a simpler problem: unconstrained optimization

minxf(x)

The unconstrained case has two approaches: the line search, and the trust region method.

Line Search

With the line search, we rearrange this to the 1-dimensional optimization problem:

minα>0f(x+αp), where p is search direction, commonly p=−∇f

This is repeated until a stopping condition is met.

Trust Region

With the trust region method, we approximate f with a quadratic model m, then:

minpm(x+p), where x+p is within the trust region Δ

The model can be defined as: m(x+p)=f+pT∇f+12pT∇2p

p can be crudely minimized by defining p=−∇f∥∇f∥Δ

There are additional subtleties to this procedure, involving the trust region Δ, and the step definition p.

Stopping Conditions

For the unconstrained problem, we examine the gradient of the objective function f(x), and when it is 0, we are at a local minimum. 

This is a common stopping condition, although stopping conditions can be more complex.

Constrained Optimization

The next step is to add equality constraints: h(x)=0

We then write a new function, which is the Lagrangian:

L(x,λ)=f(x)+λTh(x)

where λ is a vector of length t.

The solution to this problem can be found with the following iterative process:

1) minxL(x,λ)

2) update λ estimates

For inequality constraints, we will consider the interior-point method:

We add slack variables, changing the inequality constraints to equality constraints:

g(x)≤0⇒(g(x)+s)=0,s≥0

We then rewrite our Lagrangian in a way which incorporates this:

L(x,s,λh,λg)=f(x)−μ∑mi=1lnsi+λThh(x)+λTg(g(x)+s)

We have now introduced a penalty parameter, μ, which is progressively decreased.

This allows the inequality boundaries to be reached in a controlled rate.

Final Algorithm

while E(x,s)>ϵTOL

    while E(x,s;μ)>ϵμ

        compute normal step

        compute new λ

        compute hessian

        compute tangential step

        if step passes merit function test

            take step

        else

            try second order correction

            maybe take step

            reduce trust region radius

    reduce μ,ϵμ

Done!

Normal Step

The normal step attempts to satisfy the linearized constraints in the problem.

It does so in a manner similar to the basic trust region method; here the quadratic model to minimize is based of linearized constraints.

Tangential Step

The tangential step attempts to find optimality while moving tangentially to the gradients of the constraints.

This is accomplished by using the Projected Conjugate Gradient method. Here the objective function does not contain the constraints.

Instead, all steps are “projected” through a matrix which aligns them with the gradient of the constraints.

Test Cases

This is a previously covered optimal control example:

Minimize the total energy consumed by a double integrator, from t=0 to t=1, meeting constraints.

State Space Equations:

 

 

 

 

 

 

Objective Function:

 

 

Equality Constraints:

 

 

 

 

 

 

Inequality Constraints:

 

 

Computation:

Using the Direct Collocation method, with 40 time points we get:

160 variables to optimize

122 equality constraints

40 inequality constraints

When solving, hit an iteration limit of 250 in 20 seconds.

The error function at this point is less than 1.e-4

The error function is basically the maximum violation of KKT conditions.

2500 iterations of 160 variables takens around 2.5 minutes, and reduces error function to ~1. e-5

1000 iterations of 320 variables takes around 3.5 minutes

Results:

Previously computed results using MATLAB’s solvers:

References:

1. Byrd, R. H., Hribar, M. E., & Nocedal, J. (1999). An interior point algorithm for large-scale nonlinear programming ∗. Society, 9(4), 877-900.

2. Nocedal, J., & Wright, S. (2006). Numerical Optimization. 

3. Von Stryk, O. (1991). Numerical solution of optimal control problems by direct collocation. International Series of Numerical Mathematics (Vol. 111, pp. 1-13). Citeseer. Retrieved from http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.53.9817&rep=rep1&type=pdf