Solver4J – Primal-dual interior-point method

The class PrimalDualMethod implements a primal-dual interior-point method optimizer (see S.Boyd and L.Vandenberghe, "Convex Optimization", p. 609 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 PrimalDualMethod's constructor directly
instantiate a Solver4J object, and specify Solver4J.PRIMAL_DUAL_METHOD as the preferred interior-point method (you can also leave it blank, this is the default).

Code example 1

Consider the following linear problem:

${minimize}_{x, y} 2x + y$    s.t.
     $- x < 0$
     $- y < 0$
     $x + y = 1$

It can be solved like this:

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

		// Inquality constraints
		ConvexMultivariateRealFunction[] inequalities = new ConvexMultivariateRealFunction[2];
		inequalities[0] = new LinearMultivariateRealFunction(new double[] { -1,  0 }, 0);
		inequalities[1] = new LinearMultivariateRealFunction(new double[] {  0, -1 }, 0);

		OptimizationRequest or = new OptimizationRequest();
		or.setF0(objectiveFunction);
		or.setInitialPoint(new double[] { 0.9, 0.1 });
		or.setFi(inequalities);
		// Equality constraints
		or.setA(new double[][] { { 1, 1} });
		or.setB(new double[] { 1 });
		or.setTolerance(1.E-9);
		
		// optimization
		PrimalDualMethod opt = new PrimalDualMethod();
		opt.setOptimizationRequest(or);
		opt.optimize();

This will give the solution:

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

Code example 2

Consider the following linear objective with quadratic inequalities problem (the same as barrier-method example 1):

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

It can be solved like this:

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

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

		OptimizationRequest or = new OptimizationRequest();
		or.setF0(objectiveFunction);
		or.setInitialLagrangian(new double[]{10});
		or.setFi(inequalities);
		or.setInteriorPointMethod(Solver4J.PRIMAL_DUAL_METHOD);//this is also the default
		or.setToleranceFeas(5.E-6);
		//or.setCheckKKTSolutionAccuracy(true);
		//or.setCheckProgressConditions(true);

		// 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] = -Math.sqrt(2)/2;
					sol[1] = -Math.sqrt(2)/2;

Download test source bundle

Download the entire test source bundle from here.