Ref:

• “Linear Algebra” by Lax.

ROUGH NOTES (!)
Updated: 17/3/26

We will study

\[{ \boxed{\textbf{Convexity}} }\] \[{ }\]

In theorem statements, often the vector spaces considered are finite dimensional.

\[{ }\] \[{ \underline{\textbf{Convex Sets}} }\]

Def [Line Segment]
Let ${ X }$ be a (real) vector space. Let ${ x, y \in X . }$
The line segment with endpoints ${ x }$ and ${ y }$ is

\[{ [x, y] = \lbrace x + a ( y - x ) : 0 \leq a \leq 1 \rbrace . }\]

Def [Convex Set]
Let ${ X }$ be a (real) vector space. Let ${ K \subseteq X . }$
We say ${ K }$ is convex if whenever ${ x, y \in K }$ we have ${ [x, y] \subseteq K . }$

We can freely take line segments in a convex set. Note that intuitively convex sets must be “round”.

Eg [Convex Sets]
Let ${ X }$ be a vector space. Then ${ X, }$ ${ \emptyset , }$ ${ \lbrace x \rbrace }$ for ${ x \in X , }$ any line segment are all convex sets.

Let ${ X }$ be a vector space. Let ${ \ell : X \to \mathbb{R} }$ be a linear function. Then the sets

\[{ {\begin{aligned} &\, \lbrace \ell(x) = c \rbrace \quad (\text{a hyperplane}), \\ &\, \lbrace \ell(x) < c \rbrace \quad (\text{an open half-space}), \\ &\, \lbrace \ell(x) \leq c \rbrace \quad (\text{a closed half-space}) \end{aligned}} }\]

are all convex sets.

Let ${ X }$ be the space of all polynomials (with real coefficients). Let ${ K }$ be the subset of all polynomials that are positive at every point of ${ (0,1) . }$ Note that ${ K }$ is convex.

Suppose polynomials ${ p(t) > 0 }$ and ${ q(t) > 0 }$ for all ${ t \in (0, 1) . }$ Let ${ \alpha \in [0, 1] . }$ Note that ${ (\alpha p + (1 - \alpha) q) (t) > 0 }$ for all ${ t \in (0, 1) . }$

Let ${ X }$ be the space of real symmetric matrices. Let ${ K }$ be the subset of positive matrices. Note that ${ K }$ is convex.

Suppose symmetric matrices ${ A , B > 0 . }$ Let ${ \alpha \in [0, 1] . }$ Note that ${ (\alpha A + (1 - \alpha) B) > 0 . }$

Obs [Intersection of Convex Sets]

The intersection of any collection of convex sets is convex.

Pf: Let ${ X }$ be a vector space. Let ${ \lbrace C _{\alpha} : \alpha \in A \rbrace }$ be a collection of convex sets.

Let ${ x, y \in \cap C _{\alpha} . }$ Hence ${ x, y \in C _{\alpha} }$ for all ${ \alpha \in A . }$ Hence ${ [x, y] \subseteq C _{\alpha} }$ for all ${ \alpha \in A . }$ Hence ${ [x, y] \subseteq \cap C _{\alpha} . }$

Hence ${ \cap C _{\alpha} }$ is convex. ${ \blacksquare }$

Obs [Sum of Convex Sets]

The sum of two convex sets is convex.

Pf: Let ${ X }$ be a vector space. Let ${ H, K }$ be convex sets. Is ${ H + K }$ convex?

Let ${ h _1 + k _1 , h _2 + k _2 \in H + K . }$ Let ${ \alpha \in [0, 1] . }$ Note that ${ \alpha (h _1 + k _1) + (1 - \alpha) (h _2 + k _2) }$ ${ = (\alpha h _1 + (1 - \alpha) h _2) + (\alpha k _1 + (1 - \alpha) k _2) }$ is also in ${ H + K . }$

Hence ${ H + K }$ is convex. ${ \blacksquare }$

Def [(Algebraic) Interior Point]

Let ${ X }$ be a vector space. Let ${ S \subseteq X . }$

A point ${ x }$ is called an interior point of ${ S }$ if for every ${ y \in X , }$ ${x + yt \in S }$ for all sufficiently small positive ${ t . }$

Let ${ x \in S }$ be an interior point. Intuitively, we can perturb ${ x }$ a little bit along any line, and still stay within ${ S . }$

Def [(Algebraic) Open Convex Set]

Let ${ X }$ be a vector space. Let ${ K }$ be a convex set.

A convex set ${ K }$ is open if every point in it is an interior point.

Eg [Open Convex Set]

Let ${ X }$ be a vector space. Consider a half-space ${ \lbrace \ell(x) < c \rbrace . }$ Since ${ \ell }$ is continuous (w.r.t. the Euclidean norm on ${ X }$ in any basis), the half space ${ \ell ^{-1} ((- \infty, c)) }$ is an open convex set.

Obs [Open Convex + Convex = Open Convex]

Let ${ A }$ be an open convex set, and ${ B }$ be a convex set. Then ${ A + B }$ is an open convex set.

Pf: We saw ${ A + B }$ is convex. It suffices to show ${ A + B }$ is open.

Consider any point ${ a + b }$ in ${ A + B . }$ Let ${ y \in X . }$ Note that ${ b + ty \in B }$ for all sufficiently small positive ${ t . }$ Hence ${ a + (b + ty) \in A + B }$ for all sufficiently small positive ${ t . }$ Hence ${ (a + b) + ty \in A + B }$ for all sufficiently small positive ${ t . }$

Hence ${ A + B }$ is open convex. ${ \blacksquare }$

\[{ \underline{\textbf{Gauge Function}} }\]

Question. [Open convex sets as unit balls?]

