최적화 문제에서의 수치해석

최적화 문제의 정의와 유형

최적화 문제란 실수 벡터 공간에서 정의된 어떤 스칼라 함수 $f(\mathbf{x})$에 대하여 최소값 혹은 최대값을 찾는 과정이다. 일반적으로 $\mathbf{x}$는 $\mathbb{R}^n$ 공간에 속하는 $n$차원 변수 벡터이며, 목적함수(objective function) $f(\mathbf{x})$는 $n$차원에서 스칼라로 매핑되는 함수이다. 따라서 최적화 문제는 다음과 같은 형태로 나타낼 수 있다.

$$\min_{\mathbf{x} \in \mathbb{R}^n} f(\mathbf{x})$$

또는

$$\max_{\mathbf{x} \in \mathbb{R}^n} f(\mathbf{x})$$

많은 실제 응용에서 제약(constraint)이 존재하므로 제약 조건들을 갖는 문제는 보다 일반화된 형태로 표현된다. 즉

$$\min_{\mathbf{x} \in \mathcal{D}} f(\mathbf{x})$$

과 같이 $\mathbf{x}$가 만족해야 하는 영역 $\mathcal{D}$ 위에서의 최소 혹은 최대값을 모색한다. 여기서 $\mathcal{D}$는 선형 제약식 혹은 비선형 제약식을 통하여 정의되는 공간일 수 있다. 예컨대 선형 제약식은 $\mathbf{A}\mathbf{x} \le \mathbf{b}$와 같은 형태로 주어질 수 있고, 비선형 제약식은 $g(\mathbf{x}) \le 0$이나 $h(\mathbf{x}) = 0$ 같은 조건으로 주어진다. 이와 같이 정의된 최적화 문제는 크게 다음과 같은 유형으로 구분할 수 있다: 무제약(unconstrained) 최적화 문제와 유제약(constrained) 최적화 문제. 무제약 최적화 문제는 제약 조건이 없으며, 유제약 최적화 문제는 다양한 형태의 제약 조건을 포함한다.

목적함수의 구조

최적화 문제에서의 수치해석 기법을 효율적으로 설계하기 위해서는 목적함수 $f(\mathbf{x})$의 구조를 분석하는 과정이 필수적이다. 예컨대 목적함수가 이차 형태를 띠는지, 혹은 비선형성이나 비convex 특성을 갖는지에 따라 적합한 알고리즘적 접근이 달라진다. 일반적으로 매끄러운(smooth) 함수인 경우 해석적인 도함수(gradient 및 Hessian)를 구하거나 근사치로 추정할 수 있다면, 뉴턴(Newton) 방법 계열의 효율적인 방법을 적용할 수 있다. 반면 미분 가능한 구조를 갖지 않거나, 많은 국소 최적(local optimum)이 존재하는 경우에는 다른 형태의 기법이 선호될 수 있다.

목적함수가 미분 가능하다고 가정하면, 국소 최적점을 판별하기 위해 다음과 같은 조건들을 활용한다.

$$\nabla f(\mathbf{x}) = \mathbf{0}$$

이때 $\nabla f(\mathbf{x})$는 $f(\mathbf{x})$의 그래디언트이며, 이 조건이 만족되는 지점이 최적점(극값 후보)이 될 수 있다. 또한 $\nabla^2 f(\mathbf{x})$가 해당 지점에서 양의 정부호(positive definite)인가, 음의 정부호(negative definite)인가, 아니면 정부호가 아닌가에 따라 국소 최소, 국소 최대, 혹은 안장점(saddle point)이 판별된다.

수치해석적 관점에서의 핵심 과제

현실적으로는 목적함수 $f(\mathbf{x})$의 형태가 복잡할 수 있으며, 어떤 경우에는 해석적 형태를 전혀 알 수 없거나, 비선형 제약 조건이 존재하거나, 문제의 차원이 매우 커서 해의 탐색이 어려워지기도 한다. 특히 계산 복잡도가 급격히 증가하는 대규모 문제에서는 수치적 효율성(계산 시간, 메모리 사용량 등)이 매우 중요한 이슈가 된다. 따라서 최적화 알고리즘을 구성할 때 다음과 같은 수치해석적 과제들을 고려하게 된다.

계산 가능한 방식으로 그래디언트 혹은 헤시안 정보(또는 근사치)를 얻을 수 있는가. 수치적 오차가 누적되지 않도록 알고리즘적 안정성(stability)을 어떻게 확보할 것인가. 알고리즘의 수렴 속도를 높이기 위해 적절한 스텝 크기(step size)나 방향(direction)을 어떻게 결정할 것인가.

이러한 쟁점들은 다양한 최적화 방법들(예: 선형 검색(line search) 기법, 신경망 기반 기법, 확률적(stochastic) 기법 등)을 설계하고 분석할 때 반드시 다루어져야 한다.

그래디언트 기반 방법과 스텝 크기

무제약 최적화 문제에서 가장 직접적으로 적용할 수 있는 방법 중 하나는 그래디언트 하강법(gradient descent)이다. 이 방법은 매 반복(iteration)마다 현재 위치 $\mathbf{x}_k$에서의 그래디언트 $\nabla f(\mathbf{x}_k)$를 이용하여 업데이트를 수행한다. 알고리즘의 일반적 형태는 다음과 같이 쓸 수 있다.

$$\mathbf{x}_{k+1} = \mathbf{x}_k - \alpha_k \nabla f(\mathbf{x}_k)$$

