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