7.80 최적화 문제의 정의와 분류

1. 최적화 문제의 일반 정의

수학적 최적화(mathematical optimization)는 주어진 제약 조건을 만족하는 결정 변수의 집합 중에서 목적 함수(objective function)를 최소화 또는 최대화하는 값을 찾는 문제이다. 일반적인 최적화 문제는 다음과 같이 정의된다.

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

\text{subject to} \quad g_i(\mathbf{x}) \leq 0, \quad i = 1, \ldots, m

h_j(\mathbf{x}) = 0, \quad j = 1, \ldots, p

여기서 \mathbf{x} \in \mathbb{R}^n은 결정 변수(decision variable) 벡터, f: \mathbb{R}^n \to \mathbb{R}은 목적 함수, g_i: \mathbb{R}^n \to \mathbb{R}은 부등식 제약 함수, h_j: \mathbb{R}^n \to \mathbb{R}은 등식 제약 함수이다. 최대화 문제 \max f(\mathbf{x})는 \min [-f(\mathbf{x})]로 변환할 수 있으므로, 일반성의 손실 없이 최소화 문제만을 고려한다.

2. 기본 용어

허용 영역(feasible region): 모든 제약 조건을 동시에 만족하는 점들의 집합이다.

\mathcal{F} = \{ \mathbf{x} \in \mathbb{R}^n : g_i(\mathbf{x}) \leq 0, \, \forall i; \; h_j(\mathbf{x}) = 0, \, \forall j \}

허용 해(feasible solution): \mathcal{F}에 속하는 임의의 점 \mathbf{x}이다.

전역 최적해(global optimum): \mathbf{x}^* \in \mathcal{F}가 모든 허용 점에 대해 f(\mathbf{x}^*) \leq f(\mathbf{x})를 만족하면, \mathbf{x}^*를 전역 최적해라 한다.

국소 최적해(local optimum): \mathbf{x}^*의 어떤 근방 \mathcal{N}(\mathbf{x}^*) 내의 모든 허용 점 \mathbf{x} \in \mathcal{F} \cap \mathcal{N}(\mathbf{x}^*)에 대해 f(\mathbf{x}^*) \leq f(\mathbf{x})를 만족하면, \mathbf{x}^*를 국소 최적해라 한다.

전역 최적해는 반드시 국소 최적해이지만, 그 역은 일반적으로 성립하지 않는다. 볼록 최적화 문제에서는 모든 국소 최적해가 전역 최적해이다.

3. 제약 조건에 의한 분류

3.1 비제약 최적화(Unconstrained Optimization)

제약 조건이 전혀 없는 문제로, \mathcal{F} = \mathbb{R}^n이다.

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

그래디언트가 영인 정류점(stationary point)에서 최적해의 후보가 결정되며, 헤시안 행렬의 정치성(definiteness)으로 극소, 극대, 안장점을 판별한다.

3.2 제약 최적화(Constrained Optimization)

등식 제약, 부등식 제약, 또는 양자가 동시에 존재하는 문제이다. 제약의 존재는 최적해를 허용 영역의 내부 또는 경계로 제한하며, 라그랑주 승수법, KKT(Karush-Kuhn-Tucker) 조건 등의 제약 처리 기법이 요구된다.

3.3 구간 제약 최적화(Box-Constrained Optimization)

결정 변수가 상하한 범위로만 제한되는 특수한 형태이다.

\mathbf{l} \leq \mathbf{x} \leq \mathbf{u}

로봇 관절 각도 한계가 대표적인 예이다. 구간 제약은 투영(projection)을 통해 효율적으로 처리할 수 있다.

4. 목적 함수의 성질에 의한 분류

4.1 선형 최적화(Linear Optimization)

목적 함수와 모든 제약 함수가 선형인 경우이다.

\min_{\mathbf{x}} \quad \mathbf{c}^T\mathbf{x} \quad \text{s.t.} \quad \mathbf{A}\mathbf{x} \leq \mathbf{b}, \; \mathbf{A}_{eq}\mathbf{x} = \mathbf{b}_{eq}

선형 계획법(linear programming, LP)이라고도 하며, 단체법(simplex method) 또는 내점법으로 효율적으로 풀 수 있다. 최적해는 허용 영역의 꼭짓점(vertex)에 존재한다.

4.2 이차 최적화(Quadratic Optimization)

목적 함수가 이차이고 제약 함수가 선형인 경우이다.

\min_{\mathbf{x}} \quad \frac{1}{2}\mathbf{x}^T\mathbf{H}\mathbf{x} + \mathbf{c}^T\mathbf{x} \quad \text{s.t.} \quad \mathbf{A}\mathbf{x} \leq \mathbf{b}, \; \mathbf{A}_{eq}\mathbf{x} = \mathbf{b}_{eq}

\mathbf{H}가 양의 반정치이면 볼록 이차 계획(convex QP)이 되어 전역 최적해를 효율적으로 구할 수 있다. 로봇 공학에서 역동역학, 전신 운동 제어, 모델 예측 제어 등에 광범위하게 활용된다.

4.3 볼록 최적화(Convex Optimization)

