Docs / Active-Set

Active-set methods: criss-cross and PDAS

An active-set method guesses which constraints hold with equality at the optimum, solves for the point that guess implies, and repairs the guess. lpviz's Active-Set mode runs two of them: the criss-cross method, which repairs one constraint at a time, and the primal-dual active-set method (PDAS), which repairs many at once. Neither keeps the iterate inside your region, so their paths cut across the outside of the drawing.

The idea

For maximize cᵀx s.t. Ax ≤ b with n variables, a basis here is a set B of n linearly independent constraints held tight. It fixes two things:

• the point x solving A_Bx = b_B, which is where those constraint lines cross, inside your region or not;
• the multipliers y_B solving A_Bᵀy_B = c, which write the objective as a combination of the tight constraints' normals.

The basis is optimal exactly when the point breaks no other constraint (primal feasible) and every multiplier is nonnegative (dual feasible). Primal simplex keeps the first condition and works towards the second; dual simplex keeps the second and works towards the first. The methods on this page keep neither: they are free to visit any crossing of constraint lines, which is what makes their paths look so different.

The criss-cross method

Criss-cross (Terlaky, 1985; Wang, 1987) needs no phase 1 and no ratio test. At each basis it lists the constraints that are wrong — a constraint outside the basis that the point breaks, or a tight one with a negative multiplier — and fixes the first of them by index:

1. A broken constraint joins the basis; the first tight constraint whose release moves the point back towards it leaves.
2. A negative multiplier means releasing that constraint improves the objective; it leaves the basis, and the first constraint the point would run into along that direction joins.

That is all. Without a ratio test the objective can go down, and the point can jump far outside the region. What saves the method is the index rule: always fixing the lowest-index problem with the lowest-index repair provably never revisits a basis, so the walk is finite. When no repair exists, the stuck constraint is a certificate: a broken constraint no tight one can relax towards proves the LP infeasible, and a negative multiplier whose release opens a ray no constraint stops proves it unbounded.

Controls

The primal-dual active-set method

PDAS (Hintermüller, Ito and Kunisch, 2002) is Newton's method on the complementarity conditions "each constraint is tight or its multiplier is zero". From a guess of the active set it solves for the point and multipliers, then updates the guess in one block: every active constraint whose multiplier went negative is dropped, and every constraint the point breaks is added. On a strictly convex quadratic program this converges in a handful of steps.

On an LP it is ill-posed: the Newton system is only square when exactly n constraints are active, and the block update almost never produces that. So lpviz runs PDAS on the proximal method of multipliers instead. Around a primal center z and a dual center w, each subproblem

max_x min_{y ≥ 0}  cᵀx − yᵀ(Ax − b) − (ρ/2)‖x − z‖² + (δ/2)‖y − w‖²

is strictly convex in y once x = z + (c − Aᵀy)/ρ is eliminated, so every Newton system has a unique solution, whatever the active set. PDAS solves the subproblem; its solution becomes the next pair of centers; and the proximal point method reaches an optimal pair of the LP itself.

Three additions make the walk short and robust:

• Lawson–Hanson fallback. PDAS can cycle between active sets. When a subproblem repeats one, lpviz finishes that subproblem with Lawson and Hanson's monotone active-set method, which cannot cycle. Those steps carry an f in the log.
• Shrinking weights. When the iterates slide along one face, each step covers only that face's share of c/ρ, so progress crawls. While the active set holds across proximal steps, ρ and δ halve.
• Vertex identification. Once the active set has n independent constraints, lpviz solves the LP's own optimality conditions on them exactly. If that vertex is feasible with nonnegative multipliers it is the optimum, and the run ends there (marked *) instead of waiting for the centers to converge. A proximal step that repeats along a ray improving the objective ends the run as unbounded.

Controls

Reading the logs

Criss-cross on the Pentagon preset:

 Iter        x        y        Obj Pinf Dinf Tight
    1    -9.00    +4.00    -5.1e+1    0    1 1,2
    2    -2.00    +9.00    +1.3e+1    0    1 2,3
    3    +7.00    +5.00    +6.4e+1    0    0 3,4
Optimal basis after 2 pivots

• Pinf: how many constraints the point breaks. Dinf: how many tight constraints have a negative multiplier. The basis is optimal when both are zero.
• Tight: the constraints in the basis, numbered as the problem panel lists them.

PDAS on the same region:

 Iter        x        y        Obj        KKT Active
    1    +0.00    +0.00    +0.0e+0     7.0e+0 -
    2   +23.33   +10.00    +1.9e+2     1.7e+1 -
   3p    +8.24    +4.84    +7.2e+1     5.0e+0 3,4
   4*    +7.00    +5.00    +6.4e+1     0.0e+0 3,4

• KKT: the largest of the constraint violation, the stationarity gap ‖c − Aᵀy‖_∞ and the complementarity gap. In the 3D view each PDAS iterate rises by it, so the path comes down to the floor at the optimum; criss-cross has no such measure and is drawn flat, like simplex.
• Active: the constraints whose multipliers are free in that Newton step ("−" for none; a long list shows as a count).
• Markers after the iteration number: p solved its subproblem, so the centers moved; f is a Lawson–Hanson step after a cycle; * is the identified optimal vertex.

Behavior to watch for

• Index order matters enormously. On Many Facets, criss-cross with Lowest first pivots around the boundary in 3 steps. Switch to Highest first and it zig-zags in 18, alternating between crossings far outside the region and vertices on its far side.
• The objective can go down. Nothing in criss-cross forces improvement: watch the Obj column jump up and down in the highest-first run. Finiteness comes from the index rule alone.
• Block changes. In PDAS's log, the active set can lose and gain several constraints in one step, where criss-cross and simplex change one at a time. On Many Facets, the first Newton step activates every constraint the unconstrained step broke.
• The first step is c/ρ. Drag the PDAS start marker or move the ρ slider: the second iterate always sits at the start plus c/ρ, and the rest of the path pulls back from there.
• Turn off the shortcuts. With Identify vertex and Shrink weights off, PDAS is the plain proximal method of multipliers with PDAS subproblems — and on a nearly flat facet it can take hundreds of steps to slide to the optimum.