[Week 2] Convex functions

* 세션 교재: Convex Optimization - Boyd and Vandenberghe. Ch.3

이번 세션에서는 convex set에 이어 컨벡스 최적화 문제의 objective 또는 constraint의 형태가 되는 convex function에 대해 알아보자.

1. Basic properties and examples

Definition

함수 $f:\mathbf{R}^n\rightarrow\mathbf{R}$의 정의역이 convex set이고, 임의의 두 점 $x,y\in\mathbf{dom}\ f$를 잇는 선분 위의 모든 점들이 함수 $f$ 위의 점들보다 위에 있다면, 그 함수 $f$는 convex하다. 수식으로 표현하면 아래와 같다.

$f(\theta x+(1-\theta)y)\le\theta f(x)+(1-\theta)f(y), \\\ \text{with}\ 0\le\theta\le1,\quad \text{for all}\ x,y\in\mathbf{dom}\ f$

기억하기 쉽게 한 마디로 표현하면, 평균의 함숫값보다 함숫값의 평균이 크거나 같다.

만일 아래처럼 inequality 조건이 서로 다른 $x,y$에 대해 항상 strict하게 성립할 경우 $f$가 strictly convex하다고 한다.

$f(\theta x+(1-\theta)y)<\theta f(x)+(1-\theta)f(y)$
$\text{with}\,\, x\not=y,\ 0<\theta<1,\,\,\text{for all}\ x,y\in\mathbf{dom}\ f$

$f$가 convex function일 경우, $-f$를 concave function이라고 한다. 마찬가지로 strictly convex function을 뒤집으면 strictly concave function이 된다.

아래에서 확인할 수 있듯, affine function $f(x) = a^Tx + b$는 항상 convex이면서 동시에 concave이다. 반대로 convex, concave가 동시에 성립하면 affine function이다.

$\begin{aligned}&f(\theta x+(1-\theta)y)\\ &=a^T(\theta x+(1-\theta)y)+b \\ &= \theta a^Tx+(1-\theta)a^Ty+\theta b+(1-\theta)b\\ &=\theta f(x)+(1-\theta)f(y)\end{aligned} \\\ \\\text{for all}\ x,y\in\mathbf{dom}\ f,\text{with}\ 0\le\theta\le1$

복잡한 함수의 convexity를 체크하는 좋은 방법은 함숫값의 단면을 살펴보는 것이다. 어떤 함수 $f$가 convex임은 정의역과 교차하는 임의의 직선 상에서 convex임과 동치이다. 이 테크닉을 restriction to a line이라고도 한다. 예를 들어 $f(X) = \log \det X$라고 하자. 이 함수의 정의역은 $\mathbb{S}^n_{++}$이다. 이 때 임의의 $V \in\mathbb{S}^n$에 대하여, $f(X + tV) = g(t) = \log \det X + \log \det (I + tX^{-1/2}VX^{-1/2}) = \log \det X + \sum_{i=1}^n \log(1+ t\lambda_i)$이다. ($\lambda_i$는 $X^{-1/2}VX^{-1/2}$의 고윳값) 위의 계산 과정에 대한 자세한 설명은 이 글을 참고하자. 이때 restrict된 $g(t)$가 $\mathbb{S}^n_{++}$상에서 concave function이므로, log determinant는 concave function이다.

Extended value extensions

Convex function $f$를 수식으로 기술할 때 $x$가 domain set에 속하는지의 여부에 따라 아래처럼 기술할 수 있다.

$\tilde{f}(x) = \begin{aligned}\begin{cases}f(x)&x\in\textbf{dom}\,f\\ \infty &x\notin\textbf{dom}\,f \end{cases}\end{aligned}$

이렇게 정의해도 임의의 $x,y$에 대해 convex function의 정의를 만족함을 쉽게 확인할 수 있다. 반대로 concave function의 경우 domain 바깥을 $-\infty$로 나타내면 된다. 이렇게 기술하는 것은 단순히 편의에 의한 것이다.

First-order conditions

