수학적 최적화

최종 수정 2026.03.25

Here is the translated Markdown:

maximum (x, y, z) = (0, 0, 4)에서의 최댓값이 파란색 점으로 표시되어 있다.]]

Simionescu's function . 단체의 꼭짓점은 값에 따라 정렬되며, 1이 가장 낮은(f(x) 최적) 값을 갖는다.|alt=]]

수학적 최적화(또는 optimisation으로도 표기) 또는 수리 계획법은 일정한 기준에 따라 주어진 대안의 집합에서 최선의 요소를 선택하는 것이다.[^3][^4] 일반적으로 이산 최적화와 연속 최적화의 두 하위 분야로 나뉜다. 최적화 문제는 컴퓨터 과학 및 공학[^1]에서부터 운용 과학 및 경제학에 이르기까지 모든 정량적 학문 분야에서 발생하며, 해법의 개발은 수세기 동안 수학에서 관심의 대상이 되어 왔다.[^5]

보다 일반적인 접근에서, 최적화 문제는 허용된 집합 내에서 체계적으로 입력값을 선택하고 함수의 값을 계산함으로써 실수 함수를 최대화하거나 최소화하는 것으로 구성된다. 최적화 이론과 기법을 다른 정식화로 일반화하는 것은 응용 수학의 광범위한 영역을 이룬다.

최적화 문제

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

이산 변수를 가진 최적화 문제는 이산 최적화로 알려져 있으며, 정수, 순열 또는 그래프와 같은 대상을 가산 집합에서 찾아야 한다.
연속 변수를 가진 문제는 연속 최적화로 알려져 있으며, 연속 집합에서 최적의 인수를 찾아야 한다. 여기에는 제약 조건이 있는 문제와 다봉 문제가 포함될 수 있다.

최적화 문제는 다음과 같은 방식으로 표현할 수 있다: 주어진 것: 어떤 집합에서 실수로의 함수 f:A \rarr \mathbb R 구하는 것: 모든 에 대해 이 성립하는 원소 ("최소화") 또는 모든 에 대해 이 성립하는 원소 ("최대화").

이러한 정식화를 최적화 문제 또는 수리 계획법 문제라고 한다(이 용어는 컴퓨터 프로그래밍과 직접적인 관련은 없지만, 예를 들어 선형 계획법에서 여전히 사용된다 – 아래 역사 항목 참조). 많은 실제 문제와 이론적 문제를 이 일반적인 틀로 모델링할 수 있다.

다음이 성립하므로:

f(\mathbf{x}{0})\geq f(\mathbf{x}) \Leftrightarrow -f(\mathbf{x}{0})\leq -f(\mathbf{x}), 최소화 문제만 풀면 충분하다. 그러나 최대화 문제만을 고려하는 반대 관점도 마찬가지로 유효하다.

물리학 분야에서 이 기법을 사용하여 정식화된 문제는 이 기법을 에너지 최소화라고 지칭할 수 있으며,[^6] 함수의 값이 모델링되는 시스템의 에너지를 나타낸다고 말한다. 기계 학습에서는 비용 함수를 사용하여 데이터 모델의 품질을 지속적으로 평가해야 하며, 최솟값은 최적의(가장 낮은) 오차를 가진 잠재적으로 최적인 매개변수 집합을 의미한다.

일반적으로 는 유클리드 공간 \mathbb R^n의 부분집합이며, 종종 의 원소가 만족해야 하는 등식 또는 부등식인 제약 조건의 집합으로 지정된다. 의 정의역 은 탐색 공간 또는 선택 집합이라 하고, 의 원소는 후보 해 또는 실행 가능 해라고 한다.

함수 는 목적 함수, 기준 함수, 손실 함수, 비용 함수(최소화),[^7] 효용 함수 또는 적합도 함수(최대화)라고 다양하게 불리며, 특정 분야에서는 에너지 함수 또는 에너지 범함수라고도 한다. 목적 함수를 최소화(또는 최대화)하는 실행 가능 해를 최적해라고 한다.

수학에서 전통적인 최적화 문제는 보통 최소화 관점에서 기술된다.

극솟값 은 다음을 만족하는 어떤 가 존재하는 원소로 정의된다:

\forall\mathbf{x}\in A ; \text{where} ;\left\Vert\mathbf{x}-\mathbf{x}^{\ast}\right\Vert\leq\delta,,

이 표현이 성립한다;

즉, 주변의 어떤 영역에서 모든 함수 값이 해당 원소에서의 값보다 크거나 같다. 극댓값도 유사하게 정의된다.

극솟값은 인접한 어떤 원소보다도 최소한 같거나 좋은 반면, 전역 최솟값은 모든 실행 가능 원소보다 최소한 같거나 좋다. 일반적으로 최소화 문제에서 목적 함수가 볼록 함수가 아닌 한, 여러 개의 극솟값이 존재할 수 있다. 볼록 문제에서 실행 가능 원소 집합의 경계가 아닌 내부에 극솟값이 있으면 그것이 전역 최솟값이기도 하지만, 비볼록 문제에서는 하나 이상의 극솟값이 존재할 수 있으며 이들 모두가 전역 최솟값일 필요는 없다.

