Optimizers¶
This documentation is for using and building global optimizers in C++.
You should first know how global optimization works in Ibex. Read for this the user guide.
Calling IbexOpt from C++¶
Calling the default optimizer is as simple as for the default solver.
The loaded system must simply correspond to an optimization problem. The default optimizer
is an object of the class DefaultOptimizer.
Once the optimizer has been executed(), the main information is stored in three fields, where f is the objective:
loup(“lo-up”) is the lowest upper bound known for min(f).uplo(“up-lo”) is the uppest lower bound known for min(f).loup_pointis the vector for which the value taken by f is less or equal to the loup.
Example:
/* Build a constrained optimization problem from the file */
System sys(IBEX_OPTIM_BENCHS_DIR "/easy/ex3_1_3.bch");
/* Build a default optimizer with a precision set to 1e-07 for f(x) */
DefaultOptimizer o(sys,1e-07);
o.optimize(sys.box);// Run the optimizer
/* Display the result. */
output << "interval for the minimum: " << Interval(o.get_uplo(),o.get_loup()) << endl;
output << "minimizer: " << o.get_loup_point() << endl;
The output is:
interval for the minimum: [-310.0000308420031, -309.999999842]
minimizer: (<4.999999999, 4.999999999000001> ; <1, 1.000000000000001> ; <5, 5> ; <9.999965300266921e-10, 9.999965300266922e-10> ; <5, 5> ; <10, 10>)
Getting en enclosure of all global minima¶
Given a problem:
IbexOpt gives a feasible point that is sufficiently close to the real minimum \(f^*\) of the function, i.e., a point that satisfies
with loup and uplo are respectively a valid upper and lower bound of \(f^*\), whose accuracy depend on the input precision parameter (note: validated feasibility with equalities requires ‘’rigor’’ mode).
From this, it is possible, in a second step, to get an enclosure of all global minima thanks to IbexSolve. The idea is simply to ask for all the points that satisfy the previous constraints. We give now a code snippet that illustrate this.
// ========== 1st step ==========
// Build the original system:
Variable x,y;
SystemFactory opt_fac;
opt_fac.add_var(x);
opt_fac.add_var(y);
// minimize f(x)=-x-y
opt_fac.add_goal(-x-y);
// s.t. x^2+y^2<=1
opt_fac.add_ctr(sqr(x)+sqr(y)<=1);
System opt_sys(opt_fac);
// build the default optimizer
DefaultOptimizer optimizer(opt_sys,1e-01);
// run it with (x,y) in R^2
optimizer.optimize(IntervalVector(2));
// ========== 2nd step ==========
// Build the auxiliary system
SystemFactory sol_fac;
sol_fac.add_var(x);
sol_fac.add_var(y);
sol_fac.add_ctr(sqr(x)+sqr(y)<=1);
sol_fac.add_ctr(-x-y>=optimizer.get_uplo());
sol_fac.add_ctr(-x-y<=optimizer.get_loup());
System sol_sys(sol_fac);
DefaultSolver solver(sol_sys,0.01);
solver.solve(IntervalVector(2));
// Get an enclosure of all minima, (under
// the form of manifold)
const CovSolverData& minima=solver.get_data();
The generic optimizer¶
Just like the generic solver, the generic optimizer is the main C++ class
(named Optimizer) behind the implementation of IbexOpt.
It takes as the solver:
a contractor
a bisector
a cell buffer
but also requires an extra operator:
a loup finder. A loup finder is in charge of the goal upper bounding step of the optimizer.
We show below how to re-implement the default optimizer from the generic Optimizer class.
Implementing IbexOpt (the default optimizer)¶
The contraction performed by the default optimizer is the same as the default solver (see Implementing IbexSolve (the default solver)) except that it is not applied on the system itself but the Extended System.
The loup finder (LoupFinderDefault) is a mix of differents strategies. The basic idea is to
create a continuum of feasible points (a box or a polyhedron) where the goal function can be evaluated quickly,
that is, without checking for constraints satisfaction.
The polyhedron (built by a LinearizerXTaylor object) corresponds to a linerization technique described in
[Araya et al. 2014] and [Trombettoni et al. 2011], based on inner region extraction.
It also resorts to the linerization offered by affine arithmetic (a LinearizerAffine object) if the affine plugin is installed.
The box (built by a LoupFinderInHC4 object) is a technique based on inner arithmeric also described in
the aforementionned articles.
Finally, by default, the cell buffer (CellDoubleHeap) is basically a sorted heap that allows to get in priority boxes minimizing
either the lower or upper bound of the objective enclosure (see Cell Heap).
System system(IBEX_OPTIM_BENCHS_DIR "/easy/ex3_1_3.bch");
double prec=1e-7; // precision
// normalized system (all inequalities are "<=")
NormalizedSystem norm_sys(system);
// extended system (the objective is transformed to a constraint y=f(x))
ExtendedSystem ext_sys(system);
/* ============================ building contractors ========================= */
CtcHC4 hc4(ext_sys,0.01);
CtcHC4 hc4_2(ext_sys,0.1,true);
CtcAcid acid(ext_sys, hc4_2);
LinearizerXTaylor linear_relax(ext_sys);
CtcPolytopeHull polytope(linear_relax);
CtcCompo polytope_hc4(polytope, hc4);
CtcFixPoint fixpoint(polytope_hc4);
CtcCompo compo(hc4,acid,fixpoint);
/* =========================================================================== */
/* Create a smear-function bisection heuristic. */
SmearSumRelative bisector(ext_sys, prec);
/** Create cell buffer (fix exploration ordering) */
CellDoubleHeap buffer(ext_sys);
/** Create a "loup" finder (find feasible points) */
LoupFinderDefault loup_finder(norm_sys);
/* Create a solver with the previous objects */
Optimizer o(system.nb_var, compo, bisector, loup_finder, buffer, ext_sys.goal_var());
/* Run the optimizer */
o.optimize(system.box,prec);
/* Display a safe enclosure of the minimum */
output << "f* in " << Interval(o.get_uplo(),o.get_loup()) << endl;
/* Report performances */
output << "cpu time used=" << o.get_time() << "s."<< endl;
output << "number of cells=" << o.get_nb_cells() << endl;