$f:\mathbb{R}^n \rightarrow \mathbb{R}$가 미분 가능하다는 것은 domain이 open set이고, gradient $\nabla f(x) = \begin{bmatrix}\frac{\partial f(x)}{\partial x_1} \\ \vdots \\ \frac{\partial f(x)}{\partial x_n}\end{bmatrix}$가 존재함을 말한다. 이때 미분 가능한 $f$가 convex function임은 $\textbf{dom}\,f$가 convex이고, 임의의 $x,y \in \textbf{dom}\,f$에 대해 $f(y) \geq f(x) + \nabla f(x)^T(y-x)$임과 동치이다.

이 부등식의 우변은 $y$에 대한 affine function이자, $x$를 고정시켰을 때 $f(x)$의 first-order Taylor approximation이다. 이것이 항상 $f(y)$보다 작거나 같으므로, 이 선형 근사는 $f$의 global underestimator가 된다. 또 만약 $\nabla f(x)=0$이라면 $f(y) \geq f(x)$이므로, convex function에서 $\nabla f(x)=0$이면 $x$는 global minimizer가 됨을 알 수 있다.

*우리 세션에서는 증명은 다루지 않았다. 교재를 참고하자.

Second-order conditions

$f:\mathbb{R}^n \rightarrow \mathbb{R}$가 두 번 미분 가능하다는 것은 domain이 open set이고, hessian $\nabla^2 f(x) \in \mathbb{S}^n = \frac{\partial^2 f(x)}{\partial x_i \partial x_j},\quad i,\,j=1,\,2,\,...,\,n$이 존재함을 말한다. 이때 두 번 미분 가능한 $f$가 convex function임은 $\textbf{dom}\,f$가 convex이고, hessian $\nabla^2 f(x)$이 임의의 $x \in \textbf{dom}\,f$에 대하여 positive semidefinite임과 동치이다. 또한 hessian이 positive definite이면 $f$는 strictly convex이다.

이는 $\mathbb{R}$상의 함수로 축소해서 보았을 때, 도함수가 non-decreasing이라는 조건인 $f''(x) \geq 0$과 같다. 또한 기하학적으로 함수의 그래프가 $x$에서 positive (upward) curvature를 가진다는 조건으로도 해석될 수 있다.

*우리 세션에서는 증명은 다루지 않았다. 교재를 참고하자.

Examples

• Quadratic function:
  $f(x) = (1/2)x^TPx + q^Tx + r,\quad P \in \mathbb{S}^n$
  이 함수는 $\nabla^2f=P \succeq 0$이면 convex, $P \preceq 0$이면 concave이다.

• Least squares objective:
  $f(x) = ||Ax - b||_2^2$
  이 함수는 $\nabla^2 f= 2A^TA$이므로 $A$에 관계 없이 convex이다.

• Norm:
  $||x||$는 항상 convex이다. 증명은 기본 성질을 이용하면 간단하다.
  $\begin{aligned} ||\theta x + (1-\theta)y|| &\leq ||\theta x|| + ||(1-\theta)y||\quad\text{by triangle inequality}\\ &=\theta||x|| + (1-\theta)||y|| \quad\text{by homogeneity}\end{aligned}$

• Quadratic-Over-Linear:
  $f(x, y) = x^2/y,\quad y > 0$
  $\nabla^2 f(x,y) = \frac{2}{y^3} \begin{bmatrix} y \\ -x \end{bmatrix} \begin{bmatrix} y \\ -x \end{bmatrix}^T \succeq 0$이므로 convex이다.

• Max function:
  $f(x) = \max_k x_k$
  $\begin{aligned}f(\theta x + (1-\theta)y) &= \max_k (\theta x_k + (1-\theta)y_k)\\ &\leq \theta \max_k x_k + (1-\theta) \max_k y_k\\ &= \theta f(x) + (1-\theta)f(y) \end{aligned}$
  이므로 convex이다.