여기서 $\alpha_k$는 스텝 크기(step size) 혹은 학습률(learning rate)이라고 불리는 양의 상수이다. 스텝 크기를 어떻게 정하는지에 따라 알고리즘의 수렴 속도와 안정성이 크게 달라진다. 단순히 고정된 스텝 크기를 사용하는 방법을 비롯하여, 선형 검색(line search) 기법이나, 입실론 감소 방식을 취하거나, 고급 기법으로는 볼프(Wolfe) 조건을 만족하는 방법 등이 사용된다.

특히 볼프 조건(Wolfe conditions)이나 골드스타인(Goldstein conditions) 등을 통해 스텝 크기를 합리적으로 찾음으로써 불필요한 반복을 줄이고, 동시에 알고리즘의 수렴 특성을 향상시킬 수 있다. 이러한 조건들은 보통 다음과 같은 형태의 불평등을 포함한다.

$$f(\mathbf{x}_k - \alpha_k \nabla f(\mathbf{x}_k)) \le f(\mathbf{x}_k) - c_1 \alpha_k \|\nabla f(\mathbf{x}_k)\|^2$$

또한 곡률 조건(curvature condition)이라 불리는

$$|\nabla f(\mathbf{x}_k - \alpha_k \nabla f(\mathbf{x}_k))^\top \nabla f(\mathbf{x}_k)| \le c_2 \|\nabla f(\mathbf{x}_k)\|^2$$

등의 조건이 추가로 들어가는데, 여기서 $c_1$과 $c_2$는 사전에 정해진 양의 상수(예: $0 < c_1 < c_2 < 1$)이다.

뉴턴(Newton) 방법과 이차 근사

무제약 최적화 문제에서 그래디언트 기반 방법의 확장으로 뉴턴(Newton) 방법이 널리 사용된다. 뉴턴 방법은 목적함수 $f(\mathbf{x})$를 국소적으로 이차 근사(quadratic approximation)하여, 그 근사 문제의 최소점을 해석적으로 찾아서 반복적으로 갱신하는 아이디어에 기반한다. 간단히 말해, 어떤 지점 $\mathbf{x}_k$ 근방에서 테일러 전개를 이용해

$$f(\mathbf{x}) \approx f(\mathbf{x}_k) + \nabla f(\mathbf{x}_k)^\top (\mathbf{x} - \mathbf{x}_k) + \tfrac{1}{2} (\mathbf{x} - \mathbf{x}_k)^\top \nabla^2 f(\mathbf{x}_k) (\mathbf{x} - \mathbf{x}_k)$$

와 같은 근사식을 만든다. 여기서 $\nabla^2 f(\mathbf{x}k)$는 헤시안(Hessian) 행렬이다. 그 후 위 근사식을 최소화하는 $\mathbf{x}$를 찾으면, $\mathbf{x}{k+1}$에 대한 점근적 방향이 주어진다. 결과적으로 다음과 같은 업데이트 공식을 얻게 된다.

$$\mathbf{x}_{k+1} = \mathbf{x}_k - \nabla^2 f(\mathbf{x}_k)^{-1} \nabla f(\mathbf{x}_k)$$

이때 $\nabla^2 f(\mathbf{x}_k)$가 양의 정부호(positive definite)라면, 위 공식은 정방행렬의 역행렬로 적절히 정의된다. 뉴턴 방법은 이론적으로 2차 수렴(quadratic convergence)을 나타내므로, 제대로 된 헤시안 정보를 정확히 계산할 수 있다면 반복 횟수가 적게 들고 빠르게 수렴한다는 장점이 있다.

그러나 고차원 문제에서는 헤시안 계산 비용과 역행렬 연산 비용이 매우 클 수 있다. 또한 문제가 비정부호(non-definite)인 헤시안을 갖거나, 희소(sparse) 구조를 갖지 않는다면, 직접적인 뉴턴 방법을 적용하기가 까다로워진다. 이러한 점을 개선하기 위해 다양한 변형 기법들이 개발되어 왔다.

준-뉴턴(Quasi-Newton) 방법

준-뉴턴(Quasi-Newton) 방법은 뉴턴 방법에서 요구되는 헤시안 $\nabla^2 f(\mathbf{x}_k)$의 정확한 계산을 대신하여, 반복 과정 중에 추정(approximation)하는 방식을 취한다. 그래디언트 정보만을 이용해 점진적으로 헤시안을 대체할 수 있는 행렬(또는 그 역행렬)을 갱신해나가는 접근이다. 이때 활용되는 대표적 알고리즘으로는 BFGS(Broyden–Fletcher–Goldfarb–Shanno)와 L-BFGS(Limited-memory BFGS), SR1(Symmetric Rank-1) 등이 있다.

가령 BFGS 방법은 헤시안의 역행렬을 근사하는 행렬 $\mathbf{H}_k$를 반복적으로 업데이트한다. 업데이트 공식은 대체로 아래와 같은 형태를 갖는다.

$$\mathbf{H}_{k+1} = \left(\mathbf{I} - \rho_k \mathbf{s}_k \mathbf{y}_k^\top\right) \, \mathbf{H}_k \, \left(\mathbf{I} - \rho_k \mathbf{y}_k \mathbf{s}_k^\top\right) + \rho_k \mathbf{s}_k \mathbf{s}_k^\top$$

여기서

$$\mathbf{s}_k = \mathbf{x}_{k+1} - \mathbf{x}_k, \quad \mathbf{y}_k = \nabla f(\mathbf{x}_{k+1}) - \nabla f(\mathbf{x}_k), \quad \rho_k = \dfrac{1}{\mathbf{y}_k^\top \mathbf{s}_k}$$

