Semi-infinite programming chooses finitely many decision variables while enforcing infinitely many constraints, often one for every point in an interval or every scenario in a continuous uncertainty set. It is useful when a design must work everywhere in a stated range, not merely at sampled test points. The gold standard is to combine a good candidate decision with a justified search for its worst violation and a defensible bound on how far its cost is from optimal.
This guide develops the subject through original capacity-envelope, affine-design and minimax-approximation calculations. You will see exactly how a coarse grid can miss a violation, how an exchange method repairs a finite model, and how analytical bounds can turn numerical evidence into a certificate. The examples are deliberately simplified teaching models; their guarantees apply to their stated functions and domains.
Use the Gold Standard master, the Education guide to transferable understanding and the How X Works hub for wider reading. The existing Remez exchange and minimax approximation article supplies a specialist route into one important application.
Choose your semi-infinite-programming route
Chapters 1–3: Understand continuous requirements
Chapters 4–6: Search violations and bound the answer
Chapters 7–9: Certify samples and solve approximation
Chapters 10–12: Check structure, meaning and reliability
Chapter index
Understand continuous requirements · Chapters 1–3
1. Identify what is finite and what is infinite
Search violations and bound the answer · Chapters 4–6
4. Turn feasibility into a worst-violation problem
Certify samples and solve approximation · Chapters 7–9
7. Use regularity to control what happens between samples
8. Solve a two-variable envelope and prove uniqueness
9. Express minimax approximation as a semi-infinite programme
Check structure, meaning and reliability · Chapters 10–12
10. Distinguish convexity in decisions from difficulty in the index
11. Connect continuous constraints to robust design without changing the claim
Transfer and continue · Chapters 13–14
13. Transfer the method to a shifted peak and a restricted domain
14. Answer common questions and build a practical learning route
CHAPTER 1 OF 14 · Understand continuous requirements
1. Identify what is finite and what is infinite
Suppose a designer chooses a single capacity x. A simplified load curve is d(t) = t(1 − t) for every t between zero and one. The requirement is x ≥ d(t) throughout that interval. There is only one decision variable, but there is a separate inequality for every possible t. Minimising x subject to those inequalities is a semi-infinite programme.
The index t might represent normalised time, position along a component, frequency, temperature or an uncertainty scenario. Its meaning comes from the application. It is not automatically a random variable, and enforcing a condition for every t is not the same as satisfying it with high probability.
In general, write the problem as minimising f(x) subject to g(x, t) ≤ 0 for every t in a specified set T, with any additional finite constraints on x. The decision x has finitely many components. The word “semi” distinguishes this structure from problems in which the decision itself is an arbitrary function with infinitely many degrees of freedom.
An interval can be bounded and still contain infinitely many constraints
“Infinite” does not mean that time runs forever or that the index set is unbounded. The compact interval [0, 1] already contains infinitely many points. Conversely, a million scenarios still form a finite model, however expensive it is to solve.
Alexander Shapiro’s survey of semi-infinite programming develops the mathematical framework, including duality, discretisation and optimality conditions. The central modelling question is accessible before those advanced details: what exactly must hold for every index, and what evidence would justify saying that it does? State the index domain, units and boundary conditions beside the constraint. An accurate calculation over the wrong domain answers the wrong design question.
CHAPTER 2 OF 14 · Understand continuous requirements
2. Solve a complete continuous capacity requirement
For d(t) = t(1 − t), complete the square: d(t) = 1/4 − (t − 1/2)². The square is nonnegative, so the load never exceeds 1/4. It reaches that value at t = 1/2. Therefore x = 1/4 satisfies every constraint, and any smaller x fails at the midpoint.
This gives both parts of an optimality proof. The midpoint constraint gives a lower bound x ≥ 1/4 on every feasible design. The completed-square identity verifies that the candidate x = 1/4 is feasible everywhere. Since the candidate meets the lower bound, the optimum is exactly 1/4.
Notice how little computation was required. We did not enumerate infinitely many points. We used a property of the function that applies simultaneously to all of them. Semi-infinite programming is often about finding or approximating such global arguments rather than literally processing an infinite list.
Check a deliberately inadequate design
Take x = 0.2. The violation is d(t) − x = 0.05 − (t − 1/2)². It is positive when |t − 1/2| < √0.05, approximately 0.2236. Thus the design fails throughout an interval around the midpoint, even though it succeeds at both endpoints.
The largest violation is 0.05, attained at t = 1/2. This number is measured in the units of the constraint, not in units of the objective gap unless the model makes them coincide. Here they coincide because the objective is simply x and increasing x shifts every constraint equally. In a more complicated design, the cost of repairing a violation can be nonlinear or depend on which decision component changes. Keep the violation measure and the cost measure separate from the beginning.
CHAPTER 3 OF 14 · Understand continuous requirements
3. Understand what a finite grid actually proves
If we check only t = 0 and t = 1, both sampled loads are zero. The finite optimisation problem therefore returns x = 0. It is optimal for the sampled problem and badly infeasible for the continuous one. There is no contradiction: dropping constraints enlarged the feasible set.
Add t = 1/4 and t = 3/4. Both have load 3/16 = 0.1875. The sampled optimum becomes 0.1875, but the actual maximum remains 0.25. The missed violation is 1/16 = 0.0625. Four well-spaced samples are still not a universal feasibility certificate.
For this particular quadratic, the missed maximum can be calculated exactly. If the grid point nearest to 1/2 lies a distance δ away, its largest sampled load is 1/4 − δ². The sampled design underestimates the required capacity by δ². A grid containing the midpoint happens to recover the exact answer, but that success depends on knowing where this curve peaks.
Denser is evidence, not automatically proof
A finer grid usually provides more information, yet an unexamined function may have a narrow peak between samples. Without a bound on how quickly the function can change, finitely many samples alone cannot exclude that possibility. A visually smooth plot may conceal the same issue because the plot itself is produced from finitely many evaluations.
For minimisation, solving a finite restriction of the index set globally supplies a lower bound on the full optimum. The sampled optimum can be too optimistic because it ignores constraints. Its decision is an upper-bound candidate only after continuous feasibility has been established. Reversing those roles is a serious error: an attractive sampled cost is not the cost of an implementable full-domain design until the missing constraints have been checked.
CHAPTER 4 OF 14 · Search violations and bound the answer
4. Turn feasibility into a worst-violation problem
For a fixed candidate x, define V(x) = sup over t in T of g(x, t). The candidate is feasible exactly when V(x) ≤ 0. This converts an infinite family of checks into one optimisation problem over the index. It is often called a separation problem or worst-violation search.
In the capacity example, g(x, t) = t(1 − t) − x, so V(x) = 1/4 − x. The maximising index is always 1/2. In larger models, the worst index can depend strongly on the design; changing the design can move the troublesome location rather than simply lower its peak.
The direction of the numerical bound matters
Suppose a local maximisation routine returns a violation of −0.01. That means it found one point with that value, not that every point has a negative value. A point evaluation is a lower bound on the supremum. It can prove infeasibility when positive, but a negative value alone cannot prove feasibility.
To certify feasibility, obtain an upper bound on the supremum and show that it is nonpositive, or use an analytical argument valid over the whole domain. Global optimisation, interval bounds and special algebraic structure can provide that evidence. Multiple local starts are useful diagnostics, but they do not automatically turn local search into a proof.
Continuity and compactness also matter. If T is compact and g(x, ·) is continuous, the supremum is attained as a maximum. If T is open or unbounded, a worst value may be approached without being attained. For example, t on (0, 1) has supremum one but no maximiser. A separation routine that insists on finding an attained worst point can misrepresent such a problem unless the domain and limiting behaviour are handled explicitly.
CHAPTER 5 OF 14 · Search violations and bound the answer
5. Follow an exchange method from start to finish
An exchange method alternates between a finite design problem and a search for a missing troublesome constraint. Start with a small set of indices, solve the corresponding finite problem, test the candidate against the full index domain, and add an index exposing a violation. Then solve the enlarged finite problem again.
For the scalar capacity example, start with T₀ = {0, 1}. The finite problem returns x₀ = 0. The separation problem finds t = 1/2 with violation 1/4. Add that index. The next finite problem requires x ≥ 0, x ≥ 0 and x ≥ 1/4, so it returns x₁ = 1/4. The exact separation value is now zero, proving full feasibility and optimality.
This example finishes after one added index because the active location is easy to identify and does not move. General problems can require many iterations, and finite termination is not a universal property of every exchange implementation. Some methods retain all discovered constraints; others manage a smaller working set. Constraint removal needs a principled rule because a previously troublesome index can become relevant again.
Record the two optimisation tasks separately
The master problem chooses x. The separation problem searches over t with x fixed. Confusing their variables can produce an entirely different problem. Also record whether each task was solved globally or locally and what tolerance or bound supports its result.
Djelassi and Mitsos’s hybrid discretisation research combines lower- and upper-bounding ideas and proves finite convergence under stated assumptions. Its lesson for practice is not that any adaptive grid is guaranteed to work. It is that stopping rules, constraint restrictions and bounding procedures must fit together mathematically. A loop that stops because the latest local search found nothing new has weaker evidence than a loop that stops with certified feasibility and an objective bound.
CHAPTER 6 OF 14 · Search violations and bound the answer
6. Maintain lower and upper bounds on the answer
Let L be a valid lower bound from a finite relaxation and U the objective value of a fully feasible candidate. For a minimisation problem, L ≤ optimal value ≤ U. The difference U − L measures the remaining certified objective uncertainty. It is more informative than reporting only the latest design or only a solver’s success message.
In the four-point grid example, L = 0.1875. The analytical candidate x = 0.25 is feasible, so U = 0.25. The optimum is enclosed in [0.1875, 0.25]. After adding the midpoint constraint, the lower bound rises to 0.25 and the gap closes.
Separate feasibility tolerance from objective tolerance
A design may have a tiny constraint violation but a large objective gap, or be fully feasible but unnecessarily expensive. These are different deficiencies. Report both a bound on the maximum violation and an objective gap. Do not call a design “accurate to 0.001” without saying what that number measures.
For the scalar envelope, a simple repair is available. If a candidate x has a certified violation upper bound η > 0, increasing x by η makes every constraint nonpositive because each violation decreases by exactly η. The objective increases by η. This repair works because of the model’s special additive structure; it is not a general recipe for arbitrary design variables.
Suppose a numerical procedure returns x = 0.249 and certifies V(x) ≤ 0.001. Setting x to 0.250 gives a feasible capacity in exact arithmetic under that certificate. If the bound itself has rounding uncertainty, include that uncertainty before claiming the repair is sufficient. The Convex Duality guide develops the broader habit of pairing candidate solutions with valid bounds rather than treating a numerical result as self-certifying.
CHAPTER 7 OF 14 · Certify samples and solve approximation
7. Use regularity to control what happens between samples
Suppose, for a fixed candidate x, the violation function is Lipschitz in t with known constant L: its change between two indices is at most L times their distance. If every point of T lies within distance δ of a sampled point, then the full maximum violation is at most the largest sampled violation plus Lδ.
The proof is short. Take any unsampled t and choose a nearby sampled s. Then g(x, t) ≤ g(x, s) + L|t − s| ≤ sampled maximum + Lδ. Since the inequality holds for every t, it bounds the supremum. The key ingredients are a valid constant and a valid coverage distance, not the visual density of the grid.
Calculate a conservative margin
For t(1 − t) on [0, 1], the derivative is 1 − 2t, whose absolute value is at most one. Thus L = 1 is valid. A uniform grid including both endpoints with spacing h has coverage distance at most h/2. If every sampled violation is at most −h/2, the entire interval is certified feasible.
At h = 0.1, this margin is 0.05. It is conservative compared with the exact quadratic calculation, but its logic is transparent. Better structure can produce tighter bounds; a generic Lipschitz margin trades sharpness for broad applicability.
Do not estimate L from the same sparse samples and then treat the estimate as a rigorous bound. An unseen steep section is precisely what the certificate must exclude. Derivative bounds, interval arithmetic or a justified physical regularity limit can support L. In several index dimensions, coverage becomes harder because a grid must cover a region rather than a line. This growth in sampling burden is one reason adaptive separation can be valuable, provided its own global checks are reliable.
CHAPTER 8 OF 14 · Certify samples and solve approximation
8. Solve a two-variable envelope and prove uniqueness
Allow a time-varying affine capacity a + bt instead of a constant. Require a + bt ≥ t(1 − t) for every t in [0, 1], and minimise its average over the interval, which is a + b/2. Both a and b are decision variables. This is still semi-infinite programming: only the number of decisions has changed.
At t = 1/2, feasibility requires a + b/2 ≥ 1/4. That single constraint already gives a lower bound of 1/4 on the objective. The constant design a = 1/4, b = 0 is feasible by the completed-square identity, so it achieves the bound and is optimal.
Check whether a sloping design can tie
Any design attaining the same objective must have a = 1/4 − b/2. Its capacity surplus above the load is then (t − 1/2)² + b(t − 1/2). Put u = t − 1/2. If b is positive, choose a sufficiently small negative u; if b is negative, choose a sufficiently small positive u. In either case u² + bu becomes negative.
Therefore every nonzero b violates a constraint near the midpoint. The unique optimum is the constant design. The conclusion is stronger than merely finding a plausible numerical pair: it excludes all other optimal slopes using a local sign argument embedded in a global feasibility problem.
This example also explains why an active constraint may reveal the objective value without by itself identifying the whole decision. The midpoint fixes a + b/2 but leaves many possible pairs. The nearby inequalities eliminate the false ties. A finite solver using only the midpoint could return a sloping design with the correct objective and still fail the full continuum of constraints. Correct objective value alone does not establish that the returned decision is feasible.
CHAPTER 9 OF 14 · Certify samples and solve approximation
9. Express minimax approximation as a semi-infinite programme
Suppose we want an affine approximation p(t) = a + bt to t² on [0, 1], minimising the largest absolute error. Introduce a variable E and require t² − p(t) ≤ E and p(t) − t² ≤ E for every t. Minimise E. There are three decision variables and two infinite families of linear inequalities in those variables.
Consider p(t) = t − 1/8. Its error is e(t) = t² − t + 1/8 = (t − 1/2)² − 1/8. Since the square ranges from zero to 1/4, the error ranges from −1/8 to 1/8. Thus E = 1/8 is achievable.
Prove that no affine approximation can do better
For any affine p, let e₀, eₘ and e₁ be the errors at zero, one-half and one. The affine terms cancel in e₀ − 2eₘ + e₁, leaving 1/2. If every absolute error is at most E, the triangle inequality gives 1/2 ≤ |e₀| + 2|eₘ| + |e₁| ≤ 4E. Hence E ≥ 1/8.
The candidate reaches this lower bound, so it is globally minimax. Its errors at the three test locations alternate +1/8, −1/8, +1/8. This is a concrete instance of the alternation structure discussed in the NIST Digital Library of Mathematical Functions section on approximation.
The calculation reveals two complementary tasks. A few strategically chosen points establish a lower bound, while the completed-square identity checks the candidate everywhere. Using the three points alone to solve for a line would not prove that its error stays within the limit between them for an arbitrary target function. The existing Remez specialist guide explains how extreme-error locations are updated in numerical approximation.
CHAPTER 10 OF 14 · Check structure, meaning and reliability
10. Distinguish convexity in decisions from difficulty in the index
A semi-infinite problem can be convex in x even when its separation problem is difficult. If f is convex and g(·, t) is convex for every fixed t, each constraint defines a convex set in decision space. Their intersection remains convex, regardless of how complicated the dependence on t may be.
The scalar envelope illustrates an extreme case: g(x, t) = d(t) − x is affine in x for any load function d. The design problem is convex in its single decision even if d has many peaks and finding its global maximum over t is difficult. An easy-looking master problem can therefore hide a demanding verification problem.
Endpoint checking needs a reason
If the violation is affine in a scalar index on a closed interval, its maximum occurs at an endpoint. If it is convex in that index, an endpoint still attains a maximum on an interval. But a concave violation can have its maximum in the interior, as t(1 − t) does. Confusing convexity in x with convexity in t leads directly to invalid endpoint tests.
For a polynomial violation on a compact interval, checking endpoints and all interior stationary points can determine its maximum when those points are reliably found. Higher-dimensional polynomial verification is more demanding. The Polynomial Optimization guide develops algebraic lower bounds and positivity certificates that can help with such tasks.
Maintain the direction of every transformation. To prove g ≤ 0 everywhere, one can prove −g ≥ 0 everywhere. A certificate bounding g from below does not establish that requirement. When using a relaxation, ask which side of the true worst-case value it bounds and whether that side supports the claim being made. A sophisticated optimisation method can still be used in the wrong direction.
CHAPTER 11 OF 14 · Check structure, meaning and reliability
11. Connect continuous constraints to robust design without changing the claim
If t indexes uncertainty, requiring g(x, t) ≤ 0 for every t is a robust feasibility condition. If t indexes physical position, the same mathematical structure may describe a spatial design envelope. The computation can look similar while the interpretation differs: uncertainty protection and spatial coverage are not interchangeable explanations.
The Robust Optimization guide asks what can vary and when the decision is made. Semi-infinite programming focuses on the continuous family of constraints and how to solve or verify it. The two subjects overlap when a fixed decision must satisfy every scenario in a continuous uncertainty set.
Sampling probability is not universal coverage
A random test set may support a statistical statement about violation probability under additional assumptions and a specified sampling procedure. It does not automatically prove that no violating point exists. A rare region can matter greatly if the requirement is universal, and a point with zero probability under one distribution may still be part of the stated index set.
Conversely, a universal requirement can be unnecessarily conservative if the true task is explicitly probabilistic. The remedy is to choose the correct model, not to silently reinterpret a failed universal check as an acceptable probability. Write the quantifier in ordinary language: “every allowed case,” “with a specified probability,” or “on average.” Each requires different evidence.
If the index set itself depends on x, the model becomes a generalised semi-infinite programme. For example, a design might change which operating states are physically reachable. Then both the violation function and its search domain change with the decision. A fixed-domain exchange argument cannot simply be reused without checking that dependence. Explicitly recording the domain avoids treating a constraint discovered for one design as though its index were necessarily meaningful for every other design.
CHAPTER 12 OF 14 · Check structure, meaning and reliability
12. Diagnose numerical success that is not a certificate
Begin an audit with the simplest question: did the solver certify the problem that was actually intended? A finite master solver can report optimality while the full-domain design remains infeasible. A separation solver can report a local maximum while a larger peak exists elsewhere. Both messages can be internally correct and insufficient for the combined claim.
Check the signs of the inequalities, the index bounds and the units of the residual. A load expressed in kilowatts and a capacity expressed in watts can create apparently dramatic violations or false margins. Normalised coordinates also require careful conversion: a derivative bound with respect to normalised time is not numerically the same as a derivative bound per second.
Keep arithmetic error distinct from model error
Suppose a maximum-violation estimate is −10⁻⁸ while solver and evaluation errors are of similar size. Reporting strict feasibility is not justified by the sign alone. Use a bound accounting for numerical error or a deliberate margin. On the other hand, a generous numerical margin does not protect against a misspecified load function or an omitted operating range.
Test the implementation on the scalar quadratic envelope and the affine approximation example before using it on an expensive simulation. The exact answers are known, so the tests can expose missing midpoint searches, sign errors and incorrect bound directions. Then perturb the load peak away from a convenient grid node to ensure that success was not accidental.
Finally, distinguish an unresolved search from proof of infeasibility. Failure to find a feasible design within a computation budget does not show that none exists. A valid infeasibility argument might come from incompatible constraints in a finite subset, because every full solution would have to satisfy that subset. A solver timeout supplies no such logical conclusion. Preserve the candidate, discovered constraints and best valid bounds so the analysis can resume without losing what was established.
Produce a small infeasibility certificate
Add a budget constraint x ≤ 0.2 to the original quadratic-load example. The requirement at t = 1/2 says x ≥ 0.25. These two inequalities cannot both hold. That finite pair proves the entire semi-infinite model infeasible; no further sampling is needed. The certificate also identifies the conflict in terms a designer can understand: the permitted capacity is below a load that the model explicitly requires it to cover.
Repair still needs a substantive choice. Raising the budget, reducing the load, restricting the operating domain or allowing a controlled violation changes different parts of the problem. A solver should not choose among those policy changes merely because one makes the equations solvable. Present the conflicting requirements first, then evaluate any authorised revision as a new model with its own feasibility check.
CHAPTER 13 OF 14 · Transfer and continue
13. Transfer the method to a shifted peak and a restricted domain
Consider the changed load d(t) = 0.3 − (t − 0.4)² on [0, 1]. First find the minimum constant capacity covering the entire interval. Then restrict the operating domain to [0.6, 1] and solve again. Finally, compare what an endpoint-only test would have recommended in the original domain.
The full-domain maximum is 0.3 at t = 0.4, so the required capacity is 0.3. The endpoints have loads 0.14 and −0.06. An endpoint-only model, with nonnegative capacity, would select 0.14 and miss a violation of 0.16 at the interior peak. The negative endpoint load is simply a feature of this teaching function; a physical interpretation would need to justify it or modify the model.
On [0.6, 1], the derivative is −2(t − 0.4), which is negative throughout. The maximum therefore occurs at the left endpoint t = 0.6, where the load is 0.26. The restricted-domain optimum is 0.26. Here endpoint checking is valid because monotonicity has been proved on the new domain.
Explain what changed before reusing an algorithm
The decision variable and objective stayed the same, but the worst index moved relative to the allowed range. A search routine hard-coded to check t = 0.5 would miss the exact maximum in the full domain and would query an inadmissible point in the restricted one. A transferable solution uses the function and domain, not a remembered location.
For a further exercise, replace 0.4 with an unknown peak location c known to lie in [0.35, 0.45]. If one capacity must cover all t in [0, 1] and all such c, the answer remains 0.3 because each admissible c lies inside the operating interval and reaches that peak. This conclusion follows from the model’s structure; it does not require sampling many pairs. State both universal quantifiers before making the claim.
CHAPTER 14 OF 14 · Transfer and continue
14. Answer common questions and build a practical learning route
Does semi-infinite programming require infinitely many computations?
No. Analytical reformulations, global bounds and finite certificates can settle some problems exactly. Numerical methods often work with finite subproblems and a separate verification procedure. The infinite family is part of the mathematical requirement, not an instruction to run an endless loop.
Is a dense grid enough if the graph looks smooth?
Not by itself. To turn samples into a certificate, add justified information about behaviour between samples, such as derivative bounds, monotonicity, convexity in the index or an exact algebraic representation. A denser graph is still a sampled graph.
Why can a few active points determine the optimum?
Some problems have finite optimality certificates supported on a small number of active indices under suitable assumptions. Our capacity midpoint and three-point approximation bound show that idea concretely. It does not mean those indices can be guessed safely in advance or that checking only them proves candidate feasibility in every problem.
What should a first implementation contain?
Start with the scalar envelope and an endpoint-only grid. Make the program report the optimistic sampled answer, locate the missed midpoint violation, add the constraint and recover 1/4. Then implement the shifted-peak exercise so the search must find a different location. Record each master bound, candidate and separation result.
For approximation work, reproduce the line t − 1/8 and verify both its uniform error bound and the three-point lower-bound proof. Then read the specialist Remez article and the Pachón–Trefethen paper on Remez algorithms for numerical methods beyond the hand-solvable example.
For an applied design, preserve the objective, decision variables, index domain, constraint definitions, verification method, arithmetic tolerances, lower and upper bounds, and any unresolved assumptions. Ask another person to reproduce one violating case and one certificate. The useful outcome is a design whose stated range of validity can be explained and checked, rather than a reassuring plot with an unexamined gap between its samples.