Are intermediate iterates always feasible?

No. Constraint violations can persist while the method progresses, which is why residuals must be monitored.

Why update multipliers?

Their updates carry constraint-violation information forward, distinguishing the method from a fixed quadratic penalty alone.

Is it the same as ADMM?

No. ADMM introduces a particular alternating block structure; the standard method of multipliers minimizes the primal augmented Lagrangian jointly.

AI Glossary / Mathematics and optimization / Advanced

Method of multipliers

Definition

The method of multipliers is an iterative method for constrained optimization that alternates between minimizing an augmented Lagrangian and updating the Lagrange multipliers. The augmented Lagrangian combines the original objective, a multiplier term for constraint violations, and a quadratic penalty. This entry focuses on equality constraints of the form Ax=b.

What it means

The method tries to improve the objective while progressively enforcing the constraints. The multipliers carry information about constraint violations from one iteration into the next; the quadratic penalty also discourages violations within each minimization subproblem.

It is more than solving a fixed penalized objective once. The repeated multiplier update is essential. The method is also distinct from ADMM, which exploits a split-variable structure and alternates between blocks rather than carrying out the same joint primal minimization. Convergence statements require assumptions about the objective, constraints, and accuracy of the subproblem solutions.

How it works

For minimizing f(x) subject to Ax=b, define L_rho(x,y)=f(x)+yᵀ(Ax−b)+(rho/2)‖Ax−b‖², with rho>0. Here x is the decision vector and y is the multiplier vector.

At iteration k, minimize L_rho(x,y_k) over x to obtain x_(k+1). Then update y_(k+1)=y_k+rho(Ax_(k+1)−b). The new multiplier incorporates the latest feasibility residual. Repeating these steps can move the iterates toward a constrained solution under suitable conditions.

The augmented term is zero at feasible points, so it does not change objective comparisons among those points. Nevertheless, intermediate iterates can be infeasible. Their original objective values may look better than the constrained optimum simply because they violate the rules. Monitoring feasibility and appropriate optimality conditions is therefore part of evaluating progress.

Three practical examples

1. Constrained model fitting: enforce linear relationships among parameters while optimizing a chosen fitting objective.

2. Resource allocation: solve a continuous allocation model with equality balances, such as requiring a specified total, under an appropriate mathematical formulation.

3. Optimization education: compare ordinary Lagrangian methods, quadratic penalties, and ADMM to understand what multiplier updates contribute.

Think of it this way

Think of a planner proposing a solution, checking how far it misses an agreed balance, and carrying that feedback into the next proposal. The penalty discourages imbalance immediately, while the multiplier retains accumulated correction information.

The analogy does not mean that increasing pressure always solves every problem. Infeasible constraints cannot be satisfied, poorly solved subproblems can disrupt progress, and algorithmic guarantees depend on the specific mathematical setting.

Worked example

Minimize f(x)=(x−5)²/2 subject to x=2. The only feasible point is x=2, with objective 9/2=4.5. Use rho=1 and start with multiplier y_0=0.

The augmented Lagrangian is (x−5)²/2+y(x−2)+(x−2)²/2. Differentiating with respect to x gives (x−5)+y+(x−2)=2x−7+y. Its minimizing value is x=(7−y)/2.

The first update gives x_1=3.5, residual x_1−2=1.5, and y_1=1.5. The second gives x_2=(7−1.5)/2=2.75, residual 0.75, and y_2=2.25. The third gives x_3=2.375, residual 0.375, and y_3=2.625.

The residual halves each time in this example. The limit is x=2 and y=3, satisfying stationarity x−5+y=0 and the constraint. The first original objective, f(3.5)=1.125, is below 4.5, but that iterate is infeasible. It is not a better solution to the constrained problem. If we minimized the fixed quadratic penalty once with y=0 and never updated y, we would remain at 3.5 for this penalty value.

Illustrative case study

Fictional case: a team fits a forecasting adjustment subject to an exact aggregate balance. Its early optimization report emphasizes a low fitting loss while omitting the remaining balance error.

The reviewer adds the constraint residual and multiplier behavior to the report. The team checks that its subproblem is being solved to the intended accuracy and that the balance is actually feasible. It then evaluates the final constrained fit on held-out data. The optimization procedure enforces the mathematical requirement; it does not establish that the requirement or forecasting objective is appropriate for the business.

Common misconceptions and mistakes

Do not confuse the method with a single fixed penalty calculation. Do not assume its iterates satisfy the constraints at every step or that a low original objective proves success.

The penalty parameter affects the subproblems and numerical behavior; making it extremely large is not a universal improvement. Also distinguish the method of multipliers from ADMM: they are related augmented-Lagrangian approaches, but their update schedules differ. General nonconvex problems do not inherit unconditional global-optimality guarantees from a simple convex example.

Business use

The method is useful when a model or planning problem must satisfy explicit constraints while still optimizing another criterion. It offers a systematic way to combine objective progress with feasibility feedback.

For implementation review, record the precise constraint equations, penalty choices, subproblem solver, and stopping criteria. Examine numerical conditioning and whether reported feasibility is within an acceptable tolerance. A mathematically feasible allocation or fitted parameter vector still needs validation against the assumptions and consequences of the original operational problem.

Check your understanding

An iterate has an objective below the known constrained optimum but violates an equality constraint. Has the method found a superior solution?

Answer: No. The iterate is not feasible and therefore is not a valid competitor in the constrained optimization problem.

Related terms

Augmented Lagrangian
Penalty method
Constrained optimization
Lagrange multiplier
equality constraint
primal feasibility
dual variable
ADMM

Learn next

reproduce the scalar iterations and compare them with a fixed penalty method. Then study how ADMM changes the primal minimization into block updates and why the assumptions behind convergence need separate attention.

Penalty method

Sources

Boyd and colleagues, Distributed Optimization and Statistical Learning via ADMM, section 2.3: https://stanford.edu/~boyd/papers/pdf/admm_distr_stats.pdf . Aalto Dictionary of Machine Learning, method of multipliers entry: https://aaltodictionaryofml.github.io/ADictML_Main.pdf . Augmented-Lagrangian and update formulas were read. The scalar iteration and feasibility comparison are original calculations.

Previous: Method of moving asymptotes Next: Method of types