Pareto Frontiers

Multi-Objective Optimization

Pareto frontier tracing for multi-objective problems solved with Cvxium.

MultiObjectiveOptimizer is the abstract base. A subclass supplies three solves: minimize the primary objective subject to upper bounds on the auxiliary objectives (solve_with_bounds), minimize a single objective (minimize_objective), and evaluate every objective at a point (evaluate_objectives). trace then solves the N corners of the frontier, sweeps a grid of auxiliary bounds between them (the epsilon-constraint method), and returns the deduplicated points as FrontierResults. The sweep can warm-start each solve from the previous one, or fan the grid out over worker processes.

FrontierResults knows how to analyze and display itself: knee picks the sampled point farthest from the hyperplane through the corners, envelope turns a two-objective frontier into a smooth curve with certified upper and lower bounds (via interpolate_frontier), and plot draws it. For two objectives, MultiObjectiveOptimizer.refine_knee solves for the knee rather than reading it off the grid, using the frontier tangent slopes a subclass reports through tangent_slopes; each of its probes is folded back into the results.

Everything here works in Cvxium’s native minimization convention.

class cvxium.frontier.multi_objective.FrontierPoint(objectives, solution, bounds, ipm_result)

Bases: object

A single evaluated point on the Pareto frontier.

Fields:

• objectives (npt.NDArray[np.float64]) – The value of each objective at this point, of length N, as recorded by MultiObjectiveOptimizer.point_objectives (the primary corner is recorded with evaluate_objectives directly).

• solution (npt.NDArray[np.float64]) – The decision variable at this point.

• bounds (npt.NDArray[np.float64]) – The bounds passed to solve_with_bounds, of length N - 1 for the default grid; np.full(N - 1, np.inf) for a corner, where no bounds were imposed. When _build_grids is overridden, this holds whatever control values that grid supplied (for example, a scalarization weight).

• ipm_result (SolveResult) – The raw result from the inner solver.

class cvxium.frontier.multi_objective.FrontierResults(points, corners, primary_objective, n_attempted, n_skipped, tangent_slopes=None)

Bases: object

Points, corners, and tangent slopes of a traced Pareto frontier.

Returned by MultiObjectiveOptimizer.trace. Locates the sampled knee (knee), interpolates a two-objective frontier with certified bounds (envelope), and plots it (plot). MultiObjectiveOptimizer.refine_knee adds its probes to the points and records its conclusion here.

Parameters:

• points (list[FrontierPoint]) – All successfully evaluated points, corners included, deduplicated by objective vector (absolute tolerance 1e-8) and sorted by the primary objective. Knee-refinement probes are folded in as they are solved (see absorb_probe), so this is every distinct point the frontier cost, not just the ones laid out on the grid.

• corners (list[FrontierPoint]) – The corner points, one per objective whose minimization succeeded. corners[0] minimizes the primary objective; the rest minimize the auxiliary objectives in index order, skipping the primary. A failed auxiliary corner is dropped rather than stored as a placeholder, so later entries shift down, and knee raises ValueError when fewer than N corners remain.

• primary_objective (int) – Index of the primary objective.

• n_attempted (int) – Number of calls to MultiObjectiveOptimizer.solve_with_bounds: the grid points (for a parallel sweep stopped early, only those whose results were observed), plus any knee-refinement probes absorbed afterwards. Corner solves are not counted.

• n_skipped (int) – How many of those failed. A grid solve fails when it raises OptimizationError or ProblemInfeasibleError; a knee probe also when it raises NewtonStepError or BacktrackingLineSearchError.

• tangent_slopes (npt.NDArray[np.float64] | None) –

  Frontier slope d(primary) / d(auxiliary) at each point, in minimization coordinates and index-aligned with points, from MultiObjectiveOptimizer.tangent_slopes. Without it envelope has no lower bound (it still smooths and still bounds above, but the result is uncertified), and refine_knee reports no knee.

  Pass this through when rebuilding a results object. It is the only piece of state not implied by the points, so a rebuild that forgets it downgrades every envelope downstream and nothing complains: a plot simply stops shading its error band. It is a constructor argument rather than an attribute set afterwards so that the signature asks the question.

Notes

Two attributes are not constructor arguments, because refinement needs a traced frontier to run on and so cannot happen before the object exists:

• refined_knee (FrontierPoint | None) is what MultiObjectiveOptimizer.refine_knee last concluded about this frontier, or None if it has not run or reported no knee.

• knee_refinement_ran (bool) says whether refine_knee has run at all. This separates “no knee has been solved for” from “a knee was solved for and the frontier turned out to be straight”, which a bare refined_knee is None cannot express. Falling back to the sampled knee is right in the first case and wrong in the second, where the sampled argmax is exactly the grid-dependent number refine_knee declined to report.

record_refined_knee(knee)

Record the conclusion of MultiObjectiveOptimizer.refine_knee.

Called by refine_knee on every return path, including the ones that report no knee: “we looked and there is no bend” is a finding, and a consumer that cannot see it will quietly substitute the sampled argmax for it. Sets refined_knee and knee_refinement_ran.

Parameters:

knee (FrontierPoint | None) – The refined knee, or None when refinement reported no knee.

absorb_probe(point, slope)

Fold one knee-refinement solve into the traced point set.

A refinement probe is a frontier solve like any other: same optimizer, same kind of bound, an objective vector on the same curve. Reading its slope and then discarding it would leave the frontier sampled least densely exactly where the search has just shown the shape matters most, and leave n_attempted understating what the trace cost. Absorbing it means every property, envelope, and plot that reads points picks the refinement up with no further wiring. It is unconditional: a solve already paid for is information.

Every call increments n_attempted. A failed probe also increments n_skipped. A probe within 1e-8 (absolute) of an existing objective vector, the same rule trace deduplicates by, is counted but not inserted; near convergence that is the expected case. When tangent_slopes is already misaligned with points the probe is declined with a logged warning, since no insertion can restore the alignment. Otherwise the probe is inserted where it keeps points sorted by the primary objective, and its slope is inserted at the same index of tangent_slopes.

Parameters:

• point (FrontierPoint | None) – The probe, or None if its solve failed.

• slope (float | None) – The probe’s tangent slope in minimization coordinates, not in whatever space the knee search is working in: tangent_slopes holds the former, and one entry in different units from its neighbours would surface as a slightly wrong error band rather than as an exception. None records “no slope known here” as nan.

knee(knee_space='primary')

Return the frontier point farthest from the hyperplane through the corners.

Identifies the “knee in the curve” as the point farthest from the hyperplane through the N corner points, where N is the number of objectives. For two objectives this is the standard max-chord-distance method. The argmax is invariant to rescaling any objective, since the hyperplane’s normal rotates to compensate, but not to a nonlinear transform of one, which is what knee_space selects.

The hyperplane’s normal is the last right singular vector of the (N - 1) × N matrix whose rows are the corners translated so that corners[0] is at the origin. This requires the N corners to be affinely independent; if they are (nearly) coplanar in objective space the normal is numerically unreliable. That is not detected: the code’s check for a zero normal cannot fire, since singular vectors have unit norm, so identical or collinear corners yield an arbitrary normal rather than a ValueError.

Parameters:

knee_space (Literal["primary", "root"]) – Which monotone transform of the primary objective to measure the bend in. See _knee_space_transform for when "root" is well posed.

Returns:

knee – The point itself, in untransformed coordinates: knee_space selects the point, it does not change how the point is reported.

Return type:

FrontierPoint

Raises:

ValueError – When the frontier has no points, when fewer than two corners are available, or when the number of corners differs from the number of objectives (typically because a corner solve failed during trace). Also propagated from _knee_space_transform for an unrecognized knee_space, or for "root" at a negative primary objective.

envelope(num=200)

Smooth the frontier and bound how wrong the smoothing can be.

Joining solved points with straight segments asserts something false, that the frontier is piecewise linear, and the error is one-sided, so a coarse stretch reads as a hard trade-off that is not there. A two-objective Pareto boundary is convex in minimization coordinates, which turns interpolation into a bounding problem with an exact answer on both sides: every chord lies on or above the boundary, every tangent on or below it. Between consecutive points the truth is trapped in a lens whose width is a measured error bar.

Passes the auxiliary objective as x, the primary objective as y, and tangent_slopes as the slopes to interpolate_frontier, which verifies each slope against the other points before trusting it. Without tangent_slopes (or when no slope survives verification) there is no tangent bound: tangent is all -inf, max_band_width is inf, and the curve falls back to shape-preserving smoothing. Still a better plot than the polyline, just no longer certified. See MultiObjectiveOptimizer.tangent_slopes for supplying them.