비볼록 문제를 풀기 위해 제안된 많은 알고리즘은 – 상업적으로 이용 가능한 대부분의 솔버를 포함하여 – 국소 최적해와 전역 최적해를 구별할 수 없으며, 전자를 원래 문제의 실제 해로 취급한다. 전역 최적화는 비볼록 문제의 실제 최적해로의 유한 시간 내 수렴을 보장할 수 있는 결정론적 알고리즘의 개발에 관심을 두는 응용 수학 및 수치 해석의 분야이다.

표기법

최적화 문제는 종종 특수한 표기법으로 표현된다. 다음은 몇 가지 예시이다:

함수의 최솟값과 최댓값

다음 표기법을 살펴보자: \min_{x\in\mathbb R}; \left(x^2 + 1\right)

이는 실수 집합 \mathbb{R}에서 를 선택할 때 목적함수 의 최솟값을 나타낸다. 이 경우 최솟값은 에서 발생하는 1이다.

마찬가지로, 다음 표기법은

\max_{x\in\mathbb R}; 2x

가 임의의 실수일 때 목적함수 의 최댓값을 구하는 것이다. 이 경우 목적함수가 무한히 증가하므로 그러한 최댓값은 존재하지 않으며, 답은 "무한대" 또는 "정의되지 않음"이다.

최적 입력 인수

다음 표기법을 살펴보자: \underset{x\in(-\infty,-1]}{\operatorname{arg,min}} ; x^2 + 1, 또는 이와 동등하게 \underset{x}{\operatorname{arg,min}} ; x^2 + 1, ; \text{subject to:} ; x\in(-\infty,-1].

이는 구간 내에서 목적함수 를 최소화하는 인수 의 값(또는 여러 값)을 나타낸다(해당 함수의 실제 최솟값은 문제가 묻는 것이 아니다). 이 경우 답은 이다. 왜냐하면 는 실행 불가능, 즉 실행 가능 집합에 속하지 않기 때문이다.

마찬가지로, \underset{x\in[-5,5], ; y\in\mathbb R}{\operatorname{arg,max}} ; x\cos y, 또는 이와 동등하게 \underset{x, ; y}{\operatorname{arg,max}} ; x\cos y, ; \text{subject to:} ; x\in[-5,5], ; y\in\mathbb R,

이는 가 구간 에 속해야 한다는 추가 제약 조건 하에서 목적함수 의 값을 최대화하는 쌍(또는 여러 쌍)을 나타낸다(역시 표현식의 실제 최댓값은 중요하지 않다). 이 경우 해는 및 형태의 쌍이며, 여기서 는 모든 정수 범위를 갖는다.

연산자 와 는 때때로 와 로도 쓰이며, 최솟값의 인수와 최댓값의 인수를 의미한다.

역사

페르마와 라그랑주는 최적값을 식별하기 위한 미적분 기반 공식을 발견했으며, 뉴턴과 가우스는 최적값에 접근하기 위한 반복적 방법을 제안했다.

특정 최적화 문제에 대한 "선형 계획법"이라는 용어는 조지 B. 단치히에 의해 만들어졌으나, 이론의 상당 부분은 1939년에 레오니트 칸토로비치가 도입한 것이었다. (이 맥락에서 프로그래밍은 컴퓨터 프로그래밍을 의미하는 것이 아니라, 미국 군대가 제안된 훈련 및 병참 일정을 지칭하기 위해 프로그램이라는 용어를 사용한 데서 비롯된 것으로, 이것이 당시 단치히가 연구한 문제였다.) 단치히는 1947년에 심플렉스 알고리즘을 발표했으며, 존 폰 노이만과 다른 연구자들도 같은 시기에 선형 계획법의 이론적 측면(쌍대성 이론 등)에 관한 연구를 수행했다.[^8]

수리 최적화 분야의 다른 저명한 연구자들은 다음과 같다:

Richard Bellman
Dimitri Bertsekas
Michel Bierlaire
Stephen P. Boyd
Roger Fletcher
Martin Grötschel
Ronald A. Howard
Fritz John
Narendra Karmarkar
William Karush
Leonid Khachiyan
Bernard Koopman
Harold Kuhn
László Lovász
David Luenberger
Arkadi Nemirovski
Yurii Nesterov
Lev Pontryagin
R. Tyrrell Rockafellar
Naum Z. Shor
Albert Tucker

주요 하위 분야

