GOSOLVER ver. 0.0.1 - 0001 ------------------------------ GOSOLVER is a small FREEWARE (see 4.)) collection of Branch & Bound methods implemented in MatLab(R) that finds a global minimum of a (non-)convex function of several variables with respect to (non-)linear inequality constraints. gosolver_box attempts to solve problems of the form: min F(X) subject to: C(X)<=0 X LB <= X <= UB with a (twice) continuously differentiable function F and continuous functions C. _________________________________________________________________________________________ _________________________________________________________________________________________ Contents: --------- 0.) Some remarks 1.) The input/output-structure 2.) Related files 3.) References 4.) License (GPL v3) 5.) Contact Information _________________________________________________________________________________________ _________________________________________________________________________________________ 0.) Some remarks ---------------- GOSOLVER 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 GOSOLVER within some research/publication please refer to our hompage. _________________________________________________________________________________________ 1.) The input/output-structure ---------------------------------------------- The input/output-structure is: [x,fval,exitflag,output]=gosolver(fun,lb,ub,constr,options) Finite differences and automatic differentiation are not implemented yet. The first and/or second derivative(s) of the objective must be passed by the user. The available branch & bound algorithms are alpha B&B, unimodal form B&B and a hybrid B&B algorithm. For the unimodal form B&B one has to pass the first derivative of the objective function as second output argument of fun. For the other algorithms one has to pass first and second derivatives of the objective as second and third output argument. The (possibly) not box chaped feasible set of the problem that is given by C is relaxed and approximated by boxes. INPUT: ------ fun : objective function form: [F,DF,D2F] = fun(x) F: IR^n -> IR, DF: IR^n -> IR^(n x 1) D2F: IR^n -> IR^(n x n) LB : lower bounds on x UB : upper bounds on x constr : vector of an overall number of m (non-)linear inequality constraints (optional) form: G = constr(x) G: IR^n -> IR^m options : structure with different options for optimization (optional) MaxIter : max. number of iterations DEFAULT: 1000*n TolConv : tolerance for convergence DEFAULT: 1e-3 Algori : algorithm used for optimization aBB_box - alpha branch & bound method ufBB_box - unimodal form branch & bound method hybBB_box - hybrid branch & bound method DEFAULT: aBB_box Split : choice of the edge in the branching rule max - split the longest edges of a box gradmax - split the longest edges weighted with an interval gradient of the objective gradmid - split the longest edges weighted with an interval gradient of the objective and adjusted with the barycenter of the box ratz - branching rule from D. Ratz relmax - split the longest edge measured with some kind of relative length DEFAULT: max Point : choice of the point in the branching rule bary - barycenter of the box min - minimum of the objective function DEFAULT: bary Relax_para : how and how often relaxation parameters are computed - for option all and one the parameters are not computed exactly but with techniques from interval analysis all - on each generated box a (set of) relaxation parameter(s) is computed one - use the parameters from the first given global box on each generated box sub - uses a given function to compute the relaxation parameters ->for the alpha B&B method one has construct a function alpha_sub_explicit.m that returns the largest eigenvalue of D2F on a given box [lb,ub] (see below) ->for the unimodal form B&B method one has to construct a function lip_sub_explicit.m that returns lower and upper bounds of DF on a given box [lb,ub]. (see below) ->for the hybrid B&B method one has construct both mentioned functions DEFAULT: all List : return the list of boxes and related parameters generated and computed during optimization on - returns the list in output.List off - does not return the List DEFAULT: off debug : if you wish additional output during optimization set options.debug = [] OUTPUT: ------- x : last box chosen in optimization process fval_low : lower value on the value of the objective function fval_up : upper bound on the value of the objective function exitflag : integer identifying the reason the algorithm terminated -9 : an error occured in the input -3 : increase iter_max -2 : boxes become too small 1 : epsilon optimal solution 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 List : list of boxes and related parameters generated and computed during optimization IMPORTANT: ---------- 1.) If (non-)linear inequality constraints are given, then the box [lb,ub] must be that large that the feasible set of the problem is in the interior if the given box. 2.) input/output-structure for alpha_sub_explicit.m alpha_sub_explicit.m returns the smallest eigenvalue of D2F on a given box [lb,ub]. The input/ouput-structure is: alpha_relax = alpha_sub_explicit(fname,lb,ub). fname is a function handle of the objective function and lb, ub are the lower and upper bounds of a box. 3.) input/output-structure for lip_sub_explicit.m lip_sub_explicit.m returns lower and upper bounds on DF on a given box [lb,ub]. The input/ouput-structure is: [L_low,L_up] = lip_sub_explicit(fname,lb,ub). fname is a function handle of the objective function and lb, ub are the lower and upper bounds of a box. 4.) If no explicit formula for the relaxation parameters are given GOSOLVER needs a package/toolbox for interval arithmetics. The toolbox we prefer is IntLab from Prof. Dr. Siegfried M. Rump, Institute for Reliable Computing, Hamburg University of Technology. GOSOLVER is tested with IntLab, Version 6. If one wishes to use IntLab please add the correct path. NOTE that IntLab is NOT a part of GOSOLVER and that GOSOLVER does not affect or imply any license agreement for IntLab. The directory should contain a test file called test.m and a related example objective and constraint m-files. For the call of the function we refer to test.m _________________________________________________________________________________________ 2.) Realated files ------------------ Here is a list of related files that come with and that are needed by NLPSOLVER: README.txt test.m rosenbrock.m circ.m simp.m gosolver.m GG_min.m f_alpha.m refine.m aBB.m aBB_box.m ufBB.m ufBB_box.m hybBB.m hybBB_box.m __________________________________________________________________________________________ 3.) References -------------- C.S.Adjiman, C.A.Androulakis, C.A.Floudas A Global Optimization Method, αBB, for general twice-differentiable constrained NLPs - I: Theoretical advances Computers and Chemical Engineering, 22 (1998), pp. 1137-1158 C.S.Adjiman, C.A.Androulakis, C.A.Floudas A Global Optimization Method, αBB, for general twice-differentiable constrained NLPs - II: Implementation and computational results Computers and Chemical Engineering, 22 (1998), pp. 1159-1179 E. Baumann Optimal Centered Forms BIT Numer. Math., 28 (1988), pp. 80-87 T.Csendes, D.Ratz Subdivision direction selection in interval methods for global optimization SIAM J. Numer. Anal., 34 (1997), pp. 922-938 J.Gaerttner Unimodale Relaxierungen in der globalen Optimierung: Hybridverafahren und numerische Untersuchungen Bachelorthesis, KIT, Institut for Operations Research - Continuous Optimization, 2010 R.Horst An Algorithm for Nonconvex Programming Problems Math. Prog., 10 (1976), pp. 312-321 D.Ratz On the Selection of Subdivision Directions in Interval Branch-and-Bound Methods for Global Optimization Journal of Global Optimization, 7 (1995), pp. 183-207 S.M.Rump INTLAB - INTerval LABoratory In Tibor Csendes editor, Developments in Reliable Computing, pp. 77-104 Kluwer Academic Publishers, Dordrecht, 1999 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 GOSOLVER_BOX and all functions/files 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.) Contact Information ----------------------- Paul Steuermann - KIT, Germany Institute of Operations Research - Continuous Optimization e-mail: nlpsolver@ior.kit.edu Homepage: kop.ior.kit.edu