Is the method the same as gradient descent?

No. A projection enforces a selected constraint under a chosen divergence, although related algorithms may use gradient coordinates.

Must a Bregman projection be multiplicative?

No. Its form depends on the generator and constraint.

Does a feasible answer prove the intended objective is optimal?

No. Check the actual optimization algorithm and its assumptions, not just constraint satisfaction.

AI Glossary / Mathematics and optimization / Advanced

Bregman method

Definition

The Bregman method is a family of iterative projection techniques for convex feasibility and related convex optimization problems. Instead of always using ordinary straight-line distance, it measures a proposed adjustment with a divergence generated by a convex function. In classical settings, successive simple constraint corrections can solve a larger constrained problem.

What it means

Suppose an estimate must satisfy several conditions. Correcting every condition simultaneously may be expensive, while correcting one condition at a time may be easy. Projection methods exploit that difference.

A Bregman projection asks which point satisfying the selected condition is closest under a chosen mathematical measure. Choosing that measure changes the correction. Squared Euclidean distance produces familiar perpendicular projections; entropy-based geometry can produce multiplicative adjustments that are natural for positive quantities.

This entry uses the classical projection and convex-programming sense. Later Bregman iterative regularization and split Bregman algorithms share mathematical ideas but are not interchangeable names for every version of the original method.

How it works

Choose a differentiable convex generator φ. Its Bregman divergence is Dφ(x,y)=φ(x)−φ(y)−∇φ(y)·(x−y). The expression compares the function with its tangent approximation at y. It is nonnegative on the appropriate domain but is generally asymmetric and need not satisfy a triangle inequality.

Starting from an admissible point, project onto a selected constraint set by minimizing Dφ(x,current) over that set. Repeat with other constraints according to the algorithm's selection rule. For linear constraints, updates may be organized by individual rows, with gradient or dual quantities tracking corrections.

Convergence requires suitable assumptions on the generator, constraint sets and their intersection. Feasibility means finding a common admissible point. Obtaining a particular constrained objective minimum requires the corresponding optimization formulation and initialization; arbitrary repeated projections should not be advertised as solving every convex objective.

Three practical examples

1. Table adjustment: modify positive cell estimates to satisfy known totals, using an entropy-based discrepancy rather than treating equal absolute changes as equally meaningful everywhere.

2. Reconstruction: apply successive corrections to a nonnegative image estimate so that modeled measurements better satisfy convex measurement constraints.

3. Planning: solve a convex allocation formulation whose individual linear resource constraints are cheap to process, provided the chosen projection scheme matches the actual objective and domain.

Think of it this way

Think of tailoring a garment through several fittings. Each fitting corrects one requirement while trying to disturb the existing shape as little as possible. Your definition of “little” matters: preserving proportions produces different alterations from preserving absolute lengths.

The analogy does not establish convergence. Real tailoring can involve irreversible cuts and nonconvex requirements. The mathematical method depends on specific properties that a practical adjustment process may lack.

Worked example

Consider an original positive-vector example. Start with q=(1,3) and require x₁+x₂=8. Use the entropy generator φ(x)=Σ xᵢ log xᵢ on positive coordinates. The resulting divergence is Σ[xᵢ log(xᵢ/qᵢ)−xᵢ+qᵢ]. Logs are natural.

To minimize this divergence subject to the total, introduce a multiplier λ. Differentiation gives log(xᵢ/qᵢ)+λ=0, so both coordinates share a multiplier: xᵢ=cqᵢ. Their sum requires 4c=8, hence c=2 and the projection is (2,6).

Its divergence is 8 log 2−4, approximately 1.545. Ordinary squared-Euclidean projection instead adds two to each coordinate and gives (3,5). That point satisfies the same total, but its entropy divergence is 3 log 3+5 log(5/3)−4, approximately 1.850, which is higher.

The positive diagonal Hessian, with entries 1/xᵢ, confirms strict convexity in this domain and therefore uniqueness of this constrained minimizer. This is one hand-checked Bregman projection, not a benchmark or a demonstration that every multiple-constraint iteration finds the nearest feasible point.

Illustrative case study

Fictional case: a small forecasting team adjusts a positive demand table to reconcile category totals. Staff initially add equal amounts to every cell. That changes small cells proportionally far more than large cells.

The analyst demonstrates an entropy-based projection and explains why the adjustment better reflects the team's chosen notion of discrepancy. Before scaling up, the team checks whether row and column totals are consistent, how zeros should be represented, and whether the complete algorithm optimizes the intended criterion. The choice is justified by modeling assumptions rather than a claim that multiplicative updates are always more accurate.

Common misconceptions and mistakes

Do not describe a Bregman divergence as an ordinary distance metric. Swapping its arguments can change both the value and the projection.

Do not assume feasibility and nearest-point optimization are the same task. A method can reach the intersection without producing the particular closest point you expected.

Do not insert zero or negative coordinates into a logarithmic formula without examining its domain and boundary conventions. Also check whether inconsistent totals make the constraint intersection empty. Repeated computation cannot create a common point that does not exist.

Business use

For businesses, the useful decision is whether the geometry expresses a defensible cost of changing an estimate. An entropy-based discrepancy may suit positive counts or proportions; another generator may better reflect a different problem.

Evaluate constraint residuals, objective values, numerical stability and runtime separately. Record stopping tolerances and test small problems with independently known solutions. A cheap individual update does not guarantee a cheap complete solve, especially when constraints interact strongly or the requested accuracy is demanding.

Check your understanding

Why do (2,6) and (3,5) both meet the example's total but represent different projections?

Answer: The first minimizes the specified entropy divergence from (1,3); the second minimizes squared Euclidean distance. The constraint is identical, but the definition of adjustment cost differs.

Related terms

Bregman divergence
Entropy
convex feasibility
projection
row-action method
dual variable
Dykstra's algorithm
split Bregman method

Learn next

derive the Euclidean projection onto a sum constraint, then repeat the entropy calculation with a different total. Study why adding multiple convex sets introduces questions that a single projection does not settle.

Entropy

Sources

Sources: Bauschke and Borwein, “Legendre Functions and the Method of Random Bregman Projections,” introduction and formulation read: https://journalofconvexanalysis.com/articles/jca04002/jca04002.pdf?v=2 . Bregman's author publication list confirms the historical convex-programming lineage: https://www.math.bgu.ac.il/~bregman/publications.html . The original 1967 paper could not be retrieved in full; this introductory account uses the later primary analysis. Example and case are original.

Previous: Bregman divergence Next: Breusch - Godfrey test