The Gold Standard of Discrete Convex Analysis

Chapter index

Suppose five identical equipment units must be distributed among three teams. An allocation is an integer vector x=(a,b,c), where a, b and c are nonnegative and a+b+c=5. The teams cannot receive fractions of a unit. There are twenty-one feasible allocations, so this small example can be checked completely.

We assign the illustrative cost F(a,b,c)=(a−4)²+2(b−2)²+(c−1)². The targets are four, two and one, but together those targets require seven units. With only five available, some shortfall is unavoidable. The factor two places greater weight on deviations from team B’s target.

This formula is a teaching model, not an empirical claim about equipment productivity. Its units are weighted squared deviations. If the decision were about actual service, the targets and weights would need justification. A numerically exact optimizer cannot determine whether these priorities are socially appropriate or operationally realistic.

Two features make the problem more than three separate calculations. First, the decision variables are integers. Second, the total is fixed: giving a unit to one team requires taking it from another. The natural local move is therefore a transfer, such as (a,b,c) becoming (a−1,b+1,c), provided the donor has a unit.

Changing just one coordinate would violate the total. A search algorithm that tests only such changes would find no feasible move anywhere and could mistakenly label every allocation optimal. The neighbourhood must reflect the constraint before any theorem about local optimality becomes meaningful.

This is the first habit to develop: write the feasible moves alongside the feasible points. The two are related but not identical. A domain describes allowed decisions; a neighbourhood describes how the method explores them. A correct stopping certificate depends on both.

Contents · Next chapter

For an integer-valued argument t, consider q(t)=(t−4)². Define its forward difference d(t)=q(t+1)−q(t). Expanding the squares gives d(t)=2t−7. At t=0,1,2,3,4, the differences are −7,−5,−3,−1,1.

The differences are nondecreasing. Early additions reduce the cost substantially, later additions reduce it less, and additions beyond the target eventually increase it. This is the discrete counterpart of increasing slope. It does not require taking a derivative at a noninteger point.

Equivalently, q(t−1)+q(t+1)≥2q(t) wherever the three arguments are allowed. For this quadratic the left side exceeds the right side by two. A middle integer point is no more expensive than the average of its immediate neighbours.

On an integer interval, nondecreasing differences explain why a local minimum is global. If moving right no longer helps, all subsequent rightward increments are at least as large. If moving left does not help either, there is no cheaper point in either direction. This argument relies on the interval containing the intervening integer points.

A domain with holes requires care. If only t=0 and t=2 are feasible, neither point has a feasible one-step neighbour. A unit-step test is then uninformative. Encoding feasibility is not a minor implementation detail; it changes what local evidence can establish.

For practice, use q(t)=(t−2)² on t=0,1,2,3,4. The values are 4,1,0,1,4, and the differences are −3,−1,1,3. Explain why t=2 is optimal using the differences rather than the visual symmetry. That explanation will still work when the costs are not symmetric.

Previous chapter · Contents · Next chapter

The continuous version of our allocation cost is a convex quadratic. Allowing real-valued allocations can provide a useful lower bound on the integer minimum, because the continuous feasible set contains every integer feasible point. But a lower bound is not itself an implementable allocation.

For the five-unit example, the continuous optimum is (3.2,1.6,0.2). It is feasible in the relaxed problem and has cost 0.64+0.32+0.64=1.6. One can obtain it by equalizing the partial derivatives under the fixed-total constraint: 2(a−4)=4(b−2)=2(c−1)=−1.6.

The best integer allocation will have cost at least 1.6. Rounding happens to produce (3,2,0), whose cost is two, but this successful rounding is not a general argument. Independent rounding can violate equalities. For example, rounding both coordinates of (0.5,0.5) upward gives total two instead of one; rounding both downward gives zero.