• Log-sum-exp:
  $f(x) = \sum_{k=1}^n \exp x_k$는 multivariate softplus라고도 부르며, max function에 대한 smooth approximation이다. 구체적으로, $\max\{x_1,\,...,\,x_n\} \leq f(x) \leq \max\{x_1,\,...,\,x_n\} + \log n$이 성립한다. 또한 이 함수의 그래디언트는 softmax function이다. 이것이 convex function임을 증명해 보자.
  우선 $z = (e^{x_1},\,...,\,e^{x_k})$로 놓으면 $\nabla^2 f(x) = \frac{1}{\mathbf{1}^T z} \text{diag}(z) - \frac{1}{\mathbf{1}^T z}z^Tz$이다.
  이때 임의의 벡터 $v \neq 0$에 대해 $v^T\nabla^2 f(x)v = \frac{(\sum_k z_k v_k^2)(\sum_k z_k) - (\sum_k v_k z_k)^2}{(\sum_k z_k)^2}$이고 Cauchy-Schwarz inequality에 의해 $(\sum_k z_k v_k^2)(\sum_k z_k) \geq (\sum_k v_k z_k)^2$이므로 이 함수는 convex이다.

• Geometric mean:
  $f(x) = (\prod_{k=1}^n x_k)^{1/n}$은 concave function이다. 증명은 위와 유사하게 할 수 있다.

Sublevel sets

Sublevel set은 함숫값의 범위를 특정 범위로 제한한 집합을 말한다. 함수 $f:\mathbb{R}^n\rightarrow\mathbb{R}$의 $\alpha$-sublevel set은 다음과 같이 정의된다.

$C_\alpha=\{x\in\mathbf{dom}\ f\ |\ f(x)\le\alpha\}$

모든 $\alpha$에 대하여, convex function의 $\alpha$-sublevel set은 convex set이다. 또한 concave function의 $\alpha$-superlevel set($f$가 $\alpha$보다 크거나 같은 집합)도 convex set이다. 역은 성립하지 않음에 주의하자. 가령 $f(x) = -e^x$는 strictly concave function이지만 sublevel set은 convex이다.

Epigraph

함수 $f:\mathbb{R}^n\rightarrow\mathbb{R}$의 그래프는 $\mathbb{R}^{n+1}$의 subset인 $\{(x,f(x))\ |\ x\in\mathbf{dom}\ f\}$로 정의할 수 있다.

함수 $f:\mathbb{R}^n\rightarrow\mathbb{R}$의 epigraph는 $\mathbb{R}^{n+1}$의 subset인 $\mathbf{epi}\ f=\{(x,t)\ |\ x\in\mathbf{dom}\ f,\ f(x)\le t\}$로 정의할 수 있다. 즉 epigraph는 그래프의 윗 부분을 의미한다. 함수 $f$가 convex인 것은 epigraph가 convex임과 동치이다. 또 함수 $f$가 concave인 것은 hypograph $\mathbf{hypo}\ f=\{(x,t)\ |\ x\in\mathbf{dom}\ f,\ t \le f(x)\}$가 convex임과 동치이다.

Jensen's inequality

$\phi$를 열린 구간 $I$에서 convex function이라고 하자. 만일 확률변수 $X$의 support가 $I$에 포함되고 finite expectation을 가지면 아래가 성립한다.

Example. $p(x)$를 $X$의 true probability distribution이라 하고, $q(x)$를 다른 density라 하자. 그리고 $Y(X) = q(X)/p(X)$라 하자. 그러면 Jensen's inequality에 의해,

$\begin{aligned}-D(p(x)\|q(x))&=\int p(x) \log \left (\frac{q(x)}{p(x)} \right ) \, dx\\ &\le \log \left ( \int p(x) \frac{q(x)}{p(x)}\,dx \right )\\ &= \log \left (\int q(x)\,dx \right ) =0\end{aligned}$

이때 $D(p(x)\|q(x))$를 KL-divergence라 부르며, $q(x)$를 $p(x)$의 estimation으로 사용했을 때 두 분포가 얼마나 다른지를 측정하는 지표이다.

2. Operations that Preserve Convexity

어떤 문제 상황이 주어졌을 때 그것을 convex function으로 나타내고 적절히 코딩하는 것은 최적화 문제를 푸는 핵심 과정이다. 이때 문제 상황을 convex problem으로 구성하기 위해, 모든 수식 표현은 cvxpy와 같은 패키지 라이브러리 내에 있는 함수와 수식의 조합으로 표현되는데, 이것을 Disciplined Convex Programming이라고 한다. 이번 섹션은 그 기초가 되는 이론으로, convex function에 대해 convexity를 보전하는 연산에 대해 알아보자.

어떤 함수 $f$가 convex function인지 판단할 수 있는 방법에는 크게 세 가지가 있다.

