[최적화] Convex Function

 

https://convex-optimization-for-all.github.io/contents/chapter03/

Convex Functions · 모두를 위한 컨벡스 최적화

 

 

 

convex function

$f : \mathbb{R}^n \rightarrow \mathbb{R}$의 정의역이 convex set이고,

임의의 두점 $x, y \in dom f$ 를 잇는 선분 위의 모든 점들이 함수 f 위 점들보다 위에 있다면 그 함수는 convex

 

$f(\theta x+(1-\theta )y) \le \theta f(x) + (1-\theta)f(y)$, with $0 \le \theta \le 1$, for all $x, y \in dom f$

 

 

 

Strictly convex

convex function에서 $x \neq y$ 면 strictly convex

$f(\theta x+(1-\theta )y) \le \theta f(x) + (1-\theta)f(y)$, with $0 \le \theta \le 1, \ x \neq y$, for all $x, y \in dom f$

 

 

 

concave function

$-f$가 convex면, $f$는 concave

Linear 함수를 포함한 모든 affine함수 $f(x) = a^T x +b$ 는 항상 convex이며, 동시에 concave이다.

 

$$ \begin{align} f(\theta x+(1-\theta)y) &= a^T(\theta x + (1-\theta)y) +b \\ &= \theta a^T x + (1-\theta)a^T y+\theta b + (1-\theta)b \\ &= \theta(a^Tx+b) + (1-\theta)(a^Ty+b) \\ &= \theta f(x) + (1-\theta)f(y) \end{align} $$

 

 

 

Example of convex fucntions

• Exponential function 지수함수
• Power function 멱함수
• Affne
• quadratic function 이차함수
  • 2차항의 계수가 0이상이면
• least squares loss 최소제곱오차
  • 오차 제곱의 합 → 2차방정식, 2차항의 계수가 항상 양수
• Norm
  • $||x||_p = \left( \sum_{i=1}^{n}|x_i|^p \right)^{1/p} \ for \ p \ge 1, \ ||x|| = \max_{i=1,\cdots,n}|x_i|$
• indicator function
  • 임의의 집합 C가 convex면 이에 해당하지 않는 x에 대해 무한대로 정의한 indicator 함수도 convex다.
  • 정의되지 않은 부분은 정의된 부분보다 항상 크게 해 convex의 성질을 갖게 함.

 

 

 

key properties of convex functions

< Epigraph characterization >

$f$가 convex면 그 epigraph는 convex set. 그 역도 성립

 

 

< Convex sublevel sets >

함수 f가 convex면, 그 sublevel set도 convex다.

$\{ x\in dom \ f : f(x) \le t \}$, for all $t \in \mathbb R$

 

*$\alpha$ - sublevel set

$f : \mathbb R^n \rightarrow \mathbb R$ 에 대한 $C_{\alpha} = \{x \in dom \ f | f(x) \le \alpha \}$

 

https://www.chegg.com/homework-help/questions-and-answers/epi-f-convex-set-f-convex-function-sublevel-sets-ca-x-f-x-convex-convex-f-f-x-ca-x-q64688825

 

 

 

< First-order characterization >

$f$가 미분이 가능하다고 가정할 때, 함수 $f$의 도메인 $dom f$가 convex이고,

함수 f의 도메인에 속하는 임의의 $x, y$에 대하여 $f(y) \ge f(x) + \bigtriangledown f(x)^T (y-x)$ 가 성립하면

$f$는 convex이며, 그 역도 성립한다.

 

 

 

< Second-order characterization >

정의역이 convex인 함수 $f$의 2차 미분이 0보다 크거나 같을 경우,

$f$는 convex이며, 그 역 또한 성립한다.

$f$ is convex $\Leftrightarrow \bigtriangledown ^2 f(x) \ge 0$ for all $x \in dom f$, $dom f$ : convex

 

2차 미분이 0보다 클 경우, $f$는 strictly convex

 

 

< jensen’s inequality >

함수 $f$가 convex고, n개의 양수 $w_1, \cdots, w_n$에 대해서

$\sum_{i=1}^n w_i = 1$이라하면 다음이 성립

 

$\sum_{i=1}^n w_i f(x_i) \ge f(\sum_{i=1}^n w_i x_i)$

 

[예시]

$ tf(x_1) + (1-t)x_2 \ge f(tx_1+(1-t)x_2) \ \ for \ 0\le t \le 1$

 

 

 

 

 

 

[출처 및 참고]

https://web.stanford.edu/~boyd/cvxbook/

https://convex-optimization-for-all.github.io/