There is also a neighbourhood trap. Consider Q(u,v)=(u−v)²+0.1(u+v−4)² on nonnegative integer pairs. This is the restriction of a convex continuous quadratic. At (0,0), Q=1.6. Either single-coordinate increase to (1,0) or (0,1) gives 1.9, so neither helps. Yet (1,1) gives 0.4 and (2,2) gives zero.

Thus absence of a beneficial single-coordinate step does not certify a global integer minimum, even for this convex quadratic. Coordinated moves reveal an improvement hidden from the chosen neighbourhood. The calculation shows exactly what an overly broad claim would miss.

Discrete convex analysis supplies specific structures and corresponding local tests. The word convex should therefore be followed by a precise property and a precise set of moves, not treated as permission to use any convenient search rule.

Previous chapter · Contents · Next chapter

For fixed-total integer vectors, M-convexity is built around exchanging one unit between coordinates. Let eᵢ denote the vector with one in position i and zero elsewhere. If x and y are feasible and xᵢ>yᵢ, the exchange condition requires some coordinate j with xⱼ<yⱼ such that F(x)+F(y)≥F(x−eᵢ+eⱼ)+F(y+eᵢ−eⱼ).

Both exchanged vectors must remain in the effective domain. The inequality compares a pair of decisions with a pair made closer in the selected coordinates. It is stronger than saying the feasible set is connected by transfers, and stronger than saying a particular descent run happened to succeed.

Murota’s treatment of M-convex functions develops this exchange structure and its global optimality consequences. Here we can verify the structure directly for our separable allocation model.

Write F(x) as the sum of three one-variable convex costs. When xᵢ>yᵢ, moving one unit from xᵢ to yᵢ cannot increase the sum of those two coordinate costs: the unit is removed at a weakly higher marginal cost than the cost of adding it at the lower level. Since the totals of x and y agree, some coordinate j must satisfy xⱼ<yⱼ. The reverse transfer in coordinate j has the same nonincrease property.

Adding these two inequalities establishes the exchange condition. Nonnegativity is preserved because a coordinate donating a unit is strictly larger than its nonnegative counterpart. The total in each vector is unchanged. This proves both the cost inequality and feasibility, rather than checking only the arithmetic.

This reasoning also works with integer lower and upper bounds when the two original vectors obey them. The exchanged coordinates move toward each other, so they stay inside the same intervals. More complicated extra constraints require their own analysis; the argument does not automatically survive an arbitrary restriction.

Why the exchange condition connects local and global

For a finite M-convex domain, the local-to-global argument can be understood by contradiction. Suppose x has no improving unit exchange but is not globally optimal. Among all global minimizers choose y with the smallest total coordinate distance from x. Since the two vectors have the same total and are different, x has a surplus coordinate i and a deficit coordinate somewhere else.

The exchange property supplies a suitable deficit coordinate j and the two exchanged vectors x′ and y′. Local optimality says F(x′)≥F(x). Combining this with F(x)+F(y)≥F(x′)+F(y′) gives F(y′)≤F(y). Because y was already globally optimal, y′ must also be globally optimal.

But y′ moves one unit toward x in each of two coordinates, reducing their total absolute distance by two. That contradicts the choice of y as a closest global minimizer. Thus a nonoptimal x cannot pass every unit-exchange test under these assumptions.

This argument exposes why checking all feasible exchanges matters. If the implementation omits the particular exchange supplied by the structural condition, its stopping rule may not establish F(x′)≥F(x), and the contradiction no longer follows. It also exposes why the domain matters: the exchanged vectors must be feasible for the comparison to be valid.

The proof does not require knowing the global minimizer in order to run the method. The hypothetical minimizer is used only to justify the certificate. This is a useful distinction between the information required by a proof and the information required by an algorithm.

Previous chapter · Contents · Next chapter

Begin at x=(5,0,0). The cost is (5−4)²+2(0−2)²+(0−1)²=1+8+1=10. There are two distinct donor-to-recipient transfers because only team A currently has units.