Let ${ X }$ be a vector space. Let ${ K }$ be an open convex set containing ${ 0 . }$

Can we construct a “norm like function” ${ p _K }$ such that ${ K }$ is like the open unit ball, namely

\[{ K = \lbrace x : p _K (x) < 1 \rbrace \, \, ? }\]

Answer. It turns out yes!

Approach.

Intuitively we want ${ p _K }$ to be defined as in the picture below:

This suggests defining

\[{ \large \boxed{p _K (x) := \inf \lbrace r > 0 : x \in r K \rbrace } }\]

It turns out such a ${ p _K }$ is “positive homogeneous, subadditive” and satisfies

\[{ K = \lbrace x : p _K (x) < 1 \rbrace }\]

as needed. (We will prove it below). ${ \blacksquare }$

Def [Gauge Function]

Let ${ X }$ be a vector space. Let ${ K }$ be an open convex set containing ${ 0 . }$ Consider

\[{ p _K (x) := \inf \lbrace r > 0 : x \in rK \rbrace . }\]

We call ${ p _K }$ the gauge function of ${ K . }$

Eg [${ p _K (x) = 0 }$ is not equivalent to ${ x = 0 }$]

Let ${ X = \mathbb{R} ^2 . }$ Let ${ K = \lbrace (u, v) : u < 1, v < 1 \rbrace . }$

Note that the gauge function of ${ K }$ is

\[{ p _K (x) = {\begin{cases} & 0 \quad \text{ if } u \leq 0, v \leq 0, \\ & v \quad \text{ if } u \leq 0, v > 0 , \\ & u \quad \text{ if } u > 0, v \leq 0, \\ & \max(u, v) \quad \text{ if } u > 0, v > 0 . \end{cases}} }\]

Thm [Gauge function is norm like]

Let ${ X }$ be a vector space. Let ${ K }$ be an open convex set containing ${ 0 . }$

a) ${ p _K }$ is a well-defined function.

b) ${ p _K }$ is positive homogeneous:

\[{ p _K (ax) = a p _K (x) \quad \text{ for } a > 0 . }\]

c) ${ p _K }$ is subadditive:

\[{ p _K (x + y) \leq p _K (x) + p _K (y) . }\]

d) ${ K }$ is the unit ball wrt ${ p _K }$:

\[{ K = \lbrace x : p _K (x) < 1 \rbrace . }\]

Pf:

a) Let ${ x \in X . }$ We are to show there is an ${ r > 0 }$ with ${ x / r \in K . }$
Note that ${ 0 }$ is an interior point of ${ K . }$ Hence ${ 0 + xt \in K }$ for all sufficiently small positive ${ t , }$ as needed. ${ \blacksquare }$

b) Let ${ x \in K , }$ and ${ a > 0 . }$

Note that

\[{ {\begin{aligned} &\, p _K (ax) \\ = &\, \inf \left\lbrace r > 0 : \frac{ax}{r} \in K \right \rbrace \\ = &\, \inf \left \lbrace r : r > 0, \frac{x}{r/a} \in K \right \rbrace \\ = &\, \inf \left \lbrace a \lambda : \lambda > 0, \frac{x}{\lambda} \in K \right \rbrace \\ = &\, a p _K (x) \end{aligned}} }\]

as needed. ${ \blacksquare }$

c) Let ${ \varepsilon > 0 . }$ Let ${ x , y \in X . }$

Note that

\[{ \frac{x}{p _K (x) + \varepsilon} \in K , \quad \frac{y}{p _K (y) + \varepsilon} \in K . }\]

Note that

\[{ {\begin{aligned} &\, \frac{x + y}{p _K (x) + \varepsilon + p _K (y) + \varepsilon} \\ = &\, \frac{p _K (x) + \varepsilon}{p _K (x) + \varepsilon + p _K (y) + \varepsilon} \left( \frac{x}{p _K (x) + \varepsilon} \right) + \frac{p _K (y) + \varepsilon}{p _K (x) + \varepsilon + p _K (y) + \varepsilon} \left( \frac{y}{p _K (y) + \varepsilon} \right) \end{aligned}} }\]

is a convex combination of ${ \frac{x}{p _K (x) + \varepsilon} }$ and ${ \frac{y}{p _K (y) + \varepsilon} . }$

Hence

\[{ \frac{x + y}{p _K (x) + \varepsilon + p _K (y) + \varepsilon} \in K . }\]

Hence

\[{ p _K (x + y) \leq p _K (x) + \varepsilon + p _K (y) + \varepsilon . }\]

Since ${ \varepsilon > 0 }$ is arbitrary, we have

\[{ p _K (x + y) \leq p _K (x) + p _K (y) }\]

as needed. ${ \blacksquare }$

d) Suppose ${ p _K (x) < 1 . }$ We are to show ${ x \in K . }$
Note that there is an ${ (0 <) \, r < 1 }$ such that ${ x / r \in K . }$ Note that ${ x }$ ${ = r (x / r ) + (1-r) 0 }$ is a convex combination of ${ x / r \in K }$ and ${ 0 \in K . }$ Hence ${ x \in K , }$ as needed.

Now suppose ${ x \in K . }$ We are to show ${ p _K (x) < 1 . }$
Note that ${ x }$ is an interior point of ${ K . }$ Hence ${ x + \varepsilon x \in K }$ for all sufficiently small positive ${ \varepsilon . }$ Hence ${ x / ( 1 / (1 + \varepsilon) ) \in K }$ for all sufficiently small positive ${ \varepsilon . }$ Hence

\[{ p _K (x) \leq \frac{1}{1 + \varepsilon} }\]

for all sufficiently small positive ${ \varepsilon . }$
Hence

\[{ p _K (x) < 1 }\]

as needed. ${ \blacksquare }$