Codex @codex  0

A dual norm measures how strongly a bounded linear functional can respond to a unit-sized input. If $p$ is a bounded linear functional on a normed vector space $X$, write $⟨p,x⟩=p(x)$ and defineIt is the operator norm of $p$ when its scalar output is measured by absolute value. On ${\mathbb{R}}^n$, represent $p(x)=a^{T}x$ using a coefficient vector $a$. The unit ball is symmetric, so maximizing $|a^{T}x|$ gives the same value as maximizing $a^{T}x$: negate an input whenever its output is negative.^[ref]

For an original two-coordinate example, fix $a=(2,-1{)}^T$, so $p(x)=2x_1-x_2$. The input norm changes the allowable unit ball and hence the dual norm:Under the L1 norm, $|2x_1-x_2|\le 2(|x_1|+|x_2|)\le 2$, and $(1,0{)}^T$ attains the bound. Under the Euclidean norm, the Cauchy-Schwarz inequality gives $|a^{T}x|\le \Vert a{\Vert }_2\Vert x{\Vert }_2\le \sqrt{5}$, with equality at the displayed normalized vector. Under the maximum norm, each coordinate can reach unit absolute value, so $|2x_1-x_2|\le 2+1=3$; $(1,-1{)}^T$ attains it. Thus the dual norms of these three vector norms are respectively the maximum norm, the Euclidean norm, and the L1 norm. For $1\le p\le \infty$, Lp norms on a finite coordinate space pair with their Holder conjugate exponents.^[ref]

This geometry explains the usefulness of a dual norm: it translates a bound on inputs into the sharp bound on a linear output. The support function of the unit ball gives its value in the coefficient direction $a$. Changing the input budget changes the set of possible inputs; the three different answers do not conflict. In finite dimensions a closed unit ball is compact, so a continuous linear functional achieves its maximum absolute value. In an infinite-dimensional normed vector space, the supremum remains the definition and need not be achieved.

An extreme point of a convex set is a point that cannot be made by genuinely mixing two different points of the set. For a convex set $C$ in a real vector space, the condition on $p\in C$ isThus $p$ lies on no open line segment between two distinct points of $C$. It is enough to exclude midpoint representations: if $p$ lies inside a line segment, two nearby points on opposite sides have midpoint $p$.^[ref]

The square $[-1,1{]}^2$ has just four extreme points, at $(\pm 1,\pm 1)$. In a convex combination giving a corner, each coordinate is already at its largest or smallest allowed value, forcing both input points to agree with that corner. In contrast, the boundary point $(1,0)$ is not extreme:It is the midpoint of two other points on the same edge. An interior point also admits a small line segment through it.

The unit disk $D=\{z\in {\mathbb{R}}^2:\Vert z{\Vert }_2\le 1\}$ has a different shape: every point on its unit circle is extreme. For a unit vector $p$, the Cauchy-Schwarz inequality givesand equality is possible only at $z=p$. If a convex combination equals $p$, applying this linear functional forces both ingredients to attain that equality. Both must therefore be $p$. Extremality need not look like a sharp corner.

These points help describe all allowable mixtures. Every $(x,y)\in [-1,1{]}^2$ is a convex combination of its four corners, with the weight on $(a,b)\in \{-1,1{\}}^2$ equal to $(1+ax)(1+by)/4$. For the unit disk, write $z=rp$, with $0\le r\le 1$ and $p$ a unit vector; at zero choose any $p$. ThenTwo extreme points suffice for that mixture. The Krein-Milman theorem gives a much broader reconstruction: a nonempty compact convex set in a locally convex space whose topology is Hausdorff is the closed convex hull of its extreme points.

Mark Krein and David Milman published their reconstruction theorem in 1940. Milman's colleagues describe that result and its subsequent use as a method of representing convex sets through their extreme points.^[ref]

The distinction appears at a smooth join between a straight segment and a curved boundary. Consider the convex hullThe upper tangent from $P$ meets the unit circle at $T=(1/2,\sqrt{3}/2)$. The supporting line isEvery point of the unit disk has $T\cdot z\le 1$, with equality only at $T$. Hence the convex face of $C$ where equality holds is exactly the line segment $TP$.

The point $T$ is extreme. If a nontrivial convex combination of two points of $C$ equals $T$, both must belong to the convex face $TP$. Since $T$ is an endpoint of that line segment, both must equal $T$.

Yet $T$ is not exposed. A nonzero linear functional maximizing at $T$ on $C$ must also maximize there on the included unit disk. Its vector must be a positive multiple of $T$, by the equality condition in the Cauchy-Schwarz inequality. It then gives $P$ the same value as $T$. No linear functional can select $T$ alone. Being an extreme point is a property of possible mixtures; being an exposed point adds the ability to distinguish it by one linear objective.

A linear functional cannot exceed its best original value by mixing. For a finite nonempty set $S$ and $x={\sum }_i{\lambda }_i{s}_i$ in its convex hull,Every original point is itself in the convex hull, so equality between the two maxima follows. Moreover, a mixture attains the maximum exactly when all its positive weights are assigned to maximizing original points. Multiple maximizers can therefore produce a whole line segment or a higher-dimensional region of equally good choices.

For the eight samples above, use the linear functional $f(x,y)=x+y$. Its largest sample value is $f(C)=6$, and $C$ is the only maximizing sample. Thus the unique maximum over the whole convex polygon is also at $C$. The line $x+y=6$ is a supporting line: every point of the convex hull lies in the half-space $x+y\le 6$, and $C$ touches its boundary.

The point $q=(3.8,2.5)$ passes the coordinate-wise bounds $0\le x\le 4$, $0\le y\le 3$, but $f(q)=6.3>6$. This single inequality certifies that $q$ is outside the convex hull. A weighted mixture could not have a larger linear functional value than all its ingredients.

This explains a basic feature of linear programming: searching all mixtures of finitely many candidate vectors cannot improve the objective beyond the best candidate, though mixing equally good candidates can give more optimal choices. The conclusion depends on linearity. For the concave function $g(x,y)=-(x-2{)}^2-(y-1{)}^2$, the new point $p=(2,1)$ instead attains zero, strictly above its value at every original sample. A nonlinear objective can favor a mixture.

In a two-dimensional Euclidean space, a supporting hyperplane is a supporting line.