InteriorPointSolver<T>

Models & Types · AiDotNet.Solvers.InteriorPoint

Solves linear and convex quadratic programs with a primal-dual path-following interior-point method using Mehrotra’s predictor-corrector.

Implements: ILinearProgramSolver<T>, IQuadraticProgramSolver<T>

For Beginners

Picture the allowed region as a room and the goal as its lowest corner. The simplex method feels its way along the walls from corner to corner. This method starts in the middle of the room and walks downhill toward the low corner without ever touching a wall — stopping just short each time, because the arithmetic breaks down exactly at the wall. It gets very close very fast, which is why large-scale solvers reach for it.

How It Works

Implements the algorithm of S. Mehrotra, “On the Implementation of a Primal-Dual Interior Point Method”, SIAM Journal on Optimization 2(4), 1992, pp. 575-601, following the presentation and starting-point heuristic in J. Nocedal and S. J. Wright, Numerical Optimization (2nd ed., Springer 2006), Chapter 14 and Section 16.6.

How it differs from the simplex method.SimplexSolver walks from corner to corner of the feasible region along its edges, and the number of corners it visits can in the worst case grow exponentially. An interior-point method instead stays strictly inside the region and drives toward the optimum along the central path, cutting across the middle. Each step costs a matrix factorization rather than a cheap pivot, but the number of steps grows only logarithmically with the accuracy demanded and barely at all with problem size — so simplex tends to win on small problems and interior point on large or dense ones. Both implement ILinearProgramSolver, so swapping them changes nothing else.

Why one class solves both. The Newton system for a convex quadratic program is the linear program’s system with the objective’s Hessian Q added to one block. Setting Q = 0 recovers the linear case exactly, so the two share every line of the iteration; the only specialization is that when Q is absent that block is diagonal and inverts by division.

Infeasibility and unboundedness are proved, not guessed. Slow progress is not evidence of anything, so this solver reports Infeasible or Unbounded only after checking an explicit certificate: a direction y with Aᵀy ≤ 0 and bᵀy > 0 proves by Farkas’ lemma that no feasible point exists, and a direction d ≥ 0 with Ad = 0, Qd = 0 and cᵀd < 0 is a ray along which the objective falls forever. The iterates of an infeasible-start method converge to exactly these directions, so the check costs one matrix product per iteration.

Example

// minimize -x - y  subject to  x + 2y <= 4,  3x + 2y <= 6,  x, y >= 0
var program = new LinearProgram<double>(
    objective: new Vector<double>(new[] { -1.0, -1.0 }),
    inequalityMatrix: new Matrix<double>(new[,] { { 1.0, 2.0 }, { 3.0, 2.0 } }),
    inequalityBounds: new Vector<double>(new[] { 4.0, 6.0 }));
            
var solution = new InteriorPointSolver<double>().Solve(program);
// solution.Status == LinearProgramStatus.Optimal
// solution.Solution is approximately (1, 1.5), objective -2.5

Constructors

Constructor Summary
InteriorPointSolver() Creates an interior-point solver with the default options.
InteriorPointSolver(InteriorPointSolverOptions options) Creates an interior-point solver.

Methods

Method Summary
LinearProgramSolution<T> Solve(LinearProgram<T> program)
QuadraticProgramSolution<T> Solve(QuadraticProgram<T> program)