44.01.05 · optimization-control / 01-convex-sets-functions

Multicriteria and Vector Optimization: Pareto Optimality and Scalarization

shipped3 tiersLean: none

Anchor (Master): Ehrgott 2005 Multicriteria Optimization (Springer) Ch. 2-5; Miettinen 1999 Nonlinear Multiobjective Optimization (Kluwer) Ch. 2-3; Boyd & Vandenberghe 2004 Convex Optimization (Cambridge) §4.7

Intuition Beginner

Most decisions juggle several goals at once that pull in different directions. A car designer wants a car that is both cheap and fast and safe. A portfolio manager wants high return and low risk. You usually cannot have the best of every goal at the same time: making the car faster tends to make it pricier. So "the best car" is not a single answer the way "the cheapest car" would be.

Multicriteria optimization is the study of choosing well when you have several objectives and no single one to rank by. The key idea is to give up on finding one winner and instead find the set of choices that are not wasteful. A choice is wasteful if some other choice beats it on one goal while doing at least as well on every other goal. Why settle for that? You could switch to the better choice for free. So we throw wasteful options out.

What remains are the choices where you cannot improve any goal without giving up ground on another. These are the efficient or Pareto choices. They form a frontier: the menu of sensible tradeoffs. A faster car here costs more; a cheaper one there is slower; every option on the menu is a fair deal, and which one you pick depends on how much you personally value speed against price.

How do you actually compute this menu? A clean trick is to roll the several goals into one by attaching a weight to each — say, dollars-per-unit-of-speed — and then minimize the single weighted total. Each choice of weights picks out one point on the frontier. Sweep the weights across all their possibilities and you trace the whole menu. This rolling-into-one move is called scalarization, and it is the bridge from many goals back to the one-goal problems we already know how to solve.

Visual Beginner

Figure: a plane whose horizontal axis is objective one (say, cost) and whose vertical axis is objective two (say, risk), both to be made small. A shaded blob is the set of achievable outcomes. Its lower-left boundary — the curve facing the origin — is the Pareto frontier: points where you cannot reduce one objective without raising the other. Interior points and upper-right boundary points are wasteful, since you can move down-and-left into the blob. A straight line of a given slope (the weights) is pushed toward the origin until it just touches the blob; the touch point is one Pareto choice, and tilting the line sweeps along the frontier.

  risk
   ^
   |   *.            achievable outcomes (shaded blob)
   |    '..                  *  <- wasteful (can move down-left)
   |      '.. #########
   |        '..##########
   |          '#########          weighted line tilts
   |  Pareto    '#######          to sweep the frontier
   |  frontier    '####
   |  (lower-left   '##
   |   boundary)      '. <- touch point = one Pareto choice
   +---------------------\------------> cost
                          weighted line  c1*cost + c2*risk = const

Worked example Beginner

A factory can split its single hour of machine time between making widget A and widget B. Let $a$ be hours on A and $b$ hours on B, with $a + b = 1$ and $a, b \geq 0$ . Objective one is waste, equal to $a$ (machine A spills material). Objective two is delay, equal to $b$ (machine B is slow). Both should be small. We find the sensible tradeoffs.

Step 1. List the achievable outcomes. Since $b = 1 - a$ , an outcome is the pair $(waste, delay) = (a, 1 - a)$ for $a$ between $0$ and $1$ . As $a$ runs from $0$ to $1$ , this traces the straight segment from $(0, 1)$ to $(1, 0)$ .

Step 2. Find the wasteful choices. Pick any point on the segment, say $(0.3, 0.7)$ . Can another achievable point beat it on one goal without losing on the other? Every other point on the segment that has less waste has more delay, and the reverse. So no point on the segment is wasteful: the entire segment is the Pareto frontier.

Step 3. Scalarize. Attach weight $c_{1}$ to waste and $c_{2}$ to delay, both positive, and minimize $c_{1} a + c_{2} (1 - a)$ over $a$ in $[0, 1]$ . The expression equals $(c_{1} - c_{2}) a + c_{2}$ , a straight line in $a$ .

Step 4. Read off the minimizer. If $c_{1} < c_{2}$ the slope $c_{1} - c_{2}$ is negative, so the minimum is at $a = 1$ : outcome $(1, 0)$ . If $c_{1} > c_{2}$ the minimum is at $a = 0$ : outcome $(0, 1)$ . If $c_{1} = c_{2}$ every $a$ ties.

What this tells us. Each weight choice selects an endpoint of the frontier, and equal weights make the whole frontier optimal. Sweeping the ratio $c_{1} / c_{2}$ recovers the sensible tradeoffs. The weights encode how many units of delay you will trade for one unit of waste.

Check your understanding Beginner

Formal definition Intermediate+

Throughout, the ambient objective space is $R^{q}$ with the standard inner product, and ordering is induced by a proper cone.

Definition (proper cone, generalized inequality). A cone $K \subseteq R^{q}$ is proper if it is convex, closed, pointed ( $K \cap (- K) = {0}$ ), and solid (nonempty interior). A proper cone induces the partial order $u ⪯_{K} v ⟺ v - u \in K$ , with strict version $u ≺_{K} v ⟺ v - u \in int K$ (see the cone material of 44.01.01). The leading example is the nonnegative orthant $K = R_{+}^{q}$ , for which $⪯_{K}$ is componentwise $\leq$ .

Definition (vector optimization problem). Given a feasible set $D \subseteq R^{n}$ and an objective map $f_{0} : D \to R^{q}$ , the vector optimization problem is to minimize $f_{0} (x)$ with respect to $⪯_{K}$ subject to $x \in D$ . Its achievable (value) set is

