ActiveSetQuadraticProgramSolver<T>

Models & Types · AiDotNet.Solvers.QuadraticProgramming

Solves convex quadratic programs with a primal active-set method.

Implements: IQuadraticProgramSolver<T>

For Beginners

Imagine rolling a ball into a bowl that has walls. Without walls the ball settles at the bottom, which is a one-step calculation. With walls it rolls until it hits one, then rolls along that wall, possibly into a corner. The method simulates exactly that: roll, hit a wall, add it to the list of walls you are touching, roll along them, and — importantly — check whether any wall you are pressed against is one you could leave to get lower still.

How It Works

Implements the primal active-set method for convex quadratic programming (Nocedal and Wright, “Numerical Optimization”, Algorithm 16.3). The insight it exploits is that if you already knew which inequality constraints press against the optimum, the problem would collapse to an equality-constrained quadratic program — and that has a closed-form answer, obtained by solving one linear KKT system. The method therefore guesses that set, solves, and uses the answer to correct the guess:

  • if the equality-constrained step is blocked by a constraint outside the working set, that

constraint is added and the step truncated at the blocking point;

  • if the step is zero, the point solves the current subproblem; the Lagrange multipliers

then say whether every working constraint deserves to be there. A negative multiplier means the objective would improve by moving off that constraint, so it is dropped;

  • when the step is zero and no multiplier is negative, the KKT conditions hold and the point

is optimal.

The method needs a feasible starting point, and finding one is itself a linear-programming feasibility problem — so a SimplexSolver supplies it before the quadratic phase begins. That reuse is deliberate: the phase-one machinery already exists and is already tested.

Constructors

Constructor Summary
ActiveSetQuadraticProgramSolver(ActiveSetQuadraticProgramSolverOptions options, ILinearProgramSolver<T> feasibilitySolver) Creates an active-set quadratic-programming solver.

Methods

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