Is the corrector just another independent optimization run?

No. It uses the predictor's information within the same iteration.

Must the centering exponent always be three?

Three is common, but algorithm variants and implementations can use other choices.

Does correcting the direction eliminate step-length restrictions?

No. The worked example still requires a shorter step to maintain positive slacks.

AI Glossary / Mathematics and optimization / Intermediate

Mehrotra predictor - corrector method

Definition

Mehrotra's predictor - corrector method is a primal - dual interior-point optimization method that combines an affine-scaling prediction with a correction for centering and nonlinear complementarity effects. It is widely associated with linear programming and extends to other optimization settings. Its predictor and corrector calculations can reuse the same linear-system factorization within an iteration, making the additional correction comparatively economical.

What it means

An interior-point solver works with primal variables, dual variables, and positive slack quantities while approaching optimality. The predictor estimates how aggressively the algorithm could reduce complementarity. The corrector adjusts that direction using what the prediction reveals.
The word predictor does not mean forecasting future business data. It describes a trial direction in the optimization equations. Likewise, the corrector does more than undo numerical rounding: it includes a second-order complementarity term and a centering target. Implementations differ in step-length policies, initialization, scaling, and stopping rules, so a named method does not specify every detail of a solver.

How it works

For a standard linear program, write primal feasibility as Ax=b, dual feasibility as Aᵀy+s=c, and complementarity as x_i s_i=0. Interior iterates maintain x and s positive. Their average complementarity is μ=xᵀs/n.
First solve a Newton system targeting zero complementarity to obtain an affine direction. Estimate the complementarity μ_aff achievable along its feasible trial step. A common centering choice is σ=(μ_aff/μ)³. The corrected complementarity right-hand side includes σμ and subtracts the elementwise product of the affine primal and slack directions. Reusing the system matrix avoids repeating its expensive factorization. Finally choose a step that preserves positivity and evaluate feasibility residuals as well as complementarity.

Three practical examples

A linear resource-allocation model can use a primal - dual solver to approach an optimal feasible allocation and its associated dual prices.
A convex quadratic optimization package can adapt the predictor - corrector structure to its own optimality equations.
A numerical-software team can exploit a shared factorization when computing multiple search directions for a large sparse model.

Think of it this way

Think of planning a move, estimating how close that move comes to a boundary, and adjusting the route before committing. The analogy is limited because the correction follows specific algebraic equations, not visual intuition. Keeping away from a boundary during iterations also does not mean the final optimum must lie strictly inside the feasible region.

Worked example

Consider an original linear program: minimize x_1+2x_2 subject to x_1+x_2=1 and nonnegative variables. Start at x=(1/2,1/2), dual variable y=0, and dual slacks s=(1,2). Primal and dual equalities hold, and μ=(0.5×1+0.5×2)/2=3/4.
The affine direction must satisfy Δx_1+Δx_2=0, Δs_1=Δs_2=−Δy, and s_iΔx_i+x_iΔs_i=−x_i s_i. Solving gives Δx_aff=(1/6,−1/6), Δy_aff=4/3, and Δs_aff=(−4/3,−4/3).
Using a single common trial step, the largest step up to one preserving nonnegativity is 3/4, because the first slack reaches zero. The trial values are x_aff=(5/8,3/8) and s_aff=(0,1). Therefore μ_aff=3/16 and σ=((3/16)/(3/4))³=1/64.
The second-order products are (−2/9,2/9). The centering-corrector right-hand side for the complementarity equations is consequently (3/256+2/9,3/256−2/9), or (539/2304,−485/2304). This shows explicitly why the correction is not simply the same positive centering amount in every component.
With zero right-hand sides for the feasibility equations, the separate corrector has Δx_cc=(4/27,−4/27), Δy_cc=−593/3456, and both slack-direction entries equal to 593/3456. Adding predictor and corrector gives Δx=(17/54,−17/54) and both slack-direction entries equal to −4015/3456. A full unit step would make the first slack negative. A suitable shorter step is therefore still required after computing the correction.
The known solution is x=(1,0), with objective one. The calculations above illustrate one direction construction, not convergence in a single iteration. Exact rational arithmetic was used to check the example's linear equations.

Illustrative case study

In a fictional production-planning team, analysts use a solver based on this method for a continuous allocation model. They inspect both feasibility residuals and the primal - dual gap before accepting a result, then separately handle any requirement for whole production units. The example illustrates solver review; it does not report a real factory outcome or imply that a continuous solver automatically satisfies integer restrictions.

Common misconceptions and mistakes

The affine trial point may lie on the boundary, while the accepted interior iterate normally stays strictly positive in the relevant variables. Confusing these roles can produce invalid updates. Another mistake is dropping the affine cross-product correction and still claiming to implement the same predictor - corrector equations.
The method does not always use a Cholesky factorization: the appropriate linear algebra depends on the system formulation and solver. A small complementarity measure also does not alone certify a good answer when primal or dual residuals remain large. Numerical conditioning, scaling, and termination criteria remain consequential.

Business use

For business users, the method usually matters through the optimization software that implements it. Supply a well-scaled model, meaningful bounds, and accurate costs. Read the solver status and residuals rather than accepting any returned vector as optimal. Separate continuous optimization from later rounding or discrete decisions, and verify that the final operational plan remains feasible.

Check your understanding

Why is the affine common trial step 3/4?

Answer: Starting from s_1=1 with direction −4/3, the first slack reaches zero at α=3/4; a larger common step would make it negative.

Related terms

Interior-point method
Duality gap
Linear programming
Primal–dual optimization
Complementarity
Newton method
Central path
Sparse factorization

Learn next

Substitute the combined direction into the feasibility equations and verify that both remain satisfied to first order. Then compute the largest nonnegative common step and choose a slightly smaller value to retain strict positivity.

Sources

Primary source: Gertz and Wright, Object-Oriented Software for Quadratic Programming, section 2.2 and algorithm MPC: https://pages.cs.wisc.edu/~swright/ooqp/ooqp-paper.pdf . The standard-form linear-program example here is original and uses a common trial step with centering exponent three.

Previous: Mega-Merger Next: Mel