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) |