최적화 문제

수학, 컴퓨터 과학, 경제학에서 최적화 문제는 실현 가능한 모든 해결책으로부터 최선의 해결책을 찾는 문제다.

최적화 문제는 변수가 연속형인지 이산형인지에 따라 두 범주로 나눌 수 있다.

• 이산형 변수에 대한 최적화 문제는 정수, 순열 또는 그래프와 같은 개체를 카운트 가능한 집합에서 찾아야 하는 이산형 최적화로 알려져 있다.
• 연속형 변수의 문제는 연속형 최적화라고 알려져 있는데, 연속형 함수의 최적 값을 찾아야 한다. 그것들은 제한된 문제들과 복합적인 문제들을 포함할 수 있다.

연속 최적화 문제

연속 최적화 문제의 표준 형태는^[1]

${\displaystyle {\begin{aligned}&{\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\end{aligned}}}$

어디에

• f : ℝⁿ → ℝ은 n-변수 벡터 x에 대해 최소화해야 하는 객관적 함수,
• g_i(x) ≤ 0을 불평등 구속조건이라고 한다.
• h_j(x) = 0을 동일 구속조건이라고 하며,
• m ≥ 0과 p ≥ 0.

m = p = 0이면 문제는 제약 없는 최적화 문제다. 관례에 따라, 표준 형식은 최소화 문제를 정의한다. 최대화 문제는 객관적 기능을 부정하여 처리할 수 있다.

조합 최적화 문제

형식적으로 조합 최적화 문제 A는 4중^{[citation needed]}(I, f, m, g)으로, 여기서,

• 나는 하나의 예다.
• 인스턴스 x ∈ I, f(x)는 실현 가능한 해결책의 집합이다.
• x의 인스턴스(instance)와 x의 실현 가능한 솔루션 y, m(x, y)은 y의 측도를 나타내며, 일반적으로 양의 실제를 나타낸다.
• g는 목표 함수로서 최소 또는 최대 중 하나이다.

그 다음 목표는 어떤 예에서 최적의 솔루션, 즉 다음을 통해 실현 가능한 솔루션을 찾는 것이다.

${\displaystyle m(x,y)=g{}m(x,y')\mid y'\in f(x){\bigr \}}.}$

각 조합 최적화 문제에 대해, 특정 측정 m에₀ 대해 실현 가능한 해결책이 있는지 여부를 묻는 해당 의사결정 문제가 있다. 예를 들어, 정점 u와 v를 포함하는 그래프 G가 있는 경우 최적화 문제는 "u에서 가장 적은 에지를 사용하는 v까지의 경로 찾기"일 수 있다. 이 문제는 예를 들어, 4의 해답이 있을 수 있다. 해당 의사결정 문제는 "u에서 v까지 10개 이하의 엣지를 사용하는 경로가 있는가?"이다. 이 문제는 간단한 '예스'나 '아니오'로 대답할 수 있다.

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

참고 항목

• 카운팅 문제(복잡성)
• 설계 최적화
• 함수 문제
• 장갑 문제
• 운영연구
• 만족: 최적의 방법은 찾을 수 없고 "충분히 좋은" 해결책일 뿐이다.
• 검색문제
• 반무한 프로그래밍

참조

외부 링크

• "How Traffic Shaping Optimizes Network Bandwidth". IPC. 12 July 2016. Retrieved 13 February 2017.