Unconstrained version of Charibde in julia

There's a very famous saying, "solution of great problem come from day to day life", isnt it? Imagine, you are given a task which is quite tedious and difficult to complete by one worker and luckily to solve it you also have two best workers and with them you are asked to return the output in minimum time, obviously the best technique to make it done is to harness the power of these both workers in parallel which allows the task to be completed more quickly. This is the key idea behind the technique which is proposed and implemented by Charlie Vanaret in Ocaml in its Phd thesis for difficult global optimising problems (to find minimum or maximum of the given objective function in given domain) and named it Charibde: a Cooperative Approach.

Charibde is a synergetic scheme aimed to establish cooperation between the two approaches in order to benefit from their advantages:

1. quickly explore the search space;

2. avoid being trapped in local minima;

3. eliminate subspaces that are not feasible;

4. Certify the optimality of the solution;

Interval-based method is the only rigorous approach to achieve a numerical proof of optimality in global optimisation that interleave branching of the search-space and pruning out the subdomains that cannot contain an optimal solution. Generally, state-of-the-art solvers integrate local optimisation algorithms to compute a good upper bound of the global minimum over each subspace. Charibde propose a cooperative framework in which interval methods cooperate with evolutionary algorithms to enhance the pruning of the search-space.

Within our cooperative solver Charibde, the evolutionary algorithm and the interval-based algorithm run in parallel and exchange bounds, solutions and search-space in an advanced manner via message passing.

Our hybrid algorithm Charibde (Cooperative Hybrid Algorithm using Reliable Interval-Based Methods and Differential Evolution) combines DE and a IBC algorithm. Although incorporating stochastic components, Charibde is a totally reliable solver.

Interval branch & Contract Algorithm : The goal of the algorithm is to find a value x that maximizes or minimizes the value of a real-valued function f(x), called an objective function, among some set S of admissible, or candidate solutions. The set S is called the search space, or feasible region. It recursively splits the search space into smaller spaces, then minimizing f(x) on these smaller spaces; the splitting is called branching. And reducing this search space because of the given constraints in the problem is called contraction.

Differential Algorithm : A basic DE algorithm works by having a population of candidate solutions (called individuals). These individuals are moved around in the search-space by using simple mathematical formulae to combine the positions of existing agents from the population. If the new position of an agent is an improvement then it is accepted and forms part of the population, otherwise the new position is simply discarded. The process is repeated and by doing so it is hoped, but not guaranteed, that a satisfactory solution will eventually be discovered.

Implementation of Charibde has been made in julia package named CharibdeOptim for unconstraint optimisation.

The package exports three functions named ibc_minimise, diffevol_minimise, charibde_min which takes objective function and domain or search space in form of Interval or IntervalBox as arguments.

ibc_minimise and diffevol_minimise implements Interval Branch & Contract and Differential Evolution algorithm, these both algorithms can be used(Non-parallel version) by calling there respected functions.

charibde_min implements Charibde, it makes run both functions (ibc_minimise and diffevol_minimise)on two different worker processes in parallel and make them able to contact through remote channels.

Running charibde_min is little bit different form ibc_minimise and diffevol_minimise .We have to do things in given order before calling charibde_min;

This version of Charibde can only handle unconstrained optimisation problem, in next few weeks I have to develop the package to handle constraint optimisation problem also.