Giving one A unit to B produces (4,1,0), with cost zero+two+one=3. Giving it to C produces (4,0,1), with cost zero+eight+zero=8. The best transfer is A to B, reducing the cost by seven.

At (4,1,0), the feasible transfers are A to B, A to C, B to A and B to C. They produce (3,2,0), (3,1,1), (5,0,0) and (4,0,1), with respective costs 2,3,10 and 8. A to B is again the best improving move.

At (3,2,0), the feasible transfers produce (2,3,0), (2,2,1), (4,1,0) and (3,1,1). Their costs are 7,4,3 and 3. None improves on the current cost two, so the transfer method stops.

The path is therefore (5,0,0) → (4,1,0) → (3,2,0), with costs 10 → 3 → 2. Every point is integer, nonnegative and has total five. Every accepted move strictly decreases the objective.

For an arbitrary discrete objective, that would establish only local optimality. Here the proven M-convex exchange property justifies the stronger conclusion: the final point is a global minimizer. The standard exchange-descent method and stopping criterion are described in Murota’s algorithms chapter.

A transparent solution report includes the final vector and its cost, the feasible move set, the property supporting the certificate, and the reason the method stopped. Reporting only “the algorithm converged” omits the mathematical reason the answer can be trusted.

Previous chapter · Contents · Next chapter

The separable example offers another way to prove the answer. Start from (0,0,0), whose cost is sixteen+eight+one=25, and allocate units one at a time. The total-five constraint is imposed after five additions; intermediate totals describe the construction, not feasible final answers.

For team A, the successive incremental costs are −7,−5,−3,−1,1. For B they are −6,−2,2,6,10. For C they are −1,1,3,5,7. Each list is nondecreasing because each coordinate cost is convex.

The five smallest increments across the lists are −7 from A, −6 from B, −5 from A, −3 from A and −2 from B. Their sum is −23, so the constructed allocation costs 25−23=2 and gives three units to A, two to B and none to C.

Why is selecting increments legitimate? Receiving the third unit of A requires receiving its first two units. Because the list is nondecreasing, a minimum-cost collection can be chosen as a prefix of each list. No later increment needs to be taken before a cheaper prerequisite. This prefix property connects the numerical ranking to a feasible allocation.

Every five-unit allocation selects five increments in precisely this way. No five increments can have total smaller than the sum of the five globally smallest increments. Our selection achieves that bound and is feasible, providing an independent optimality certificate.

This proof is specific to separable convex resource allocation with the simple total constraint. Do not use it unchanged when the cost includes interactions between teams. Then the cost of adding a unit to one team may depend on the allocations of others, so fixed per-team increment lists may no longer represent the objective.

The final allocation is unique here because the fifth selected increment, −2, is strictly smaller than the next available value, −1. In other examples ties at that boundary can produce multiple optimal allocations. A tie is a property to report, not an error to conceal.

Previous chapter · Contents · Next chapter

There are twenty-one nonnegative integer triples summing to five. A direct enumerator can loop a from zero to five, loop b from zero to five minus a, and set c=5−a−b. This generates each feasible allocation once and avoids scanning an unnecessarily large cube.

The smallest costs are two at (3,2,0), three at (3,1,1), three at (4,1,0), and four at (2,2,1). The next best value is seven. These results agree with the exchange path and marginal-cost certificate.

Enumeration serves two different purposes. For this fully specified finite instance, it proves which point is optimal. It also checks that an implementation of the more general algorithm returns the right result. It does not prove a general theorem for every possible allocation model.

If the two methods disagree, inspect feasibility before cost arithmetic. An enumerator might accidentally permit negative allocations, omit a boundary point, or use at most five units while the solver uses exactly five. Those are different optimization problems, even if the same cost formula appears in both programs.

Then check the objective implementation. The coefficient two multiplies the whole squared deviation of B. Writing (2b−2)² instead changes both its target and weighting. Likewise, using absolute deviations instead of squares changes the marginal lists and can introduce additional ties.

