최적화 문제

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 최적화 문제의 정의
3. 최적화 문제의 분류
4. 연속 최적화 알고리즘
- 4.1. 도함수 기반 알고리즘 (경사 하강법)
- 4.2. 도함수 미사용 알고리즘
5. 이산 최적화 알고리즘
6. 계산 복잡도
7. 최적화 문제의 역사
참조

1. 개요

최적화 문제는 주어진 조건 내에서 목적 함수의 값을 최소 또는 최대화하는 문제로, 수학적 모델링을 통해 해결된다. 최적화 문제는 목적 함수, 제약 조건, 실행 가능 영역 등으로 구성되며, 고려하는 공간, 제약 조건의 유무, 목적 함수와 제약 조건의 형태, 연속/이산 여부에 따라 다양하게 분류된다. 해결 방법으로는 함수의 기울기를 이용하는 경사 하강법과 같은 도함수 기반 알고리즘과, 넬더-미드 방법과 같은 도함수를 사용하지 않는 알고리즘, 그리고 조합 최적화 문제 해결을 위한 알고리즘 등이 있다. 최적화 기법은 카를 프리드리히 가우스의 최급강하법에서 시작하여, 조지 단치히의 선형 계획법 개발을 통해 현대적인 이론이 정립되었다.

2. 최적화 문제의 정의

최적화 문제는 주어진 함수 f^영어: A → ℝ에 대해, 다음 조건을 만족하는 x₀ ∈ A를 찾는 문제이다.^[5]

: $x_0 \in A: \forall x \in A,\ f(x_0) \le f(x)$ (최소화 문제)

: $x_0 \in A: \forall x \in A,\ f(x_0) \ge f(x)$ (최대화 문제)

여기서,

f^영어는 '''목적 함수'''(objective function, cost function)라고 불리며, 최소화 또는 최대화하고자 하는 대상을 나타내는 함수이다.^[3]
$x$ 는 찾아야 할 변수이고, 집합 $A$ 는 '''제약 조건'''(constraint)을 만족하는 변수 $x$ 의 집합을 의미한다.^[3]
제약 조건의 집합 $A$ 를 '''실행 가능 영역'''(feasible region) 또는 '''허용 영역'''이라고 하며, 이 영역 내의 원소를 '''실행 가능해'''(feasible solution) 또는 '''가능해'''라고 한다.^[6]
목적 함수를 최소 또는 최대로 하는 실행 가능해를 (전역적) 최소해, 최대해라고 하며, 이때의 목적 함수 값을 최소값, 최대값이라고 한다. 최소해와 최대해를 통틀어 '''최적해'''(optimal solution)라고 부른다.^[7]

최대화 문제는 목적 함수에 덧셈의 역원(부호 반전)을 적용하여 최소화 문제로 변환할 수 있다. 즉,

\max f(x) = \min (-f(x))

와 같이 표현하여 최소화 알고리즘을 적용할 수 있다.^[5]

3. 최적화 문제의 분류

최적화 문제는 다양한 기준에 따라 분류될 수 있다.

크게 목적 함수와 제약 조건의 종류에 따라 여러 문제 클래스로 나눌 수 있다.^[2] 세부적으로, 조합 최적화 문제는 다음과 같은 네 가지 요소로 구성된다.

'''I''': 인스턴스들의 집합
'''f(x)''': 인스턴스 x ∈ I 가 주어지면, 실행 가능한 해들의 집합
'''m(x, y)''': 인스턴스 x와 x의 실행 가능한 해 y가 주어지면, y의 측도 (일반적으로 양수 실수)
'''g''': 목표 함수 (최소: min, 최대: max)

여기서 목표는 어떤 인스턴스 x에 대해 ''최적 해''를 찾는 것이다. 즉, 다음을 만족하는 실행 가능한 해 y를 찾는 것이다.