볼록 프로그래밍은 목적 함수가 볼록(최소화)이거나 오목(최대화)이고 제약 집합이 볼록인 경우를 연구한다. 이는 비선형 프로그래밍의 특수한 경우로 보거나, 선형 또는 볼록 이차 프로그래밍의 일반화로 볼 수 있다. ** 선형 프로그래밍(LP)은 볼록 프로그래밍의 한 유형으로, 목적 함수 f가 선형이고 제약 조건이 선형 등식과 부등식만으로 명시되는 경우를 연구한다. 이러한 제약 집합을 다면체라 하며, 유계인 경우 폴리토프라 한다. ** 이차 원뿔 프로그래밍(SOCP)은 볼록 프로그램이며, 특정 유형의 이차 프로그램을 포함한다. ** 준정부호 프로그래밍(SDP)은 기본 변수가 준정부호 행렬인 볼록 최적화의 하위 분야이다. 이는 선형 및 볼록 이차 프로그래밍의 일반화이다. ** 원뿔 프로그래밍은 볼록 프로그래밍의 일반적인 형태이다. LP, SOCP, SDP는 모두 적절한 유형의 원뿔을 사용한 원뿔 프로그램으로 볼 수 있다. ** 기하 프로그래밍은 포지노미얼로 표현된 목적 함수 및 부등식 제약 조건과 단항식으로 표현된 등식 제약 조건을 볼록 프로그램으로 변환할 수 있는 기법이다.
정수 프로그래밍은 일부 또는 모든 변수가 정수 값을 취하도록 제약된 선형 프로그램을 연구한다. 이는 볼록이 아니며, 일반적으로 일반 선형 프로그래밍보다 훨씬 더 어렵다.
이차 프로그래밍은 목적 함수에 이차 항을 허용하지만, 실행 가능 집합은 선형 등식과 부등식으로 명시되어야 한다. 이차 항의 특정 형태에 대해 이는 볼록 프로그래밍의 한 유형이다.
분수 프로그래밍은 두 비선형 함수의 비율 최적화를 연구한다. 오목 분수 프로그램의 특수한 부류는 볼록 최적화 문제로 변환할 수 있다.
비선형 프로그래밍은 목적 함수 또는 제약 조건, 또는 양쪽 모두가 비선형 부분을 포함하는 일반적인 경우를 연구한다. 이는 볼록 프로그램일 수도 있고 아닐 수도 있다. 일반적으로 프로그램이 볼록인지 여부는 문제를 푸는 난이도에 영향을 미친다.
확률적 프로그래밍은 일부 제약 조건이나 매개변수가 확률 변수에 의존하는 경우를 연구한다.
강건 최적화는 확률적 프로그래밍과 마찬가지로 최적화 문제의 기반이 되는 데이터의 불확실성을 포착하려는 시도이다. 강건 최적화는 불확실성 집합에 의해 정의된 모든 가능한 불확실성의 실현 하에서 유효한 해를 찾는 것을 목표로 한다.
조합 최적화는 실행 가능한 해의 집합이 이산적이거나 이산적인 것으로 축소할 수 있는 문제를 다룬다.
확률적 최적화는 무작위(잡음이 있는) 함수 측정값 또는 탐색 과정에서의 무작위 입력과 함께 사용된다.
무한 차원 최적화는 실행 가능한 해의 집합이 함수 공간과 같은 무한 차원 공간의 부분집합인 경우를 연구한다.
휴리스틱 및 메타휴리스틱은 최적화되는 문제에 대해 거의 또는 전혀 가정을 하지 않는다. 일반적으로 휴리스틱은 최적해가 반드시 발견됨을 보장하지 않는다. 반면에 휴리스틱은 많은 복잡한 최적화 문제에 대한 근사해를 찾는 데 사용된다.
제약 만족은 목적 함수 f가 상수인 경우를 연구한다(이는 인공지능, 특히 자동 추론에서 사용된다). ** 제약 프로그래밍은 변수 간의 관계가 제약 조건의 형태로 기술되는 프로그래밍 패러다임이다.
선언적 프로그래밍은 모든 제약 조건이 아닌 적어도 하나의 제약 조건이 만족되어야 하는 경우에 사용된다. 이는 특히 스케줄링에서 유용하다.
공간 사상은 적절한 물리적으로 의미 있는 조잡한 모델 또는 대리 모델을 활용하여 공학 시스템을 고충실도(정밀) 모델 정확도로 모델링하고 최적화하기 위한 개념이다.

여러 하위 분야에서 기법들은 주로 동적 맥락(즉, 시간에 따른 의사 결정)에서의 최적화를 위해 설계된다:

변분법은 특정 곡선을 경계로 하되 가능한 한 최소 면적을 갖는 곡면을 찾는 것과 같이, 어떤 목표를 달성하는 최선의 방법을 찾는 것과 관련된다.
최적 제어 이론은 제어 정책을 도입한 변분법의 일반화이다.
동적 프로그래밍은 확률적 요소, 무작위성, 미지의 모델 매개변수가 있는 확률적 최적화 문제를 풀기 위한 접근법이다. 이는 최적화 전략이 문제를 더 작은 하위 문제로 분할하는 데 기반하는 경우를 연구한다. 이러한 하위 문제들 사이의 관계를 기술하는 방정식을 벨만 방정식이라 한다.
평형 제약이 있는 수학적 프로그래밍은 제약 조건에 변분 부등식이나 상보성 조건이 포함되는 경우이다.

다목적 최적화

최적화 문제에 둘 이상의 목적을 추가하면 복잡성이 증가한다. 예를 들어, 구조 설계를 최적화하려면 가볍고 동시에 강성이 높은 설계를 원할 것이다. 두 목적이 상충할 때는 절충이 이루어져야 한다. 가장 가벼운 설계 하나, 가장 강성이 높은 설계 하나, 그리고 무게와 강성의 타협인 무한히 많은 설계가 있을 수 있다. 하나의 기준을 다른 기준의 희생으로 개선하는 절충 설계의 집합을 파레토 집합이라 한다. 최적 설계들의 무게 대 강성을 도시하여 만든 곡선을 파레토 프론티어라 한다.

어떤 설계가 다른 어떤 설계에 의해 지배되지 않으면 "파레토 최적"("파레토 효율적" 또는 파레토 집합에 속한다고 동등하게 표현)이라 판단된다: 어떤 측면에서 다른 설계보다 열등하고 어떤 측면에서도 더 나은 점이 없다면, 그 설계는 지배되며 파레토 최적이 아니다.