1. Convex function의 정의를 그대로 이용 (위의 restriction to a line을 이용해도 좋다.)
2. Second-order condition 확인 (Hessian을 계산하기 쉽지 않을 때가 많으므로, 거의 단순한 함수에만 사용한다.)
3. Convex function에 다음 연산을 해도 여전히 convex이다.

• Non-negative weighted sum
• Composition with affine function
• Point-wise maximum and supremum
• Composition
• Minimization
• Perspective

Nonnegative scaling, sum, and integral

정의로부터 바로 확인할 수 있고 concave function에서도 동일하다.

• $f$가 convex일 때, $\alpha \geq 0$에 대하여 $\alpha f$도 convex이다.
• $f_1, f_2$가 convex일 때, $f_1 + f_2$도 convex이다.
• $f_1,f_2,...$가 convex일 때, infinite sum $\sum_{i=1}^{\infty} f_i$도 convex이다.
• $f(x, \alpha)$가 $\alpha \in \mathcal{A}$에서 $x$에 대해 convex일 때, $\displaystyle \int_{\alpha \in \mathcal{A}} f(x,\alpha) \,d\alpha$도 convex이다.

Composition with affine function

$f(x)$가 convex이면 $f(Ax+b)$도 convex이다.

• Log barrier function $f(x) = -\sum_{i=1}^m \log(b_i-a^T_i x)$은 convex이다.
• Norm이 convex이므로, approximation error로 많이 쓰이는 $||Ax-b||$도 convex이다.

Pointwise maximum

$f_1,\,...,\,f_m$이 convex이면 $f(x) = \max\{f_1(x),\,...,\,f_m(x)\}$도 convex이다.

• Piecewise linear function $f(x) = \max_{i=1,\,...,\,m} (a_i^Tx +b)$는 convex이다.
• $x \in \mathbb{R}^n$의 가장 큰 원소부터 $r$개의 합 $f(x) = x_{[1]} + \cdots + x_{[r]}$은 $f(x) = \max\{x_{i_1} + \cdots + x_{i_r}\,|\,1 \leq i_1 \leq \cdots \leq i_r \leq n\}$으로 볼 수 있으므로 convex이다.

Pointwise supremum

$f(x,y)$가 $y \in\mathcal{A}$에서 $x$에 대해 convex일 때, $g(x) = \sup_{y \in\mathcal{A}}f(x,y)$는 convex이다.

• 집합 $C$에서 가장 먼 점과의 거리 $f(x) = \sup_{y \in C} ||x-y||$는 convex이다.
• symmetric matrix의 maximum eigenvalue $\lambda_{\max}(X) = \sup_{||y||_2 = 1}y^T X y$는 convex이다.
• 집합 $C$의 support function $S_C(x) = \sup_{y \in C} y^Tx$는 convex이다.

Partial minimization

$g(x) = \inf_{y \in C} f(x,y)$를 $f$의 partial minimization이라고 한다. 만약 $f(x,y)$와 $C$가 convex라면 $g$도 convex이다.

• $\text{dist}(x,S) = \inf_{y \in S} ||x-y||$는 convex이다.

Composition with scalar functions

$g:\mathbb{R}^n \rightarrow \mathbb{R}$, $h: \mathbb{R}\rightarrow \mathbb{R}$에 대해
$f(x)=h(g(x))$는 다음 조건 중 하나를 만족 시 convex이다.

$g$ convex, $h$ convex, $\tilde{h}$ nondecreasing
$g$ concave, $h$ convex, $\tilde{h}$ nonincreasing

• $g$ is convex $\implies$ $\exp g(x)$ is convex
  
• $g$ is concave and positive $\implies$ $1/g(x)$ is convex

General composition rule

$g:\mathbb{R}^n →\mathbb{R}^k$, $h: \mathbb{R}^k→\mathbb{R}$에서
$f(x)=h(g_1(x), g_2(x), … , g_k(x))$는 함수의 각 argument $g_i$에 대해 다음 조건 중 하나를 만족 시 convex이다.

$g_i$ convex, $\tilde{h}$ nondecreasing in its $i$th argument
$g_i$ concave, $\tilde{h}$ nonincreasing in its $i$th argument
$g_i$ affine

