수학적 최적화

최종 수정 2026.03.24

Here is the translated Markdown:

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


![Simionescu's function](https://upload.wikimedia.org/wikipedia/commons/3/33/Nelder-Mead_Simionescu.gif)
. 단체의 꼭짓점들은 값에 따라 정렬되며, 1이 가장 낮은(<math>f(x)</math> 최적) 값을 갖는다.|alt=]]

**수학적 최적화**(또는 *mathematical 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]

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

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

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

전역 수렴

더 일반적으로, 목적함수가 이차 함수가 아닌 경우, 많은 최적화 방법은 반복의 일부 부분 수열이 최적해에 수렴하도록 다른 방법을 사용한다. 수렴을 보장하기 위한 최초이자 여전히 널리 쓰이는 방법은 함수를 1차원을 따라 최적화하는 선형 탐색에 의존한다. 수렴을 보장하기 위한 두 번째이자 점점 더 널리 쓰이는 방법은 신뢰 영역을 사용한다. 선형 탐색과 신뢰 영역 모두 현대의 비미분 최적화 방법에서 사용된다. 일반적으로 전역 최적화기는 고급 국소 최적화기(예: 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 "공간 매핑이 핸드셋 안테나 설계에서 EM 최적화를 능가하다,"] microwaves&rf, August 30, 201

[^22]: Cervantes-González, Juan C.. 휴대폰 부품 및 인체의 EM 효과를 고려한 핸드셋 안테나의 공간 매핑 최적화. (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)