Multi-Objective Optimization

Part 7 turns from methods to the harder questions real optimization raises, and the first is the most common of all: engineering objectives conflict. A transformer should be cheap and efficient, but efficiency demands more copper and better steel, which cost money. A control system should be fast and stable, but the gains that speed it up erode its stability margin. A portfolio should earn a high return at low risk, but the assets that promise more return carry more of it. In each case, improving one objective actively worsens another. There is no single design that is best on every count, because no such design exists.

A multi-objective problem simply writes several objectives down at once:

The notation hides a genuine difficulty: what does \(\min\) of a vector even mean? Real numbers are totally ordered — any two can be compared — but vectors are not. Is \((3, 8)\) better or worse than \((5, 4)\)? It is cheaper in the first objective and dearer in the second; the question has no answer until someone says how much a unit of the first is worth in terms of the second. This is the whole problem in miniature, and it forces a distinction the rest of the chapter depends on.

The one comparison we can make between vectors without any trade-off information is the cautious one: a design is clearly better than another only if it is better in some objective and no worse in every other. This is Pareto dominance, named for the economist Vilfredo Pareto.

Dominance sorts the whole feasible set into two kinds of design. A design that is dominated by some other is simply wasteful — another feasible design beats it outright, so no rational decision maker would ever choose it. A design that is dominated by nothing feasible is Pareto optimal (or non-dominated, or efficient): you cannot improve any one of its objectives without giving up ground on another. The collection of all such designs is the Pareto-optimal set, and it is the true answer to a multi-objective problem — not one design, but every design worth considering.

The image of the Pareto-optimal set in objective space is the Pareto front — the boundary of the achievable region, along its lower-left edge for a minimisation. It is the trade-off surface made visible: every point on it is a design you might rationally build, and moving along it means trading a measured amount of one objective for a measured amount of another. The slope of the front at a point is literally the exchange rate between the objectives there.

Two reference points frame the front and recur throughout the methods that follow. The ideal point \(\mathbf{z}^{\star}\) takes the best value of each objective separately — the corner you would reach if the objectives did not conflict. It is almost never attainable; if it were, the problem would not be multi-objective. The nadir point takes the worst value each objective attains on the Pareto front, marking the front's opposite extreme. Together they bound the front and give the natural scale for normalising objectives that come in different units.

The shape of the front matters more than it first appears, because it decides which solution methods will work. A convex front bulges toward the ideal point; a non-convex (concave) front has stretches that bow away from it. Both are perfectly ordinary — many real problems produce fronts with concave regions, disconnected pieces, or sharp knees. As the next section shows, the simplest and most popular scalarization method is blind to exactly the concave stretches, which is why the shape is not a curiosity but a design constraint on the whole approach.

The oldest way to handle several objectives is to collapse them into one. Assign each objective a weight reflecting its importance and add them up — a scalarization that turns the vector problem back into an ordinary single-objective one we already know how to solve.

It is appealingly simple, and when the front is convex it works: every Pareto point can be reached by some weight vector. But the method carries a fatal blind spot on non-convex fronts, and the geometry makes the reason plain. Minimising \(w_1 f_1 + w_2 f_2\) is the same as sliding a straight line of slope \(-w_1/w_2\) toward the origin until it just touches the achievable region. The point it touches is always on the convex hull of the front. A solution sitting in a concave dip lies above the line joining its neighbours, so no such line can touch it first — some other point is always reached sooner.

The cure for the weighted sum's blindness is to stop adding objectives together. The ε-constraint method keeps just one objective to minimise and demotes the rest to constraints, each capped at a chosen bound \(\varepsilon_i\).

The picture is a movable wall. Capping \(f_2 \le \varepsilon\) slices off the part of objective space above the wall; minimising \(f_1\) within what remains slides to the leftmost surviving point of the front — which may sit squarely in a concave dip. Push the wall down step by step and the found point walks along the entire front, concavities included. The price is that the bounds must be chosen with some care: set \(\varepsilon\) too tight and the problem becomes infeasible; too loose and the constraint is inactive and you recover only the single-objective optimum.

A third family sidesteps weights and bounds by measuring distance to the ideal point. Compromise programming minimises \(\lVert \mathbf{F}(\mathbf{x}) - \mathbf{z}^{\star}\rVert_p\) — the \(L_p\) distance from a design's score-vector to the unattainable ideal — and returns the Pareto point that comes closest to having everything at once. With \(p = 2\) it picks the balanced, "knee"-like solution; with \(p = \infty\) (the weighted Chebyshev form) it too can reach any Pareto point, convex or not. Objectives should be normalised by the ideal–nadir range first, so that a large-numbered objective does not swamp a small-numbered one purely through its units.

Every scalarization shares one inconvenience: it delivers a single point per solve, so approximating the whole front means running the optimizer many times, once per weight or bound. Population methods have a decisive structural advantage here. A population is a set of solutions, so a single run can approximate the entire Pareto front at once — which is why the evolutionary algorithms of Chapters 24–25 became the dominant tools for multi-objective problems. The catch is that their selection step, built to rank a population by one number, must be rebuilt to rank by dominance instead.

The standard answer is Deb's NSGA-II (2002), and it earns its status from two ingredients that together push a population toward the front while spreading it evenly along it.

Crowding distance is worth stating precisely, because it is how NSGA-II avoids the classic failure of collapsing onto one corner of the front. For each objective, sort the front and give every individual the normalised gap between its two neighbours; sum these gaps across objectives. The two boundary individuals — best and worst in each objective — are given infinite distance so they are never discarded, which anchors the spread of the front at its extremes.

The full generation then reads like a standard GA with a dominance-aware twist: combine parents and offspring (elitism — the best are never lost), sort the combined pool into fronts, and fill the next generation front by front until one front overflows the population size. That last, overflowing front is admitted in order of decreasing crowding distance, taking the isolated individuals and dropping the crowded ones. Selection for mating uses a tournament on the pair (front rank first, crowding distance as the tie-breaker). Pushed toward \(F_1\) by the sorting and spread along it by crowding, the population converges to a well-distributed approximation of the whole front in one run.

Whatever method produces the front, it produces a set, and an engineer must eventually build one design. Turning the Pareto set into a single choice is multi-criteria decision making, and the field is organised by when the decision maker's preferences enter.

The a posteriori route has become the default precisely because it separates the two hard things — computing the trade-offs, and judging them — and shows the decision maker the real cost of every preference before any is committed to. A common automatic pick from a generated front is the knee point, where the front bends most sharply: just before the knee, a small sacrifice in one objective buys a large gain in another; just after it, the exchange rate turns punishing. The knee is where a balanced compromise gives the most for the least, and compromise programming with \(p = 2\) tends to land near it.

Set against each other, the methods of this chapter divide cleanly by what they cost and what they can reach.

For dominance problems, test each pair objective by objective and remember that a tie in one objective still allows domination if the other is strictly better. For scalarization problems, watch the front's shape — if it is non-convex, expect the weighted sum to skip points. Difficulty rises down the list.