Parameters:

num (int) – Number of points on the returned dense grid.

Returns:

envelope – The dense grid, bounds, and curve, in minimization coordinates, with the auxiliary objective on x.

Return type:

FrontierEnvelope

Raises:

ValueError – When the frontier does not have exactly two objectives (including when it has no points) or has fewer than two points. Also propagated from interpolate_frontier: num below 2, fewer than two distinct auxiliary values, non-finite objective values, or tangent_slopes of a different length from points.

Notes

Convexity is assumed, not checked. Because the verified tangents lie below every point, max_band_width stays nonnegative to within the verification tolerance even when the points contradict convexity; such a contradiction shows instead as tangent rising above chord between two points, so compare those two arrays to detect it.

plot(annotate_knee=True, ax=None, x_label='Primary Objective', y_label='Auxiliary Objective')

Plot the two-objective Pareto frontier.

Puts the primary objective on the x-axis and the auxiliary objective on the y-axis. The frontier is drawn by _draw_frontier (the certified interpolant, with its error band shaded when slopes are known, or else the polyline), and the region between that curve and the largest auxiliary value is shaded light blue.

With annotate_knee, the sampled knee (in the primary knee space) is marked with dashed guide lines to the axes and, when it is not an end point, a short tangent line. This is the sampled knee, not refined_knee. The annotation is skipped when knee raises ValueError.

Parameters:

• annotate_knee (bool) – When True, mark the knee point and draw a tangent line estimated from the adjacent frontier points.

• ax (Axes | None) – Axes to plot onto; None creates a new figure.

• x_label (str) – Label for the x-axis (the primary objective).

• y_label (str) – Label for the y-axis (the auxiliary objective).

Returns:

ax – The axes plotted onto.

Return type:

Axes

Raises:

• ValueError – When the frontier has no points.

• NotImplementedError – When the frontier does not have exactly two objectives.

Notes

The knee’s tangent slope is the secant between the knee’s two neighbours (in order of the auxiliary objective) rather than a value derived from Lagrange multipliers, so it does not depend on how solve_with_bounds normalizes the auxiliary constraint internally.

class cvxium.frontier.multi_objective.MultiObjectiveOptimizer(primary_objective=0)

Bases: ABC, Generic[WarmStartT]

Abstract base for tracing the Pareto frontier of a multi-objective problem.

A subclass implements three methods:

• solve_with_bounds: minimize the primary objective subject to upper bounds on each auxiliary objective.

• minimize_objective: minimize a single objective with no bounds on the others.

• evaluate_objectives: return all N objective values at a point.

Then trace solves the corners, sweeps a grid of auxiliary bounds between them, and collects the resulting Pareto-optimal points.

Optional overrides extend it: tangent_slopes reports the frontier’s slope at each point, which certifies FrontierResults.envelope and enables refine_knee; point_objectives records objectives that are not a function of the solution alone; _build_grids sweeps a different control variable; and _extract_warm_start threads a richer warm-start payload, of type WarmStartT, between solves.

Parameters:

primary_objective (int) – Index into the vector returned by evaluate_objectives of the objective to minimize during the sweep. All other objectives are auxiliary and receive parametric upper bounds. The two-objective features (envelope, refine_knee) assume it is 0 or 1.

Notes

Warm starts. trace threads each solve’s warm-start payload (by default its solution) into the x0 of the next solve_with_bounds or minimize_objective. Whether that helps depends on the inner solver. The previous optimum lies on the boundary of the constraints that bind there, since a Pareto frontier is exactly the locus where they bind, so it is at best marginally feasible for the next subproblem. Both PrimalDualSolver and BarrierSolver need a strictly feasible start and run Phase I (Solver._solve_feasibility) when x0 is not one; they differ in what happens next.

• Primal-dual solvers (PrimalDualSolver) handle warm starts well. They chase KKT residuals directly and have no central path to return to, so a near-optimal x0 looks almost done and progress starts from the first step. Measured speedups on frontier sweeps range from about 4.6x (a distance objective with a swept variance ceiling and an active ∞-norm constraint) down to parity (a variance objective whose active ∞-norm constraint forces extra Newton iterations for active-set discovery). The primal-dual solver was never slower than the barrier method in these measurements, so preferring it is robust even where the speedup is small.