:m(x, y) = g{ m(x, y') : y' ∈ f(x) }

각 조합 최적화 문제에 대해, 특정 측도 m₀에 대한 실행 가능한 해가 있는지 묻는 해당 결정 문제가 존재한다. 예를 들어, 정점 u와 v를 포함하는 그래프 G가 있는 경우, 최적화 문제는 "u에서 v까지 가장 적은 수의 간선을 사용하는 경로를 찾아라"가 될 수 있다. 이 문제의 답은 4가 될 수 있다. 해당 결정 문제는 "10개 이하의 간선을 사용하는 u에서 v까지의 경로가 있는가?"가 될 것이며, 이 문제는 간단한 '예' 또는 '아니요'로 대답할 수 있다.

근사 알고리즘 분야에서는 어려운 문제에 대한 근사 최적 해를 찾도록 알고리즘이 설계된다. 일반적인 결정 버전은 허용 가능한 해만 지정하므로 문제의 부적절한 정의가 된다. 적절한 결정 문제를 도입할 수도 있지만, 이 문제는 최적화 문제로 더 자연스럽게 특징지어진다.^[2]

3. 1. 고려하는 공간에 따른 분류

고려하는 집합 A가 포함된 공간에 따라 무한 차원과 유한 차원의 문제로 크게 나뉜다. A가 함수 공간에 포함되는 경우 무한 차원의 최적화 문제가 되며, 변분 문제와 최적 제어 문제가 대표적이다.^[1] A가 유클리드 공간에 포함되는 경우 유한 차원의 최적화 문제가 된다.^[1]

3. 2. 제약 조건 유무에 따른 분류

연속 최적화 문제의 표준형은 다음과 같다.^[1]

:\underset{x}{\operatorname{minimize}} f(x)

:\operatorname{subject\;to} g_i(x) \leq 0, \quad i = 1,\dots,m

:h_j(x) = 0, \quad j = 1, \dots,p

여기서

f : ℝⁿ → ℝ는 n-변수 벡터 x에 대해 최소화될 목적 함수이고,
g_i(x) ≤ 0는 부등식 제약 조건이라고 하며,
h_j(x) = 0는 등식 제약 조건이라고 한다.

만약 m = p = 0 이면, 제약 조건이 없는 최적화 문제이다. 최적화 문제는 고려하는 집합 A가 포함된 공간에 따라 무한 차원과 유한 차원의 문제로 크게 나뉜다. 또한 A가 전체 공간과 같이 실질적으로 제약 조건이 없는 문제는 무제약 문제(제약 없음 문제)가 되며, 그렇지 않은 경우는 유제약 문제(제약 조건 있는 문제)가 된다.

3. 3. 목적 함수와 제약 조건의 형태에 따른 분류 (유한 차원)

목적 함수와 제약 조건의 형태에 따라 최적화 문제는 다음과 같이 분류할 수 있다.

'''선형 계획법''': 목적 함수가 1차식으로 표현되고, 제약 조건이 일차 방정식 및 일차 부등식으로 정의되는 경우이다.
'''정수 계획법''': 선형 계획법 중 일부 변수가 정수 값만 가질 수 있도록 제한되는 경우이다.
'''이차 계획법''': 목적 함수가 이차식으로 정의되고, 제약 조건이 일차 방정식 및 일차 부등식으로 정의되는 경우이다.
'''볼록 계획법''': 목적 함수가 볼록 함수이고, 제약 조건의 집합도 볼록 집합인 경우이다.
'''반정부호 계획법''': 반정부호 행렬을 변수로 하는 볼록 계획법의 일종이다.
'''비선형 계획법''': 목적 함수 또는 제약 조건에 비선형적인 항이 포함된 경우이다.

3. 4. 연속/이산 여부에 따른 분류

최적화 문제는 목적 함수와 제약 조건의 종류에 따라 여러 문제 클래스로 나눌 수 있는데, 변수가 연속적인 값을 가지는지, 이산적인 값을 가지는지에 따라 다음과 같이 분류할 수 있다.^[2]

'''연속 최적화 문제''': 변수가 연속적인 값을 가지는 문제이다.
'''이산 최적화 문제''' ('''조합 최적화 문제'''): 변수가 이산적인 값을 가지는 문제이다. 정수 계획법 등이 이에 해당한다.

4. 연속 최적화 알고리즘

연속 최적화 문제(continuous optimization problem^영어)는 제약 조건의 집합이 유클리드 공간 $\mathbb{R}^n$ 의 부분 집합인 문제이다.

무제약 문제를 해석적으로 풀 때는 최적성의 필요 조건(편미분을 취하여 0)을 만족하는 점에 최소해가 있다. 속박 조건이 있는 경우에는 라그랑주 승수법을 사용할 수 있다.

Mathematica의 FindMinimum 기본 설정은 다음과 같다.^[8]^[9]^[10]

제약 조건이 있는 경우: 내점법
목적 함수가 제곱합인 경우: 레벤베르크-마쿼트법
그 외 (250차원 미만): BFGS법
250차원 이상: L-BFGS법

4. 1. 도함수 기반 알고리즘 (경사 하강법)

함수의 기울기(도함수) 정보를 활용하여 최적해를 찾아가는 방법이다.^[1]

선형 탐색과 신뢰 영역은 경사 하강법의 대표적인 두 가지 프레임워크이다.
최급강하법은 가장 기본적인 경사 하강법이다.
확률적 경사 하강법은 최급강하법의 온라인 학습 버전으로, 신경망 등에서 사용된다.
AdaGrad는 학습률을 자동으로 조정한다.
RMSProp
Adam
켤레 기울기법
쌍 켤레 기울기법
비선형 켤레 기울기법
뉴턴법
준 뉴턴법
DFP법
BFGS법
BHHH법
SR1법
기억 제한 준 뉴턴법은 대규모(고차원) 문제에 적합하다.
L-BFGS
L-BFGS-B는 L-BFGS에 정의역의 경계를 지정할 수 있도록 한 것이다.
OWL-QN은 L-BFGS에서 목적 함수에 L1 정규화 항이 붙은 형태에 대응할 수 있도록 한 것이다.
가우스-뉴턴법은 비선형 최소 자승법 문제(제곱합의 최적화 문제)를 푸는 데 사용된다.
레벤베르크-마쿼트법
내점법은 제약 조건이 있는 문제에 대해, 실행 가능 영역 내부에서 최적해를 찾아가는 방법이다.

4. 2. 도함수 미사용 알고리즘

다음은 함수의 도함수 정보를 사용하지 않고 최적해를 찾는 방법이다.

넬더-미드 방법: 심플렉스를 이용하는 방법이다.
[좌표 하강법](https://en.wikipedia.org/wiki/Coordinate_descent): 각 변수 축 방향으로 번갈아 가며 최적화하는 방법이다.
[적응 좌표 하강법](https://en.wikipedia.org/wiki/Adaptive_coordinate_descent)
블록 좌표 하강법(block coordinate descent)
[마이클 J. D. 파월](https://en.wikipedia.org/wiki/Michael_J._D._Powell) 개발
[파월 방법](https://en.wikipedia.org/wiki/Powell%27s_method): 켤레 방향을 이용하는 방법이다.
[BOBYQA](https://en.wikipedia.org/wiki/BOBYQA) - 비선형 함수와 파라미터의 값 영역에 대한 제약
[LINCOA](https://en.wikipedia.org/wiki/LINCOA) - 비선형 함수와 선형 제약 조건
[COBYLA](https://en.wikipedia.org/wiki/COBYLA) - 비선형 함수와 비선형 제약 조건
[TOLMIN (optimization software)](https://en.wikipedia.org/wiki/TOLMIN_%28optimization_software%29)
[UOBYQA](https://en.wikipedia.org/wiki/UOBYQA)
[NEWUOA](https://en.wikipedia.org/wiki/NEWUOA)
진화 전략
CMA-ES
[자연 진화 전략](https://en.wikipedia.org/wiki/Natural_evolution_strategy)
[차분 진화](https://en.wikipedia.org/wiki/Differential_evolution): 생물의 진화 과정을 모방하여 최적해를 찾는 방법이다.

Mathematica의 NMinimum의 기본 설정은 선형 계획 문제의 경우 심플렉스법을 사용하고, 정수 파라미터가 있는 경우 등은 차분 진화를 사용하며, 그 외에는 넬더-미드 방법을 사용한다.

5. 이산 최적화 알고리즘

이산 최적화 문제(영어: discrete optimization problem)는 제약 조건 집합 A가 $\mathbb{Z}^n$ 의 부분 집합인 문제이다. 자세한 내용은 조합 최적화를 참조하면 된다.

6. 계산 복잡도

형식적으로, 조합 최적화 문제 ''A''는 ''(I, f, m, g)'' 네 가지 요소로 구성된다.^[2]

''I''는 인스턴스들의 집합이다.
인스턴스 ''x'' ∈ ''I''가 주어지면, ''f''(''x'')는 실행 가능한 해들의 집합이다.
인스턴스 ''x''와 ''x''의 실행 가능한 해 ''y''가 주어지면, ''m''(''x'', ''y'')는 ''y''의 측도를 나타내며, 일반적으로 양수 실수이다.
''g''는 목표 함수이며, min 또는 max이다.

목표는 어떤 인스턴스 ''x''에 대해 ''최적 해''를 찾는 것이다. 즉, 다음과 같은 실행 가능한 해 ''y''를 찾는 것이다.

: ''m''(x, y) = g{ ''m''(x, y') : y' ∈ ''f''(x) }.

각 조합 최적화 문제에 대해, 특정 측도 ''m''₀에 대한 실행 가능한 해가 있는지 묻는 해당 결정 문제가 존재한다.^[2] 예를 들어, 정점 ''u''와 ''v''를 포함하는 그래프 ''G''가 있는 경우, 최적화 문제는 "''u''에서 ''v''까지 가장 적은 수의 간선을 사용하는 경로를 찾아라"가 될 수 있다. 이 문제의 답은 4가 될 수 있다. 해당 결정 문제는 "10개 이하의 간선을 사용하는 ''u''에서 ''v''까지의 경로가 있는가?"가 될 것이다. 이 문제는 간단한 '예' 또는 '아니요'로 대답할 수 있다.

근사 알고리즘 분야에서는 어려운 문제에 대한 근사 최적 해를 찾도록 알고리즘이 설계된다.^[2] 일반적인 결정 버전은 허용 가능한 해만 지정하므로 문제의 부적절한 정의가 된다. 적절한 결정 문제를 도입할 수도 있지만, 이 문제는 최적화 문제로 더 자연스럽게 특징지어진다.

계산 복잡도 이론에서 다루는 문제의 복잡도 분류는 다음과 같다.

P
NP
co-NP

7. 최적화 문제의 역사

최적화 기법이 가장 오래 등장한 것은 카를 프리드리히 가우스까지 거슬러 올라가는 최급강하법이다. 역사적으로 처음 도입된 용어는 1940년대에 조지 단치히에 의해 만들어진 "선형 계획법"이다. 여기서 "계획법"으로 번역되는 'programming'이라는 단어는 컴퓨터 프로그래밍과는 다른 의미로, 미국군에서 훈련 및 보급 계획을 의미하는 'program'에서 유래했다. 최적화 문제 연구에 기여한 주요 수학자들은 다음과 같다.

존 폰 노이만
레오니트 칸토로비치
Naum Shor
Leonid Khachian
Boris Polyak
유리 네스테로프
Arkadii Nemirovskii
Michael J. Todd
리처드 벨만
호앙 투이 (수학자)

참조

_[1] 서적 Convex Optimization https://web.stanford[...] Cambridge University Press
_[2] 서적 Complexity and Approximation Springer
_[3] 문서 矢部2006、2頁
_[4] 문서 矢部2006、ⅳ頁
_[5] 문서 矢部2006、5頁
_[6] 문서 矢部2006、46頁
_[7] 문서 矢部2006、47頁
_[8] 웹사이트 局所的非線形数値最適化—Wolfram言語ドキュメント http://reference.wol[...]
_[9] 웹사이트 極小値探索概論—Wolfram言語ドキュメント http://reference.wol[...]
_[10] 웹사이트 準ニュートン法—Wolfram言語ドキュメント http://reference.wol[...]
_[11] 웹사이트 大域的非線形数値最適化—Wolfram言語ドキュメント http://reference.wol[...]

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com