Convexity

Convex Sets.

• Convex set

C is Convex set if
$x, x' \in C$ then $(1-\theta)x + \theta x' \in C$ for any $0 \le \theta \le 1$

Operations on Convex Sets.

• Intersection :

If A and B are convex sets, then $A \cap B$ is a convex set

Example 1 the set of positive-definite matrices $S^+_n$ is convex because..

$H_y = \{X|y'Xy > 0\}$ is convex for all $y$.
$S_n^+= \cap_{y}H_y$ Thus $S_n^+$ is convex.

• Affine transformation

If $S \in R^n$ is convex then $f(S) = \{y|y = Ax + b, x \in S \}$ is convex.
Similarly, $f^{-1}(S)$ is convex if $f(x) = Ax+b$ is an affine map.

• Projection

If S is convex then each projection $\pi(S) = \{y|(x,y) \in S \}$ is convex.

• Separating Hyperplanes

If C and D are convex, and disjoint then there exists a separating hyperplane between them:

$a^Tx \ge b$ for all $x \in C$
$a^Tx \le b$ for all $x \in D$

• Supporting Hyperplanes

Suppose $x$ is an element of the convex set C. and $x_0$ is in the boundary of C.

There is a Hyperplane H s.t. $H = \{x | a^Tx = a^Tx_0\}$ and $a^Tx \ge a^Tx_0$ for all $x \in C$

Convex Functions.

• Some terminology

• proper function : A function $f = S \subseteq R^m \to [-\infty, \infty]$ is said to be proper if there is no $x \in S$ with $f(x) = -\infty$ and there is some $x$ with $f(x) \neq \infty$.
  
  
• Effective domain $dom f$ : the set of points where $f$ is finite. i.e, $dom f = \{x \in S|f(x) < \infty \}$
  
  
• A proper convex function $f$ is $closed$ if it is lower semi-continuous; that is, in case for each $\alpha$ the set $\{x:f(x) > \alpha\}$ is open.

• 동치명제

  A function $f$ is convex if and only if the $epigraph$
  $epi f =\{(x,t) \in R^{n+1} | f(x) \leq t \}$
  is a convex set.

• How to show a function is convex?
  0차, 1차, 2차 미분의 관점에서 각각 보일 수 있다.

Zeroth-order characterization of convexity
:A function $f : R^n \to R$ is convex if and only if $g(t) = f(x + tv)$ is convex for each $x \in dom f$ and $v \in R^n$

특징 : x에 대한 convexity를 t에 대한 convexity로 바꿔버린다.

Example : Log determinant
let $f(A) = log det(A)$ then let $g(t) = f(A + tV)$.
$g(t) = log det(A + tV) = log det(A) + log det(I + tA^{-1/2}VA^{-1/2})$
$log det(A) + \sum_{i}log(1 + t\lambda_i)$, where $\lambda_i$ is ith eigenvalue of $A^{-1/2}VA^{-1/2}$.
Therefore, $f(A)$ is concave.

First-order characterization of convexity
: A differentiable function $f : R^n \to R$ is convex if and only if $f(y) \ge f(x) + \bigtriangledown f(x)^T(y-x)$ is convex for every $x,y \in dom f$

특징 : 접선(평면) 성질에 의해 자명.

Second-order characterization of convexity
: Hessian 행렬의 non-posivite-definie 성질확인.

Example : log-sum-exp
$f(x) = log\sum_{i} exp \; x_i$ is convex.

Functions of Convex Functions

다음은 함수의 convexity를 보존하는 연산들이다.

• Nonnegative weighted sum - trivial

• Composition with an affine function
  - If $f : R^n \to R$ is convex and g : $R^m \to R^n$ is affine, givne by $g(x) = Ax + b$, then the composition $(f\;o\; g)(x) = f(Ax+b)$ is convex.
  

• pointwise maximum and supremum
  The maximum of convex functions is convex. Can be shown with the notion of epigraph. similary,
  $g(x) = sup_{y \in A}f(x,y)$ is convex if $f$ is convex in $x$ for $y \in A$
  - Example : Largest eigenvalue
  For $X \in S^n$ a symmetric matrix.
  $\lambda_{max}(X) = sup_{y^Ty = 1}y^TXy$
  X is linear for each y s.t. $y^ty = 1$ thus convex. Therefore, $\lambda_{max}(X)$ is convex.

• Composition
  - $f\;o\;g$ is convex if g is concave and f is convex and nondecreasing

  • $f\;o\;g$ is concave if g is concave and f is concave and nondecreasing
  • $f\;o\;g$ is concave if g is convex and f is concave and nonincreasing

Log-Convexity

: $f(x)^\theta f(y)^{1-\theta} \ge f(\theta x + (1-\theta)y)$

Important properties

• The product of log-concave functions is log-concave (trivial)

• If $f:R^{n+m} \to R$ is log-concave then the marginal
  $g(x) = \int_{R^m} f(x,y) dy$ is log-concave.

  $proof)$ $g(\theta x_1 + (1-\theta)x_2) = \int_{R^m}f(\theta x_1 + (1-\theta)x_2, y)dy$
  $\ge \int_{R_m}f(x_1,y)^\theta f(x_2,y)^{1-\theta}dy$
  $\ge (\int_{R_m}f(x_1,y)dy)^\theta + (\int_{R^m}f(x_2, y)dy)^{1-\theta}$ By Jensen's ineq

• The convolution
  $(f \star g)(x) = \int f(x-y)g(y)dy$ of log-concave functions is log-concave.

Conjugate function

The conjugate function $f^*$ of a proper function $f$ is given by

$f^*(y) = sup_{x \in dom f}\{<x,y> - f(x)\}$. The conjugate is always a convex function : trivial

• If $f$ is differentiable, then $y = \bigtriangledown f(x^*)$

• If f is strictly convex, we can write $\bigtriangledown f^{-1}(y) = x^*$, so $f^*(y) = <\bigtriangledown f^{-1}(y), y - f(\bigtriangledown f^{-1}(y))$

• Fenchel's inequality
  From definition, $f(x) + f(x^*) \ge <x,y>$
  

• Fenchel's duality

  Suppose that $f : R^n \to R \cup \{\infty\}$ and $g : R^m \to R \cup \{\infty\}$ are closed proper convex functions and $A \in R^{mn}$ is an m x n matrix. Then
  
  $inf_{x} \{f(x) + g(Ax) \} = sup_{\lambda}\{-f^\star(A^T\lambda)-g^\star(-\lambda)\}$
  
  proof : by Fenchel's inequality

  Question:

• 127p-separating / supporting plane pf

• epigraph convexity pf

• 129p closed convex function??

• 130p zeroth-order pf

• 133p 134p log convexity properties : convolution 의미?