Chapter 2 Convex functions

Stanford 대학의 Convex Optimization 온라인 강의를 듣고 배운 개념을 정리한 글 입니다. 이 글은 강의에서 쓰는 교재를 참고하여 정리 하였습니다. 이 글을 읽기전 Introduction을 듣고 이 글을 읽는 것을 추천 드립니다.

---

Chapter 2 Convex functions

chapeter 1에서는 1차원에서 만든 convex sets에 대하여 다뤘다. chapeter 2에서는 n차원에서의 Convex functions를 다룬다.

 

2.1 Basic properties and example

 

 convex function의 기본속성과 예를 보기전에 먼저 convex function을 정의해 보자.

 

함수 \(f :\mathbf{R}^n \rightarrow \mathbf{R}\)의 \(dom\ f \) (domain f : f의 정의역)가 convex set이고, 다음 조건을 만족하면 \(f\)는 convex function 이다.

 

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

 

위식을 그림으로 나타내면 Figure 2.1과 같다.

 

Figure 2.1 Convex function

 

Figure 2.1처럼 convex function은 함수 \(f\) 에 존재하는 임의 점 \(x,y\)를 잇는 선분은 항상 함수 \(f\) 위에 있다.

 

또, \(dom\ f \)가 convex이고 서로 다른 두점 \(x,y\)가 \(x,y \in dom\ f \)일때, 다음 조건을 만족하면 \(f\)를 strictly convex 라고 한다.

 

$$ f(\theta x + (1-\theta)y) < \theta f(x) + (1-\theta)f(y),\ 0<\theta<1 $$

 

2.1.1 Examples of convex functions on \(\mathbf{R}\)

convex function의 대표적인 예는 다음과 같다.

 

  ● affine : \(a^T x +b\) on \(\mathbf{R}\), \(a,b \in \mathbf{R}\)

 

이를 증명하면, 모든 affine 함수 \(f(x)\ =\ a^T x + b\)는 아래 식을 만족한다. (여기서 vector a 와 vector x는 열벡터이다.

 

$$ f(\theta x + (1-\theta)y)\ =\ a^T(\theta x + (1-\theta)y) +b $$

$$ \qquad = \theta a^T x + (1-\theta)a^T y +\theta b + (1-\theta) b $$

$$ = \theta(a^T x +b) +(1-\theta)(a^T y + b) $$

$$ = \theta f(x) + (1-\theta) f(y) $$

 

따라서, affine 함수는 항상 convex하다, 또, 위식에서 부등호가 아니라 등호(=)이기 때문에 concave하다고 말할 수 있다.

 

● exponential : \(e^{ax}\), \(a \in \mathbf{R}\)

 

지수함수는 그래프를 그려보면 convex를 쉽게 확인할 수 있다.

 

Figure 2.2 Covex function : Exponential

 

● powers(멱함수) : \(x^\alpha\) on \(\mathbf{R}_{++}\), \(\alpha \ge 1\) or \(\alpha \le 0\)