• Barrier solvers (BarrierSolver, InteriorPointMethodSolver) struggle. A start next to the boundary is far from the central path for the initial barrier parameter t, so the first Newton steps are cut short by the backtracking line search before real progress begins. And a marginal start that numerical noise tips into infeasibility sends the solve through Phase I; a Phase I failure raises ProblemInfeasibleError, which _sweep_grid counts as a skipped point, so it shows up as a missing grid point rather than an exception. In practice a naive barrier warm start makes a sweep slower than cold starts.

So an implementation should either use a primal-dual inner solver and forward x0, or use a barrier solver and ignore x0, letting each grid solve start cold. The cause is geometric, not an implementation detail: a point near the previous optimum is what a primal-dual method wants and exactly what a barrier method does not.

Threading richer warm-start state. By default the payload threaded between solves is the decision vector. A subclass whose solver carries additional warm-start state can parametrize MultiObjectiveOptimizer with a payload type and override _extract_warm_start to return it; the base threads that opaque payload through x0 unchanged. This also lets a subclass that sweeps a constraint in the loosening direction, so that the previous optimum stays strictly interior to the next subproblem, warm-start a barrier solver safely: the boundary adjacency described above does not arise there.

abstractmethod solve_with_bounds(bounds, x0=None)

Minimize the primary objective subject to upper bounds on the auxiliaries.

trace calls this at every grid point and refine_knee at every probe. An implementation should raise OptimizationError or ProblemInfeasibleError when a subproblem cannot be solved: trace then skips the point (refine_knee also tolerates NewtonStepError and BacktrackingLineSearchError), while any other exception propagates out of the sweep.

Parameters:

• bounds (npt.NDArray[np.float64]) – bounds[j] is the upper bound on auxiliary objective j (in the order the objectives appear in evaluate_objectives, skipping the primary), of length N - 1. When _build_grids is overridden, this holds whatever control values that grid supplies instead.

• x0 (WarmStartT | None) – Warm-start payload from the previous solve (see _extract_warm_start), or None for a cold start. Adjacent frontier points typically have similar solutions, but whether to use it depends on the inner solver; see the class Notes.

Returns:

result – The inner solver’s result; its solution is the decision variable.

Return type:

SolveResult

abstractmethod minimize_objective(objective_index, x0=None)

Minimize a single objective with no bounds on the others.

Used by trace to compute the N corner points of the frontier, which also fix the sweep range for each auxiliary objective. An exception from the primary objective’s solve propagates out of trace; an auxiliary solve that raises OptimizationError or ProblemInfeasibleError just drops that corner.

Parameters:

• objective_index (int) – Index into the vector returned by evaluate_objectives.

• x0 (WarmStartT | None) – Warm-start payload from the previous solve, or None for a cold start.

Returns:

result – The inner solver’s result; its solution is the decision variable.

Return type:

SolveResult

refine_knee(results, max_iter=24, slope_spread_tol=0.001, knee_space='primary')

Solve for the knee instead of picking the nearest sampled point.

On a convex two-objective frontier f(a), with a the auxiliary objective, the knee has a closed form. Distance to the corner chord is proportional to the vertical gap chord(a) - f(a); differentiating, the gap is largest where

f'(a) = m_chord,

the tangent parallel to the chord. Convexity makes f’ monotone, so this is a one-dimensional monotone root-find in which every probe is a real solve that reports its own slope. The knee is therefore solved for rather than read off an interpolant or quantized to the sweep grid, and the final iterate is itself a frontier point, with no confirming solve.

The search starts from the sampled interval whose slopes bracket the chord slope, and steps by safeguarded regula falsi (see _next_probe). It stops as soon as the tangent parallels the chord to within slope_spread_tol, which is the quantity being solved for, so it usually costs a handful of solves rather than the full max_iter. A relative-bracket backstop catches a frontier too flat for that criterion to bite.

Returns None when the knee is not well determined, which is a real condition rather than a failure: when results has no tangent_slopes, does not have exactly two objectives and two corners, has corners at the same auxiliary value, or has fewer than two finite slopes; when the frontier is straight to tolerance (see Notes); and when the first probe fails or reports no slope. Every probe is folded into results with FrontierResults.absorb_probe, so this updates its points, counters, and tangent_slopes.

