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