• $g$ is convex $\implies \sum_{i=1}^m \exp g_i(x)$ is convex
• $f(x) = p(x)^2 / q(x)$ is convex if $p$ is nonnegative and convex, $q$ is positive and concave

Perspective

함수 $f: \R^n → \R$의 perspective는 $g:\R^n\times \R → \R,\,\,g(x,t)=tf(x/t)$로 정의된다.
$g$의 정의역은 $\mathbf{dom}\ g = \{(x,t)\,|\, x/t \in\mathbf{dom}\ f,\, t>0 \}$이다.
함수 $f$가 convex이면 함수 $g$도 convex이다.

• $f(x)=−\log x$ is convex $\implies$ relative entropy $g(x,t)=t\log t−t\log x$ is convex on $\R_{++}^2$

3. The conjugate function

함수 $f : \mathbb{R}^n \rightarrow \mathbb{R}$ 에 대하여, $f$의 conjugate $f^* : \mathbb{R}^n \rightarrow \mathbb{R}$는 다음과 같이 정의된다.

$f^*(y) = \sup_{x \in \textbf{dom}\,f} (y^T x -f(x))$

이때 $\textbf{dom}\,f^*$는 supremum이 bounded인 범위이다.

이 함수는 기하적으로 closed convex function을 epigraph의 관점에서 살펴보았을 때, supporting hyperplane의 $x=0$에서의 offset으로 해석될 수 있다. Conjugate function은 뒤에서 배울 Lagrange dual function과 깊은 관련이 있다. 또, conjugate function은 affine function의 supremum 형태이므로, 원래 함수와 관계 없이 항상 convex이다.

Examples

• Affine function: $f(x)=ax+b$일 때 $yx-ax-b$는 $y=a$일때만 bounded이다. 따라서 $f^*$의 domain은 singleton $\{a\}$이고 $f^*(a)=-b$이다.
  

• Negative logarithm: $f(x)=-\log x$ ($x >0)$일 때 $y \geq 0$이면 $xy+\log x$는 unbounded이다. 반대로 $y <0$이면 $y = -1/x$일 때 maximum이므로 $\mathbf{dom}\,f^*= \{y\,|\,y<0\}$이고 $f^*(y)=-\log(-y)-1$이다.
  

• Inverse: $f(x) = 1/x,\,\,x>0$일 때 $f^*(y) = -2(-y)^{1/2},\,\,y\leq 0$이다.

• strictly convex quadratic: $f(x) = \frac{1}{2}x^TQx,\,\,Q\in\mathbb{S}_{++}^n$일 때 $f^*(y) = \sup_x(y^Tx - (1/2) x^TQ x) = \frac{1}{2}y^T Q^{-1} y$이다.

Fenchel’s inequality

Conjugate function의 정의로부터 그대로 도출된다.

$f(x)+f^*(y)\ge y^Tx$

Conjugate of the conjugate

함수 $f$가 closed / convex일 때, $f^{**}=f$이다.

Differentiable functions

미분 가능한 함수 $f$의 conjugate를 $f$의 Legendre transform이라고 한다. $\mathbb{R}^n$에서 정의된 $f$가 convex이고 미분 가능하다고 하자. 이때 $y^Tx -f(x)$의 maximizer $x^*$는 $y = \nabla f(x^*)$를 만족하며, 반대로 $y = \nabla f(x^*)$를 만족하는 $x^*$는 $y^Tx -f(x)$의 maximizer이다.

따라서 $y = \nabla f(x^*)$에 대해 $f^*(y) = x^{*T}\nabla f(x^*) -f(x^*)$가 성립하므로, 임의의 $y$에 대한 conjugate function의 값을 gradient equation $y=\nabla f(z)$를 $z$에 대해 풀어서 구할 수 있다.

4. Quasiconvex functions

Quasiconvex는 convex보다 조금 약한 개념이지만, 여전히 유용한 성질들을 많이 보존하고 있다. 함수$f : \R^n → \R$의 정의역 $\textbf{dom}\,f$가 convex이고, 모든 $\alpha$에 대해 sublevel sets $S_{\alpha} = \{x \in \textbf{dom}\,f\,|\,f(x) \leq \alpha\}$가 convex라면 $f$를 quasiconvex function이라고 한다.