O = f_{0} (D) = {f_{0} (x) : x \in D} \subseteq R^{q} .

Definition (Pareto optimal / efficient). A feasible $x^{⋆}$ is Pareto optimal (its value $f_{0} (x^{⋆})$ is efficient) if no feasible $x$ satisfies $f_{0} (x) ⪯_{K} f_{0} (x^{⋆})$ with $f_{0} (x) \neq = f_{0} (x^{⋆})$ . Equivalently, $f_{0} (x^{⋆})$ is a minimal element of $O$ for $⪯_{K}$ :

(f_{0} (x^{⋆}) - K) \cap O = {f_{0} (x^{⋆})} .

A feasible $x^{⋆}$ is weakly Pareto optimal (value weakly efficient) if no feasible $x$ satisfies $f_{0} (x) ≺_{K} f_{0} (x^{⋆})$ , i.e.

(f_{0} (x^{⋆}) - int K) \cap O = \emptyset .

Every efficient value is weakly efficient; the Pareto frontier is the set of efficient values. A value $u$ is the utopia (ideal) point if $u_{i} = in f_{x \in D} (f_{0} (x))_{i}$ for each $i$ ; it is generally unachievable, and the frontier is the achievable surface facing it.

Definition ( $K$ -convexity). The map $f_{0}$ is $K$ -convex on the convex set $D$ if for all $x, y \in D$ and $θ \in [0, 1]$ ,

f_{0} (θ x + (1 - θ) y) ⪯_{K} θ f_{0} (x) + (1 - θ) f_{0} (y) .

Equivalently, the extended achievable set $A = f_{0} (D) + K = O + K$ is convex. The set $A$ — the achievable values together with everything they $K$ -dominate — is the multicriteria analogue of the value set of 44.02.01; minimal elements of $O$ coincide with minimal elements of $A$ .

Definition (scalarization). For a weight $λ \in K^{*}$ (the dual cone $K^{*} = {λ : ⟨ λ, u ⟩ \geq 0 \forall u \in K}$ of 44.01.01), the scalarized problem is the single-objective program

x \in D min ⟨ λ, f_{0} (x)⟩ .

For the orthant, $K^{*} = R_{+}^{q}$ and this is the familiar weighted-sum objective $\sum_{i} λ_{i} (f_{0} (x))_{i}$ with $λ ⪰ 0$ . Weights in the interior $int K^{*}$ (all $λ_{i} > 0$ for the orthant) play the decisive role below.

Counterexamples to common slips

Weakly efficient is strictly weaker than efficient. For the orthact in $R^{2}$ , the point $(0, 5)$ on the achievable segment from $(0, 5)$ to $(3, 0)$ is weakly efficient on the horizontal edge ${(0, t) : t \geq 5}$ if that edge is achievable, yet a point with the same first coordinate and smaller second coordinate dominates it; an axis-parallel flat piece of the frontier carries weakly efficient points that are not efficient.
Boundary weights lose efficiency. Scalarizing with $λ$ on the boundary of $K^{*}$ (some $λ_{i} = 0$ ) can return a minimizer that is only weakly efficient or even dominated: a zero weight ignores an objective entirely, so the minimizer may be improvable on that ignored coordinate. Interior weights are what guarantee efficiency.
The achievable set need not be convex. Without $K$ -convexity of $f_{0}$ , $O$ can be nonconvex, and then some efficient points lie in a "dent" of the frontier that no supporting hyperplane touches. The weighted-sum method finds only supported efficient points; the unsupported ones require the $ε$ -constraint method.

Key theorem with proof Intermediate+

The two directions of the scalarization correspondence are unequal in strength. Minimizing an interior-weighted sum always lands on the frontier, with no convexity needed; the converse — that every efficient point is some weighted-sum minimum — requires convexity and is the supporting-hyperplane theorem of 02.11.02 applied to the extended achievable set $A$ , exactly as strong duality in 44.02.01 separated a point from the value set.

Theorem (scalarization and the Pareto frontier).

(i) (Sufficiency, unconditional.) Let $λ \in int K^{*}$ . If $x^{⋆} \in D$ minimizes $⟨ λ, f_{0} (x)⟩$ over $D$ , then $x^{⋆}$ is Pareto optimal. If $λ \in K^{*} ∖ {0}$ and $x^{⋆}$ is the unique minimizer, then $x^{⋆}$ is Pareto optimal; for a non-unique minimizer with $λ \in K^{*} ∖ {0}$ , $x^{⋆}$ is at least weakly Pareto optimal.

(ii) (Necessity under convexity.) Suppose the problem is convex: $D$ is convex and $f_{0}$ is $K$ -convex, so $A = O + K$ is convex. If $x^{⋆}$ is Pareto optimal, then there exists $λ \in K^{*} ∖ {0}$ such that $x^{⋆}$ minimizes $⟨ λ, f_{0} (x)⟩$ over $D$ ; if $x^{⋆}$ is weakly Pareto optimal, the same conclusion holds. Thus every (weakly) efficient value is supported by a scalarization.