A useful audit artifact is a complete list of feasible vectors and costs, plus the accepted descent path. Small examples are valuable because another reader can inspect them without trusting a large software package. For larger instances, retain independent lower bounds, special-case checks or certificates appropriate to the structure.

The existing Operations Research article on equal optimal values provides a complementary lesson: identifying a best score does not always identify a unique decision, and secondary preferences should be stated explicitly.

Previous chapter · Contents · Next chapter

Exchange is not the only discrete convex structure. L-natural convexity, written L♮-convexity, uses the integer lattice and a rounded midpoint inequality. For any integer vectors x and y, it requires G(x)+G(y)≥G(ceil((x+y)/2))+G(floor((x+y)/2)), where rounding is coordinatewise and infeasible points have value +∞.

The ceiling and floor points replace a midpoint that may not be integral. The inequality must hold for every pair in the defining condition, not just a selection of nearby pairs. Murota’s overview of discrete convex analysis explains this characterization and the associated local optimality test.

For an elementary example, take G(u,v)=u²+v² on all integer pairs. Let x=(0,3) and y=(3,0). The endpoint sum is nine+nine=18. The rounded midpoints are (2,2) and (1,1), whose values sum to eight+two=10. Thus this pair satisfies the inequality.

The general proof separates the coordinates. For two integers with a fixed sum, the sum of their squares is minimized when they differ by at most one. Replacing each coordinate pair by its rounded average cannot increase the combined cost. Adding the coordinate inequalities proves the property for G.

The fixed-total domain in our original allocation example behaves differently. If x=(1,0) and y=(0,1) both have total one, their coordinatewise ceiling midpoint is (1,1) and floor midpoint is (0,0). Neither has total one. Thus one should not casually treat a fixed-total exchange domain as an L♮-convex domain.

The distinction is useful: M-type structure organizes transfers that preserve a total, while L-type structure organizes coordinated lattice changes. Their relationship is part of a broader theory, but they are not interchangeable labels for any integer problem with a smooth-looking cost.

Previous chapter · Contents · Next chapter

For M-convex minimization, the relevant local checks are unit exchanges x−eᵢ+eⱼ. For L♮-convex minimization, the usual criterion checks x+d and x−d for all binary vectors d in {0,1}ⁿ. Such a move can change several coordinates together.

This explains the failure of the single-coordinate test in chapter 3. From (0,0), the coordinated increment d=(1,1) reveals an improvement that either individual increment misses. The point of that example was not to classify its quadratic into every discrete convex class; it was to demonstrate that the neighbourhood cannot be chosen casually.

A neighbourhood can be local in step size while large in number of candidates. There are potentially exponentially many binary direction vectors. Saying “check the local neighbourhood” therefore does not by itself prove an efficient implementation. Specialized structure can make the search easier, but its computational benefit must be established separately.

For our three-team M-convex example, there are at most six directed exchanges to consider at a point. Boundary coordinates eliminate some moves because a team with zero units cannot donate. With n teams, a direct exchange scan has at most n(n−1) candidates per iteration.

That count is not the full running time. Each objective evaluation may be expensive, and the number of iterations matters. In the separable case, a transfer changes only two coordinate costs, so its difference can be computed without reevaluating the entire sum. This is a concrete improvement justified by the formula.

When documenting a solver, state the exact directions it tests. Terms such as local search, coordinate descent and hill climbing hide important choices. Two methods with the same informal name may have different stopping points because they examine different neighbours.

Previous chapter · Contents · Next chapter

A binary incidence vector represents a set: coordinate i is one when item i is selected and zero otherwise. A fixed-size family of such vectors makes unit exchange resemble removing one selected item and adding another. This is why matroid exchange ideas are central to M-convex analysis.

Our equipment allocation allows coordinates larger than one, so it is not merely a subset-selection example. Nevertheless, the logic is similar: a structured exchange rule prevents a local obstruction from hiding a better feasible decision. Discrete convex analysis extends this kind of reasoning to functions on integer vectors.

