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