![maximum](https://upload.wikimedia.org/wikipedia/commons/7/72/Max_paraboloid.svg) (*x, y, z*) = (0, 0, 4)에서의 최댓값은 파란 점으로 표시되어 있다.]]

수학적 최적화

최종 수정 2026.03.25

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].

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

마찬가지로, \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가 상수인 경우를 연구한다(이는 인공지능, 특히 자동 추론에서 사용된다). ** 제약 프로그래밍은 변수 간의 관계가 제약 조건의 형태로 기술되는 프로그래밍 패러다임이다.
선언적 프로그래밍은 모든 제약 조건이 아닌 적어도 하나의 제약 조건이 충족되어야 하는 경우에 사용된다. 이는 특히 스케줄링에서 유용하다.
공간 매핑은 적절하고 물리적으로 의미 있는 조잡한 모델 또는 대리 모델을 활용하여 공학 시스템을 고충실도(정밀) 모델 정확도로 모델링하고 최적화하기 위한 개념이다.

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

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

다목적 최적화

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

어떤 설계가 다른 어떤 설계에 의해서도 지배되지 않으면 "파레토 최적"("파레토 효율적" 또는 파레토 집합에 속함과 동등)이라고 판단된다. 즉, 어떤 측면에서 다른 설계보다 열등하면서 어떤 측면에서도 더 낫지 않다면 지배되는 것이며 파레토 최적이 아니다.

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

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

다봉 또는 전역 최적화

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

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

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

임계점과 극값의 분류

실행 가능성 문제

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

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

존재성

카를 바이어슈트라스의 최대·최소값 정리는 콤팩트 집합 위에서 정의된 연속 실수값 함수가 최댓값과 최솟값을 가진다고 말한다. 더 일반적으로, 콤팩트 집합 위에서 하반연속 함수는 최솟값을 가지며, 상반연속 함수는 최댓값을 가진다.

최적성의 필요조건

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

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

최적성의 충분조건

1차 도함수 판정법은 극값이 될 수 있는 점을 식별하지만, 그 점이 최솟값인지, 최댓값인지, 혹은 둘 다 아닌지를 구별하지는 못한다. 목적함수가 두 번 미분 가능할 때, 제약 조건이 없는 문제에서는 2차 도함수 또는 2차 도함수 행렬(헤세 행렬이라 한다)을 확인하여, 제약 조건이 있는 문제에서는 목적함수와 제약 조건의 2차 도함수 행렬인 테두리 헤세 행렬을 확인하여 이러한 경우를 구별할 수 있다. 최댓값 또는 최솟값을 다른 정상점과 구별하는 조건을 '2차 조건'이라 한다('2차 도함수 판정법' 참조). 후보 해가 1차 조건을 만족하면, 2차 조건까지 만족하는 것으로 적어도 국소 최적성을 확립하기에 충분하다.

최적해의 민감도와 연속성

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

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

최적화의 미적분학

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

나아가, 임계점은 헤세 행렬의 정부호성을 사용하여 분류할 수 있다: 임계점에서 헤세 행렬이 양의 정부호이면 그 점은 국소 최솟값이고, 헤세 행렬이 음의 정부호이면 그 점은 국소 최댓값이며, 마지막으로 부정부호이면 그 점은 일종의 안장점이다.

제약 조건이 있는 문제는 라그랑주 승수의 도움으로 제약 조건이 없는 문제로 변환할 수 있는 경우가 많다. 라그랑주 완화는 어려운 제약 조건 문제에 대한 근사 해를 제공할 수도 있다.

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

전역 수렴

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

계산 최적화 기법

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

최적화 알고리즘

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

반복법

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

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

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

휴리스틱

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

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

응용 분야

역학

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

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

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

경제학과 금융

경제학은 행위자의 최적화와 밀접하게 연결되어 있어, 영향력 있는 한 정의는 경제학을 "대안적 용도를 가진 목적과 희소한 수단 사이의 관계로서의 인간 행동에 대한 연구"라는 과학(qua science)으로 관련지어 기술한다.[^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: 실용적 최적화 방법, 2nd Ed., 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 "공간 매핑이 휴대폰 안테나 설계에서 EM 최적화를 능가하다,"] 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)