The neighbouring Submodular Optimization root studies diminishing returns for set functions. The same collection of ideas appears in discrete convex analysis, but the optimization direction and constraints matter. A guarantee for greedy maximization of a monotone submodular set function is not a certificate for arbitrary integer minimization.

For a learner, keep three questions separate. What is the domain: sets, binary vectors or general integer vectors? What property does the objective satisfy? What constraint and neighbourhood does the theorem use? Similar notation does not make the answers identical.

The primary survey by Kazuo Murota places M-convexity, L-convexity and their duality in a common framework, including applications with indivisible goods. It is a route into the advanced theory once the elementary examples are comfortable.

Another useful comparison is Knuth optimisation for interval dynamic programming. That method uses its own structural inequalities to restrict a search. It is not interchangeable with M-convex descent, but it teaches the same discipline: prove the specific structural condition before using the computational shortcut.

Previous chapter · Contents · Next chapter

The allocation example can be read through marginal costs. At the optimum (3,2,0), the costs of adding one unit are −1 for A, 2 for B and −1 for C. The costs saved by removing the last assigned unit are −3 for A and −2 for B, interpreted as the corresponding forward increments already paid.

A transfer from donor i to recipient j changes the cost by the recipient’s next increment minus the donor’s last increment. Every such difference is nonnegative at the optimum. For example, A to C changes cost by −1−(−3)=2, matching the direct increase from two to four.

A threshold λ between −2 and −1 separates the selected increments from the unselected increments. For example λ=−1.5 makes three increments of A and two of B lie below the threshold, with none from C. This is a numerical certificate for this separable instance, not an instruction to charge teams a negative market price.

Now increase the total supply to six. The next increment is −1, tied between A and C. Allocations (4,2,0) and (3,2,1) both have cost one. With seven units, the target allocation (4,2,1) has cost zero. The value of an extra unit is therefore sensitive to the current supply and to ties.

For a real project, a shadow value or marginal threshold belongs to a specified model. It may change when targets, bounds or interactions change. It does not automatically measure the external value of buying another unit, because purchase price and implementation costs may not be included in F.

The distinction between an internal optimization certificate and an external decision is essential. A mathematically justified allocation can still require practical review for installation, compatibility, staffing and fairness. Those requirements should be represented or explicitly handled alongside the model.

Previous chapter · Contents · Next chapter

The clean exchange proof assumes the feasible domain has the required structure. Adding “team C may receive either zero or two units, but never one” introduces a hole. A one-unit transfer into C is then impossible from zero, even when a two-unit reallocation would improve the objective.

Do not handle such a constraint by silently ignoring the infeasible intermediate point and still claiming the old local certificate. Either establish a new appropriate property and neighbourhood or use a method suited to the revised discrete problem. Mixed-integer optimization, dynamic programming or complete enumeration may be appropriate depending on size and structure.

Numerical tolerances create another issue. If costs are floating-point estimates, an apparent zero difference might be a small positive or negative value. For our integer-coefficient example, all feasible costs are integers, so exact arithmetic is straightforward. Introducing a tolerance here would obscure a problem that does not need one.

When coefficients are measured quantities, separate arithmetic error from model uncertainty. High-precision computation can reduce rounding error but cannot make an uncertain target exact. A result that changes under a plausible small change in priorities should be reported as sensitive even if the optimizer itself is reliable.

A practical diagnostic record includes the current vector, its cost, every feasible exchange difference, and the acceptance rule. Check whether the total remains constant after each move and whether every coordinate satisfies its bounds. Recompute the full objective occasionally to catch errors in incremental updates.

Strictly decreasing moves cannot cycle on a finite feasible domain. Allowing zero-cost moves can produce cycles unless a separate tie-breaking or anti-cycling rule is used. If the purpose is simply to find one optimum, stopping when no strict improvement remains is enough under the established M-convex conditions. If the purpose is to explore all optima, design that as a separate task.