"파레토 최적" 해들 중에서 "선호 해"를 결정하는 선택은 의사 결정자에게 위임된다. 다시 말해, 문제를 다목적 최적화로 정의한다는 것은 일부 정보가 누락되어 있음을 의미한다: 바람직한 목적은 주어지지만 그 조합들은 서로에 대해 상대적으로 평가되지 않는다. 일부 경우에는 누락된 정보를 의사 결정자와의 상호작용 세션을 통해 도출할 수 있다.

다목적 최적화 문제는 (부분) 순서가 더 이상 파레토 순서에 의해 주어지지 않는 벡터 최적화 문제로 더욱 일반화되었다.

다봉 또는 전역 최적화

최적화 문제는 종종 다봉적이다; 즉, 여러 개의 좋은 해를 갖는다. 이들은 모두 전역적으로 좋을 수도 있고(동일한 비용 함수 값), 전역적으로 좋은 해와 국소적으로 좋은 해가 혼합되어 있을 수도 있다. 모든(또는 적어도 일부의) 다중 해를 얻는 것이 다봉 최적화기의 목표이다.

고전적 최적화 기법은 반복적 접근 방식의 특성상 여러 해를 얻는 데 사용될 때 만족스러운 성능을 보이지 못한다. 알고리즘의 여러 실행에서 서로 다른 시작점을 사용하더라도 서로 다른 해가 얻어진다는 보장이 없기 때문이다.

여러 개의 국소 극값이 존재할 수 있는 전역 최적화 문제에 대한 일반적인 접근법으로는 진화 알고리즘, 베이즈 최적화, 담금질 기법 등이 있다.

임계점과 극값의 분류

실행가능성 문제

충족가능성 문제는 실행가능성 문제라고도 불리며, 목적함수 값에 관계없이 실행 가능한 해를 찾는 문제이다. 이는 모든 해에 대해 목적함수 값이 동일하여 어떤 해든 최적해가 되는, 수학적 최적화의 특수한 경우로 볼 수 있다.

많은 최적화 알고리즘은 실행 가능한 점에서 시작해야 한다. 이러한 점을 얻는 한 가지 방법은 여유 변수를 사용하여 실행가능성 조건을 완화하는 것이다. 충분한 여유가 있으면 어떤 시작점이든 실행 가능하다. 그런 다음 여유 변수가 영 또는 음이 될 때까지 최소화한다.

존재성

카를 바이어슈트라스의 최대·최소값 정리는 콤팩트 집합 위의 연속 실수값 함수가 최댓값과 최솟값을 가진다는 것을 나타낸다. 보다 일반적으로, 콤팩트 집합 위의 하반연속 함수는 최솟값을 가지며, 콤팩트 집합 위의 상반연속 함수는 최댓값을 가진다.

최적성의 필요조건

페르마의 정리 중 하나는 비제약 문제의 최적해가 목적함수의 일계 도함수 또는 기울기가 영인 정류점에서 발견된다고 말한다(일계 도함수 판정법 참조). 보다 일반적으로, 목적함수의 일계 도함수 또는 기울기가 영이거나 정의되지 않는 임계점, 또는 선택 집합의 경계에서 발견될 수 있다. 내부 최적점에서 일계 도함수가 영임을 나타내는 방정식(또는 연립방정식)을 '일계 조건' 또는 일계 조건의 집합이라 한다.

등식 제약 문제의 최적해는 라그랑주 승수법을 통해 구할 수 있다. 등식 및/또는 부등식 제약이 있는 문제의 최적해는 '카루시-쿤-터커 조건'을 사용하여 구할 수 있다.

최적성의 충분조건

일계 도함수 판정법은 극값이 될 수 있는 점을 식별하지만, 이 판정법으로는 해당 점이 극소인지, 극대인지, 또는 둘 다 아닌지를 구별하지 못한다. 목적함수가 두 번 미분 가능할 때, 비제약 문제에서는 이계 도함수 또는 이계 도함수의 행렬(헤시안 행렬이라 함)을, 제약 문제에서는 목적함수와 제약 조건의 이계 도함수 행렬인 테두리 헤시안을 검사하여 이러한 경우를 구별할 수 있다. 극대, 극소를 다른 정류점과 구별하는 조건을 '이계 조건'이라 한다('이계 도함수 판정법' 참조). 후보 해가 일계 조건을 만족하면, 이계 조건도 함께 만족하는 것으로 적어도 국소 최적성을 확립하기에 충분하다.

최적해의 민감도와 연속성

포락선 정리는 기저 매개변수가 변할 때 최적해의 값이 어떻게 변하는지를 설명한다. 이러한 변화를 계산하는 과정을 비교정태분석이라 한다.

클로드 베르주(1963)의 최대값 정리는 기저 매개변수의 함수로서 최적해의 연속성을 설명한다.

최적화의 미적분학

두 번 미분 가능한 함수의 비제약 문제에서, 일부 임계점은 목적함수의 기울기가 영인 점(즉, 정류점)을 찾아 구할 수 있다. 보다 일반적으로, 영 부분기울기는 볼록 함수 및 신경망의 손실 함수 최소화에서 나타나는 기타 국소 립시츠 함수를 이용한 최소화 문제에서 국소 최솟값이 발견되었음을 증명한다. 양-음 모멘텀 추정은 국소 최솟값을 회피하고 목적함수의 전역 최솟값에 수렴할 수 있게 한다.[^9]