Proof of (i). Let $λ \in int K^{*}$ and suppose $x^{⋆}$ minimizes $⟨ λ, f_{0} (\cdot)⟩$ . Suppose, toward a contradiction, $x^{⋆}$ is not Pareto optimal: there is feasible $x$ with $f_{0} (x) ⪯_{K} f_{0} (x^{⋆})$ and $f_{0} (x) \neq = f_{0} (x^{⋆})$ . Write $d = f_{0} (x^{⋆}) - f_{0} (x) \in K$ , $d \neq = 0$ . A defining property of $int K^{*}$ is that $⟨ λ, d ⟩ > 0$ for every nonzero $d \in K$ (an interior dual vector is strictly positive on $K ∖ {0}$ ; this is the strict-positivity characterization recorded below in Proposition 1). Hence $⟨ λ, f_{0} (x)⟩ = ⟨ λ, f_{0} (x^{⋆})⟩ - ⟨ λ, d ⟩ < ⟨ λ, f_{0} (x^{⋆})⟩$ , contradicting minimality of $x^{⋆}$ . So $x^{⋆}$ is Pareto optimal. For the weak claim with $λ \in K^{*} ∖ {0}$ : if $f_{0} (x) ≺_{K} f_{0} (x^{⋆})$ then $d = f_{0} (x^{⋆}) - f_{0} (x) \in int K$ , and a nonzero $λ \in K^{*}$ satisfies $⟨ λ, d ⟩ > 0$ on $int K$ , again contradicting minimality, so $x^{⋆}$ is weakly Pareto optimal. $□$

Proof of (ii). Assume $D$ convex and $f_{0}$ $K$ -convex, so $A = O + K$ is convex (the sum of the convex set $O + K$ structure is convex by the operation calculus of 44.01.01; convexity of $A$ is the content of $K$ -convexity). Let $x^{⋆}$ be weakly Pareto optimal and set $a^{⋆} = f_{0} (x^{⋆})$ . Weak efficiency says $(a^{⋆} - int K) \cap O = \emptyset$ , and since $A = O + K$ and $int K$ is a cone stable under adding $K$ , this upgrades to

(a^{⋆} - int K) \cap A = \emptyset .

The set $a^{⋆} - int K$ is open, convex, and nonempty, and $A$ is convex; they are disjoint. By the separating-hyperplane theorem for convex sets — the finite-dimensional case of the geometric Hahn-Banach result of 02.11.02, requiring no choice principle — there is a nonzero $λ \in R^{q}$ and a scalar $γ$ with

⟨ λ, v ⟩ \leq γ \leq ⟨ λ, a ⟩ for all v \in a^{⋆} - int K, a \in A .

First, $λ \in K^{*}$ : for any $k \in K$ and $a \in A$ , the point $a + t k \in A$ for all $t \geq 0$ (since $A + K = A$ ), so $⟨ λ, a ⟩ + t ⟨ λ, k ⟩ \geq γ$ for all $t \geq 0$ , forcing $⟨ λ, k ⟩ \geq 0$ ; thus $λ \in K^{*}$ , and $λ \neq = 0$ . Next, taking $v \to a^{⋆}$ from within $a^{⋆} - int K$ (legitimate since $a^{⋆}$ is in the closure of that open set) and $a = a^{⋆} \in A$ gives $⟨ λ, a^{⋆} ⟩ \leq γ \leq ⟨ λ, a^{⋆} ⟩$ , so $γ = ⟨ λ, a^{⋆} ⟩$ . The right inequality then reads $⟨ λ, a ⟩ \geq ⟨ λ, a^{⋆} ⟩$ for all $a \in A \supseteq O$ , that is $⟨ λ, f_{0} (x)⟩ \geq ⟨ λ, f_{0} (x^{⋆})⟩$ for all $x \in D$ . So $x^{⋆}$ minimizes the scalarized objective with weight $λ \in K^{*} ∖ {0}$ . Pareto optimal implies weakly Pareto optimal, so the conclusion covers efficient points as well. $□$

Bridge. This theorem builds toward the conic and generalized-inequality programs of 44.05.01 and appears again in every weighted-objective trainer, regularizer, and portfolio model downstream. This is exactly the supporting-hyperplane mechanism of 44.02.01, transplanted from the scalar value set to the vector achievable set $A$ : the weight $λ$ is the normal to a supporting hyperplane of $A$ at the efficient value $a^{⋆}$ , so scalarization is the search for that support, and $int K^{*}$ is what guarantees the support is non-degenerate exactly as $int$ feasibility guaranteed a non-vertical support in duality. The foundational reason the weighted-sum method can miss efficient points is a non-convex achievable set, where the frontier dents inward and no supporting hyperplane touches the dent — the precise multicriteria analogue of a positive duality gap. Putting these together, sufficiency is dual to necessity: interior weights certify efficiency unconditionally, while convexity certifies that every efficient point carries a weight, and the bridge between the two directions is the convexity of $A$ , the single object through which the Lagrange-multiplier theory of 44.02.01 and the cone calculus of 44.01.01 become one tradeoff geometry.

Exercises Intermediate+

Exercise 2 (easy, symbolic).

Show that if $x^{⋆}$ is the unique minimizer of $⟨ λ, f_{0} (\cdot)⟩$ over $D$ for some $λ \in K^{*} ∖ {0}$ , then $x^{⋆}$ is Pareto optimal.

Hint

A dominating $x$ has $⟨ λ, f_{0} (x)⟩ \leq ⟨ λ, f_{0} (x^{⋆})⟩$ ; uniqueness then forces $f_{0} (x) = f_{0} (x^{⋆})$ .

Answer