Previous chapter · Contents · Next chapter

Keep the original five-unit domain and quadratic cost, but introduce a ten-unit discount specifically at y=(1,1,3). Define H(x)=F(x)−10 when x=y, and H(x)=F(x) otherwise. The discount is an illustrative package incentive that only applies to that complete allocation.

At y, the original cost is nine+two+four=15, so the discounted cost is five. This discount is not yet enough to beat the old optimum two. Increase the discount to twenty instead. The revised cost at y becomes minus five, making it better than every undiscounted allocation.

At x=(3,2,0), none of the four feasible unit-exchange neighbours is y. Their costs remain 7,4,3 and 3, while H(x)=2. Therefore the old optimum is still a strict local minimum under unit exchanges, but it is no longer a global minimum. A descent method starting there stops at the wrong global answer.

We can identify a failed exchange inequality. Compare x=(3,2,0) and y=(1,1,3), using coordinate A as the surplus coordinate of x. C is the only deficit coordinate, so the required exchanged points are (2,2,1) and (2,1,2). Their costs are four and seven, and neither receives the discount. The exchange condition would require H(x)+H(y)=−3 to be at least eleven, which is false.

The failure is therefore structural, not a programming defect. The package incentive destroys the M-convex property. Keeping the same transfer algorithm may still produce a useful heuristic, but the old stopping theorem no longer applies.

For a second exercise, replace the package incentive with a new nonnegative weight on B’s squared deviation. Does the exchange proof survive? Yes: the cost remains separable with convex coordinate sequences, including a zero weight if allowed. The numerical optimum may change, but the same type of structural reasoning remains available. Distinguishing those two changes is the point of the transfer test.

Previous chapter · Contents · Next chapter

A good first exercise is to reproduce the five-unit allocation without software. List the coordinate increments, choose the five cheapest compatible increments, and verify the resulting cost directly. Then start from a different feasible allocation and follow improving transfers. Explain why the paths may differ while the certified optimum is the same.

Next, write a small enumerator for all twenty-one feasible points and compare it with the transfer algorithm. Add a trace that records each accepted move and its cost difference. Finally introduce the package discount from chapter 13 and confirm that the local certificate fails exactly where the exchange inequality fails.

This sequence develops several distinct capabilities: modeling an integer domain, calculating marginal costs, identifying a structural property, implementing a compatible algorithm and recognizing a theorem’s limits. None is replaced by memorizing the names M-convex and L-convex.

Is every convex function on integer points M-convex?

No. M-convexity requires a specific exchange property and an appropriate domain. The continuous convexity of a formula does not supply that property automatically. Check the exact discrete definition rather than relying on a bowl-shaped graph.

Does local optimality always imply global optimality?

Only under conditions connecting the objective, domain and neighbourhood. The one-dimensional convex interval case, the M-convex exchange case and the L♮-convex lattice case have different local tests. The discounted example shows how a strict local minimum can fail to be globally best after structure is lost.

Must the optimum be unique?

No. With six units in our separable model, two allocations share the best cost one. Record ties and, if necessary, specify a secondary criterion. Do not add an unstated preference and present the selected point as the only mathematical solution.

What should a complete result include?

State the variables, integer domain, objective units, constraints, structural claim, neighbourhood, stopping rule and independent check. Identify whether the result is a global certificate or a heuristic outcome. Preserve a small counterexample when a proposed assumption fails; it is often more useful than a vague warning.

Where does advanced study continue?

Study the exchange and midpoint definitions in the linked primary texts, then move to conjugacy, separation and structured algorithms. Use the Optimisation root to keep the decision model in view and the Education parent to design practice that changes assumptions deliberately.

The dependable outcome is not just a low number. It is an integer decision that is feasible, an explanation of why the allowed local checks are sufficient, and a clear account of the changes that would require a different method.

Previous chapter · Contents · Gold Standard master