만약 $-f$가 quasiconvex라면 $f$를 quasiconcave라고 하며, $f$가 quasiconvex인 동시에 quasiconcave이면 quasilinear라고 한다.

Examples

• $\sqrt{|x|}$는 $\R$에서 quasiconvex이다.
• $ceil(x) = \inf\{z \in \Z\,|\,z \geq x\}$는 quasilinear이다.
• $\log x$는 $\R_{++}$에서 quasilinear이다.
• $f(x_1, x_2) = x_1x_2$는 $\R^2_{++}$에서 quasiconcave이다.
• linear fractional function $f(x) = \frac{a^Tx +b}{c^T x + d},\,\,c^Tx + d >0$은 quasilinear이다.

Properties of quasiconvex functions

Modified Jensen inequality

Quasiconvex function $f$와 $0 \leq \theta \leq 1$에 대하여 $f(\theta x + (1-\theta)y) \leq \max\{f(x), f(y)\}$이다.

First-order condition

Domain이 convex이고 미분 가능한 함수 $f$가 quasiconvex인 것은 아래와 동치이다.

$f(y) \leq f(x) \implies \nabla f(x)^T(y-x) \leq 0$

Operations that preserve quasiconvexity

대부분 convex function과 유사하지만, 한 가지 주의할 점은 quasiconvex function의 합은 quasiconvex가 아닐 수도 있다는 것이다.

5. Log-concave and log-convex functions

어떤 함수 $f: R^n \rightarrow R$ 이 정의역에 속하는 모든 $x$에 대해 $f(x)>0$ 이고, $\log f$ 가 concave이면, $f$ 를 log-concave라고 한다. 반대로, $\log f$가 convex이면 $f$는 log-convex하다. (log가 concave function이므로 log-concave 표현을 조금 더 많이 쓴다.)

만일 concave인 $f$가 non-negative라면, 그것은 log-concave function이기도 하다.

$f$가 log-concave인 것은 다음 부등식으로도 나타낼 수 있다.

$f(\theta x+(1-\theta)y) \geq f(x)^{\theta}f(y)^{1-\theta} \\\ \\\text{for all}\ x,y\in\mathbf{dom}\ f,\text{with}\ 0\le\theta\le1$

Examples

• Affine function: $\{x|a^Tx+b>0\}$에서 정의된 $f(x)=a^Tx+b$는 log-concave이다.

• Powers: $\mathbb{R}_{++}$에서 정의된 $f(x)=x^a$는 $a\le0$에서 log-convex이고 $a\ge0$에서 log-concave이다.

• Exponentials: $f(x)=e^{ax}$는 log-convex이면서 log-concave이다.

• Multivariate normal Distribution:
  $f(x)=\frac{1}{\sqrt{(2\pi)^n\text{det}\sum}}\exp({-\frac{1}{2}(x-\bar{x})^T\sum^{-1}(x-\bar{x})})$는 log-concave하다.

• 이 외의 Normal, Uniform, Exponential, Beta, Wishart, Weibull 등 많은 probability distribution의 density function은 log-concave하다.

Properties

Twice differentiable log-convex/concave functions

$f$가 두 번 미분 가능하고 $\mathbf{dom}\ f$가 convex일 때, $\nabla^2 \log f(x) =\frac{1}{f(x)}\nabla^2f(x)-\frac{1}{f(x)^2}\nabla f(x) \nabla f(x)^T$ 가 성립한다.

따라서 함수 $f$가 log-concave임과 $f(x)\nabla^2f(x)\preceq \nabla f(x)\nabla f(x)^T$는 동치이다.

Integration

• 만약 $f:\mathbb{R}^n\times\mathbb{R}^m\rightarrow\mathbb{R}$이 log-concave하면, $g(x)=\displaystyle \int f(x,y)dy$는 log-concave이다.

• 만약 $C\subseteq\mathbb{R}^n$이 convex이고 $y$가 log-concave pdf를 가진 random variable이라면, $f(x)=\mathbb{P}(x+y\in C)$는 log-concave이다.

Example.

Gaussian density의 cumulative distribution function $\Phi (x)=\frac{1}{\sqrt{2\pi}}\int^x_{-\infin}e^{-u^2/2}du$는 log-concave하다.