나아가, 임계점은 헤시안 행렬의 정치성을 사용하여 분류할 수 있다: 임계점에서 헤시안이 양 정치이면 그 점은 극소점이고, 헤시안 행렬이 음 정치이면 그 점은 극대점이며, 부정치이면 그 점은 일종의 안장점이다.

제약 문제는 라그랑주 승수를 이용하여 비제약 문제로 변환할 수 있는 경우가 많다. 라그랑주 완화는 어려운 제약 문제에 대한 근사해를 제공할 수도 있다.

목적함수가 볼록 함수인 경우, 모든 국소 최솟값은 전역 최솟값이기도 하다. 내부점 방법과 같이 볼록 함수를 최소화하기 위한 효율적인 수치 기법이 존재한다.

전역 수렴

보다 일반적으로, 목적함수가 이차 함수가 아닌 경우, 많은 최적화 방법은 반복 수열의 일부 부분 수열이 최적해에 수렴하도록 보장하기 위해 다른 방법을 사용한다. 수렴을 보장하는 최초이자 여전히 널리 사용되는 방법은 일차원에서 함수를 최적화하는 직선 탐색에 의존한다. 수렴을 보장하는 두 번째이자 점점 더 널리 사용되는 방법은 신뢰 영역을 사용한다. 직선 탐색과 신뢰 영역은 모두 현대의 비미분 최적화 방법에서 사용된다. 일반적으로 전역 최적화기는 고급 국소 최적화기(예: BFGS)보다 훨씬 느리므로, 서로 다른 시작점에서 국소 최적화기를 시작하여 효율적인 전역 최적화기를 구축할 수 있는 경우가 많다.

계산 최적화 기법

문제를 해결하기 위해 연구자들은 유한한 단계 내에 종료되는 알고리즘, 해에 수렴하는 반복 방법(특정 문제 유형에 대해), 또는 일부 문제에 대해 근사 해를 제공할 수 있는 휴리스틱(반복이 반드시 수렴하지는 않지만)을 사용할 수 있다.

최적화 알고리즘

선형 계획법을 위해 설계된 조지 댄치그의 단체법
이차 계획법 및 선형-분수 계획법을 위해 설계된 단체법의 확장
네트워크 최적화에 특히 적합한 단체법의 변형
조합 알고리즘
양자 최적화 알고리즘

반복 방법

비선형 계획법 문제를 해결하기 위해 사용되는 반복 방법은 헤시안, 기울기, 또는 함수값만을 평가하는지에 따라 다르다. 헤시안(H)과 기울기(G)를 평가하면 수렴 속도가 향상되지만, 이러한 양이 존재하고 충분히 매끄럽게 변하는 함수의 경우, 이러한 평가는 각 반복의 계산 복잡도(또는 계산 비용)를 증가시킨다. 일부 경우에는 계산 복잡도가 과도하게 높을 수 있다.

최적화기에 대한 주요 기준 중 하나는 필요한 함수 평가 횟수이며, 이는 이미 그 자체로 큰 계산 노력을 요구하고, 주로 N개의 변수에 대해 연산해야 하는 최적화기 자체 내부의 노력보다 대개 훨씬 크다. 도함수는 이러한 최적화기에 상세한 정보를 제공하지만, 계산이 더욱 어렵다. 예를 들어 기울기를 근사하는 데 최소 N+1번의 함수 평가가 필요하다. 2차 도함수의 근사(헤시안 행렬에 수집됨)의 경우, 함수 평가 횟수는 N² 차수이다. 뉴턴 방법은 2차 도함수를 필요로 하므로, 각 반복마다 함수 호출 횟수가 N² 차수이지만, 더 단순한 순수 기울기 최적화기의 경우 N에 불과하다. 그러나 기울기 최적화기는 일반적으로 뉴턴 알고리즘보다 더 많은 반복을 필요로 한다. 함수 호출 횟수에 대해 어느 것이 최선인지는 문제 자체에 달려 있다.

