Does minimax require probabilities for scenarios?

No. It uses the allowed set and its worst objective value, though probabilities may be useful for comparing alternatives.

Is every min-max problem convex?

No. Convexity requires appropriate structure in the decision-dependent functions and feasible set.

Can min and max always be swapped?

No. Equality requires additional assumptions, as the binary counterexample shows.

AI Glossary / Mathematics and optimization / Intermediate

Min-max optimization

Definition

Min-max optimization chooses a decision that minimizes the largest value of an objective over a specified set of alternatives, scenarios, or adversarial choices. A common form is min_x max_u f(x,u), where x is the decision and u describes uncertainty. It is also called minimax optimization and often represents a worst-case design objective.

What it means

Instead of asking which decision performs best on average, the formulation asks which decision has the best worst-case outcome within the modeled set. The inner maximization finds the most unfavorable allowed scenario for each proposed decision. The outer minimization then compares those worst-case values.
The scenario set is part of the model, not a statement about everything that can happen. Leaving out a plausible scenario can make a claimed guarantee incomplete, while including unrealistic extremes can produce an unnecessarily conservative decision. Min-max is also distinct from max-min optimization: the latter commonly maximizes a guaranteed benefit, although sign changes can connect the formulations.

How it works

Specify the feasible decisions, the uncertainty or opponent choices, and whether the objective represents a cost to minimize or a benefit to maximize. For finitely many scenario costs f_i(x), minimizing their maximum can be written by adding a variable t: minimize t subject to f_i(x)≤t for every scenario.
If every f_i is convex and the decision set is convex, this epigraph formulation is a convex optimization problem. For a large or continuous scenario set, an algorithm may alternate between choosing a decision and searching for a violating worst-case scenario. Exact worst-case evaluation can support stronger guarantees than an approximate search that merely finds one unfavorable example.

Three practical examples

A capacity planner can choose a setting that limits the highest modeled cost across several demand scenarios.
An approximation algorithm can minimize the largest error over a specified interval rather than minimizing average squared error.
A machine-learning study can formulate robustness against a defined set of input perturbations, while distinguishing the exact inner maximum from an approximate attack.

Think of it this way

Think of selecting equipment by its poorest acceptable performance across a checklist of operating conditions. The best choice is the one whose worst listed result is least damaging. The analogy is limited because unlisted conditions receive no protection from the mathematical model, and a checklist may not capture probabilities, changing decisions, or interactions between choices.

Worked example

Consider an original planning model with a continuous setting x between zero and ten. Two possible scenario costs are C_1(x)=2x+4 and C_2(x)=24−x. The first cost rises with x, while the second falls. The objective is to minimize max{C_1(x),C_2(x)}.
At x=0 the costs are four and 24, so the worst cost is 24. At x=10 they are 24 and 14, so the worst cost is again 24. Equalizing the two costs gives 2x+4=24−x, hence x=20/3, approximately 6.667. Both costs then equal 52/3, approximately 17.333.
Why is this optimal? Below 20/3, the second cost is larger and decreases as x increases. Above 20/3, the first cost is larger and increases as x increases. Their maximum therefore reaches its minimum at the intersection. The equivalent epigraph problem minimizes t subject to 2x+4≤t, 24−x≤t, and 0≤x≤10.
For comparison, assigning probability one-half to each scenario gives expected cost (C_1+C_2)/2=14+x/2. That different objective is minimized at x=0, where the expected cost is 14 but the worst cost is 24. The minimax decision accepts a higher average under these illustrative probabilities to reduce the worst modeled cost.
If a third allowed scenario has constant cost 30, the worst cost becomes at least 30 for every setting. Since the first two costs never exceed 24 on the interval, every setting now has worst cost 30. This change shows how adding a scenario can alter both the optimum value and the uniqueness of a decision. It does not mean the original arithmetic was wrong; it means the model changed.

Illustrative case study

In a fictional logistics team, planners compare an expected-cost plan with a minimax plan using a documented set of disruption scenarios. They explain the tradeoff to decision makers instead of calling one answer universally safer. The team also reviews whether important disruptions are missing and whether some combinations are implausible. This is an illustrative planning exercise, not an operational recommendation or a report of measured cost savings.

Common misconceptions and mistakes

The order of minimum and maximum generally matters. For a simple counterexample, let x and u each be zero or one, and let f(x,u)=1 when they are equal and zero otherwise. If u chooses after x, it can match x, so min_x max_u f=1. If x chooses after u, it can differ from u, so max_u min_x f=0.
Minimax theorems give equality under suitable assumptions, but those assumptions cannot be omitted. Another error is treating an approximate inner search as proof that no worse scenario exists. A discovered high cost is evidence of a bad case, not automatically the maximum over the entire uncertainty set.

Business use

For business use, the formulation makes risk priorities explicit. Document the scenario set, the timing of decisions, any possibility of later adjustment, and the cost measure. Compare the worst-case solution with relevant alternatives and explain what protection is actually established. If the inner maximization is approximate, report that limitation alongside the result rather than presenting an unrestricted guarantee.

Check your understanding

Why does the two-scenario example balance the costs at the optimum?

Answer: On one side of their intersection the declining second cost dominates; on the other side the rising first cost dominates. Moving toward the intersection reduces the maximum.

Related terms

Robust optimization
Adversarial Training
Worst-case analysis
Saddle point
Epigraph formulation
Max-min optimization
Scenario analysis
Minimax theorem

Learn next

Restrict the planning setting to integers from zero through ten. Compare the worst costs at six and seven, then explain why a continuous minimax solution need not remain feasible after adding an integer restriction.

Sources

Primary author sources: Boyd and Vandenberghe, Convex Optimization, epigraph formulation: https://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf . Mutapcic and Boyd, research summary on exact and approximate worst-case searches: https://web.stanford.edu/~boyd/papers/prac_robust.html . All numerical scenarios and the binary counterexample here are original.

Previous: Min-conflicts Next: Mini-batch