04-08 Relaxation

다음과 같은 문제가 주어졌다고 하자.

\[\text{min}_{x} \text{ } f(x) \text{ subject to } x \in C\]

이때, domain set \(C\)를 \(\tilde{C} \supseteq C\)로 변경하는 것을 Relaxation이라고 한다.

\[\text{min}_{x} \text{ } f(x) \text{ subject to } x \in \tilde{C}\]

\(C\)보다 더 큰 domain set에 대해 최적화하는 것이므로 그 optimal value는 항상 원래의 문제보다 더 작거나 같다.

Important special case: relaxing non-affine equality constraints

\(h_{j}(x) = 0, j = 1, \dotsc, r,\) where \(h_{j}, j = 1, \dotsc, r\) are convex but non-affine, are placed with \(h_{j(x)} \le 0, j = 1, \dotsc, r.\)

Equality constraint를 inequality constraint로 바꿈으로써 제약조건이 느슨해지고, domain의 크기가 커지는 효과가 발생한다. 주어진 equality constraint가 convex이고 non-affine일때, 이 방법을 이용하여 문제를 convex 문제로 변경하여 풀이할 수 있다. (단, relaxation 이후에도 동일한 solution이 도출됨이 보장되는 경우에 한함.)