Suppose $f_{0} (x) ⪯_{K} f_{0} (x^{⋆})$ with $f_{0} (x) \neq = f_{0} (x^{⋆})$ for some feasible $x$ . Then $f_{0} (x^{⋆}) - f_{0} (x) \in K$ , and since $λ \in K^{*}$ , $⟨ λ, f_{0} (x^{⋆}) - f_{0} (x)⟩ \geq 0$ , i.e. $⟨ λ, f_{0} (x)⟩ \leq ⟨ λ, f_{0} (x^{⋆})⟩$ . By minimality of $x^{⋆}$ the reverse holds too, so $⟨ λ, f_{0} (x)⟩ = ⟨ λ, f_{0} (x^{⋆})⟩$ , making $x$ another minimizer. Uniqueness forces $x = x^{⋆}$ (hence $f_{0} (x) = f_{0} (x^{⋆})$ ), contradicting $f_{0} (x) \neq = f_{0} (x^{⋆})$ . So $x^{⋆}$ is Pareto optimal. The uniqueness hypothesis substitutes for interiority of $λ$ .

Exercise 3 (medium, symbolic).

State the $ε$ -constraint method: minimize one objective subject to upper bounds on the others, $min_{x \in D} (f_{0} (x))_{1}$ s.t. $(f_{0} (x))_{i} \leq ε_{i}$ for $i = 2, \dots, q$ . Show that any optimal solution is weakly Pareto optimal, and that if it is the unique optimum it is Pareto optimal.

Hint

A point that strictly dominates the optimum is still feasible for the $ε$ -problem and has a smaller first objective.

Answer

Let $x^{⋆}$ solve the $ε$ -problem. Suppose $x^{⋆}$ is not weakly Pareto optimal: some feasible $x$ has $(f_{0} (x))_{i} < (f_{0} (x^{⋆}))_{i}$ for all $i$ . Then for $i \geq 2$ , $(f_{0} (x))_{i} < (f_{0} (x^{⋆}))_{i} \leq ε_{i}$ , so $x$ is feasible for the $ε$ -problem, while $(f_{0} (x))_{1} < (f_{0} (x^{⋆}))_{1}$ contradicts optimality of $x^{⋆}$ . So $x^{⋆}$ is weakly Pareto optimal. If $x^{⋆}$ is the unique optimum: a dominator $x$ with $f_{0} (x) ⪯_{K} f_{0} (x^{⋆})$ , $f_{0} (x) \neq = f_{0} (x^{⋆})$ has $(f_{0} (x))_{i} \leq (f_{0} (x^{⋆}))_{i} \leq ε_{i}$ for $i \geq 2$ , so $x$ is feasible with $(f_{0} (x))_{1} \leq (f_{0} (x^{⋆}))_{1}$ ; uniqueness forces $x = x^{⋆}$ , a contradiction, so $x^{⋆}$ is Pareto optimal. Unlike weighted sums, the $ε$ -constraint method reaches unsupported efficient points in nonconvex problems by slicing the achievable set with the box ${(f_{0})_{i} \leq ε_{i}}$ rather than a hyperplane.

Exercise 4 (medium, symbolic).

Consider regularized least squares as a bicriterion problem: minimize the pair $(∥ A x - b ∥_{2}^{2}, ∥ x ∥_{2}^{2})$ over $x \in R^{n}$ with $K = R_{+}^{2}$ . Scalarize with weights $(1, μ)$ , $μ > 0$ . Find the minimizer and describe the curve it traces as $μ$ varies.

Hint

The scalarized objective is $∥ A x - b ∥_{2}^{2} + μ ∥ x ∥_{2}^{2}$ ; set its gradient to zero.

Answer

The scalarized objective $∥ A x - b ∥_{2}^{2} + μ ∥ x ∥_{2}^{2}$ has gradient $2 A^{⊤} (A x - b) + 2 μx$ , zero at $x (μ) = (A^{⊤} A + μ I)^{- 1} A^{⊤} b$ — the ridge/Tikhonov solution. As $μ$ ranges over $(0, \infty)$ , the pair $(∥ A x (μ) - b ∥_{2}^{2}, ∥ x (μ) ∥_{2}^{2})$ traces the Pareto frontier: the L-curve, convex and decreasing, running from the unregularized least-squares fit (small $μ$ : small residual, large norm) to the origin-ward shrinkage limit (large $μ$ : large residual, small norm). Each interior weight $μ > 0$ certifies a Pareto point by Theorem part (i), and since the problem is convex part (ii) guarantees the whole frontier is swept. The "corner" of the L-curve is a common heuristic choice of $μ$ .

Exercise 5 (medium, symbolic).

Markowitz risk-return: minimize the pair $(- r^{⊤} x, x^{⊤} Σ x)$ over the simplex ${x ⪰ 0, 1^{⊤} x = 1}$ , where $r$ is the expected-return vector and $Σ ≻ 0$ the covariance. Explain why the achievable set is convex and what the scalarization weight means.

Hint

$- r^{⊤} x$ is affine (so concave and convex) and $x^{⊤} Σ x$ is convex with $Σ ≻ 0$ ; the feasible set is a polytope.

Answer

The feasible simplex is convex, and the objective map $x \mapsto (- r^{⊤} x, x^{⊤} Σ x)$ is $R_{+}^{2}$ -convex: the first component is affine, the second is convex since $Σ ≻ 0$ (by the PSD-Hessian criterion of 44.01.01). Hence the extended achievable set $A = O + R_{+}^{2}$ is convex and Theorem part (ii) applies: every efficient portfolio is a weighted-sum minimizer. Scalarizing with weight $(γ, 1)$ gives $min_{x} - γ r^{⊤} x + x^{⊤} Σ x$ , the mean-variance problem; $γ > 0$ is the risk-tolerance parameter, and as $γ$ sweeps $(0, \infty)$ the minimizers trace the efficient frontier in risk-return space. The weight $γ$ is the investor's marginal rate of substitution between variance and expected return.

