Solver4J – Barrier interior-point method

The class BarrierMethod implements a barrier interior-point method optimizer (see S.Boyd and L.Vandenberghe, "Convex Optimization", p. 568 for more details), and can be used to solve the following convex optimization problem:

${minimize}_{x} f_{0} (x)$ s.t.
$f_{i} (x) < 0$ , $i = 1,...,m$
$Ax = b$

where $f_{0},..., f_{m} : R^{n} \to R$ are convex and twice differentiable, and $A \in R^{p x n}$ with $rank A = p < n$ .

There are two ways for using this optimizer:

call the BarrierMethod's constructor directly, passing in an instance of a BarrierFunction for the inequality constraints as argument
instantiate a Solver4J object, and specify Solver4J.BARRIER_METHOD as the preferred interior-point method in your optimization request (default is primal-dual interior-point method).

The inequalities

f_{i} (x) < 0

can be ordinary double comparisons for real functions as well as generalized inequalities (see S.Boyd and L.Vandenberghe, "Convex Optimization", 11.6 for more details). Solver4J comes out of the box with generalized barrier functions for SDP and SOCP optimization problems.

Code example 1

Consider the following linear objective with quadratic inequalities problem:

${minimize}_{x, y} x + y$ s.t.
$x^{2} + y^{2} < 1$

It can be solved like this:

		// Objective function (linear)
		LinearMultivariateRealFunction objectiveFunction = new LinearMultivariateRealFunction(new double[] { 1, 1 }, 0);

		// Inequality constraints
		ConvexMultivariateRealFunction[] inequalities = new ConvexMultivariateRealFunction[1];
		inequalities[0] = FunctionsUtils.createCircle(2, 1);//dim=2, radius=1, center=(0,0)

		OptimizationRequest or = new OptimizationRequest();
		or.setF0(objectiveFunction);
		or.setInitialPoint(new double[] { 0, 0 });
		or.setTolerance(1.E-5);

		// optimization
		BarrierFunction bf = new LogarithmicBarrier(inequalities, 2);
		BarrierMethod opt = new BarrierMethod(bf);
		opt.setOptimizationRequest(or);
		opt.optimize();

This will give the solution (that we expect):

					double[] sol = opt.getOptimizationResponse().solution;
				  sol[0] = -Math.sqrt(2)/2;
					sol[1] = -Math.sqrt(2)/2;

Code example 2

Consider the following linear problem:

${minimize}_{x, y} x + y$    s.t.
     $x - 3 < 0$
     $- x < 0$
     $y - 3 < 0$
     $- y < 0$

It can be solved like this:

		
	    // Objective function (plane)
		double[] C = new double[] { 1., 1. };
		LinearMultivariateRealFunction objectiveFunction = new LinearMultivariateRealFunction(C, 0.);

	   	//inequalities
		ConvexMultivariateRealFunction[] inequalities = new ConvexMultivariateRealFunction[4];
		inequalities[0] = new LinearMultivariateRealFunction(new double[]{ 1., 0.}, -3.);
		inequalities[1] = new LinearMultivariateRealFunction(new double[]{-1., 0.},  0.);
		inequalities[2] = new LinearMultivariateRealFunction(new double[]{ 0., 1.}, -3.);
		inequalities[3] = new LinearMultivariateRealFunction(new double[]{ 0.,-1.},  0.);
		
		//optimization problem
		OptimizationRequest or = new OptimizationRequest();
		or.setInteriorPointMethod(Solver4J.BARRIER_METHOD);//select the barrier interior-point method
		or.setF0(objectiveFunction);
		or.setFi(inequalities);
		or.setTolerance(1.E-5);
		
		//optimization
		Solver4J opt = new Solver4J();
		opt.setOptimizationRequest(or);
		opt.optimize();

This will give the solution (that we expect):

					double[] sol = opt.getOptimizationResponse().solution;
				  sol[0] = 0;
					sol[1] = 0;

Download test source bundle

Download the entire test source bundle from here.