Does it solve every constrained optimization problem?

No. The standard problem here is nearest-point projection onto an intersection of closed convex sets.

Are the correction vectors extra constraints?

No. They are stored quantities used by the iteration.

Why did ordinary alternating projections stop at the wrong answer?

They reached a point belonging to both sets; that point was feasible but was not closest to the original point.

AI Glossary / Mathematics and optimization / Advanced

Dykstra's projection algorithm

Definition

Dykstra's projection algorithm finds the point nearest to a given starting point within an intersection of closed convex sets. It repeatedly projects onto the individual sets while retaining correction vectors. These corrections distinguish it from ordinary alternating projections, which can find a feasible point without finding the nearest one.

What it means

Suppose a proposed solution violates several constraints. There may be many ways to make it feasible. Dykstra's method addresses the more specific objective of changing it as little as possible according to the chosen distance. The objective is defined relative to the original point, not simply relative to the previous iterate.

How it works

In the Euclidean setting, assume the closed convex sets have a nonempty intersection and their individual projections can be computed. Start at the given point with one zero correction vector per set. Before projecting onto a set, add its stored correction; after projecting, replace that correction with the difference between the adjusted input and its projection. Cycle through the sets. The resulting iterates converge to the projection onto the intersection. Practical stopping requires care: small changes alone can be misleading, and an intermediate point need not satisfy every constraint.

Three practical examples

A fictional planning tool adjusts two continuous settings subject to several linear inequalities. If its objective is minimum Euclidean change from the original settings, projecting onto the feasible intersection directly expresses that objective.
A fictional data-reconciliation system corrects a numerical vector subject to bounds and linear consistency conditions. Separate projections may be convenient, but the system must still verify the final combined constraints and specify how adjustment distances are measured.
A fictional image-processing experiment imposes several convex restrictions on a reconstruction. Projection onto their intersection can serve as a subproblem. The method does not establish that those restrictions adequately describe the real image or that every image-processing constraint is convex.

Think of it this way

Imagine adjusting a point to satisfy several boundaries while keeping a ledger of each adjustment. Without that ledger, repeated adjustments can settle at a permitted location that is unnecessarily far from the original. Dykstra's correction vectors preserve information needed for the nearest-point objective. They are part of the mathematics, not an optional audit record.

Worked example

Use two coordinates (u,v). Let set A require v>=0 and set B require v>=u. Start at s=(2,-1). Both sets are closed convex half-planes, and their intersection is nonempty.
Projection onto A replaces a negative second coordinate with zero. For a point below the boundary v=u, projection onto B replaces both coordinates with their average.
Ordinary alternating projections first send s to (2,0) in A, then to (1,1) in B. Since (1,1) belongs to both sets, further ordinary projections leave it unchanged. Its squared distance from s is (1-2) squared + (1+1) squared = 5.
For Dykstra's method, use correction vectors p=q=(0,0). The first cycle also reaches (1,1), but stores p=(0,-1) for A and q=(1,-1) for B.
In the second cycle, add p to (1,1), obtaining (1,0). It is already in A, so its projection remains (1,0), and the new p is zero. Add q to this point, obtaining (2,-1). Project onto B to get (0.5,0.5), and update q to (1.5,-1.5). The next cycle leaves the result unchanged.
The final squared distance is (0.5-2) squared + (0.5+1) squared = 4.5, smaller than 5. Independently, projecting s directly onto B gives (0.5,0.5), which also lies in A. No point in the smaller intersection can beat the nearest point in B, so this confirms the intersection projection.

Illustrative case study

In a fictional planning workshop, a team treats the example's coordinates as two standardized continuous settings. Its initial checker accepts (1,1) because both inequalities hold. A reviewer notes that the stated requirement was minimum squared adjustment from (2,-1), not merely feasibility.
The team compares objective values and finds that (0.5,0.5) improves the squared adjustment from 5 to 4.5. It then preserves the correction vectors between cycles and checks the resulting trace against the independent geometric solution.
The review also catches a stopping mistake: the first cycle's endpoint already satisfies all constraints, yet it is not the desired projection. The team therefore documents feasibility and optimality separately. This small example happens to reach the answer quickly; the workshop does not generalize that iteration count to larger problems. The scenario illustrates a mathematical distinction rather than a measured operational saving.

Common misconceptions and mistakes

Feasibility is not the same as nearest-point optimality. Both candidate points in the example are feasible, but only one minimizes distance to the starting point.
Discarding the correction vectors changes the algorithm. They must remain associated with their respective sets across cycles.
A distance objective requires meaningful scaling. Standardizing the example's coordinates is an assumption; mixing unrelated physical units without a deliberate metric changes what minimum adjustment means.
The stated convergence result assumes closed convex sets and a nonempty intersection. Applying the same iteration to incompatible or nonconvex constraints does not automatically retain that guarantee.
Reaching a stable-looking iterate is not, by itself, a general-purpose certificate of the requested accuracy.

Business use

Specify the original proposal, the constraints, and the adjustment metric before selecting a projection method. In the example, an objective comparison distinguishes two feasible plans that a simple rule checker treats alike. Test individual projections independently, then check both feasibility and distance-related convergence of the combined procedure. If changing one coordinate is more costly than changing another, investigate an appropriate weighted formulation instead of assuming ordinary Euclidean distance expresses that business preference.

Check your understanding

What are the two feasible endpoints in the example?

Answer: (1,1) and (0.5,0.5).

Which has the smaller squared distance to (2,-1)?

Answer: (0.5,0.5), with value 4.5.

Why is its optimality established?

Answer: It is the projection onto B and also belongs to A, so it already minimizes distance over the intersection.

Related terms

Convex set
Constrained optimization
Convergence
Euclidean projection
alternating projections
feasibility
correction vector
nearest-point problem
stopping criterion

Learn next

Change the starting point and recompute the two half-plane projections. Then consider how a weighted distance changes the geometric objective. Keep the projection formulas consistent with the chosen metric rather than changing only the final distance calculation.

Sources

Birgin and Raydan, Dykstra's Algorithm and Robust Stopping Criteria, Sections 1–2, author manuscript: https://www.ime.usp.br/~egbirgin/publications/brsurveydy.pdf The two half-planes, numerical trace, and planning scenario are original illustrations. The correction-vector sign convention used here is the opposite of the manuscript's stored increments, with equivalent updates.

Previous: Dyadic distribution Next: Dyna-Q