Parameters:

• results (FrontierResults) – A traced two-objective frontier, used for its corners (hence the chord) and its slopes. Must carry tangent_slopes.

• max_iter (int) – Cap on the number of probes. A ceiling rather than a target: the search normally converges on slope long before reaching it, and each probe is a real solve.

• slope_spread_tol (float) – Does double duty. Below this spread of slopes across the traced points, relative to the largest slope magnitude, the frontier counts as straight and no knee is reported at all. Within this of the chord slope, relative to the chord slope’s own magnitude (which the corners fix and the grid does not), a probe’s tangent counts as parallel and the search stops.

• knee_space (Literal["primary", "root"]) – Which monotone transform of the primary objective to solve in. Both the chord and every probe’s tangent are measured in it, so the search is internally consistent; what changes is the answer, since a nonlinear transform genuinely moves the bend. "root" requires a primary objective that is the square of a nonnegative convex function, or the monotone precondition is lost; see _knee_space_transform.

Returns:

knee – The refined knee, or None when the knee is not well determined.

Return type:

FrontierPoint | None

Raises:

• ValueError – Propagated from _knee_space_transform for an unrecognized knee_space, or for "root" at a negative primary objective, unless one of the early None returns above comes first.

• Exception – Any exception from solve_with_bounds other than the four that _probe treats as a failed probe, and any exception from tangent_slopes, propagates.

Notes

A straight frontier has no knee, and saying so is the point. When the slope is nearly constant it nearly equals the chord slope everywhere, so the root-find is ill-conditioned, but so is the question. Max chord distance would still return an argmax, determined by differences near the noise floor and liable to move a long way if the grid changes. This returns None instead, leaving the caller to fall back to a rule that does not depend on curvature that is not there. That is also the regime where the choice matters least: along a straight stretch every point trades at the same rate.

The answer is recorded on results via FrontierResults.record_refined_knee, as well as returned. A refined knee is off-grid by construction, so a consumer that only has the results object cannot recover it and will reach for the sampled knee instead, marking a point the caller did not use and looking entirely correct doing it.

Unlike FrontierResults.envelope, the search uses the slopes as reported, without verifying them against the other points.

tangent_slopes(results)

Return the frontier tangent slope d(primary) / d(auxiliary) at each point.

A scalarized sweep knows its own frontier derivative for free. A subproblem minimizing

f_0 + λ f_1

lands where the tangent has slope -λ, by the envelope theorem; an epsilon-constraint subproblem gets the same number from the KKT multiplier on its bound. Supplying it upgrades FrontierResults.envelope from a smoothing heuristic to an interpolation of value and slope, unlocks the tangent bound that certifies it, and enables refine_knee.

The base returns None: correct but uninformative. It cannot be derived generically, because solve_with_bounds chooses how a bound spreads into constraint rows, so only the subclass knows which multipliers belong to it and how they combine. A subclass that bounds one objective with one row can return that row’s multiplier directly; one that spreads a scalar bound across several scaled rows has to aggregate them. The multipliers for a point are on point.ipm_result.duals.

trace calls this on the freshly traced frontier, before returning it. The knee search also calls it once per probe, on a one-point FrontierResults that shares the traced frontier’s corners (see _raw_slope_at), so an implementation must work from results.points and not assume the full grid.

Parameters:

results (FrontierResults) – The frontier whose slopes are wanted.

Returns:

slopes – Slopes in minimization coordinates, of length len(results.points) and aligned with results.points, or None when unknown. Non-finite entries mean “no slope known here” and are skipped; a corner with a genuinely vertical tangent should report nan. envelope verifies the slopes against the other points before trusting them, so an inaccurate one loosens its bound rather than invalidating it; refine_knee uses them as reported.

Return type:

npt.NDArray[np.float64] | None

abstractmethod evaluate_objectives(x)

Return all N objective values at a decision variable.

Parameters:

x (npt.NDArray[np.float64]) – Decision variable.

Returns:

objectives – Objective values, of length N. The element at index self.primary_objective is the primary objective; all others are auxiliary.

Return type:

npt.NDArray[np.float64]

point_objectives(result, bounds)

