Chapter 1 - Introduction

Mathematical optimization

---

$mathematical \ optimization \ problem$, 또는 $optimization \ problem$ 은 다음과 같은 형식으로 가지고 있습니다.

(1.1)

• vector $x = (x_{1},...,x_{n})$ : 문제의 $optimization \ variable$ or $decision \ variable$
• function $f_{0}:R^{n}\rightarrow R$ : $objective \ function$
• function $f_{i}:R^{n}\rightarrow R, \ i=1,...,m$ : $(ineuqality) \ constraint \ functions$
• $b_{1},...,b_{m}$ : limits, or bound for the constraints
• vector $x^{*}$ : $optimal$ or $solution$ of the problem

제약을 만족하는 모든 벡터 중에서 목표 값이 가장 작은 경우 : 모든 $z$에 대해 $f_{i} \leq b_{1},...,f_{m}(z) \leq b_{m}$을 만족할 때, 우리는 $f_{0}(z) \geq f_{0}(x^{*})$과 같은 부등식을 가지고 있습니다.

우리는 일반적으로 특정 형태의 목적함수 또는 제약함수에 의해 특성화 된 최적화 문제의 families or classes를 고려합니다. 예시로, $linear \ program$이라고 불리는 최적화문제에 대해서 말해보겠습니다. 만약 objective function과 constraint function $f_{0},...,f_{m}$가 linear하다면 즉, 다음을 만족합니다.

$f_{i}(\alpha x + \beta y) = \alpha f_{i}(x) + \beta f_{i}(y)$ -- (1.2)

모든 $x, y \in R^{n}$그리고 모든 $\alpha, \beta \in R$이고, 최적화 문제가 linear하지 않다면, 이것은 $nonliear \ program$이라고 부릅니다.

 

이책은 $convex \ optimization \ problems$라고 하는 최적화 문제 클래스에 관한 것입니다.  $convex \ optimization \ problem$의 objective function과 constraint function은 convex합니다. 즉, 다음과 같은 부등식을 만족합니다.

$f_{i}(\alpha x + \beta y) \leq \alpha f_{i}(x) + \beta f_{i}(y)$ -- (1.3)

모든 $x, y \in R^{n}$이고 모든 $\alpha, \beta \in R$ with $\alpha, \beta \in R, \alpha \geq 0, \beta \geq 0$입니다. 

모든 $linear \ program$은 $convex \ optimization$문제이므로 convex optimization을 linear programming으로 간주할 수 있습니다.

Solving optmization problems

---

 

알고리즘의 효율성, 즉 optimization problem(1.1)을 해결하는 능력은 상당히 다양하며 특정 형태와 같은 요인에 따라 달라집니다. objective function과 constraint function, 얼마나 많은 변수와 constraint가 있는지 희소성과 같은 특수 구조입니다. (각 constraint function이 소수의 변수에만 의존하는 경우에 문제는 $sparse$합니다.)

objective function과 constraint function이 smooth한 경우에도 (예시 : 다항식) 일반 optimization problem(1.1)은 의외로 해결하기 어렵습니다. 따라서 일반적인 문제에 대한 접근은 매우 긴 시간계산이나 해결책을 찾기 못할 가능성 같은 일종의 타협을 포함합니다.

대부분의 최적화 문제를 해결하기 어려운 일반적인 규칙에는 몇가지 중요한 예외가 있는데, 몇가지 문제 클래스의 경우에 수백 또는 수천개의 변수와 제약조건을 사용하여 큰 문제라도 안정적으로 해결할 수 있는 효과적인 알고리즘을 가지고 있습니다. 잘 알려진 두가지 예외는 least-squares와 linear programming입니다.

 

Least-squares problems

---

$least-squares$ 문제는 제약조건이 존재하지 않는 문제이며, (즉, $m = 0$) 그리고 목적함수는 다음과 같은 제곱합과 같은 형태로 이루어져 있습니다. $a^{T}_{i}x - b_{i}$

minimize $f_{0}(x) = \left \| Ax - b \right \|^{2}_{2}=\sum^{k}_{i=1}(a^{T}_{i}x - b_{i})^{2}$ -- (1.4)

$A \in R^{k \times n}$(with $k \geq n$), $a^{T}_{i}$는 A 행렬의 행이며, 그리고 vector $x \in R ^{n}$는 optimization variable입니다.