헤시안을 평가(또는 유한 차분을 사용하여 헤시안을 근사)하는 방법: ** 뉴턴 방법 ** 순차 이차 계획법: 소규모-중규모 제약 조건 문제를 위한 뉴턴 기반 방법. 일부 버전은 대규모 문제를 처리할 수 있다. ** 내부점 방법: 제약 최적화를 위한 대규모 방법 유형으로, 일부는 (부분)기울기 정보만 사용하고 다른 일부는 헤시안 평가를 필요로 한다.
기울기를 평가하거나, 어떤 방식으로 기울기를 근사(또는 부분기울기까지)하는 방법: ** 좌표 하강법: 각 반복에서 단일 좌표를 갱신하는 알고리즘 ** 켤레 기울기법: 대규모 문제를 위한 반복 방법. (이론적으로 이 방법은 이차 목적함수에 대해 유한 단계 내에 종료되지만, 유한 정밀도 컴퓨터에서는 이 유한 종료가 실제로 관찰되지 않는다.) ** 기울기 하강법(또는 "최급 하강법" 또는 "최급 상승법"): 역사적·이론적으로 중요한 (느린) 방법으로, 거대한 문제의 근사 해를 찾는 데 다시 관심을 받고 있다. ** 부분기울기법: 일반화된 기울기를 사용하는 대규모 국소 립시츠 함수를 위한 반복 방법. 보리스 T. 폴리악에 따르면, 부분기울기-사영법은 켤레 기울기법과 유사하다. ** 하강 번들법: 국소 립시츠 함수를 가진 소규모-중규모 문제, 특히 볼록 최소화 문제를 위한 반복 방법(켤레 기울기법과 유사). ** 타원체법: 준볼록 목적함수를 가진 소규모 문제를 위한 반복 방법으로, 특히 일부 조합 최적화 문제의 다항 시간 복잡도를 확립하는 데 큰 이론적 관심을 받고 있다. 준뉴턴법과 유사성이 있다. ** 조건부 기울기법(프랭크-울프): 특히 교통 네트워크에서 선형 제약 조건을 가진 특수 구조 문제의 근사 최소화를 위한 방법. 일반적인 비제약 문제의 경우, 이 방법은 (거의 모든 문제에 대해) 구식으로 간주되는 기울기법으로 축소된다. ** 준뉴턴법: 중규모-대규모 문제(예: N<1000)를 위한 반복 방법. ** 동시 섭동 확률적 근사(SPSA) 방법: 확률적 최적화를 위한 방법; 무작위(효율적) 기울기 근사를 사용한다.
함수값만 평가하는 방법: 문제가 연속적으로 미분 가능하면, 유한 차분을 사용하여 기울기를 근사할 수 있으며, 이 경우 기울기 기반 방법을 사용할 수 있다. ** 보간법 ** 패턴 탐색법: 아래에 나열된 넬더-미드 휴리스틱(단체를 사용)보다 더 나은 수렴 특성을 가진다. ** 거울 하강법

휴리스틱

(유한 종료) 알고리즘 및 (수렴) 반복 방법 외에도 휴리스틱이 있다. 휴리스틱은 해를 찾는 것이 (수학적으로) 보장되지 않지만, 특정 실용적 상황에서 유용한 알고리즘이다. 잘 알려진 휴리스틱 목록:

차분 진화
동적 이완
진화 알고리즘
유전 알고리즘
무작위 재시작 언덕 오르기
밈 알고리즘
넬더-미드 단체 휴리스틱: 기울기를 호출하지 않는 근사 최소화를 위한 널리 사용되는 휴리스틱
입자 군집 최적화
담금질 기법
확률적 터널링
타부 탐색

응용 분야

역학

강체 동역학(특히 다관절 강체 동역학) 문제는 수리 계획법 기법을 필요로 하는 경우가 많은데, 강체 동역학을 구속 다양체 위에서의 상미분방정식을 푸는 문제로 볼 수 있기 때문이다.[^10] 여기서 구속 조건은 "이 두 점은 항상 일치해야 한다", "이 표면은 다른 표면을 관통해서는 안 된다", "이 점은 항상 이 곡선 위의 어딘가에 있어야 한다"와 같은 다양한 비선형 기하학적 구속 조건이다. 또한 접촉력을 계산하는 문제는 선형 상보성 문제를 풀어서 해결할 수 있으며, 이는 QP(이차 계획법) 문제로도 볼 수 있다.

많은 설계 문제 또한 최적화 프로그램으로 표현할 수 있다. 이러한 응용을 설계 최적화라고 한다. 그 하위 분야 중 하나는 공학 최적화이며, 또 다른 최근 성장하고 있는 하위 분야는 다분야 설계 최적화로, 많은 문제에서 유용하지만 특히 항공우주 공학 문제에 적용되어 왔다.

이 접근법은 우주론과 천체물리학에 적용될 수 있다.[^11]

경제학과 금융

경제학은 행위자의 최적화와 밀접하게 연결되어 있어, 영향력 있는 한 정의에서는 경제학을 과학으로서 "목적과 대안적 용도를 가진 희소한 수단 사이의 관계로서의 인간 행동에 대한 연구"로 설명한다.[^12] 현대 최적화 이론은 전통적인 최적화 이론을 포함하면서도 게임 이론 및 경제적 균형 연구와 겹치는 부분이 있다. Journal of Economic Literature 분류 코드는 수리 계획법, 최적화 기법 및 관련 주제를 JEL:C61-C63으로 분류한다.

미시경제학에서 효용 극대화 문제와 그 쌍대 문제인 지출 최소화 문제는 경제적 최적화 문제이다. 소비자가 일관되게 행동하는 한, 소비자는 효용을 극대화하고 기업은 이윤을 극대화하는 것으로 가정된다. 또한 행위자는 흔히 위험 회피적인 것으로 모형화되어 위험을 피하는 것을 선호한다. 자산 가격도 최적화 이론을 사용하여 모형화되지만, 기초가 되는 수학은 정적 최적화가 아닌 확률 과정의 최적화에 의존한다. 국제 무역 이론도 국가 간 무역 패턴을 설명하기 위해 최적화를 사용한다. 포트폴리오 최적화는 경제학에서의 다목적 최적화의 한 예이다.