Return the objective vector to record for a point solved at bounds.

The grid sweep, the auxiliary corners, and the knee probes all build their FrontierPoint objectives through this; the primary corner uses evaluate_objectives directly. The default is evaluate_objectives(result.solution): the objectives are a function of the decision vector alone. Override it when they are not, for example when an auxiliary coordinate is the bound a point was solved at rather than anything its solution attains.

Parameters:

• result (SolveResult) – The result of solve_with_bounds or minimize_objective.

• bounds (npt.NDArray[np.float64]) – The auxiliary bounds it was solved at, of length N - 1; all inf for a corner.

Returns:

objectives – The objective vector to record, of length N.

Return type:

npt.NDArray[np.float64]

trace(num_points=50, callback=None, n_jobs=1)

Trace the Pareto frontier over a grid of auxiliary bounds.

Parameters:

• num_points (int) –

  Number of grid points along each auxiliary-objective dimension. With the default _build_grids, the total number of solves is at most

  N + num_points^(N - 1),
  

  where N is the number of objectives; an override that returns a differently shaped grid changes that count.

• callback (Callable[[FrontierPoint, int, int], bool] | None) – If given, called after each successful solve as callback(point, k, total), where point is the FrontierPoint just computed, k is the 1-based solve index (corners and grid points numbered continuously), and total is the total expected number of solves. The corner callbacks necessarily fire against the estimate N + num_points^(N - 1), since the grid cannot be built until the corners have fixed its bounds; after that total is re-derived from the grid _build_grids actually returned. The two agree unless _build_grids is overridden. Return True to stop the sweep early, False to continue. Failed solves do not trigger the callback. When n_jobs is not 1 the callback fires in completion order rather than grid order.

• n_jobs (int) – Number of worker processes for the grid sweep. 1 runs the sweep sequentially in-process and warm-starts each solve from the previous one. Any other value fans the grid solves out over a ProcessPoolExecutor (any value below 1 means one worker per core), which is a large win when a single solve is expensive: the grid points are independent, so wall-clock time can drop nearly linearly in the worker count. The parallel path solves each point cold, so it is best paired with an inner solver whose cold-start cost is what dominates. Corners are always computed sequentially before the sweep. Requires the optimizer (and everything it references) to be picklable.

Returns:

results – The deduplicated points sorted by the primary objective, the corners, the solve counts, and the slopes from tangent_slopes.

Return type:

FrontierResults

Raises:

• ValueError – When num_points is below 1, when evaluate_objectives returns fewer than two objectives, or when _build_grids returns no axes at all.

• Exception – Any exception from the primary objective’s minimize_objective or evaluate_objectives (OptimizationError and ProblemInfeasibleError included) propagates, as does one from an auxiliary corner or grid solve other than those two (for example NewtonStepError or BacktrackingLineSearchError), and any exception from tangent_slopes.

Notes

1. Call minimize_objective for every objective to get the N corner points (see _compute_corners). A failed auxiliary corner is dropped.

2. Set the sweep range for each auxiliary objective: from its value at the primary corner to its own minimum at its corner, swapped if needed so the range is ascending. When an auxiliary corner failed, its range collapses to the single value at the primary corner.

3. If all corners share one objective vector (within 1e-8), the frontier is a single point: skip the sweep and log it. The sweep is also skipped when the callback stopped during the corners.

4. Call _build_grids for the sweep grids. By default that is a uniform grid of num_points values per auxiliary dimension strictly between the ends of the range; the endpoints are excluded because the corners already sit there, and re-solving there can leave the inner feasible set with empty interior, which breaks interior-point methods.

5. Call solve_with_bounds at each grid point, sequentially with warm starts or in parallel. A point whose solve raises OptimizationError or ProblemInfeasibleError is skipped silently.

6. Deduplicate by objective vector (within 1e-8 absolute tolerance, corners first so they survive), sort by the primary objective, and attach tangent_slopes.

Frontier Interpolation

Smooth interpolation and rigorous bounds for a two-objective Pareto frontier.

A traced frontier is a handful of solved points. Plotting it means joining them, and the usual straight segments quietly assert something false: that the frontier is piecewise linear. It is not, and the error is one-sided, so the picture is biased rather than merely coarse.

