Today’s Lesson

1. Convex Optimization
   1. Convex Sets
   2. Convex Functions
2. Some Examples

Descent Direction (Review)

• $p^k$ is required to be a descent direction such that $(p^k)^\intercal \nabla f(x^k) < 0$
  • This condition guarantees that $f$ can be reduced along the direction $p^k$
• Generally the search direction has the form: $$p^k = (-B^k)^{-1} \nabla f(x^k)$$
  • $B^k\in\mathbb{R}^{n\times n}$ is symmetric and non-singular matrix
• With $B^k$ being positive definite, we have $$(p^k)^\intercal \nabla f(x^k) = -\nabla f(x^k)^\intercal (B^k)^{-1} \nabla f(x^k) < 0$$

Search Directions (Review)

• Steepest-descent (最速降下)
  • $p^k = -\nabla f(x^k)$
  • Direction of most rapid decrease
• Newton direction (ニュートン方向)
  • $p^k = -\nabla^2 f(x^k)^{-1} \nabla f(x^k)$
• Quasi-Newton (准ニュートン法)
  • $p^k = -(B^k)^{-1} \nabla f(x^k)$
  • $B^k$ approximates the hessian $\nabla^2 f(x^k)$
  • Symmetric Rank-One (SR1)
  • BFGS (Broyden-Fletcher-Goldfarb-Shannon)
• Non-linear Conjugate Gradient Methods (共役勾配法)
  • $p^k = - \nabla f(x^k) + \beta^k p^{k-1}$

Line Search Rate of Convengence (Review)

Finding $\alpha$ (Review)

• Given $p^k$, we want to find $\alpha^k$ for each iteration $k=1,\ldots$ $$a^k = \argmin_{\alpha>0} f(x^k+\alpha p^k)$$
  • Exact optimization is too costly
  • Commonly approximated
• Approximating $\alpha^k$ such that $$f(x^k + \alpha^k p^k) < f(x^k)$$
  • Try to improve the value of $f$ each iteration

Wolfe Conditions (Review)

1. Find a sufficient decrease in the objective function, as measured by $$f(x^k+\alpha p^k) \leq f(x^k) + c_1 \alpha \nabla (f^k)^\intercal p^k$$
   • $c_1 \in (0,1)$: constant (in practice $c_1 \approx 10^{-4}$)
   • Known as Armijo condition
2. Ensure we make “reasonable progress” $$\nabla f(x^k + \alpha^k p^k)^\intercal p^k \geq c_2 \nabla f(x^k)^\intercal p^k$$
   • $c_2 \in (c_1,1)$: constant (in practice $c_2 \approx 0.9$ for Newton/quasi-Newton methods)
   • Known as curvature condition

Convex Program (Review)

An optimization problem is called a convex optimization problem (凸最適化問題) if the objective and constraint functions $f_0,\ldots,f_m$ satisfy

$$f_i(\alpha x + \beta y) \leq \alpha f_i(x) + \beta f_i(y), \\ \forall x,y\in\mathbb{R}^n \quad\text{and} \\ \forall \alpha, \beta \in \mathbb{R} \;\; \text{s.t}\;\; \alpha+\beta=1,\,\alpha\geq 0,\,\beta\geq 0$$

Affine Sets (1)

• A set $C \subseteq \mathbb{R}^n$ is affine (アフィン) if the line through any two distinct points in $C$ lies in $C$: $$\theta\,x_1 + (1-\theta)\,x_2 \in C, \quad \forall x_1, x_2 \in C,\; \text{and} \; \theta \in \mathbb{R}$$
• If $C$ is an affine set and $x_0 \in C$, then the set $$V = C - x_0 = \{x - x_0 \;|\; x\in C\}$$ is a subspace
  • A subset is closed under sums and scalar multiplication $$\alpha\,v_1 + \beta\,v_2 + x_0 = \\ \alpha\,(v_1 + x_0) + \beta\,(v_2 + x_0) + (1-\alpha-\beta)\,x_0 \in C$$

Affine Sets (2)

• The dimension (次元) of an affine set $C$ is the dimension of the subspace $V=C-x_0$, where $x_0$ is any element of $C$.
• The set of all affine combinations of points in some set $C\subseteq\mathbb{R}^n$ is called the affine hull (アフィン包) of $C$, and denoted $\aff{C}$:

$$\begin{align} \aff{C} = \{&\theta_1 x_1+ \cdots + \theta_k x_k \;| \\ &\; x-1, \ldots, x_k \in C,\;\theta_1+\cdots+\theta_k=1\}\; . \end{align}$$

• Note: the affine hull is the smallest affine set that contains $C$, i.e., if $S$ is any affine set with $C \subseteq S$, then $\aff{C} \subseteq S$.
  • The affine dimension (アフィン次元) of a set $C$ is the dimension of its affine hull.

Affine Sets (3)

