../

2026/09/10 Convex Optimization Scribe

$\newcommand{\R}{\mathbb{R}}$

Hyperspace separation Theorem

There is a small error from last class

if $A, B \subseteq \R^n$ are two relative interior disjoint sets then $\exists V \in \R^n, v\ne0, c\in\R$ such that

$$\langle v, x \rangle \le c \le \langle v, y \rangle$$

$$\mathbf{relint} = {c \in C | B(x, r) \cup \mathbf{aff}~ C \subset C\text{ some }r > 0}$$

Consider the above example, $B$ is just a line. It has no unit balls therefore no interior $\mathbf{int}~ A \cap \phi = \phi$. So their interiors are disjoint. But we cannot separate them.

To fix this we introduce relative interior where we calculate the interior relative to the the convex hull of the set.

Convex Function

$f: C \subset \R^n \rightarrow \R$ is convex if

  1. $C$ is a convex set
  2. $f(\theta x + (1-\theta y)) \le \theta f(x) + (1 - \theta)f(y), \forall x, y \in \mathbf{dom}~f, \forall \theta \in [0, 1]$

Think of $\theta$ as parameter to move along the chord between $x$ and $y$. This chord has to be above the function at all times

Concave

A function $f$ is concave iff $-f$ is convex according to the definition from above.

Why should $\mathbf{dom}~ f$ be convex?

That condition seems extraneous right? NO. Without that functions that are convex by nature won’t be convex because of the domain

Consider the function $f(x) = \frac{1}{x^2}$. It is convex over $(0, \infty)$ and $(-\infty, 0)$ but not the union of both. Because the union is not a convex set.

Notice that the definition of concave also requires the domain to be a convex set. I don’t think there are concave sets.

Both convex and concave

  • As the inequalities are not strict, it is possible for a function to be both convex and concave
  • It implies that the function is affine and in fact this is a double-implication
  • If a function is affine then it is both concave and convex
  • If a function is both concave and convex then it is affine