What is NLP?<\/h2>\n
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.<\/p>\n
My interest is in applying it to optimal control problems, which can have quite complicated nonlinear dynamics and constraints.<\/p>\n
The Math:<\/h2>\n
The nonlinear, in\/equality constrained optimization problem can be written as:<\/p>\n
minxf(x)<\/p>\n
subject to\u00a0h(x)=0<\/p>\n
g(x)\u22640<\/p>\n
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<\/p>\n
How to solve this?<\/h2>\n
\u00a0First, look at a simpler problem: unconstrained optimization<\/p>\n
minxf(x)<\/p>\n
The unconstrained case has two approaches: the line search, and the trust region method.<\/p>\n
Line Search<\/h3>\n
With the line search, we rearrange this to the 1-dimensional optimization problem:<\/p>\n
min\u03b1>0f(x+\u03b1p), where\u00a0p\u00a0is search direction, commonly\u00a0p=\u2212\u2207f<\/p>\n
This is repeated until a stopping condition is met.<\/p>\n
- \n
<\/a><\/dt>\n
- <\/dd>\n<\/dl>\n
Trust Region<\/h3>\n
With the trust region method, we approximate\u00a0f\u00a0with a quadratic model\u00a0m, then:<\/p>\n
minpm(x+p), where\u00a0x+p\u00a0is within the trust region\u00a0\u0394<\/p>\n
The model can be defined as:\u00a0m(x+p)=f+pT\u2207f+12pT\u22072p<\/p>\n
p\u00a0can be crudely minimized by defining\u00a0p=\u2212\u2207f\u2225\u2207f\u2225\u0394<\/p>\n
There are additional\u00a0subtleties\u00a0to this procedure, involving the trust region\u00a0\u0394, and the step definition\u00a0p.<\/p>\n
- \n
<\/a><\/dt>\n
- <\/dd>\n<\/dl>\n
Stopping Conditions<\/h3>\n
For the unconstrained problem, we examine the gradient of the objective function\u00a0f(x), and when it is 0, we are at a local minimum.\u00a0<\/p>\n
This is a common stopping condition, although stopping conditions can be more complex.<\/p>\n
Constrained Optimization<\/h3>\n
The next step is to add equality constraints:\u00a0h(x)=0<\/p>\n
We then write a new function, which is the\u00a0Lagrangian<\/em>:<\/p>\n
L(x,\u03bb)=f(x)+\u03bbTh(x)<\/p>\n
where\u00a0\u03bb\u00a0is a vector of length t.<\/p>\n
The solution to this problem can be found with the following iterative process:<\/p>\n
1)\u00a0minxL(x,\u03bb)<\/p>\n
2) update\u00a0\u03bb\u00a0estimates<\/p>\n
For inequality constraints, we will consider the interior-point method:<\/p>\n
We add slack variables, changing the inequality constraints to equality constraints:<\/p>\n
g(x)\u22640\u21d2(g(x)+s)=0,s\u22650<\/p>\n
We then rewrite our Lagrangian in a way which incorporates this:<\/p>\n
L(x,s,\u03bbh,\u03bbg)=f(x)\u2212\u03bc\u2211mi=1lnsi+\u03bbThh(x)+\u03bbTg(g(x)+s)<\/p>\n
We have now introduced a penalty parameter,\u00a0\u03bc, which is progressively decreased.<\/p>\n
This allows the inequality boundaries to be reached in a controlled rate.<\/p>\n
Final Algorithm<\/h2>\n
while\u00a0E(x,s)>\u03f5TOL<\/p>\n
\u00a0 \u00a0 while\u00a0E(x,s;\u03bc)>\u03f5\u03bc<\/p>\n
\u00a0 \u00a0 \u00a0 \u00a0 compute normal step<\/p>\n
\u00a0 \u00a0 \u00a0 \u00a0 compute new\u00a0\u03bb<\/p>\n
\u00a0 \u00a0 \u00a0 \u00a0 compute hessian<\/p>\n
\u00a0 \u00a0 \u00a0 \u00a0 compute tangential step<\/p>\n
\u00a0 \u00a0 \u00a0 \u00a0 if step passes merit function test<\/p>\n
\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 take step<\/p>\n
\u00a0 \u00a0 \u00a0 \u00a0 else<\/p>\n
\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 try second order correction<\/p>\n
\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 maybe take step<\/p>\n
\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 reduce trust region radius<\/p>\n
\u00a0 \u00a0 reduce\u00a0\u03bc,\u03f5\u03bc<\/p>\n
Done!<\/p>\n
Normal Step<\/h3>\n
The normal step attempts to satisfy the linearized constraints in the problem.<\/p>\n
It does so in a manner similar to the basic trust region method; here the quadratic model to minimize is based of linearized constraints.<\/p>\n
Tangential Step<\/h3>\n
The tangential step attempts to find optimality while moving tangentially to the gradients of the constraints.<\/p>\n
This is accomplished by using the Projected Conjugate Gradient method. Here the objective function does not contain the constraints.<\/p>\n
Instead, all steps are “projected” through a matrix which aligns them with the gradient of the constraints.<\/p>\n
Test Cases<\/h2>\n
This is a previously covered optimal control example:<\/p>\n
Minimize the total energy consumed by a double integrator, from t=0 to t=1, meeting constraints.<\/p>\n
State Space Equations:<\/h3>\n
<\/p>\n
x\u02d9=v<\/div>\n<\/p>\n
<\/p>\n
v\u02d9=u<\/div>\n<\/p>\n
<\/p>\n
w\u02d9=12u2<\/div>\n<\/p>\n
Objective Function:<\/h3>\n
<\/p>\n
minuw(1)<\/div>\n<\/p>\n
Equality Constraints:<\/h3>\n
<\/p>\n
x(0)=0,x(1)=0<\/div>\n<\/p>\n
<\/p>\n
v(0)=1,v(1)=\u22121<\/div>\n<\/p>\n
<\/p>\n
w(0)=0<\/div>\n<\/p>\n
Inequality Constraints:<\/h3>\n
<\/p>\n
l\u2212x(t)\u22650<\/div>\n<\/p>\n
Computation:<\/h3>\n
Using the Direct Collocation method, with 40 time points we get:<\/p>\n
160 variables to optimize<\/p>\n
122 equality constraints<\/p>\n
40 inequality constraints<\/p>\n
When solving, hit an iteration limit of 250 in 20 seconds.<\/p>\n
The error function at this point is less than 1.e-4<\/p>\n
The error function is basically the maximum violation of KKT conditions.<\/p>\n
2500 iterations of 160 variables takens around 2.5 minutes, and reduces error function to ~1. e-5<\/p>\n
1000 iterations of 320 variables takes around 3.5 minutes<\/p>\n
Results:<\/h3>\n
- \n
<\/a><\/dt>\n
- <\/dd>\n<\/dl>\n
- \n
<\/a><\/dt>\n
- <\/dd>\n<\/dl>\n
- \n
<\/a><\/dt>\n
- <\/dd>\n<\/dl>\n
- \n
<\/a><\/dt>\n
- <\/dd>\n<\/dl>\n
Previously computed results using MATLAB’s solvers:<\/p>\n
- \n
<\/a><\/dt>\n
- <\/dd>\n<\/dl>\n
References:<\/h2>\n
1.\u00a0Byrd, R. H., Hribar, M. E., & Nocedal, J. (1999). An interior point algorithm for large-scale nonlinear programming \u2217.\u00a0Society<\/em>,\u00a09<\/em>(4), 877-900.<\/p>\n
2.\u00a0Nocedal, J., & Wright, S. (2006).\u00a0Numerical Optimization<\/em>.\u00a0<\/p>\n
3.\u00a0Von Stryk, O. (1991).\u00a0Numerical solution of optimal control problems by direct collocation<\/em>.\u00a0International Series of Numerical Mathematics<\/em>\u00a0(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<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"
Lab Presentation on Nonlinear Programming (Constrained, Nonlinear Optimization) 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 \u2026 Continue reading
- <\/dd>\n<\/dl>\n
- <\/dd>\n<\/dl>\n
- <\/dd>\n<\/dl>\n
- <\/dd>\n<\/dl>\n
- <\/dd>\n<\/dl>\n
- <\/dd>\n<\/dl>\n
- <\/dd>\n<\/dl>\n