• If the affine dimension of a set $C \subseteq \mathbb{R}^n$ is less than $n$, then the affine set $\aff{C}\neq \mathbb{R}^n$.
• We can define the relative interior of the set $C$, denoted $\relint{C}$, as its interior relative to $\aff{C}$: $$\relint{\mathcal{D}} = \{\, x\in\mathcal{D} \;|\; B(x,r) \cap \aff{\mathcal{D}} \subseteq \mathcal{D} \;\text{for some}\; r>0 \,\}$$ where $$B(x,r) = \{\, y \;|\; \|x-y\| \leq r \,\}$$

Convex Sets

• A set $C$ is convex (凸) if the line segment between any two points in $C$ lies in $C$, i.e., if $$\theta\,x_1 + (1-\theta)\,x_2 \in C,\quad \forall x_1,x_2 \in C \;\text{and}\; 0 \leq \theta \leq 1$$
• The convex hull (凸包) of a set $C$ is the set of all convex combinations of points in $C$:

$$\begin{align} \conv{C} = \{&\theta_1x_1 + \cdots + \theta_k x_k \;|\;\\ & x_i \in C,\; \theta_i \geq 0,\; i=1,\ldots,k,\; \\ & \theta_1+\cdots+\theta_k=1\}\;. \end{align}$$

• The convex hull $\conv{C}$ is the smallest convex set that contains $C$.

Cones

• A set $C$ is called a cone (錐すい) if $$\theta\,x\in C, \forall x \in C \quad\text{and}\quad \theta \geq 0$$
• A set $C$ is called a convex cone (凸錐) if $$\theta_1\,x_1 + \theta_2\,x_2 \in C, \forall x_1, x_2 \in C \quad\text{and}\quad \theta_1, \theta_2 \geq 0$$
• The conic hull (錐包) of a set $C$ is the set of all conic combinations of points in $C$, i.e., $$\{ \theta\,x_1+\cdots+\theta_k\,x_k \;|\; x_i \in C,\; \theta_i\geq0,\; i=1,\ldots,k \}$$

Hyperplane

• A hyperplane（超平面） is a set of the form $$\{\;x \;|\; a^\intercal x = b\;\}$$ where $\alpha \in \mathbb{R}^n$, $a \neq 0$, and $b \in \mathbb{R}$
  • It is the solution set of a non-trivial linear equation among the component of $x$ (and thus an affine set)
  • Can be interpreted as a hyperplane with normal vector $\alpha$ and offset from origin $b$
• A hyperplane divides $\mathbb{R}^n$ into two halfspaces（半空間） which have the form $$\{\;x \;|\; a^\intercal x \leq b\;\}$$
  • Halfspaces are convex, but not affine

Euclidean Ball

• A (Euclidean) ball（球体） in $\mathbb{R}^n$ has the form

$$\begin{align} B(x_c, r) &= \{\; x \;|\; \|x-x_c\|_2 \leq r\;\} \\ &= \{\; x \;|\; (x-x_c)^\intercal (x-x_c) \leq r^2 \;\} \end{align}$$ where $r>0$

• Vector $x_c$ is the center of the ball
• Scalar $r$ is the radius

Polyhedra

• A polyhedron（多面体） is defined as the solution set of a finite number of linear equalities and inequalities: $$\begin{align} \mathcal{P} = \{\;x \;|\; & a_j^\intercal x - b_j \leq 0,\; j=1,\ldots,m, \\ & c_j^\intercal x-d_j=0,\; j=1,\ldots,p\;\} \end{align}$$
  • Formed by the intersection of halfspaces
  • Halfspaces are convex, intersection conserves convexity

Operations that Preserve Convexity

• Intersection. If $S_1$ and $S_2$ are convex, then $S_1 \cap S_2$ is convex.
• Affine functions $f(x) = Ax+b$ where $A\in\mathbb{R}^{m\times n}$ and $b\in\mathbb{R}^m$.
  • Suppose $S\subseteq \mathbb{R}^n$ is convex and $f \colon \mathbb{R}^n \to \mathbb{R}^m$ is an affine function. Then the image of $S$ under $f$, $$f(S) = \{ f(x) \;|\; x\in S \}$$ is convex.
• Perspective function $P\colon \mathbb{R}^{n+1} \to \mathbb{R}^n$, with domain $\dom{P}=\mathbb{R}^n \times \mathbb{R}_{++}$ ($\mathbb{R}_{++}=\{x\in\mathbb{R} \;|\; x>0\}$). If $C\subseteq \dom{P}$ is convex, then its image $$P(C)= \{P(x) \;|\; x\in C \}$$ is convex.

Extended-value Extensions