이다. 이러한 방식을 통해, 매 반복마다 적은 계산량으로 헤시안 역행렬 근사를 갱신할 수 있게 된다. L-BFGS는 메모리 사용량을 줄이기 위해 과거의 정보 중 일부만을 저장하고 갱신한다는 차이가 있으며, 특히 대규모 문제(수십만 차원 이상)에서도 효과적으로 적용되고 있다.

선형 대수적 고려와 수치적 안정성

준-뉴턴 방법을 비롯한 고급 최적화 기법에서는 선형 대수학의 수치적 안정성이 중요한 쟁점이 된다. 예컨대

$$\nabla^2 f(\mathbf{x}_k)^{-1}$$

의 직접 계산이 불안정해지거나, 업데이트되는 근사 행렬이 축적된 부동소수점 연산 오차로 인해 대칭성이 깨지는 등 문제가 발생할 수 있다. 이 때문에 알고리즘 내에서 수치 안정성을 보장하기 위한 보정 기법(correction technique)이 종종 사용된다. BFGS 행렬 갱신의 경우에도, 업데이트 과정에서 $\mathbf{y}_k^\top \mathbf{s}_k$가 매우 작아지는 현상이 발생하면 수치적 문제가 일어날 수 있으므로, 이를 보완하기 위한 다양한 실전 기법들이 제시되어 왔다.

이차 신뢰영역(Trust-region) 방법

뉴턴 계열 알고리즘은 선형 검색(line search)을 통해 스텝 크기를 조정하는 방식으로 접근한다. 그러나 다른 시각으로는, 각 반복에서 만들어지는 이차 근사 모델이 해당 근사식이 '신뢰할 수 있는' 범위 안에서만 의미가 있다고 가정한 뒤, 그 영역(보통 구(球) 형태)을 설정하고 그 내부에서만 최소점을 찾는 방법을 사용할 수도 있다. 이를 이차 신뢰영역(Trust-region) 방법이라고 한다.

이 방법에서의 핵심은, 현재 지점 $\mathbf{x}_k$ 근방에서의 이차 모델

$$m_k(\mathbf{p}) = f(\mathbf{x}_k) + \nabla f(\mathbf{x}_k)^\top \mathbf{p} + \tfrac{1}{2} \mathbf{p}^\top \mathbf{B}_k \mathbf{p}$$

를 정의하고, $|\mathbf{p}| \le \Delta_k$ 인 영역(여기서 $\Delta_k$는 트러스트 영역의 반경)에서 $m_k(\mathbf{p})$를 최소화하는 $\mathbf{p}$를 찾아서 $\mathbf{x}_{k+1} = \mathbf{x}_k + \mathbf{p}$로 설정한다. $\mathbf{B}_k$는 헤시안 또는 그 근사 행렬이 될 수 있다. 이때 $m_k(\mathbf{p})$를 실제로 최소화하는 과정에서는 적절한 근사 알고리즘(예: 이차 프로그래밍, 사전조건화된(preconditioned) 기법 등)이 쓰일 수 있으며, 매 반복마다 실제 목적함수 감소량과 이차 모델이 예측한 감소량을 비교하여 $\Delta_k$를 조절하게 된다.

수치해석적 관점에서, 이차 신뢰영역 방법은 선형 검색 기반의 뉴턴 방법보다 안정적으로 작동할 수 있다는 장점이 있다. 모델의 신뢰도가 낮으면 단계 폭 $\Delta_k$가 자동으로 줄어들어 과도한 이동을 막아 주고, 반대로 모델이 비교적 정확하다고 판단되면 $\Delta_k$를 늘려 넓은 영역을 탐색하게 한다.

비선형 제약 조건이 있는 경우의 접근

다양한 실전 최적화 문제에서는 $\mathbf{A}\mathbf{x} \le \mathbf{b}$, $\mathbf{C}\mathbf{x} = \mathbf{d}$와 같은 선형 제약이나, $g(\mathbf{x}) \le 0$, $h(\mathbf{x}) = 0$와 같은 비선형 제약 조건이 동시에 주어질 수 있다. 이때는 유제약(constrained) 최적화 방법론을 고려해야 하며, 대표적으로 내점점법(interior-point method), 활동제약집합(active set) 기법, 벌점(penalty) 혹은 장벽(barrier) 함수를 사용하는 접근 등이 있다.

활동제약집합 기법은 현재의 해에서 활성화(active)되어 있는 제약 조건들을 식별한 뒤, 효과적으로 국소적인 서브문제를 풀어가는 방법이다. 내점점법은 점이 제약 영역의 내부를 유지하면서 중심 경로(central path)를 따라 최적해로 접근하는 기법으로, 큰 차원에서도 비교적 효율적으로 작동한다. 벌점 혹은 장벽 함수 접근은 원래의 목적함수에 제약 위반 정도를 반영하는 항을 추가하여 무제약 최적화 형태로 변환한 뒤, 기존의 뉴턴 기반 기법 등을 사용할 수 있도록 한다.

전역 최적화(global optimization)와 지역 최적화(local optimization)

수치해석 관점에서 최적화 알고리즘은 주로 어떤 지역 최적해(local optimum)를 찾는 형태로 구현된다. 예컨대 그래디언트 하강법, 뉴턴 계열 방법 등은 현재 해 근방에서 목적함수를 감소시키는 방향으로 이동하면서, 결과적으로는 국소적으로 최적화된 지점에 수렴한다. 그러나 어떤 최적화 문제는 국소 최적이 다수 존재하고, 그 중 특정 지점이 전역 최적(global optimum)일 때 원하는 해를 찾기 위해서는 전역적 탐색 능력을 가진 알고리즘을 고려해야 한다.