1970년대 이후 경제학자들은 제어 이론을 사용하여 시간에 따른 동적 의사결정을 모형화해 왔다.[^13] 예를 들어, 동적 탐색 모형은 노동 시장 행동을 연구하는 데 사용된다.[^14] 결정론적 모형과 확률론적 모형 사이의 구분은 매우 중요하다.^15 거시경제학자들은 경제 전체의 동학을 노동자, 소비자, 투자자, 정부의 상호의존적인 최적화 의사결정의 결과로 설명하는 동적 확률적 일반균형(DSGE) 모형을 구축한다.[^16][^17]

전기공학

전기공학에서 최적화 기법의 일반적인 응용 분야로는 능동 필터 설계,[^18] 초전도 자기 에너지 저장 시스템에서의 누설 자기장 저감, 마이크로파 구조의 공간 사상 설계,[^19] 휴대 단말기 안테나,[^20][^21][^22] 전자기 기반 설계 등이 있다. 마이크로파 부품 및 안테나의 전자기적으로 검증된 설계 최적화는 1993년 공간 사상의 발견 이래 적절한 물리 기반 또는 경험적 대리 모형과 공간 사상 방법론을 광범위하게 활용해 왔다.[^23][^24] 최적화 기법은 전력 조류 해석에도 사용된다.[^25]

토목공학

최적화는 토목공학에서 널리 사용되어 왔다. 건설 관리와 교통 공학은 최적화에 크게 의존하는 토목공학의 주요 분야에 속한다. 최적화로 해결되는 가장 일반적인 토목공학 문제로는 도로의 절토 및 성토, 구조물 및 기반 시설의 수명 주기 분석,[^26] 자원 평준화,[^27][^2] 수자원 배분, 교통 관리[^28] 및 일정 최적화가 있다.

운영 과학

최적화 기법을 광범위하게 사용하는 또 다른 분야는 운영 과학이다.[^29] 운영 과학은 또한 개선된 의사결정을 지원하기 위해 확률적 모형화와 시뮬레이션을 사용한다. 운영 과학은 점점 더 사건에 적응하는 동적 의사결정을 모형화하기 위해 확률적 계획법을 사용하고 있으며, 이러한 문제는 대규모 최적화 및 확률적 최적화 방법으로 풀 수 있다.

제어공학

수학적 최적화는 현대 제어기 설계에 널리 사용된다. 모형 예측 제어(MPC)나 실시간 최적화(RTO)와 같은 상위 수준 제어기는 수학적 최적화를 활용한다. 이러한 알고리즘은 온라인으로 실행되며, 구속 조건과 제어 대상 시스템의 모형을 포함하는 수학적 최적화 문제를 반복적으로 풀어 공정 플랜트의 초크 밸브 개도와 같은 의사결정 변수의 값을 반복적으로 결정한다.

지구물리학

최적화 기법은 지구물리학적 매개변수 추정 문제에 정기적으로 사용된다. 예를 들어 지진 기록과 같은 지구물리학적 측정 데이터가 주어지면, 기반 암석과 유체의 물리적 특성과 기하학적 형상을 구하는 것이 일반적이다. 지구물리학의 대부분의 문제는 비선형이며, 결정론적 방법과 확률론적 방법 모두 널리 사용된다.

분자 모형화

비선형 최적화 방법은 형태 분석에서 널리 사용된다.

전산 시스템 생물학

최적화 기법은 모형 구축, 최적 실험 설계, 대사 공학, 합성 생물학 등 전산 시스템 생물학의 많은 측면에서 사용된다. 선형 계획법은 발효 산물의 최대 가능 수율을 계산하고, 복수의 마이크로어레이 데이터 세트로부터 유전자 조절 네트워크를 추론하는 데[^30] 그리고 고처리량 데이터로부터 전사 조절 네트워크를 추론하는 데 적용되어 왔다.[^31] 비선형 계획법은 에너지 대사를 분석하는 데 사용되었으며,[^32] 대사 공학과 생화학적 경로의 매개변수 추정에 적용되어 왔다.[^33]

기계 학습

솔버

같이 보기

최속강하선
곡선 적합
결정론적 전역 최적화
목표 계획법
최적화 분야의 주요 출판물
최소제곱법
수리 최적화 학회 (구 수리 계획법 학회)
수학적 최적화 알고리즘
수학적 최적화 소프트웨어
공정 최적화
시뮬레이션 기반 최적화
최적화를 위한 테스트 함수
차량 경로 문제

주석

더 읽을거리

- - - - G.L. Nemhauser, A.H.G. Rinnooy Kan and M.J. Todd (eds.): 최적화, Elsevier, (1989).
Stanislav Walukiewicz：정수 계획법, Springer，ISBN 978-9048140688, (1990).
R. Fletcher: 실용적 최적화 방법, 제2판, Wiley, (2000).
Panos M. Pardalos：수치 최적화에서의 근사와 복잡성: 연속 및 이산 문제, Springer，ISBN 978-1-44194829-8, (2000).
Xiaoqi Yang, K. L. Teo, Lou Caccetta (Eds.)：최적화 방법과 응용，Springer, ISBN 978-0-79236866-3, (2001).
Panos M. Pardalos, and Mauricio G. C. Resende(Eds.)：응용 최적화 핸드북、Oxford Univ Pr on Demand, ISBN 978-0-19512594-8, (2002).
Wil Michiels, Emile Aarts, and Jan Korst: 국소 탐색의 이론적 측면, Springer, ISBN 978-3-64207148-5, (2006).
Der-San Chen, Robert G. Batson, and Yu Dang： 응용 정수 계획법: 모델링과 풀이，Wiley，ISBN 978-0-47037306-4, (2010).
Mykel J. Kochenderfer and Tim A. Wheeler: 최적화 알고리즘, The MIT Press, ISBN 978-0-26203942-0, (2019).
Vladislav Bukshtynov: 최적화: 실전에서의 성공, CRC Press (Taylor & Francis), ISBN 978-1-03222947-8, (2023) .
Rosario Toscano: 휴리스틱 칼만 알고리즘을 이용한 최적화 문제 풀이: 새로운 확률적 방법, Springer, ISBN 978-3-031-52458-5 (2024).
Immanuel M. Bomze, Tibor Csendes, Reiner Horst and Panos M. Pardalos: 전역 최적화의 발전, Kluwer Academic, ISBN 978-1-4419-4768-0 (2010).