Exercise 6 (hard, symbolic).

Prove the strict-positivity characterization used in the Key theorem: $λ \in int K^{*}$ if and only if $⟨ λ, d ⟩ > 0$ for every $d \in K ∖ {0}$ , for a proper cone $K$ .

Hint

For the forward direction, perturb $λ$ within $K^{*}$ . For the reverse, use compactness of $K \cap {∥ d ∥ = 1}$ to get a positive margin.

Answer

( $\Rightarrow$ ) Let $λ \in int K^{*}$ and $d \in K ∖ {0}$ . If $⟨ λ, d ⟩ = 0$ , then for small $ε > 0$ the vector $λ - ε d /∥ d ∥^{2}$ still lies in $K^{*}$ (interiority) yet pairs to $- ε < 0$ with $d \in K$ , contradicting $K^{*}$ membership. Since $⟨ λ, d ⟩ \geq 0$ always for $λ \in K^{*}$ , strictness follows. ( $\Leftarrow$ ) Suppose $⟨ λ, d ⟩ > 0$ for all $d \in K ∖ {0}$ . The set $S = K \cap {∥ d ∥ = 1}$ is compact (closed and bounded; $K$ closed), so $m = min_{d \in S} ⟨ λ, d ⟩ > 0$ . For any $μ$ with $∥ μ - λ ∥ < m$ and any $d \in S$ , $⟨ μ, d ⟩ = ⟨ λ, d ⟩ + ⟨ μ - λ, d ⟩ \geq m - ∥ μ - λ ∥ > 0$ ; by positive homogeneity $⟨ μ, d ⟩ \geq 0$ for all $d \in K$ , so $μ \in K^{*}$ . Thus a ball around $λ$ lies in $K^{*}$ , giving $λ \in int K^{*}$ . (Solidity and pointedness of $K$ guarantee $S \neq = \emptyset$ and the strict positivity is consistent.)

Exercise 7 (hard, symbolic).

Exhibit a nonconvex bicriterion problem with an efficient point that no weighted-sum scalarization can reach, and verify the $ε$ -constraint method reaches it.

Hint

Use an achievable set that is a non-convex arc dented toward the origin, so a frontier point lies above every supporting line.

Answer

Let $D = {1, 2, 3}$ and $f_{0} (1) = (0, 2)$ , $f_{0} (2) = (1, 1)$ , $f_{0} (3) = (2, 0)$ , with $K = R_{+}^{2}$ . All three are efficient (no point dominates another). For weighted sums with $λ = (λ_{1}, λ_{2}) ≻ 0$ : the scalar values are $2 λ_{2}$ , $λ_{1} + λ_{2}$ , $2 λ_{1}$ . The middle point $f_{0} (2) = (1, 1)$ is the strict minimizer only if $λ_{1} + λ_{2} < 2 λ_{2}$ and $< 2 λ_{1}$ , i.e. $λ_{1} < λ_{2}$ and $λ_{2} < λ_{1}$ simultaneously — impossible. So $(1, 1)$ is unsupported: it lies on the dented part of the frontier, above the line through $(0, 2)$ and $(2, 0)$ . The $ε$ -constraint method recovers it: $min (f_{0})_{1}$ s.t. $(f_{0})_{2} \leq 1$ admits only points $2$ and $3$ , with first objectives $1$ and $2$ ; the minimum is at $x = 2$ , returning $(1, 1)$ . Slicing with the box reaches the unsupported efficient point that no hyperplane supports.

Exercise 8 (hard, symbolic).

For a convex bicriterion problem with a differentiable, decreasing Pareto frontier $f_{2} = φ (f_{1})$ in value space, show that the optimal weight ratio $λ_{1} / λ_{2}$ at an efficient point equals $- φ^{'}$ there, the marginal rate of substitution, and connect this to the multiplier reading of 44.02.01.

Hint

The weight vector is normal to the supporting line of the achievable set at the efficient point; the frontier's tangent has slope $φ^{'}$ .

Answer

By Theorem part (ii), the efficient value $a^{⋆} = (f_{1}^{⋆}, f_{2}^{⋆})$ is supported by a hyperplane (here a line) with normal $λ = (λ_{1}, λ_{2}) \in int R_{+}^{2}$ : $λ_{1} f_{1} + λ_{2} f_{2} \geq λ_{1} f_{1}^{⋆} + λ_{2} f_{2}^{⋆}$ for all achievable $(f_{1}, f_{2})$ , with equality along the supporting line. That line is tangent to the frontier $f_{2} = φ (f_{1})$ at $a^{⋆}$ , and the level line $λ_{1} f_{1} + λ_{2} f_{2} = const$ has slope $- λ_{1} / λ_{2}$ in the $(f_{1}, f_{2})$ -plane. Tangency to the frontier, whose slope is $φ^{'} (f_{1}^{⋆})$ , forces $- λ_{1} / λ_{2} = φ^{'} (f_{1}^{⋆})$ , i.e. $λ_{1} / λ_{2} = - φ^{'} (f_{1}^{⋆}) > 0$ . This is the marginal rate of substitution: at the optimum, one unit of $f_{1}$ trades against $- φ^{'}$ units of $f_{2}$ . It is the multicriteria face of the sensitivity reading of 44.02.01, where the Lagrange multiplier was the marginal price $- \partial p^{⋆} / \partial u_{i}$ ; here the weight ratio is the marginal price of one objective in units of another along the frontier.