전역 최적화 알고리즘은 다양한 방식으로 구현되지만, 대표적인 전략으로는 분기-한계(branch-and-bound), 준동형 기법, 전역적 탐색 휴리스틱 등이 있다. 분기-한계 방법은 해 공간을 여러 범위로 분할(분기)하며, 각 범위에 대해 목적함수의 상계 혹은 하계를 계산(한계)하여 더 이상 탐색할 필요가 없는 범위를 잘라내는 기법이다. 이렇게 하여 문제의 해 공간을 점진적으로 축소하면서 전역 해에 도달할 수 있다. 대체로 분기-한계 방법은 (준)선형, 이차, 혹은 특정 구조를 가진 문제에서 효과가 큰 편이다.

비구조적이고 비선형적이며 국소 최적이 많아 미분 기반의 탐색이 어려운 경우에는 휴리스틱(heuristic) 혹은 메타휴리스틱(meta-heuristic) 방법이 유용하게 쓰인다. 예컨대 유전 알고리즘(genetic algorithm), 입자 군집 최적화(particle swarm optimization), 담금질 모의(simulated annealing), 진화전략(evolution strategy) 같은 다양한 기법들이 제안되어 왔다. 이러한 알고리즘들은 확률적(probablistic) 요소와 진화적(evolutionary) 프로세스를 이용하여 전역적으로 영역을 탐색하면서, 점진적으로 해를 개선해 나간다.

확률적 최적화와 확률적 경사하강

데이터 과학 및 기계학습 분야에서는 목적함수가 통계적 특성을 갖거나, 샘플링을 통해 근사화되어 나타나는 경우가 빈번하다. 이때는 확률적 최적화 기법(stochastic optimization)이 사용된다. 대표적으로 확률적 경사 하강(stochastic gradient descent, SGD)은 대규모 데이터셋에 대해 평균 손실 함수를 최소화할 때, 전체 데이터의 그래디언트 대신 무작위로 선택된 소규모 배치(mini-batch) 데이터에 의한 근사 그래디언트를 활용하여 해를 갱신한다.

고전적인 SGD 업데이트 식은 다음과 같은 형태를 갖는다.

$$\mathbf{x}_{k+1} = \mathbf{x}_k - \alpha_k \nabla \widehat{f}(\mathbf{x}_k)$$

여기서 $\nabla \widehat{f}(\mathbf{x}_k)$는 일부 샘플 혹은 미니배치를 이용해 추정한 확률적 경사(gradient)이다. 학습률(learning rate) $\alpha_k$의 선택이나 변동 방식, 모멘텀(momentum) 또는 적응적(adaptive) 스텝 조정 기법(예: Adam, RMSProp, Adagrad 등)이 결합될 수 있다. 이러한 방식은 대규모 혹은 스트리밍 형태의 문제에서 매우 효과적이며, 전역 최적보다는 빠른 근사적 수렴에 초점을 두는 경향이 있다.

다목적 최적화(Multi-objective optimization)

현실 세계에서는 하나의 목적함수만 최소화 혹은 최대화하는 문제보다는, 여러 목표가 동시에 주어지는 다목적(multi-objective) 최적화 상황이 흔하다. 예를 들어, 비용과 품질, 또는 성능과 에너지 효율과 같은 상충 관계(trade-off)를 갖는 여러 지표를 동시에 고려해야 할 때가 있다.

수치해석적 접근에서는 각 목표를 가중합(weighted sum)으로 합쳐 단일 스칼라 형태로 만든 뒤, 일반적 최적화 기법을 적용할 수도 있고, 목표마다 서로 다른 제약을 두는 방식을 취하기도 한다. 가중합 접근은 구현이 간단하지만, 적절한 가중치 비율을 정하는 것이 쉽지 않을 수 있다. 또 다른 방법으로 파레토 최적(Pareto optimality) 개념을 직접 추적하여, 파레토 전선(front)를 구하는 알고리즘이 존재한다. 이를 위한 전형적인 방법으로 NSGA-II(Non-dominated Sorting Genetic Algorithm II) 같은 진화연산 기반의 휴리스틱이 많이 사용된다.

파레토 전선은 여러 목적함수들이 동시에 개선될 수 없는 지점들의 집합으로서, 각 점이 서로 우열관계에 있지 않다(즉, 한 점이 다른 점보다 한 가지 목적함수에 대해서는 더 우수하지만, 다른 목적함수에 대해서는 열등할 수 있다). 이런 맥락에서 다목적 최적화 문제를 수치해석적으로 접근하려면, 각 목적함수를 어떻게 정의하고 비교할지, 그리고 목표 간의 상충관계를 어떻게 정량화할지를 신중히 설정해야 한다.

복잡도와 병렬화(parallelization)

고차원 문제나 거대한 데이터 규모를 다루는 최적화에서는, 알고리즘의 계산 복잡도와 실행 시간을 제어하기 위해 병렬화(parallelization)가 매우 중요해진다. 예컨대 그래디언트 계산 또는 목적함수 평가 자체가 병렬화될 수 있는 구조라면, 클러스터나 GPU 등을 활용하여 반복 과정을 가속할 수 있다.

병렬화 가능성을 극대화하기 위해서는 알고리즘 설계 시 연산들 간의 데이터 의존성을 최소화해야 한다. 예를 들어, 확률적 최적화 기법들은 각 배치에서 병렬 처리를 진행하기에 비교적 유리하다. 그 밖에 분산(distributed) 환경에서 거대 규모의 스파스(sparse) 행렬 연산을 수행할 때, 통신량을 줄이고 로드 밸런싱(load balancing)을 최적화하는 것이 핵심 이슈로 등장한다. 이는 최적화 알고리즘이 단지 이론적으로만 설계되는 것이 아니라, 실질적인 컴퓨팅 자원 및 분산 시스템 아키텍처와 어떻게 결합되는지가 매우 중요함을 시사한다.

