397.55 제약 기반 다목적 최적화

1. 개요

제약 기반 다목적 최적화(constraint-based multi-objective optimization)는 다목적 최적화 문제에서 복수의 목적 함수 중 하나를 주 목적(primary objective)으로 선정하고, 나머지 목적 함수들을 상한 제약(upper bound constraint)으로 변환하여 단일 목적 제약 최적화 문제로 환원하는 스칼라화 기법이다. 대표적 방법인 ε-제약법(ε-constraint method)은 Haimes, Lasdon, Wismer(1971)에 의해 도입되었으며, 가중합 방법과 달리 비볼록(non-convex) 파레토 전선에도 적용 가능하다는 이론적 장점을 갖는다.

로봇 임무 계획에서 제약 기반 다목적 최적화는 “에너지 소모를 특정 임계값 이하로 유지하면서 임무 시간을 최소화하라”, “위험 노출을 일정 수준 이하로 제한하면서 커버리지를 최대화하라“와 같은 자연스러운 제약 형태의 임무 요구사항을 직접적으로 반영할 수 있다.

2. ε-제약법의 수학적 정식화

2.1 기본 형태

k개의 목적 함수 f_1(\mathbf{x}), f_2(\mathbf{x}), \ldots, f_k(\mathbf{x})를 동시에 최소화하는 다목적 문제에 대해, ε-제약법은 하나의 목적 함수(예: f_1)를 주 목적으로 설정하고, 나머지 (k-1)개의 목적 함수를 제약 조건으로 변환한다:

\min_{\mathbf{x} \in \mathcal{X}} f_1(\mathbf{x})

\text{subject to} \quad f_i(\mathbf{x}) \leq \epsilon_i, \quad i = 2, 3, \ldots, k

여기서 \epsilon_i는 i번째 목적 함수에 대한 상한값이다. \epsilon_i의 체계적 변동을 통해 파레토 전선의 서로 다른 영역을 탐색할 수 있다.

2.2 ε 값의 범위 결정

각 \epsilon_i의 유효 범위는 개별 최적화를 통해 결정된다. i번째 목적의 이상값(ideal value)과 나디르값(nadir value)은 각각:

f_i^{\min} = \min_{\mathbf{x} \in \mathcal{X}} f_i(\mathbf{x}), \quad f_i^{\max} = \max_{\mathbf{x}^* \in \mathcal{P}_S} f_i(\mathbf{x}^*)

이며, \epsilon_i는 [f_i^{\min}, f_i^{\max}] 구간 내에서 변동된다. 이 구간을 N_i등분하면:

\epsilon_i^{(j)} = f_i^{\min} + \frac{j}{N_i} (f_i^{\max} - f_i^{\min}), \quad j = 0, 1, \ldots, N_i

k-목적 문제에서 \prod_{i=2}^{k} (N_i + 1)개의 ε-제약 문제를 풀어야 하므로, 목적 함수의 수 k가 증가하면 탐색 비용이 지수적으로 증가한다.

3. 이론적 성질

3.1 파레토 최적성 보장

정리 (필요 조건): 해 \mathbf{x}^*가 파레토 최적이면, 적절한 ε 값에 대해 \mathbf{x}^*는 해당 ε-제약 문제의 최적해이다.

정리 (충분 조건): ε-제약 문제의 유일한 최적해는 원래 다목적 문제의 파레토 최적해이다. 유일하지 않은(비유일) 최적해의 경우, 약 파레토 최적(weakly Pareto-optimal)하지만 파레토 최적이 아닐 수 있다.

이를 보완하기 위해, Mavrotas(2009)는 부 목적 함수를 주 목적 함수에 사전식(lexicographic)으로 추가하는 증강 ε-제약법(augmented ε-constraint method, AUGMECON)을 제안하였다:

\min_{\mathbf{x} \in \mathcal{X}} f_1(\mathbf{x}) - \delta \sum_{i=2}^{k} \frac{s_i}{r_i}

\text{subject to} \quad f_i(\mathbf{x}) + s_i = \epsilon_i, \quad s_i \geq 0, \quad i = 2, \ldots, k

여기서 s_i는 잉여 변수(surplus variable), r_i = f_i^{\max} - f_i^{\min}은 정규화 범위, \delta는 충분히 작은 양수이다. 이 증강 형태는 약 파레토 해를 제거하고 정확한 파레토 해만 생성한다.

3.2 비볼록 파레토 전선에서의 완전성

ε-제약법의 핵심적 장점은 비볼록 파레토 전선의 모든 파레토 해를 원칙적으로 도출할 수 있다는 것이다. 가중합 방법이 볼록 포락선(convex hull) 위의 해만 도출하는 것과 대비적이다. 이는 ε-제약 문제의 실행 가능 영역이 초평면이 아닌 초사각형(hyperbox)으로 정의되기 때문이다.