Advanced results Master

Proper efficiency and the interior of the dual cone

The sufficiency direction is sharp once efficiency is strengthened to exclude unbounded tradeoff rates. A point $x^{⋆}$ is properly efficient in Geoffrion's sense ^{[Geoffrion 1968]} if it is efficient and there is a constant $M > 0$ such that for each objective $i$ and each feasible $x$ with $(f_{0} (x))_{i} < (f_{0} (x^{⋆}))_{i}$ , some objective $j$ degrades with bounded rate, $((f_{0} (x))_{j} - (f_{0} (x^{⋆}))_{j}) / ((f_{0} (x^{⋆}))_{i} - (f_{0} (x))_{i}) \leq M$ . The trade-off ratios stay finite; the improperly efficient points are those where an unbounded amount of one objective is sacrificed for an infinitesimal gain in another. For convex problems the properly efficient points are exactly the minimizers of $⟨ λ, f_{0} (\cdot)⟩$ over strictly positive weights $λ \in int K^{*}$ — the interior-weight scalarizations cut out proper efficiency, while boundary weights $λ \in \partial K^{*} ∖ {0}$ reach the remaining weakly efficient and improperly efficient frontier pieces. This refines the Key theorem: the dual cone stratifies the frontier, its interior indexing the well-behaved core and its boundary the degenerate edges.

Benson's theorem, the recession cone, and existence of efficient points

Whether the efficient set is nonempty is governed by the recession structure of the achievable set, the cone material of 44.01.01. Benson's characterization recasts efficiency through the augmented set: $a^{⋆} \in O$ is efficient if and only if the only $k \in K$ with $a^{⋆} - k \in cl (O + K)$ is $k = 0$ . Existence then follows from a compactness-with-cone argument: if $O$ is closed, $K$ -bounded below (the section $(a - K) \cap O$ is compact for some $a$ ), and the recession cone of $O + K$ meets $- K$ only at the origin, the efficient set is nonempty and every feasible value is dominated by an efficient one (external stability). This is the vector-valued analogue of the Weierstrass attainment that the scalar value function of 44.02.01 enjoyed under coercivity, with the orthant order replaced by the cone order and "minimum exists" replaced by "the minimal frontier is nonempty and dominating."

Achievement scalarizing functions and reachability of every efficient point

The weighted-sum method's blindness to unsupported points is repaired in full generality not only by the $ε$ -constraint method but by achievement scalarizing functions. For a reference point $z \in R^{q}$ and weights $w ≻ 0$ , minimizing the Chebyshev-type functional

s_{z} (x) = i max w_{i} ((f_{0} (x))_{i} - z_{i}) + ρ i \sum w_{i} ((f_{0} (x))_{i} - z_{i}),

with a small augmentation $ρ > 0$ , has the property that its minimizers are properly efficient and, conversely, every properly efficient point is the minimizer for some reference $z$ — including the unsupported points a weighted sum cannot reach, because the level sets of the Chebyshev norm are boxes (cones congruent to $- K$ ) rather than halfspaces, so they support the frontier from inside its dents. The augmentation term excludes the merely weakly efficient minimizers the pure $max$ would admit. This is the basis of interactive reference-point methods, where a decision maker steers $z$ to navigate the frontier.

Vector optimization over general proper cones

Replacing the orthant by a general proper cone $K$ — the Lorentz cone, the positive-semidefinite cone $S_{+}^{q}$ , or a polyhedral order cone — gives vector optimization with respect to generalized inequalities, the setting of 44.05.01. The achievable set lives in a space ordered by $K$ , efficiency means minimality for $⪯_{K}$ , and scalarization weights run over $K^{*}$ ; for the self-dual cones the weights and the order live in the same cone. The semidefinite case orders matrix-valued objectives by the Löwner order $A ⪯_{S_{+}^{q}} B ⟺ B - A ⪰ 0$ , and the scalarization $⟨ Λ, F_{0} (x)⟩ = tr (Λ F_{0} (x))$ with $Λ ≻ 0$ recovers efficient matrix-objective designs, the engine behind experiment design and robust control synthesis. The entire scalarization correspondence transfers verbatim because its only inputs were the cone, its dual, and the supporting-hyperplane theorem.