고차원 최적화와 차원 축소

최적화 문제에서 차원이 매우 높아지면, 기존 방법들이 갖는 국소 탐색 특성으로 인해 탐색 효율이 저하되는 현상이 발생한다. 이를 ‘차원의 저주(curse of dimensionality)’라고 하며, 국소 최적에 빠질 가능성이 커지는 동시에, 실제 계산 비용도 막대해진다. 이때 차원 축소(dimensionality reduction) 기술을 최적화 과정에 접목하는 시도가 이루어진다.

대표적으로 주성분 분석(PCA), 랜덤 투영(random projection), 오토인코더(autoencoder) 등으로 저차원 서브공간에 문제를 사상(mapping)하여, 그 공간에서의 최적해를 우선 구한 후, 다시 원본 공간으로 복원하여 근사적 해를 구하는 식이다. 수치해석적 관점에서는 차원 축소 과정에서의 근사 오차와, 축소된 문제에서의 최적점 구하기가 전체 성능에 얼마나 영향을 주는지 면밀히 분석해야 한다.

민감도 분석(sensitivity analysis)과 해석

최적화 문제의 해를 구한 뒤에는, 문제의 파라미터가 변동될 때 최적해가 어떻게 달라지는지 분석하는 일이 중요하다. 이를 민감도 분석(sensitivity analysis)이라고 부른다. 예를 들어 선형 계획법(linear programming) 문제

$$\min_{\mathbf{x} \in \mathbb{R}^n} \mathbf{c}^\top \mathbf{x}$$

subject to

$$\mathbf{A}\mathbf{x} \le \mathbf{b}, \quad \mathbf{x} \ge \mathbf{0}$$

이 있다고 하자. 이 문제의 최적해 $\mathbf{x}^$와 이와 대응하는 쌍대 변수(dual variable) $\boldsymbol{\lambda}^$가 구해졌을 때, 비용 벡터 $\mathbf{c}$나 우변 $\mathbf{b}$의 일부 성분이 변동하면 최적해가 어떻게 달라지는지, 혹은 어떤 조건하에서 최적해가 유지되는지 확인할 수 있다. 일반적으로 쌍대 변수는 해당 제약 조건을 느슨하게 혹은 엄격하게 만들었을 때, 목적함수가 얼마나 민감하게 변화하는지를 정량적으로 알려주는 역할을 한다.

민감도 분석은 단지 선형 최적화에서만 활용되는 것은 아니다. 비선형 최적화에서의 KKT(Karush-Kuhn-Tucker) 조건에서도 라그랑주 승수(Lagrange multiplier)는 제약 조건을 약간 변화시켰을 때 목적함수 값이 어떻게 변하는지에 대한 정보를 제공한다. 예컨대 비선형 유제약 문제

$$\min_{\mathbf{x} \in \mathbb{R}^n} f(\mathbf{x})$$

subject to

gi(x)≤0(i∈I),hj(x)=0(j∈E)[라인피드]g_i(\mathbf{x}) \le 0 \quad (i \in I), \quad h_j(\mathbf{x}) = 0 \quad (j \in E) [라인피드]

에서 라그랑주 승수를 $\lambda_i^$, $\mu_j^$라 하면, 최적점 $\mathbf{x}^*$에서 성립하는 KKT 조건은

$$\nabla f(\mathbf{x}^*) + \sum_{i \in I} \lambda_i^* \nabla g_i(\mathbf{x}^*) + \sum_{j \in E} \mu_j^* \nabla h_j(\mathbf{x}^*) = \mathbf{0}$$

과 같은 형태를 갖는다. 만일 $g_i(\mathbf{x}^)$가 활성화(active)되어 있어 엄밀히 등호로 성립한다면, $\lambda_i^$는 해당 제약의 민감도를 나타낸다. 이렇게 구한 라그랑주 승수들은 문제 설정이 변경될 때 최적해와 목적함수 값이 어떻게 움직일지 가늠해볼 수 있는 근거가 된다.

민감도 분석이 특히 중요한 이유는, 실제 환경에서는 모델에 쓰이는 계수나 데이터가 시간이 지남에 따라 변화하거나, 본질적으로 추정치일 수 있기 때문이다. 따라서 해가 조금씩 변동하더라도 큰 손실이 없도록 하는 해를 찾거나, 문제 파라미터 범위에 대한 신뢰구간을 설정하여 결과의 안정성을 확인하기도 한다.

로버스트(robust) 최적화와 불확실성 대응

현실 세계에서 모든 입력 데이터나 모델 파라미터가 완벽히 알려져 있지 않은 경우가 많다. 문제의 계수나 제약 조건에 불확실성이 존재한다면, 단순히 명시된 지표의 최적값을 찾기보다, 이러한 불확실성이 야기하는 리스크를 고려하여 의사 결정을 해야 한다. 이를 로버스트(robust) 최적화라고 한다.

로버스트 최적화에서의 전형적 접근은, 문제 데이터를 하나의 특정 값으로 간주하지 않고, 일정 범위나 확률 분포를 설정하는 것이다. 예컨대 선형 문제

$$\mathbf{c}^\top \mathbf{x}$$

subject to

$$\mathbf{A}\mathbf{x} \le \mathbf{b}$$

에서 $\mathbf{A}$와 $\mathbf{b}$가 정확히 정해져 있지 않고, 어떤 불확실성 집합 $\mathcal{U}$에 속해 있을 때, 모든 $(\mathbf{A}, \mathbf{b}) \in \mathcal{U}$에 대해 제약을 만족시키고 목적함수가 일정 수준 이하가 되도록 $\mathbf{x}$를 찾는 방식을 취한다. 즉