외부 링크

최적화 소스 코드 링크
- - 최적화

참고 문헌

[^1]: Martins, Joaquim R. R. A.. 공학 설계 최적화. Cambridge University Press. (2021-10-01)

[^2]: Piryonesi, S. Madeh. Piryonesi, S. M., Nasseri, M., & Ramezani, A. (2018). 활동 분할 및 자원 제약 조건이 있는 건설 프로젝트의 자원 평준화: 시뮬레이티드 어닐링 최적화.. (9 July 2018)

[^4]: 수리 계획법: 개요

[^5]: Du, D. Z.. 최적화 백과사전. Springer

[^6]: Hartmann, Alexander K. 물리학에서의 최적화 알고리즘. Citeseer. (2002)

[^7]: Erwin Diewert, W.. 비용 함수. Palgrave Macmillan UK. (2017)

[^8]: Bixby, Robert E. 선형 및 혼합 정수 계획법 계산의 간략한 역사. (2012)

[^9]: Abdulkadirov, R.. 앙상블 신경망과 차분 기울기 양-음 모멘텀을 이용한 위성 이미지 인식. (February 2024)

[^10]: Vereshchagin, A.F.. 조작 로봇 운동의 모델링 및 제어

[^11]: Haggag, S.. 최적 제어를 이용한 우주론적 인플레이션 모델

[^12]: [[Lionel Robbins]] (1935, 2nd ed.) ''[[An Essay on the Nature and Significance of Economic Science#Major propositions An Essay on the Nature and Significance of Economic Science]]'', Macmillan, p. 16.

[^13]: Dorfman, Robert. 최적 제어 이론의 경제학적 해석

[^14]: Sargent, Thomas J.. 동태적 거시경제 이론. Harvard University Press

[^16]: Rotemberg, Julio. 통화 정책 평가를 위한 최적화 기반 계량경제학 프레임워크

[^17]: ''[[The New Palgrave Dictionary of Economics]]'' (2008), 초록 링크가 포함된 제2판에서 발췌:• "[http://www.dictionaryofeconomics.com/article?id=pde2008_N000148&edition=current&q=optimization&t

[^18]: De, Bishnu Prasad. 심플렉스 입자 군집 최적화를 이용한 아날로그 능동 필터 설계의 최적 부품 값 선택. (2014-09-27)

[^19]: Koziel, Slawomir. 마이크로파 부품 최적화를 위한 다중 근사 모델 공간 매핑. (January 2008)

[^20]: Tu, Sheng. 세선 모델을 활용한 휴대폰 안테나의 공간 매핑 최적화. (July 2013)

[^21]: N. Friedrich, [http://mwrf.com/software/space-mapping-outpaces-em-optimization-handset-antenna-design "공간 매핑이 휴대폰 안테나 설계에서 전자기 최적화를 능가하다,"] microwaves&rf, August 30, 201

[^22]: Cervantes-González, Juan C.. 휴대폰 부품 및 인체의 전자기 효과를 고려한 휴대폰 안테나의 공간 매핑 최적화. (February 2016)

[^23]: Bandler, J.W.. 전자기 최적화를 위한 공간 매핑 기법. (1994)

[^24]: Bandler, J.W.. 공격적 공간 매핑을 활용한 전자기 최적화. (1995)

[^25]: 최적 전력 흐름의 볼록 완화: 튜토리얼

[^26]: Piryonesi, Sayed Madeh. 구조물 유지보수에서 비용-안전 최적화(CSO) 문제를 해결하기 위한 수리 계획 모델. (9 January 2017)

[^27]: Hegazy, Tarek. 유전 알고리즘을 이용한 자원 배분 및 평준화 최적화. (June 1999)

[^28]: Herty, M.. 교통 흐름 네트워크의 모델링, 시뮬레이션 및 최적화. (2003-01-01)

[^29]: 정치 무대의 새로운 세력: 제오포니스텐

[^30]: Wang, Yong. 다중 마이크로어레이 데이터세트로부터의 유전자 조절 네트워크 추론. (2006-07-24)

[^31]: Wang, Rui-Sheng. 고처리량 데이터로부터의 전사 조절 네트워크 추론. (2007-09-22)

[^32]: Vo, Thuy D.. 에너지 대사의 시스템 분석을 통한 리 증후군의 영향받는 호흡 사슬 복합체 규명. (May 2007)

[^33]: Mendes, P.. 생화학적 경로의 비선형 최적화: 대사 공학 및 매개변수 추정에의 응용. (1998)