Synthesis. The achievable set $A = O + K$ is exactly the object that generalises the scalar value set of 44.02.01 from the order of the real line to the order of a proper cone, and the central insight is that scalarization is the search for a supporting hyperplane to $A$ whose normal lies in $K^{*}$ . The foundational reason the weighted-sum method is incomplete is that hyperplanes support only the convex hull of the frontier, so dented, unsupported efficient points need the box-shaped support of an achievement function or the $ε$ -constraint slice — the precise multicriteria shadow of the duality gap. Putting these together, the interior $int K^{*}$ indexes the properly efficient core via Geoffrion's bounded-tradeoff condition, the boundary $\partial K^{*}$ indexes the degenerate weak and improper edges, and the recession structure of 44.01.01 governs whether the frontier is nonempty through Benson's stability. This is exactly the same separation engine of 02.11.02 that powered strong duality in 44.02.01, read now in value space: the weight $λ$ is dual to the tradeoff direction, at once the supporting normal, the marginal rate of substitution $- φ^{'}$ along the frontier, and the price assigned to one objective in units of another. The bridge is the cone order, the single structure through which efficiency, scalarization, sensitivity, and the conic programs of 44.05.01 are one theory, and it appears again in every regularized estimator and mean-variance portfolio that picks a frontier point by a choice of weights.

Full proof set Master

Proposition 1 (strict positivity of interior dual vectors). For a proper cone $K$ with dual cone $K^{*}$ , $λ \in int K^{*}$ if and only if $⟨ λ, d ⟩ > 0$ for all $d \in K ∖ {0}$ .

Proof. This is Exercise 6; the forward direction perturbs $λ$ inside $K^{*}$ to contradict $⟨ λ, d ⟩ = 0$ , and the reverse uses the positive minimum $m = min {⟨ λ, d ⟩ : d \in K, ∥ d ∥ = 1} > 0$ on the compact cross-section to fit a ball ${μ : ∥ μ - λ ∥ < m} \subseteq K^{*}$ around $λ$ . Pointedness and solidity of $K$ make the cross-section a nonempty compact set, so the minimum is attained and positive. $□$

Proposition 2 (sufficiency of interior-weight scalarization). If $λ \in int K^{*}$ and $x^{⋆}$ minimizes $⟨ λ, f_{0} (\cdot)⟩$ over $D$ , then $x^{⋆}$ is Pareto optimal — with no convexity hypothesis.

Proof. If a feasible $x$ had $f_{0} (x) ⪯_{K} f_{0} (x^{⋆})$ with $f_{0} (x) \neq = f_{0} (x^{⋆})$ , then $d := f_{0} (x^{⋆}) - f_{0} (x) \in K ∖ {0}$ , so $⟨ λ, d ⟩ > 0$ by Proposition 1, whence $⟨ λ, f_{0} (x)⟩ = ⟨ λ, f_{0} (x^{⋆})⟩ - ⟨ λ, d ⟩ < ⟨ λ, f_{0} (x^{⋆})⟩$ , contradicting minimality. $□$

Proposition 3 (necessity under convexity — every efficient point is supported). If $D$ is convex, $f_{0}$ is $K$ -convex, and $x^{⋆}$ is weakly Pareto optimal, there is $λ \in K^{*} ∖ {0}$ with $x^{⋆}$ minimizing $⟨ λ, f_{0} (\cdot)⟩$ over $D$ .

Proof. This is part (ii) of the Key theorem. The steps: (a) $A = O + K$ is convex by $K$ -convexity of $f_{0}$ on convex $D$ ; (b) weak efficiency gives $(a^{⋆} - int K) \cap A = \emptyset$ with $a^{⋆} = f_{0} (x^{⋆})$ , two disjoint convex sets one of which is open; (c) the finite-dimensional geometric Hahn-Banach separation of 02.11.02 yields nonzero $λ$ and $γ$ separating them; (d) the recession invariance $A + K = A$ forces $λ \in K^{*}$ and the boundary contact at $a^{⋆}$ forces $γ = ⟨ λ, a^{⋆} ⟩$ , giving $⟨ λ, f_{0} (x)⟩ \geq ⟨ λ, f_{0} (x^{⋆})⟩$ for all $x \in D$ . $□$

Proposition 4 (weighted-sum reaches exactly the supported frontier; convexity removes the gap). Let $P$ be the set of efficient values, $P_{ws}$ the set of values attained as minimizers of some $⟨ λ, f_{0} (\cdot)⟩$ with $λ \in int K^{*}$ . Then $P_{ws} \subseteq P$ always, and $P_{ws}$ is dense in $P$ when the problem is convex; the inclusion can be strict (a proper subset) when $O + K$ is nonconvex.

Proof. $P_{ws} \subseteq P$ is Proposition 2. For the convex case: by Proposition 3 every efficient value $a^{⋆}$ carries a supporting $λ \in K^{*} ∖ {0}$ ; if $λ \in int K^{*}$ then $a^{⋆} \in P_{ws}$ directly, and the boundary-weight efficient points are limits of interior-weight ones because $int K^{*}$ is dense in $K^{*}$ and the supported value depends continuously on the weight where the minimizer is stable, giving density. For strictness in the nonconvex case, Exercise 7 exhibits an efficient $(1, 1)$ that no interior weight supports (it lies strictly above every supporting line of $O$ ), so $(1, 1) \in P ∖ P_{ws}$ , and the inclusion is proper. The gap between $P$ and $P_{ws}$ is the multicriteria analogue of the duality gap of 44.02.01, closed precisely by convexity of the achievable set. $□$

Connections Master

The Lagrangian duality and supporting-hyperplane theory of 44.02.01 is the immediate parent: the scalarization weight $λ$ is the normal to a supporting hyperplane of the achievable set $A = O + K$ at an efficient value, exactly as the Lagrange multiplier was the supporting slope of the scalar value set, and the marginal-rate-of-substitution reading of $λ$ along the Pareto frontier is the multi-objective form of the sensitivity reading $λ_{i}^{⋆} = - \partial p^{⋆} / \partial u_{i}$ . The duality gap there and the unsupported-frontier gap here are the same convexity failure seen in two settings.
The convex-set and cone calculus of 44.01.01 supplies every structural input: the proper cone $K$ , its dual cone $K^{*}$ whose interior parametrizes the scalarizations, the convexity of $O + K$ under $K$ -convexity of $f_{0}$ , and the recession-cone conditions controlling existence of efficient points. Vector optimization is convex analysis run with the partial order of a cone in place of the real line's order.
The conic and semidefinite programming of 44.05.01 is the downstream specialization to general proper cones: ordering matrix objectives by the Löwner order $⪯_{S_{+}^{q}}$ and scalarizing by $tr (Λ \cdot)$ with $Λ ≻ 0$ is vector optimization over the PSD cone, and the self-dual cones (orthant, Lorentz, PSD) are exactly the standard ordering cones whose duals coincide with themselves, so the weight and the order inhabit the same cone.
The geometric Hahn-Banach separation theorem of 02.11.02 is the engine of the necessity direction: separating the open convex set $a^{⋆} - int K$ from the convex achievable set $A$ is what produces the supporting weight, the same separation principle that underlies strong duality and the supporting-hyperplane structure of every convex program in the section.

Historical & philosophical context Master

The optimization notion of efficiency is named for Vilfredo Pareto, whose Manuale di economia politica (1906) defined an allocation as optimal when no individual can be made better off without making another worse off — a welfare-economics criterion about distributions among agents. The mathematical-programming usage is a deliberate transplant of the form of that criterion, not its content: here the several coordinates are competing objectives of one decision maker, not the utilities of several agents, and "no one made worse off" becomes "no objective improved without degrading another." Conflating the two is a recurring error; the optimization Pareto frontier is a menu of tradeoffs for a single optimizer, while the economics Pareto set is a statement about social states.

The vector-maximization theory was placed on rigorous footing by Tjalling Koopmans' 1951 analysis of efficient production and by Harold Kuhn and Albert Tucker's same-year treatment of vector maxima, which gave the first scalarization and constraint-qualification results. Arthur Geoffrion's 1968 paper ^{[Geoffrion 1968]} (Journal of Mathematical Analysis and Applications 22, 618-630) introduced proper efficiency to exclude the unbounded-tradeoff pathologies and proved the exact correspondence between properly efficient points and strictly positive weighted-sum minimizers. In parallel, Harry Markowitz's 1952 Portfolio Selection ^{[Markowitz 1952]} (Journal of Finance 7, 77-91) gave the canonical applied instance, the mean-variance efficient frontier, founding modern portfolio theory and supplying the risk-return bicriterion that remains the standard illustration of the subject.

Bibliography Master

@book{boyd2004convex,
  author    = {Boyd, Stephen and Vandenberghe, Lieven},
  title     = {Convex Optimization},
  publisher = {Cambridge University Press},
  year      = {2004}
}

@book{ehrgott2005multicriteria,
  author    = {Ehrgott, Matthias},
  title     = {Multicriteria Optimization},
  edition   = {2nd},
  publisher = {Springer},
  year      = {2005}
}

@book{miettinen1999nonlinear,
  author    = {Miettinen, Kaisa},
  title     = {Nonlinear Multiobjective Optimization},
  series    = {International Series in Operations Research and Management Science},
  publisher = {Kluwer Academic Publishers},
  year      = {1999}
}

@article{geoffrion1968proper,
  author  = {Geoffrion, Arthur M.},
  title   = {Proper Efficiency and the Theory of Vector Maximization},
  journal = {Journal of Mathematical Analysis and Applications},
  volume  = {22},
  number  = {3},
  pages   = {618--630},
  year    = {1968}
}

@article{markowitz1952portfolio,
  author  = {Markowitz, Harry},
  title   = {Portfolio Selection},
  journal = {The Journal of Finance},
  volume  = {7},
  number  = {1},
  pages   = {77--91},
  year    = {1952}
}

@inproceedings{kuhn1951nonlinear,
  author    = {Kuhn, Harold W. and Tucker, Albert W.},
  title     = {Nonlinear Programming},
  booktitle = {Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability},
  pages     = {481--492},
  publisher = {University of California Press},
  year      = {1951}
}

Prerequisites

44.01.01
44.02.01

Tier anchors

beginner: Boyd & Vandenberghe 2004 Convex Optimization (Cambridge) §4.7 — the optimal-tradeoff/Pareto-frontier picture
intermediate: Boyd & Vandenberghe 2004 Convex Optimization (Cambridge) §4.7; Ehrgott 2005 Multicriteria Optimization (Springer) Ch. 2-4
master: Ehrgott 2005 Multicriteria Optimization (Springer) Ch. 2-5; Miettinen 1999 Nonlinear Multiobjective Optimization (Kluwer) Ch. 2-3; Boyd & Vandenberghe 2004 Convex Optimization (Cambridge) §4.7

References

Boyd, S. & Vandenberghe, L. — Convex Optimization (Cambridge University Press, 2004) · §4.7 multicriterion optimization; §4.7.2 Pareto optimal points and values; §4.7.4 scalarization; §2.4.1 proper cones and generalized inequalities; §4.7.5 examples (regularized least squares, risk-return)
Ehrgott, M. — Multicriteria Optimization (Springer, 2nd ed., 2005) · Ch. 2 efficiency and nondominance; Ch. 3 the weighted-sum method and supported solutions; Ch. 4 scalarization (epsilon-constraint, Benson, achievement functions)
Miettinen, K. — Nonlinear Multiobjective Optimization (Kluwer, 1999) · Ch. 2 Pareto optimality and the ordering cone; Ch. 3 scalarization methods and their Pareto-optimality guarantees
Markowitz, H. — Portfolio Selection · Journal of Finance 7 (1952), 77-91
Geoffrion, A. M. — Proper Efficiency and the Theory of Vector Maximization · Journal of Mathematical Analysis and Applications 22 (1968), 618-630

Estimated time

beginner: 18m
intermediate: 45m
master: 80m