$$\min_{\mathbf{x}} \max_{(\mathbf{A}, \mathbf{b}) \in \mathcal{U}} \mathbf{c}^\top \mathbf{x}$$

subject to

$$\mathbf{A}\mathbf{x} \le \mathbf{b} \quad \forall (\mathbf{A}, \mathbf{b}) \in \mathcal{U}$$

같이 정식화될 수 있다. 이러한 문제는 보수적으로 보일 수 있으나, 의사 결정자가 사전에 허용 가능한 최악 상황(worst case)을 통제해 놓음으로써, 예측 불확실성이 큰 환경에서 더 안정적인 해를 얻는다.

또 다른 방식으로는 확률적 성질을 반영하여 확률적 제약(probabilistic constraint) 혹은 chance constraint 형태로 문제를 다룰 수도 있다. 예컨대 $P(\mathbf{A}\mathbf{x} \le \mathbf{b}) \ge 1 - \epsilon$ 같은 확률적 조건을 만족시키도록 $\mathbf{x}$를 결정한다. 이는 분포가 알려져 있거나, 적절한 샘플링으로 추정 가능한 경우에 주로 적용된다.

이산(discrete) 및 정수(integer) 최적화

지금까지 다룬 최적화는 대부분 연속(continuous) 변수를 상정했지만, 실제로는 변수 $\mathbf{x}$가 이산적(discrete)인 경우가 자주 발생한다. 예컨대 물류나 스케줄링 문제에서 트럭이나 기계의 배치 개수를 정수로 결정해야 할 수 있고, 그래프 이론에서 경로 선택이나 색칠 문제도 이산적 결정 구조를 갖는다.

이러한 이산 최적화 문제는 일반적으로 다음과 같은 형태를 갖는다.

$$\min_{\mathbf{x}} f(\mathbf{x})$$

subject to

$$\mathbf{A}\mathbf{x} \le \mathbf{b}, \quad \mathbf{x} \in \mathbb{Z}^n$$

등으로 나타낼 수 있다. $\mathbf{x}$가 모든 정수값을 허용할 수도 있고, 0-1(이진) 변수만을 허용하는 경우도 있다. 이를 정수 선형 계획(integer linear programming) 또는 혼합 정수 계획(mixed-integer linear programming, MILP) 등으로 분류한다. 이산 최적화는 연속 최적화보다 계산 난이도가 훨씬 높아지는 경향이 많으며, 일반적으로 NP-난해(NP-hard) 문제군에 속한다.

이산 최적화 문제를 풀기 위해서는 분기-한계(branch-and-bound)나 분할 평면(cutting plane) 기법 등이 광범위하게 사용된다. 분기-한계는 해 공간을 작은 부분문제로 분할(분기)하면서, 각 부분문제에 대한 상계(upper bound)나 하계(lower bound)를 구해 탐색을 배제할 것인지 결정(한계)하여 진행한다. 분할 평면 기법은 실수 해를 가지는 완화(relaxation) 문제로부터 일정한 불일치(violation)를 보이는 해를 깎아 내는 추가 제약(컷)을 생성함으로써, 점진적으로 정수 해만 남도록 유도한다.

현대에는 상업용 최적화 소프트웨어(CPLEX, Gurobi 등)에서 고성능의 혼합 정수 최적화 솔버가 제공되고 있으며, 다양한 휴리스틱 및 메타휴리스틱 기법도 개발되어 있다. 예컨대 유전 알고리즘, GRASP(Greedy Randomized Adaptive Search Procedure), 최소 충돌 탐색(min-conflicts search) 등이다. 대규모 이산 최적화에서는 문제 구조에 맞춘 휴리스틱이 실제로는 가장 빠르고 효율적인 경우도 많다.

동적 최적화와 제어

시변(time-varying) 환경이나 동적인 프로세스 제어에서, 최적화 문제는 시간 축을 포함한 동적(dynamical) 형태로 확장된다. 대표적인 예로 모델 예측 제어(MPC, Model Predictive Control)가 있다. 이는 시스템의 미래 동작을 예측 모델로 추정하면서, 일정 구간의 조작 변수(control variable) 스케줄을 결정하는 과정을 반복적으로 최적화하는 프레임워크다.

시스템의 동적 방정식이

$$\mathbf{x}_{t+1} = \mathbf{F}(\mathbf{x}_t, \mathbf{u}_t)$$

로 주어지고, 목적함수가 시간 축으로 적분(또는 합)된 형태

$$J = \sum_{t=0}^{T-1} L(\mathbf{x}_t, \mathbf{u}_t)$$

를 최소화하고자 할 때, $\mathbf{x}_t$는 상태(state), $\mathbf{u}_t$는 제어 입력(control input)이며, 상태 및 제어 변수에 대한 제약 조건(예: $\mathbf{x}_t \in \mathcal{X}, \mathbf{u}_t \in \mathcal{U}$)이 주어질 수 있다. 이를 해석적 혹은 수치적으로 풀어야 하고, 문제가 비선형이면 비선형 동적 계획법, 혹은 민첩한 실시간 최적화 기법을 동원해야 한다.

동적 최적화 문제는 상태 피드백, 잡음(noise), 외란(disturbance) 등이 존재하는 현실적 상황까지 고려하게 되므로, 로버스트 제어 이론 및 확률론적 제어 이론과도 밀접한 연관성이 있다. 특히 산업 현장에서는 대규모 공정에서 프로세스 효율을 높이거나 에너지를 절감하기 위해, 온라인(online) 최적화 기법이 빠른 샘플링 주기로 작동하도록 설계되고 있다.