• It is often convenient to extend a convex function to all of $\mathbb{R}^n$ by defining the value to be $\infty$ outside of its domain. If $f$ is convex, we define its extended-value extension $f\colon \mathbb{R}^n \rightarrow \mathbb{R}\cup\{\infty\}$ by $$\tilde{f}= \left\{\begin{array}{lr} f(x) & x\in\dom{f} \\ \infty & x\notin\dom{f} \\ \end{array}\right.$$
• This allows us to manipulate functions without having to worry about the domains
• We will always assume we are using the extended functions when applicable

First-Order Conditions

• Suppose $f$ is differentiable. Then $f$ is convex if and only if $\dom{f}$ is convex and $$f(y) \geq f(x) + \nabla f(x)^\intercal (y-x)$$ holds for all $x, y\in\dom{f}$.

Second-Order Conditions

• Assuming $f$ is twice differentiable, then $f$ is convex if and only if $\dom{f}$ is convex and its Hessian is positive semi-definite: for all $x\in\dom{f}$, $$\nabla^2f(x) \succeq 0$$
  • $X\succeq Y$ denotes matrix inequality between symmetric matrices $X$ and $Y$
  • For a function on $\mathbb{R}$, this reduces to $f''(x)\geq 0$ (and $\dom{f}$ being convex)

Simple Example: Max Function

• Max function. $f(x) = \max\{x_1,\ldots,x_n\}$ satisfies, for $0 \leq \theta \leq 1$ , $$\begin{align} f(\theta\,x + (1-\theta)\,y) &= \max_i (\theta\,x_i + (1-\theta)\,y_i) \\ &\leq \max_i x_i + (1-\theta)\max_i y_i \\ &= \theta f(x) + (1-\theta)f(y) \end{align}$$

Operations that Preserve Convexity

• Non-negative weighted sum. $f = w_1 f_1 + \cdots + w_m f_m$ is convex when $w_i > 0$ and $f_i$ are convex.
• Composition with an affine mapping. Suppose $f \colon \mathbb{R}^n \rightarrow \mathbb{R}$, $\in\mathbb{R}^{n\times m}$, and $b\in\mathbb{R}^n$. Define $g \colon \mathbb{R}^m \rightarrow \mathbb{R}$ by $$g(x) = f(Ax+b)$$ with $\dom{g} = \{\,x \;|\; Ax+b\in\dom{f}\,\}$. Then if $f$ is convex, so is $g$.
• Pointwise maximum and supremum. If $f_1$ and $f_2$ are convex functions, then their *pointwise maximum $f$, defined by $$f(x) = \max\{\,f_1(x),\,f_2(x)\,\}$$ is also convex.

Example: Binary Hinge loss

• The binary hinge loss（ヒンジ損失） is defined as: $$L(y) = \max( 0,\;1-t\; y )$$ where
  • $y$: is the output of a model (e.g., $y = w^\intercal x + b$)
  • $t$: is either +1 or -1 depending on the true class of the example
• For a given dataset, we can write the training loss of linear SVM with $$\sum_{i=0}^N \max(0,\;1-t_i\;w^\intercal x)$$
  • Is this convex?

Optimal and Locally Optimal Points

• The optimal value $p^\star$ is defined as $$\begin{align} p^\star = \inf \{\, f_0(x) \;|\; &f_i(x) \leq 0,\,i=1,\ldots,m\, \\ &h_i(x)=0,\,i=1,\ldots,p\} \end{align}$$
  • If $p^\star$ is infeasible it will have the extended value $+\infty$
  • If $p^\star=-\infty$, we say it is unbounded below
• We say $x^\star$ is an optimal point or solution if it is feasible and $f_0(x^\star)=p^\star$. $$\begin{align} X_{opt} = \{\, x \;|\; &f_i(x) \leq 0, i=1,\ldots,m, \\ &h_i(x)=0, i=1,\ldots,p,\; f_0(x)=p^\star \,\} \end{align}$$

Feasibility Problem

• Sometimes it is important to know if the problem is feasible
• This can be formulated by the following optimization problem: $$\begin{align} \text{find} \quad & x \\ \text{subject to} \quad & f_i(x) \leq 0, \quad i=1,\ldots,m \\ & h_i(x) = 0, \quad i=1,\ldots,p \end{align}$$
  • If a solution $x^\star \neq \infty$ is found, we say that the problem is feasible

Example: Segmentation

KITTI semantic segmentation benchmark

• Space of interest $\Omega \in \mathbb{R}^2$
• Objective: find partition with $k+1$ regions $$\begin{align} \min_{\{\Omega_i\}}&\quad \sum_{i=0}^k \int_{\Omega_i} f_i(x)\, dx + \frac{1}{2}\sum_{i=1}^k | \partial \Omega_i | \\ \text{subject to}&\quad \bigcup_{i=0}^k \Omega_i = \Omega, \quad \Omega_s \cap \Omega_t = \varnothing\quad \forall s \neq t \end{align}$$

Video

Next Class

1. Convex Optimization
   1. Duality
2. More examples