4. 로봇 임무 계획에의 적용

4.1 에너지 제약 하의 경로 최적화

이동 시간 최소화를 주 목적으로, 에너지 소모를 제약으로 설정하는 로봇 경로 계획 문제를 고려하자:

\min_{\pi} T(\pi)

\text{subject to} \quad E(\pi) \leq \epsilon_E

여기서 T(\pi)는 경로 \pi의 총 이동 시간, E(\pi)는 경로의 총 에너지 소모, \epsilon_E는 허용 에너지 상한(예: 배터리 잔량의 안전 마진)이다.

이 문제는 자원 제약 최단 경로 문제(Resource-Constrained Shortest Path Problem, RCSPP)의 형태를 가지며, NP-난해(NP-hard)하지만 쌍대점 열거(label-setting) 알고리즘이나 라그랑주 완화(Lagrangian relaxation)를 통해 효율적으로 근사 해를 도출할 수 있다.

4.2 위험 제약 하의 다중 로봇 순찰

다중 로봇 순찰 문제에서, 총 커버리지 최대화를 주 목적으로 하고, 각 로봇의 위험 노출을 개별 제약으로 설정한다:

\max_{\mathbf{A}} C(\mathbf{A})

\text{subject to} \quad R_r(\mathbf{A}) \leq \epsilon_R, \quad \forall r \in \mathcal{R}

여기서 C(\mathbf{A})는 할당 \mathbf{A}에 따른 총 영역 커버리지, R_r은 로봇 r의 누적 위험 노출이다.

4.3 LTL 명세 하의 제약 기반 최적화

형식 임무 명세(LTL) 만족을 전제 조건으로 하고, 복수의 비용 기준 중 하나를 주 목적, 나머지를 제약으로 설정하는 문제는 다음과 같다:

\min_{\rho \in \mathcal{L}(\mathcal{P})} J_1(\rho)

\text{subject to} \quad J_i(\rho) \leq \epsilon_i, \quad i = 2, \ldots, k

여기서 \mathcal{L}(\mathcal{P})는 제품 오토마톤 \mathcal{P}의 수락 실행 집합이다. 이 문제는 자원 제약 래소 경로 탐색으로 환원되며, 제품 오토마톤의 간선에 다중 비용 레이블을 부여하여 탐색한다.

5. 라그랑주 완화 기반 해법

5.1 라그랑주 이중 문제

ε-제약 문제의 제약을 라그랑주 승수(Lagrange multiplier) \lambda_i \geq 0으로 완화하면 다음의 라그랑주 이중 문제(Lagrangian dual problem)를 얻는다:

\max_{\boldsymbol{\lambda} \geq 0} \min_{\mathbf{x} \in \mathcal{X}} \left[ f_1(\mathbf{x}) + \sum_{i=2}^{k} \lambda_i (f_i(\mathbf{x}) - \epsilon_i) \right]

라그랑주 완화는 제약을 벌칙(penalty)으로 변환하여 풀기 어려운 제약 문제를 비제약 문제로 근사한다. 이중 함수(dual function)의 최대화는 부분 경사법(subgradient method)을 통해 수행된다.

5.2 부분 경사 갱신

라그랑주 승수의 부분 경사 갱신 규칙은 다음과 같다:

\lambda_i^{(t+1)} = \max\left(0, \lambda_i^{(t)} + \alpha^{(t)} (f_i(\mathbf{x}^{(t)}) - \epsilon_i)\right)

여기서 \alpha^{(t)}는 t-번째 반복에서의 스텝 크기이다. 스텝 크기의 선택은 수렴 속도에 영향을 미치며, Polyak(1969)의 스텝 크기 규칙이 흔히 사용된다:

\alpha^{(t)} = \frac{z^{\text{UB}} - L(\boldsymbol{\lambda}^{(t)})}{\left\| \mathbf{g}^{(t)} \right\|^2}

여기서 z^{\text{UB}}는 실행 가능 해의 목적값(상한), L(\boldsymbol{\lambda}^{(t)})는 현재 이중 목적값, \mathbf{g}^{(t)}는 부분 경사 벡터이다.

6. 목표 계획법(Goal Programming)

6.1 기본 형태

목표 계획법(goal programming)은 각 목적 함수에 대해 달성하고자 하는 목표값(target value) t_i를 설정하고, 목표로부터의 편차(deviation)를 최소화하는 방법이다:

\min_{\mathbf{x} \in \mathcal{X}} \sum_{i=1}^{k} \left( w_i^+ d_i^+ + w_i^- d_i^- \right)

\text{subject to} \quad f_i(\mathbf{x}) - d_i^+ + d_i^- = t_i, \quad d_i^+, d_i^- \geq 0