결합 문제와 다분야 협업

최적화 문제에서 한 분야의 접근만으로는 해결하기 어려운 복합적인 상황이 흔히 등장한다. 예컨대 부분적으로는 연속 변수가, 다른 부분으로는 정수 변수가 들어가며, 동적 요인과 불확실성이 함께 작용할 수 있다. 이런 결합 문제(hybrid problem)는 전산 유체 역학(CFD), 전자회로 설계, 금융 리스크 관리, 공급망(supply chain) 설계 등 다양한 영역에서 나타난다.

다분야(multidisciplinary) 최적화(MDO, Multidisciplinary Design Optimization) 역시 서로 다른 물리나 수학적 모델이 상호 얽혀 있는 체계를 통합적으로 최적화하는 분야다. 항공우주나 자동차 산업에서의 설계 최적화가 대표적 예시이며, 구조해석, 유동해석, 열해석 등이 결합된 대규모 문제를 수치해석적으로 풀어야 한다. 이 경우 연산 자원이 방대하게 필요하고, 단일 알고리즘보다는 모듈 방식의 최적화 소프트웨어 및 분산 컴퓨팅을 활용한 협업이 이루어진다. 문제 설정 자체가 복잡해질수록, 최적화 전문가, 모델링 전문가, 컴퓨터 과학자 등이 함께 작업해야 한다.

볼록 최적화(convex optimization)와 확장

최적화 문제에서 볼록성(convexity)은 알고리즘적 단순화와 이론적 보장을 동시에 가져다주는 중요한 특성이다. 만일 목적함수가 볼록 함수(convex function)이고 제약 집합이 볼록 집합(convex set)이라면, 모든 국소 최적해가 전역 최적해이기도 하다는 점이 증명 가능하다. 또한 볼록 최적화 문제는 매우 풍부한 해석적·수치적 기법이 축적되어 있어, 고차원에서도 안정적이고 효율적인 알고리즘을 설계하기 상대적으로 용이하다.

예를 들어 2차 프로그램(quadratic program, QP)은 다음과 같은 형태로 쓸 수 있다.

$$\min_{\mathbf{x} \in \mathbb{R}^n} \tfrac{1}{2} \mathbf{x}^\top \mathbf{Q} \mathbf{x} + \mathbf{c}^\top \mathbf{x}$$

subject to

$$\mathbf{A}\mathbf{x} \le \mathbf{b},$$

여기서 행렬 $\mathbf{Q}$가 양의 반정부호(positive semidefinite)이면, 목적함수가 볼록이다. 선형 제약 또한 볼록 집합을 정의하므로, 이는 볼록 최적화로 분류된다. 이를 효율적으로 푸는 알고리즘으로는 내점점법(interior-point method), 이차 프로그래밍 전용 솔버 등이 있으며, 대규모 문제에서도 상당히 빠르게 수렴한다.

이보다 더 일반화된 형태로, 반정부호 행렬에 관한 제약을 포함하는 반정의 계획(semi-definite programming, SDP)이나, 콘 제약을 포함하는 2차 이하 콘 계획(second-order cone programming, SOCP) 등이 있다. 예컨대 반정의 계획에서의 제약은

$$\mathbf{X} \succeq \mathbf{0}$$

와 같은 형태로, 행렬 $\mathbf{X}$가 반정부호 행렬이 되도록 요구한다. 이러한 구조는 행렬 부호 조건이나 스펙트럴(spectral) 특성을 이용해야 하는 문제에서 자주 등장한다. 수치해석적으로는 메모리 사용량이 커질 수 있으나, 볼록 해석(convex analysis)에 기반한 범용 내점점법 알고리즘들이 잘 정립되어 있다.

비볼록(nonconvex) 문제와 볼록화(convexification)

실제 문제 중에는 목적함수나 제약 조건이 비볼록 구조를 띠어 복수의 지역 최적(local optimum)이 존재하고, 심지어 계산 복잡도가 매우 높아지는 경우가 흔하다. 이런 문제에 대해 볼록화(convexification) 기법이 연구되어 왔다. 볼록화란, 원래의 비볼록 문제를 다룰 수 있는 볼록 근사 문제로 치환하거나, 혹은 문제의 구조를 세분화하여 일부 구간에서 볼록 형태로 처리하는 방식 등을 말한다.

예컨대 정수계수, 혹은 0-1 변수로 인해 나타나는 이진적 비선형성이 있을 때, 선형 혹은 이차 이슈로 환원하기 위해 다양한 절단평면(cutting plane) 기법이나 분할 기법을 사용해 국소적으로 볼록집합을 근사화한다.

그 밖에, 유전 알고리즘이나 시뮬레이션 최적화 기법을 통해 전역 탐색을 수행하면서, 국소 구간에서는 볼록 최적화 알고리즘을 접목하는 하이브리드 접근도 시도된다. 예를 들어, 전역적인 탐색 단계에서 다소 거칠게 해 공간을 뒤진 다음, 일정 조건에서 ‘유망한’ 지점 근방을 볼록 근사로 다루어 세밀하게 수렴하는 전략이 그것이다.

대체모델(서로게이트, surrogate) 기법과 미분 불가능 문제

목적함수가 명시적인 수식으로 주어지지 않거나, 미분 계산이 불가능하거나, 혹은 실험·시뮬레이션을 통해서만 값을 얻을 수 있는 블랙박스(black-box) 구조를 띠는 경우가 있다. 이럴 때 파생된 기법 중 하나가 서로게이트(surrogate, 대체모델) 기반 최적화다.

