최적화 문제의 분류

제약조건이 있는 비선형 다변수 함수 $f(\mathbf{x})$의 최소값 (또는 최대값)을 구하는 문제를 정적 최적화(static optimization) 문제 또는 비선형 프로그래밍 문제(NLP, nonlinear programming problem)라고 한다. 수식으로 표현하면 다음과 같다.

 

$$\begin{array}{rl}& p^{\ast }=\underset{\mathbf{x}}{min}f(\mathbf{x})\\ \\ subjectto& g_i(\mathbf{x})\le 0,i=1,...,m\\ \\ & h_j(\mathbf{x})=0,j=1,...,p\end{array}$$

 

여기서 $\mathbf{x}\in R^n$을 최적화 변수(optimization variable)라고 하고, $f(\mathbf{x}):R^n\to R$ 을 목적함수(objective function), $g_i(\mathbf{x}):R^n\to R$ 을 부등식 제약함수(inequality constraint function), $h_j(\mathbf{x}):R^n\to R$ 을 등식 제약함수(equality constraint function)라고 한다. 부등식, 등식 제약함수는 편의상 다음과 같이 벡터 형태로 표현하기도 한다.

 

$$\begin{array}{rl}\mathbf{g}(\mathbf{x})& \le 0\\ \\ \mathbf{h}(\mathbf{x})& =0\end{array}$$

 

여기서 부등식과 등식은 벡터 함수 $\mathbf{g}(\mathbf{x}),\mathbf{h}(\mathbf{x})$의 성분별로 적용된다.

 

 

만약 제약조건을 만족하는 $\mathbf{x}$값이 존재하지 않는다면 최적화 문제는 실현불가능(infeasible)이라고 하고 그 때의 최소값은 $p^{\ast }=\mathrm{\infty }$가 된다.

비선형 다변수 함수 $f(\mathbf{x})$의 최대값을 구하는 문제는 $-f(\mathbf{x})$의 최소값을 구하는 문제와 같으므로 최적화 문제를 최소화와 최대화 문제로 따로 구별할 필요는 없다.

 

 

만약 목적함수와 부등식 제약함수가 컨벡스(convex) 함수이고 등식 제약함수가 어파인(affine) 함수로 주어진다면, 이 최적화 문제를 컨벡스 최적화 문제(convex optimization problem)라고 한다. 즉 컨벡스 최적화 문제는 다음과 같다.

 

$$\begin{array}{rl}& p^{\ast }=\underset{\mathbf{x}}{min}f(\mathbf{x})\\ \\ subjectto& g_i(\mathbf{x})\le 0,i=1,...,m\\ \\ & A\mathbf{x}=\mathbf{b}\end{array}$$

 

여기서 $f(\mathbf{x})$와 $g_i(\mathbf{x}),i=1,\dots ,m$ 는 컨벡스 함수이고 $A$는 $p\times n$ 행렬, $\mathbf{b}$는 $p\times 1$ 벡터이다.

만약 목적함수와 부등식 제약함수, 등식 제약함수가 모두 어파인(affine) 함수로 주어진다면, 이 최적화 문제를 선형 프로그래밍(LP, linear programming)문제라고 한다. 즉 LP 문제는 다음과 같다.

 

$$\begin{array}{rl}& p^{\ast }=\underset{\mathbf{x}}{min}{\mathbf{c}}^T\mathbf{x}+\mathbf{d}\\ \\ subjectto& G\mathbf{x}\le \mathbf{z}\\ \\ & A\mathbf{x}=\mathbf{b}\end{array}$$

 

여기서 $G$는 $m\times n$ 행렬, $\mathbf{z}$는 $m\times 1$ 벡터, $A$는 $p\times n$ 행렬, $\mathbf{b}$는 $p\times 1$ 벡터이다. LP는 다면체(polyhedron) 상에서 어파인 함수를 최소화하는 문제다.

 

만약 목적함수가 2차함수이고, 부등식 제약함수와 등식 제약함수가 어파인(affine) 함수로 주어진다면, 이 최적화 문제를 2차 프로그래밍(QP, quadratic programming)문제라고 한다. 즉 QP 문제는 다음과 같다.

 

$$\begin{array}{rl}& p^{\ast }=\underset{\mathbf{x}}{min}\frac{1}{2}{\mathbf{x}}^{T}P\mathbf{x}+{\mathbf{c}}^T\mathbf{x}+\mathbf{d}\\ \\ subjectto& G\mathbf{x}\le \mathbf{z}\\ \\ & A\mathbf{x}=\mathbf{b}\end{array}$$

 

여기서 $P$는 $n\times n$ 행렬, $G$는 $m\times n$ 행렬, $\mathbf{z}$는 $m\times 1$ 벡터, $A$는 $p\times n$ 행렬, $\mathbf{b}$는 $p\times 1$ 벡터이다. $P\ge 0$ 이면 목적함수가 컨벡스 함수이므로 QP는 컨벡스 문제가 된다. QP는 다면체 상에서 컨벡스 2차함수를 최소화하는 문제다.