Convexity fixes this. A two-objective Pareto boundary in minimization coordinates is convex, which turns the interpolation problem into a bounding problem with an exact answer on both sides:

• Every chord between two attainable points lies on or above the boundary, so the piecewise-linear plot is an upper bound.

• Every tangent line lies on or below the boundary, globally and not just near its point of contact, so the upper envelope of the tangents is a lower bound.

Between consecutive points the true frontier is therefore trapped in a lens, and the lens width is a measured error bar rather than a guess. Shade it and the plot reports its own resolution; take a curve through it and the curve is certified.

The tangent slopes are not an extra burden: a weighted-sum sweep already knows them. Minimizing

f_0 + λ f_1

puts the solution where the boundary’s tangent has slope

df_0 / df_1 = -λ,

so the sweep’s own control variable is the derivative, exactly, by the envelope theorem. An epsilon-constraint sweep gets the same number from the KKT multiplier on its bound. Supplying these turns the interpolant from a fit into an interpolation of both value and slope.

Everything here works in Cvxium’s native minimization convention. A caller plotting a maximized objective negates both axes, which swaps the two bounds: the chord becomes the lower bound and the tangent envelope the upper one.

class cvxium.frontier.frontier_interpolation.FrontierEnvelope(x, chord, tangent, curve, max_band_width)

Bases: object

Smooth frontier curve together with the bounds that certify it.

The four arrays share the dense grid x and use the same coordinate convention as the data passed to interpolate_frontier.

Fields:

• x (npt.NDArray[np.float64]) – Dense grid of length num, spanning the auxiliary objective from the smallest to the largest value among the input points.

• chord (npt.NDArray[np.float64]) – The piecewise-linear interpolant through the points, which is what joining them with straight segments draws. An upper bound on a convex frontier.

• tangent (npt.NDArray[np.float64]) – Upper envelope of the verified tangent lines. A lower bound on a convex frontier; -inf everywhere when no slope was supplied or none survived verification.

• curve (npt.NDArray[np.float64]) – The smooth interpolant, clipped into [tangent, chord] so that it cannot assert anything the bounds rule out.

• max_band_width (float) – Widest gap chord - tangent, as a fraction of the range of the primary objective across the input points: 0.02 means the frontier is pinned everywhere to within 2% of its own vertical extent. A rigorous replacement for judging by eye whether the grid was fine enough. inf when there is no tangent bound, and 0.0 when the primary objective is constant.

cvxium.frontier.frontier_interpolation.interpolate_frontier(x, y, slopes=None, num=200)

Interpolate a convex Pareto frontier and bound the interpolation error.

Parameters:

• x (npt.NDArray[np.float64]) – Auxiliary objective (the swept axis) at each solved point, of length n, in minimization coordinates. Need not be sorted; duplicates are collapsed, keeping the lowest y at each x.

• y (npt.NDArray[np.float64]) – Primary objective at each solved point, of length n, in minimization coordinates.

• slopes (npt.NDArray[np.float64] | None) – Tangent slope dy / dx at each point, of length n. For a weighted-sum sweep minimizing y + λ x this is -λ. Non-finite entries mean “unknown here” and are skipped when building the tangent bound, so a frontier that knows only some of its slopes still gets a partial certificate. Supplied slopes are verified against the other samples before being trusted (see _supports_every_sample) and silently dropped if they fail, so an inaccurate subproblem loosens the bound rather than invalidating it. Wherever no verified slope is available, including when slopes is None, the smooth curve uses shape-preserving (PCHIP) slopes.

• num (int) – Number of points in the returned dense grid.

Returns:

envelope – The dense grid, the chord and tangent bounds, the certified smooth curve, and the widest band width.

Return type:

FrontierEnvelope

Raises:

ValueError – When num < 2, or when the samples are invalid (see _normalize_samples): arrays of different lengths, non-finite x or y, or fewer than two distinct x values.

Notes

Convexity is assumed, not checked: it is a property of the problem (a convex decision set and convex objectives, in minimization coordinates), not of the samples, and a near-degenerate sample can violate it through solver noise without the frontier being non-convex. When the samples do contradict it, the tangent bound can rise above the chord between two samples, and the curve is clipped to the chord there. Because the verified tangents lie below every sample, max_band_width stays nonnegative to within the tolerance and does not reveal such a crossing; compare tangent with chord directly to detect one.