OBOE solver

OBOE (Oracle Based Optimization Engine) is an open source software for general convex optimization.

It assumes that a user-made code, thereafter named oracle, is capable of delivering first order information on the key elements of the problem (support the feasible set, support to the objective function). The engine exploits this information to construct the so-called localization set which is a polyhedral approximation of the set of optimal solutions.

To implement OBOE on a typical problem of convex optimization such as "min {f(x) | x in X}" the user must implement an oracle with the following specification:

  • Input to the Oracle: a query point x provided by OBOE.
  • Output from the Oracle:
    • If x is feasible, the oracle returns the value f(x) and an element of the subgradient of f at x.
    • If x is infeasible, the oracle returns a hyperplane separating x and the feasible set X.

An optimization session alternates computations by the oracle and by OBOE until the relative optimality gap at the current iterate meets the target value assigned by the user. The user can alternatively set his own stopping rule.

The query points that OBOE selects are approximate minimizers of a logarithmic barrier function on the polyhedral set plus a proximal term. OBOE is an implementation of ACCPM, the Analytic Center Cutting Plane Method.

You can freely download OBOE sources on the coin-or.org website.