NLPSOLVER ver. 0.0.1 - 0002
---------------------------
NLPSOLVER is a FREEWARE (see 4.)) collection of SQP solver implemented in MatLab(R)
that finds a (local) minimum of a function of several variables with respect to
inequality and equality constraints.
nlpsolver attempts to solve problems of the form:
min F(X) subject to: C(X) <= 0, Ceq(X) = 0
X LB <= X <= UB
with continuously differentiable functions F, C, Ceq.
_________________________________________________________________________________________
_________________________________________________________________________________________
Contents:
---------
0.) Some remarks
1.) The input/output-structure
2.) Related files
3.) References
4.) License (GPL v3)
5.) Changes
6.) Planned extensions
7.) Contact Information
_________________________________________________________________________________________
_________________________________________________________________________________________
0.) Some remarks
----------------
As we had need for an easy to use NLP solver in MatLab(R) that we do not need to compile on
each computer, and that our students may handle, we decided to implement some SQP methods.
NLPSOLVER can still be seen as an early beta version and will be upgraded and updated in the
future. However, if one has some remarks, suggestions, or too much time, feel free to write
an e-mail (see 5.)).
If one uses NLPSOLVER within some research/publication please refer to our hompage.
_________________________________________________________________________________________
1.) The input/output-structure
----------------------------------------------
The input/output-structure is:
[x,fval,exitflag,output,LAMBDA]=nlpsolver(fun,x0,lb,ub,constr,OPTIONS)
This is similar to the input/output structure of fmincon (from the MatLab(R) Optimization
Toolbox).
However linear equality and inequality constraints must be contained in
the constraint function.
If the problem has no inequality or equality constraints, then one has
to set them and the derivatives as the empty set.
Finite differences and automatic differentiation are not implemented
yet. The first derivatives of the objective/constraints must be passed
by the user.
INPUT:
------
fun : objective function
form: [F,DF] = fun(x)
F: IR^n -> IR, DF: IR^n -> IR^(n x 1)
x0 : initial point in IR^n
LB : lower bounds on x
UB : upper bounds on x
constr : linear and non linear constraints
form: [G,Geq,DG,DGeq]=constr(x)
G : IR^n -> IR^p (inequality-constraints)
Geq : IR^n -> IR^q (equality-constraints)
DG : IR^n -> IR^(n x p)
DGeq: IR^n -> IR^(n x q)
options : structure with different options for optimization
MaxIter : max. number of iterations
DEFAULT: 1000*n
TolConv : tolerance for convergence
DEFAULT: 1e-6
Algori : algorithm used for optimization
blf_sqp_soc - backtracking line search
filter SQP (SOC)
blf_sqp_mod - backtracking line search
filter SQP (MOD)
trf_sqp_soc - trust region filter SQP (SOC)
trf_sqp_mod - trust region filter SQP (MOD)
rfsqp - reduced feasible SQP
DEFAULT: blf_sqp_mod
Activ : how to predict the active set
linea - uses the activ set of the
linearised constraints of the
LP/QP-subproblems
creal - uses the original constraints
(constraints not approximated)
idfun - uses an identification function
NOTICE: option idfun is not
properly implemented
- that will be corrected
in the next version
DEFAULT: linea
Multi : determines how to compute the multiplieres
L_1 - compute multipliers by minimizing
the gradient of the Lagrangian in
L_1-sense (uses linprog)
L_2 - compute multipliers by minimizing
the gradient of the Lagrangian in
L_2-sense (uses lsqlin)
sub - use multipliers computed in
subproblems
DEFAULT: L_1
debug : if you wish additional output during
optimization set options.debug = []
OUTPUT:
-------
x : solution
fval : value of the objective function in x
exitflag : integer identifying the reason the algorithm terminated
-9 : an error occured in the input
-3 : increase iter_max
-1 : no feasible solution found
0 : no progress
1 : KKT-point found
2 : feasible point found
output : structure containing information about the optimization
Algori : algorithm used for optimization
iter : number of iterations
Time : CPU time
Term : reason the algorithm terminated
LX : differential of the Lagrangian
LXnorm : value of norm(LX) at output point
lambda : structure containing the Lagrangian multipliers at the
solution
ineqnonlin : inequalities
eqnonlin : equalities
lower : lower bounds
upper : upper bounds
The directory should contain a test file called test.m and
a related example objective as well as constraint m-files.
For the call of the function we refer to test.m
The list with the input/output structure can also be displayed
by typing 'help nlpsolver' in MatLab(R).
_________________________________________________________________________________________
2.) Realated files
------------------
Here is a list of related files that come with and that are needed by NLPSOLVER:
README.txt
test.m
fun.m
constr.m
nlpsolver.m
BFGS_Powell.m
blf_sqp_mod.m
blf_sqp_soc.m
comp_multi.m
comp_soc.m
comp_sos.m
dummy_constr_.m
filter_acc_mod.m
filter_acc_soc.m
filter_add_mod.m
filter_add_soc.m
filter_unblock.m
rest_mod.m
rest_mod_2.m
rest_soc.m
rest_soc_2.m
rfsqp.m
trf_sqp_mod.m
trf_sqp_soc.m
_________________________________________________________________________________________
3.) References
--------------
R.Fletcher, N.I.M.Gould, S.Leyffer, P.L.Toint, A.Wächter
Global convergence of a trust-region SQP-filter algorithm for general
nonlinear programming
SIAM J.Optim., Vol.13, No.3 (2002), pp 635-659
R.Fletcher, S.Leyffer
Nonlinear programming without a penalty function
Math.Program., Ser.A 91 (2002), pp.239-269
C.T.Lawrence, A.L.Tits
A computationally effficient Feasible Sequential Quadratic Programming
Algorithm
SIAM J.Optim., Vol.11, No.4 (2001), pp.1092-1118
S.Ulbrich
On the superlinear local convergence of a filter-SQP method
Math.Program., Ser.B 100 (2004), pp.217-245
A.Wächter, L.T.Biegeler
Line search filter methods for nonlineare programming:
motivation and global convergence
SIAM J.Optim., Vol.16, No.1 (2005), pp.1-32
A.Wächter, L.T.Biegeler
Line search filter methods for nonlineare programming:
local convergence
SIAM J.Optim., Vol.16, No.1 (2005), pp.32-48
We are very sorry if we forgot any reference.
If one notices that there is some missing reference,
then please feel free to write an e-mail (see 5.)) so that we
can add it to the list.
_________________________________________________________________________________________
4.) License (GPL)
-----------------
The following license is related to NLPSOLVER and all functions listed in 2.)
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see .
_________________________________________________________________________________________
5.) Changes
-----------------------
ver. 0.0.1 - 0002: Some bugs from ver. 0.0.1 - 0001 were found and fixed.
Fixed bugs and description of the bugs
1. rfsqp.m: If the starting point was optimal then the algorithm threw an error.
2. comp_multi.m: For the option 'linea' the handling of LB and UB was not correct.
_________________________________________________________________________________________
6.) Planned Extensions
-----------------------
ver. 0.0.2 - XXXX (planned: Dec. 2012):
- Implementation and integration of SLP methods
- Implementation and integration of a Simplex method
- Option for the subsolver that "solves" linear subproblems
ver. 0.0.3 - XXXX (planned: Jul. 2013):
- Handling of sparse structures
- Implementation and integration of an Interior Point method for linear and quadratic problems
- Extension of the option for the subsolver that "solves" linear and/or quadratic subproblems
- Option for the approximation of the derivatives with finite difference methods
ver. X.X.X - XXXX (planned: ---):
- Parallelization of subroutines
- Adaptation of the algorithms for distributed computing
- Implementation and integration of methods for nonsmooth optimization
- Implementation and integration of convergent derivative free methods
_________________________________________________________________________________________
7.) Contact Information
-----------------------
Paul Steuermann - KIT, Germany
Institute of Operations Research - Continuous Optimization
e-mail: nlpsolver@ior.kit.edu
Homepage: kop.ior.kit.edu