서로게이트 기법은 고비용의 실제 함수 평가 대신, 비교적 저비용으로 근사할 수 있는 대체모델을 학습하여 그 모델 위에서 최적화를 수행한다. 대체모델로는 회귀나 신경망, 가우시안 프로세스(Gaussian process), 방사 기저함수(RBF) 등을 쓸 수 있으며, 목적함수 평가 횟수를 줄여도 빠른 근사적 수렴을 달성하려고 한다. 예를 들어, 베이지안 최적화(Bayesian optimization)는 가우시안 프로세스를 활용해, 불확실성이 큰 영역을 선별적으로 탐색하면서 기대 개선(expected improvement)을 극대화하는 지점을 찾는다.

미분 불가능 문제에 대해서는, 직접적인 그래디언트 정보를 구하기 어렵기 때문에, 유한 차분(finite difference) 등을 통해 근사하거나, 심지어 그래디언트가 존재하지 않아도 개선 가능한 방향을 찾는 기법(패턴 탐색, Nelder–Mead 단체(simplex) 방법 등)을 사용하기도 한다. 이들은 일반적으로 대규모 문제보다는 저차원 문제에서 잘 동작하지만, 문제 구조에 따라 효율적인 적용도 가능하다.

분산(distributed)·병렬(parallel)·클라우드 환경의 최적화

데이터가 매우 거대하거나(‘빅데이터’), 다수의 에이전트(agent)가 분산된 환경에서 협력 혹은 경쟁하여 최적 의사결정을 해야 하는 상황에서는, 분산(distributed) 혹은 병렬(parallel) 최적화 기법이 필수적이다. 예컨대 ADMM(Alternating Direction Method of Multipliers)은 분산된 형태로 볼록 최적화를 풀기에 적합한 알고리즘으로 널리 알려져 있다.

분산 환경에서 각 서브시스템 혹은 노드는 자신의 국소 목적함수와 제약을 부분적으로만 알고 있고, 전체 최적화를 위해서는 노드 간 통신과 협업이 필요하다. 이때 ADMM 절차는 라그랑주 승수 갱신과 국소 최적화 문제 풀이를 번갈아 수행하면서, 전체 시스템의 일관성을 맞추어준다. 클라우드 컴퓨팅이나 대규모 병렬 연산이 가능해진 현대 환경에서는 이러한 기법들이 실제로 적용되는 사례가 급증하고 있다.

GPU나 TPU와 같은 대규모 병렬 하드웨어도 딥러닝 분야에서 확률적 경사하강을 가속하기 위해 광범위하게 활용된다. 최근에는 단순한 행렬 연산뿐 아니라, 더 복잡한 최적화 루틴도 병렬화·벡터화(vectorization) 기법을 적극 활용하여 연산 효율을 획기적으로 끌어올리는 방향으로 발전 중이다.

고급 최적화 소프트웨어와 자동 미분

수치해석적 관점에서, 최적화 문제를 프로토타입 단계에서 검증하고 실제로 적용할 때는, 수많은 알고리즘과 접근 방식 중 하나를 직접 코딩하기보다, 이미 정평이 나 있는 전문 최적화 소프트웨어를 사용하기도 한다. 예컨대 상업용 솔버(예: CPLEX, Gurobi)는 선형·이차·혼합정수·이진 등 광범위한 문제 유형을 빠르고 견고하게 풀어준다. 학술적으로는 IPOPT(내점점법 기반의 비선형 최적화), SNOPT(제약된 비선형 최적화), Knitro 등이 널리 쓰인다.

동시에, 자동 미분(automatic differentiation, AD) 도구는 복잡한 계산 그래프(computational graph)를 가진 모델의 그래디언트와 헤시안을 정확하고 빠르게 구해준다. 기존에 수작업으로 미분 공식을 세우지 않아도 되므로, 최적화 알고리즘을 적용하는 데 드는 준비 시간이 크게 단축된다. 텐서플로(TensorFlow), 파이토치(PyTorch) 같은 딥러닝 프레임워크들은 자동 미분 엔진을 기반으로 GPU 병렬 처리까지 결합하여, 매우 규모가 큰 최적화 문제도 실시간에 가깝게 학습을 진행할 수 있게 만든다.

실전 튜닝과 구현 디테일

최적화 알고리즘을 이론적으로는 멋지게 설계해도, 실전 구현 단계에서는 여러 종류의 ‘튜닝(tuning)’ 노하우가 필요하다. 예를 들어:

• 스텝 크기나 학습률 스케줄을 어떻게 조절하는가.

• 중단 조건(stopping criteria)에서 정밀도(precision) 수준을 어디까지 요구할 것인가. 도메인 특화(특정 산업·기술 분야) 방식으로 초기 해를 어떻게 설정하거나 제약을 간소화할 것인가.

• 수치 불안정에 대한 예비 검사를 어떻게 진행할 것인가.

이 같은 세부적 이슈들은 수치해석에서의 경험적 지식과 함께, 문제 자체의 물리적·산업적 배경을 아우르는 융합적 이해가 있어야 제대로 풀린다. 예컨대 수렴 속도를 높이기 위해 각 변수의 크기나 단위를 적절히 스케일링(scaling)하여 전처리를 하거나, 중간 과정에서 조건수가 나빠지는 것을 막기 위해 사전조건화(preconditioning)를 수행하기도 한다.

이처럼 최적화 문제에서의 수치해석은 이론, 알고리즘, 구현 기법, 실제 적용 사례가 유기적으로 연결되어 있으며, 문제 규모나 성격에 따라 다른 해법이 요구된다. 끊임없이 새 알고리즘과 소프트웨어가 개발되는 이유도, 문제의 복잡성과 응용 분야가 워낙 광범위하기 때문이다.