목적 함수가 볼록 함수이고, 허용 영역이 볼록 집합인 경우이다. 볼록 최적화의 핵심 성질은 모든 국소 최적해가 전역 최적해라는 점이며, 이는 다항 시간 내에 전역 최적해를 보장하는 효율적 알고리즘의 존재를 의미한다. 선형 계획법, 볼록 이차 계획법, 반정치 계획법(SDP), 원뿔 계획법(SOCP) 등이 볼록 최적화의 하위 범주에 속한다.

4.4 비선형 최적화(Nonlinear Optimization)

목적 함수 또는 제약 함수 중 하나 이상이 비선형인 일반적인 경우이다. 국소 최적해와 전역 최적해의 구별이 필수적이며, 대부분의 알고리즘은 국소 최적해만을 보장한다. 로봇 역기구학, 궤적 최적화, 파라미터 추정 등 로봇 공학의 핵심 문제 대다수가 비선형 최적화에 해당한다.

5. 변수의 성질에 의한 분류

5.1 연속 최적화(Continuous Optimization)

결정 변수가 연속 값을 취하는 경우이다. 미분 기반 방법(경사 하강법, 뉴턴법 등)의 적용이 가능하며, 본 서적에서 주로 다루는 범주이다.

5.2 이산 최적화(Discrete Optimization)

결정 변수가 정수 또는 이진 값과 같은 이산 값만을 취하는 경우이다. 조합 최적화(combinatorial optimization)라고도 하며, 로봇의 작업 순서 결정, 자원 할당 등에 나타난다. 일반적으로 NP-어려운(NP-hard) 문제에 속하여 대규모 문제에서는 근사 알고리즘이나 휴리스틱 방법이 사용된다.

5.3 혼합 정수 최적화(Mixed-Integer Optimization)

연속 변수와 이산 변수가 혼합된 문제이다. 로봇의 접촉 계획(contact planning)에서 접촉 여부(이진 변수)와 접촉력(연속 변수)을 동시에 최적화하는 경우가 대표적이다. 혼합 정수 이차 계획법(MIQP), 혼합 정수 비선형 계획법(MINLP) 등이 이 범주에 포함된다.

6. 결정론적 문제와 확률적 문제

6.1 결정론적 최적화(Deterministic Optimization)

목적 함수와 제약 함수의 모든 매개변수가 정확히 알려져 있는 경우이다. 문제의 구조가 확정적이므로 재현 가능한 최적해를 산출한다.

6.2 확률적 최적화(Stochastic Optimization)

목적 함수 또는 제약 함수에 불확실성이 포함된 경우이다. 기대값(expectation)을 최적화하거나, 확률적 제약(chance constraint)을 만족시키는 해를 구한다. 로봇의 센서 불확실성, 환경의 불확정성 등을 고려한 강건한 의사결정에 필수적이다.

6.3 강건 최적화(Robust Optimization)

불확실성이 구간이나 집합으로 기술되며, 최악의 경우(worst case)에 대해 최적화하는 접근법이다. 모델 불확실성이 있는 로봇 제어기의 설계에 적용된다.

7. 단일 목적과 다중 목적 최적화

7.1 단일 목적 최적화(Single-Objective Optimization)

하나의 스칼라 목적 함수를 최적화하는 문제이다.

7.2 다중 목적 최적화(Multi-Objective Optimization)

두 개 이상의 목적 함수를 동시에 최적화하는 문제이다.

\min_{\mathbf{x}} \quad [f_1(\mathbf{x}), f_2(\mathbf{x}), \ldots, f_k(\mathbf{x})]^T

일반적으로 모든 목적 함수를 동시에 최소화하는 단일 해는 존재하지 않으며, 파레토 최적해(Pareto optimal solution)의 집합을 구하는 것이 목표이다. 해 \mathbf{x}^*가 파레토 최적이란, 어떤 목적 함수도 다른 목적 함수의 값을 악화시키지 않고서는 개선할 수 없음을 의미한다. 로봇의 시간-에너지 상충, 정밀도-속도 상충 등이 다중 목적 최적화로 정식화된다.

8. 문제 규모에 의한 분류

8.1 소규모 문제

결정 변수의 수가 수십 이하인 문제로, 뉴턴법 등의 2차 정보 기반 알고리즘이 효과적이다. 역기구학, 소규모 파라미터 튜닝 등이 해당한다.

8.2 대규모 문제

결정 변수의 수가 수천에서 수백만에 이르는 문제이다. 궤적 최적화, 다체 시스템의 전신 운동 제어, 심층 신경망의 학습 등이 해당하며, 문제의 희소 구조(sparsity)를 활용하는 알고리즘이 필수적이다.

9. 로봇 공학에서의 최적화 문제 분류 체계

로봇 공학에서 발생하는 주요 최적화 문제를 분류하면 다음과 같다.

이러한 분류 체계는 각 문제에 적합한 알고리즘을 선택하는 데 기초적인 지침을 제공한다. 문제의 볼록성, 미분 가능성, 제약 구조, 규모 등이 알고리즘 선택의 핵심 기준이 된다.

10. 참고 문헌

• Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.
• Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.
• Bertsekas, D. P. (2016). Nonlinear Programming (3rd ed.). Athena Scientific.
• Bazaraa, M. S., Sherali, H. D., & Shetty, C. M. (2006). Nonlinear Programming: Theory and Algorithms (3rd ed.). Wiley.
• Betts, J. T. (2010). Practical Methods for Optimal Control and Estimation Using Nonlinear Programming (2nd ed.). SIAM.

version: 1.0