여기서 d_i^+와 d_i^-는 각각 양 편차(초과)와 음 편차(미달), w_i^+와 w_i^-는 편차에 대한 가중치이다.

6.2 사전식 목표 계획법

사전식 목표 계획법(lexicographic goal programming)은 목표를 우선순위 수준(priority level)으로 계층화하고, 상위 수준의 목표를 먼저 최적화한 후 하위 수준의 목표를 순차적으로 최적화한다. 상위 수준의 최적성을 유지하면서 하위 수준의 편차를 최소화하므로, 목표 간 명확한 우선순위가 존재하는 임무에 적합하다.

6.3 로봇 임무에의 적용

로봇 임무 계획에서 목표 계획법은 다음과 같이 적용된다:

• 1순위: 안전성 — 위험 노출 편차를 0으로 유지
• 2순위: 임무 완수 — 과업 미수행 편차를 최소화
• 3순위: 효율성 — 에너지 과소모 편차를 최소화

이 계층 구조를 통해 안전을 최우선으로 보장하면서 임무 완수와 효율성을 순차적으로 추구하는 계획이 생성된다.

7. 물리적 실현법(Physical Programming)

Messac(1996)이 제안한 물리적 실현법은 각 목적 함수에 대해 선호 영역(preference region)을 정의하여 목적값의 바람직한 정도를 연속적으로 표현하는 방법이다. 선호 영역은 다음의 범주로 분류된다:

1. 극히 바람직함(Highly Desirable): 목적값이 이상적 수준에 있는 범위
2. 바람직함(Desirable): 수용 가능한 범위
3. 수용 가능(Tolerable): 최소한의 수준
4. 수용 불가(Undesirable): 허용되지 않는 범위
5. 극히 수용 불가(Highly Undesirable): 절대적으로 배제해야 하는 범위

각 선호 영역에 기반하여 클래스 함수(class function)를 구성하고, 이를 합산한 집계 함수(aggregate function)를 최소화한다. 이 방법은 운영자가 물리적 단위로 선호를 표현할 수 있어 직관적이며, 무차원 가중치의 결정 문제를 회피한다.

8. 계산 복잡도와 확장성

8.1 ε-제약법의 계산 비용

k-목적 문제에 대해 각 부 목적의 ε 범위를 N등분하면, 총 N^{k-1}개의 제약 최적화 문제를 풀어야 한다. 각 단일 제약 문제의 복잡도가 C_1이면, 총 계산 비용은 O(N^{k-1} \cdot C_1)이다.

다목적 문제의 목적 수가 4 이상인 경우, 체계적 ε 스캔은 비실용적이 되며, 적응적(adaptive) 탐색 전략이 필요하다.

8.2 효율적 탐색 전략

1. 적응적 ε 선택: 이미 탐색된 파레토 해에 기반하여 파레토 전선의 희소 영역에 ε 값을 집중 배치한다.
2. 병렬화: 각 ε-제약 문제는 독립적이므로, 대규모 병렬 컴퓨팅을 통해 동시에 풀 수 있다.
3. 조기 중단(Early termination): 비실행 가능(infeasible)한 ε 조합을 사전에 식별하여 불필요한 계산을 방지한다.
4. AUGMECON2: Mavrotas, Florios(2013)가 제안한 개선된 증강 ε-제약법으로, 비실행 가능 영역의 자동 탐지와 파레토 해의 효율적 열거를 지원한다.

9. 참고 문헌

• Haimes, Y.Y., Lasdon, L.S., Wismer, D.A. (1971). “On a Bicriterion Formulation of the Problems of Integrated System Identification and System Optimization.” IEEE Transactions on Systems, Man, and Cybernetics, 1(3), pp. 296–297.
• Messac, A. (1996). “Physical Programming: Effective Optimization for Computational Design.” AIAA Journal, 34(1), pp. 149–158.
• Mavrotas, G. (2009). “Effective Implementation of the ε-Constraint Method in Multi-Objective Mathematical Programming Problems.” Applied Mathematics and Computation, 213(2), pp. 455–465.
• Mavrotas, G., Florios, K. (2013). “An Improved Version of the Augmented ε-Constraint Method (AUGMECON2) for Finding the Exact Pareto Set in Multi-Objective Integer Programming Problems.” Applied Mathematics and Computation, 219(18), pp. 9652–9669.
• Polyak, B.T. (1969). “Minimization of Unsmooth Functionals.” USSR Computational Mathematics and Mathematical Physics, 9(3), pp. 14–29.
• Miettinen, K. (1999). Nonlinear Multiobjective Optimization. Springer.

버전: 2026-03-24
출처: Robotics Engineering 서적, Volume 9, Part 53, Chapter 397