수학적 최적화

함수 $f(x,y)=4-x^{2}-y^{2}$의 그래프. $(x,y)=(0,0)$에서 최댓값 4를 갖는다.

수학적 최적화(數學的 最適化, 영어: mathematical optimization)는 주어진 조건 아래에서 함수의 값을 최소화하거나 최대화하는 문제를 다루는 응용수학의 한 분야이다. 수리 계획법(영어: mathematical programming)이라고도 한다.

최소화하거나 최대화하려는 함수를 목적함수(영어: objective function), 값을 정해야 하는 변수를 결정 변수(영어: decision variable), 변수가 만족해야 하는 조건을 제약 조건(영어: constraint)이라고 한다. 예를 들어 주어진 자원으로 이익을 최대화할 생산량을 정하거나, 관측 자료와 예측값 사이의 오차를 최소화하는 모형을 찾는 문제가 이에 속한다.

최적화 문제는 변수와 함수의 성질에 따라 선형 계획법, 정수 계획법, 비선형 계획법, 볼록 최적화 등으로 나뉜다. 최적화 이론은 최적해의 존재 여부와 성질을 다루며, 알고리즘 연구는 최적해나 근사해를 구하는 계산 방법을 다룬다. 최적화는 운용과학, 경제학, 통계학, 기계 학습, 공학 등에서 사용된다.

기본 관점과 예

같은 상황도 무엇을 최선의 선택으로 보느냐에 따라 서로 다른 최적화 문제로 나타낼 수 있다. 예를 들어 생산 비용을 줄이는 문제와 정해진 비용 안에서 생산량을 늘리는 문제는 서로 다른 목적함수와 제약 조건을 갖는다.

두 제품의 생산량을 정하는 문제는 선형 계획법의 간단한 예이다. 생산량 $x,y$를 각각 킬로그램 단위의 음이 아닌 실수로 나타내고, 단위 생산량당 이익이 각각 3과 2라고 하자. 첫째 자원은 두 제품 모두 1킬로그램당 1단위씩 필요하고, 총 4단위까지 사용할 수 있다. 둘째 자원은 첫 제품에는 1킬로그램당 2단위, 둘째 제품에는 1단위씩 필요하고, 총 6단위까지 사용할 수 있다. 이때 이익을 최대화하는 문제는 다음과 같다.

${\begin{aligned}\max _{x,y}\quad &3x+2y\\{\text{subject to}}\quad &x+y\leq 4,\\&2x+y\leq 6,\\&x\geq 0,\quad y\geq 0.\end{aligned}}$

이 모형은 각 제품의 이익과 자원 소비량이 생산량에 비례하며, 전체 이익과 소비량은 두 제품의 값을 더해 계산할 수 있다고 가정한다. 생산에 드는 고정 비용이나 생산량에 따른 단가 변화가 있다면 그에 맞게 모형을 수정해야 한다.

두 부등식을 더하면 $3x+2y\leq 10$이므로 이익은 10을 넘을 수 없다. 한편 $x=y=2$는 모든 제약을 만족하면서 이익 10을 달성한다. 따라서 최적 생산량은 $(2,2)$이고 최적값은 10이다. 두 자원 제약에서 동시에 등호가 성립해야 이 상한을 달성하므로 이 경우 최적해는 하나뿐이다.

정의와 기본 개념

 이 부분의 본문은 최적화 문제입니다.

문제의 표기

집합 $C$와 그 위의 실숫값 함수 $f$가 주어졌을 때, 최소화 문제는

$\min _{x\in C}f(x)$

로 쓴다. 여기서 $x$는 결정 변수이고 $C$는 변수가 가질 수 있는 값들의 집합이다. $C$의 원소 $x^{*}$가 모든 $x\in C$에 대하여 $f(x^{*})\leq f(x)$를 만족하면 $x^{*}$를 최적해(영어: minimizer, optimal solution)라고 한다. 최대화에서는 부등호를 반대로 한다. $f$를 최대화하는 해는 $-f$를 최소화하는 해와 같으므로, 이론에서는 주로 최소화 문제로 통일하여 서술한다.

최적해와 최적값은 구별한다. 최소화 문제의 최적값은 목적함숫값들의 하한이다.

$p^{*}=\inf _{x\in C}f(x)$

이 정의에 따르면 최솟값을 달성하는 원소가 없어도 최적값을 나타낼 수 있다. 예를 들어 $x>0$에서 $f(x)=1/x$는 하한이 0이지만 실제로 값이 0인 점은 없다. 이 문제는 최적값이 유한하면서도 최적해가 존재하지 않는 예이다.

최적해 전체의 집합은

$\operatorname {arg\,min} _{x\in C}f(x)=\{x\in C:f(x)=p^{*}\}$

로 나타낸다. 이 집합은 비어 있을 수도 있고 여러 원소를 가질 수도 있다. 예를 들어 $f(x)=0$을 $0\leq x\leq 1$에서 최소화하면 구간 안의 모든 점이 최적해이다. 또한 목적함숫값을 한없이 작게 만들 수 있으면 $p^{*}=-\infty$이며, 실숫값 함수에서는 이 값을 달성하는 최적해가 없다.

제약 조건과 가능해

선형 부등식들이 정하는 가능 영역의 예. 모든 제약을 만족하는 공통부분이 가능 영역이다.

실수 변수 $x\in \mathbb {R} ^{n}$를 사용하는 문제에서는 제약 조건을 방정식과 부등식으로 나타내는 경우가 많다. 함수들의 공통 정의역을 $D\subseteq \mathbb {R} ^{n}$이라 하면 다음과 같이 쓸 수 있다.

${\begin{aligned}\min _{x\in D}\quad &f(x)\\{\text{subject to}}\quad &g_{i}(x)\leq 0\quad (i=1,\ldots ,m),\\&h_{j}(x)=0\quad (j=1,\ldots ,p).\end{aligned}}$

여기서 $g_{i}$는 부등식 제약 함수이고 $h_{j}$는 등식 제약 함수이다. 모든 제약을 만족하는 $x$를 가능해(영어: feasible solution)라고 하며, 그 집합

$C=\{x\in D:g_{i}(x)\leq 0\ (i=1,\ldots ,m),\ h_{j}(x)=0\ (j=1,\ldots ,p)\}$

을 가능 영역이라고 한다.

가능 영역이 공집합이면 문제는 실행 불가능하다. 예를 들어 한 실수 변수에 $x\leq 0$과 $x\geq 1$을 동시에 요구하면 가능해가 없다. 이는 가능해는 있으나 목적함수에 하한이 없거나 최적값을 달성하지 못하는 경우와 구별된다. 최소화 문제의 표기에서는 $\inf \varnothing =+\infty$로 정하여 실행 불가능한 경우의 최적값을 나타내기도 한다.

별도의 제약 없이 $\mathbb {R} ^{n}$ 전체에서 함수를 최소화하는 문제는 무제약 최적화 문제이다. 한편 정수 계획법에서는 변수 일부나 전부에 정수 조건을 부과한다. 같은 목적함수를 사용하더라도 허용되는 변수의 범위나 제약을 바꾸면 가능 영역과 최적해가 달라질 수 있다.

전역 최적해와 국소 최적해

 극값 문서를 참고하십시오.

전역 극값과 국소 극값의 예. 전역 극값은 표시된 정의역 전체에서 비교하고, 국소 극값은 해당 점의 근방에서 비교한다.

극값을 구할 때는 비교하는 범위를 구별한다. 가능 영역 $C$ 전체에서 가장 작은 목적함숫값을 갖는 점을 전역 최적해(영어: global minimizer)라고 한다. 반면 $x^{*}\in C$의 어떤 근방에 있는 가능해들만 비교하여 가장 작은 값을 갖는 점을 국소 최적해(영어: local minimizer)라고 한다. 유클리드 공간에서는 어떤 $\varepsilon >0$에 대하여

$f(x^{*})\leq f(x)\quad {\text{for all }}x\in C{\text{ with }}\|x-x^{*}\|_{2}<\varepsilon$

가 성립한다는 뜻이다. 여기서 $\|x-x^{*}\|_{2}$는 유클리드 거리이다. 가능 영역의 경계에 있는 점도 이 정의에 포함된다.

함수 $f(x)=x^{3}-3x$를 실수 전체에서 보면 $x=1$은 국소 최소점이지만, $x$가 음의 방향으로 한없이 작아질 때 함숫값도 한없이 작아지므로 전역 최소점은 아니다. 모든 전역 최적해는 국소 최적해이지만 그 역은 일반적으로 성립하지 않는다. 여러 국소 최적해가 존재할 때 그 목적함숫값이 서로 같을 필요도 없다.

국소 최적해의 정의에서 $x\neq x^{*}$인 근방의 모든 가능해에 대해 엄격한 부등식 $f(x^{*})<f(x)$가 성립하면 엄격한 국소 최적해(영어: strict local minimizer)라고 한다. 국소 최적해에는 주변의 다른 가능해에서 같은 목적함숫값을 갖는 경우도 포함된다. 이산 문제의 국소 탐색에서는 변수 하나를 바꾸거나 경로의 일부를 교환하는 등의 연산으로 이웃을 별도로 정하기도 한다. 이때 국소 최적성은 선택한 이웃의 정의에 따라 달라진다.

문제의 유형

최적화 문제를 나누는 기준에는 변수의 종류, 볼록성, 함수의 형태, 불확실성의 유무, 목적함수의 수 등이 있다. 한 문제가 여러 유형에 동시에 속할 수 있다. 예를 들어 선형 계획 문제는 연속 최적화이면서 볼록 최적화이고, 정수 조건을 추가한 선형 문제는 이산 최적화의 대상이 된다.

연속 최적화와 이산 최적화

 정수 계획법 및 조합 최적화 문서를 참고하십시오.

연속 최적화에서는 결정 변수가 실수 구간이나 실수 공간의 영역에서 값을 취한다. 이산 최적화에서는 정수, 유한한 선택지, 순열과 같은 이산적인 대상을 선택한다. 정수 계획법은 정수 조건을 가진 변수로 문제를 표현하며, 조합 최적화는 경로·배치·순서와 같은 조합적 구조를 다룬다. 외판원 문제는 주어진 도시를 각각 한 번씩 방문하고 출발점으로 돌아오는 경로 가운데 총길이가 가장 짧은 것을 찾는 대표적인 예이다.

정수 계획법에서 일부 변수는 정수이고 나머지는 연속인 문제를 혼합 정수 계획 문제(영어: mixed-integer programming problem)라고 한다. 예를 들어 물류 시설의 개설 여부는 0과 1로 표현하고, 열린 시설에서 출하하는 양은 음이 아닌 실수로 표현할 수 있다.

선택지가 유한하면 모든 후보를 비교하는 알고리즘으로 최적해를 구할 수 있다. 그러나 후보 수가 문제의 크기에 따라 급격히 늘어나면 이 방법은 계산에 너무 오래 걸린다. 이산 문제 가운데서도 목적함수와 제약의 구조를 이용해 효율적으로 풀 수 있는 문제가 있다.

볼록 최적화와 비볼록 최적화

 이 부분의 본문은 볼록 최적화입니다.

볼록 함수의 그래프. 그래프 위 두 점을 잇는 선분은 두 점 사이에서 그래프보다 아래로 내려가지 않는다.

볼록 집합은 집합 안의 임의의 두 점을 잇는 선분 전체를 포함하는 집합이다. 볼록 집합 $C$ 위의 함수 $f$가 임의의 $x,y\in C$와 $0\leq t\leq 1$에 대해

$f(tx+(1-t)y)\leq tf(x)+(1-t)f(y)$

를 만족하면 볼록 함수라고 한다. 볼록 집합 위에서 볼록 함수를 최소화하는 문제를 볼록 최적화 문제라고 한다. 변수의 정의역이 볼록하고, 부등식 제약 함수가 볼록하며 등식 제약 함수가 아핀이면 가능 영역도 볼록하다.

볼록 최적화 문제에서는 모든 국소 최적해가 전역 최적해이다. 또한 최적해가 여러 개이면 그 두 최적해를 잇는 선분 위의 점도 모두 최적해이다. 다만 볼록성만으로 최적해가 존재하거나 유일하다는 결론이 나오지는 않는다.

비볼록 문제에서는 여러 국소 최적해나 안장점이 나타날 수 있으며, 국소적인 정보만으로 전역 최적성을 판단하기 어려울 수 있다. 비볼록 문제 가운데도 변수 변환을 통해 볼록 문제로 바꾸거나, 문제의 특수한 구조를 이용해 효율적으로 풀 수 있는 경우가 있다.

선형·이차·비선형 계획법

 선형 계획법 및 비선형 계획법 문서를 참고하십시오.

선형 계획법은 목적함수와 제약을 일차식과 상수항으로 표현하는 문제를 다룬다. 예를 들어

$\min _{x}c^{\mathsf {T}}x\quad {\text{subject to }}Ax\leq b,\ Ex=d$

와 같이 쓴다. 부등식은 각 성분에 대해 해석한다. 목적함수와 제약 함수가 엄밀히는 아핀 함수여도 선형 계획 문제라고 부른다. 앞서 든 생산 계획 문제가 여기에 해당한다.

이차 계획법(영어: quadratic programming)은 목적함수가 이차식이고 제약이 선형인 문제를 다룬다. 목적함수는 대칭행렬 $Q$를 사용하여

$f(x)={\frac {1}{2}}x^{\mathsf {T}}Qx+c^{\mathsf {T}}x+r$

로 나타낼 수 있다. $Q$가 양의 준정부호이면 목적함수가 볼록하므로 볼록 최적화 문제가 된다. 예를 들어 최소제곱법의 목적함수 $\|Ax-b\|_{2}^{2}$는 이러한 볼록 이차식이다. 일반적인 이차 계획 문제에서 $Q$가 양의 준정부호라고 가정할 수는 없다.

비선형 계획법은 목적함수나 제약 조건에 비선형 함수가 나타나는 문제를 다룬다. 비선형 함수도 볼록할 수 있으므로 비선형 계획 문제가 모두 비볼록인 것은 아니다. 앞의 최소제곱 문제가 그 예이다.

불확실성을 포함하는 최적화

 확률적 계획법 문서를 참고하십시오.

확률적 계획법에서는 정확히 알 수 없는 수요나 가격 등을 확률 변수로 나타내고, 알려져 있거나 추정한 확률 분포를 이용한다. 예를 들어 불확실한 양을 $\xi$, 결정 $x$에 따른 비용을 $f(x,\xi )$라 하자. 비용의 기댓값이 정의된다면 이를 최소화하는 문제

$\min _{x\in C}\mathbb {E} [f(x,\xi )]$

를 고려할 수 있다. 여러 시점에 걸친 문제에서는 처음의 결정과 추가 정보를 얻은 뒤의 결정을 구분한다. 나중의 결정은 그 시점까지 알게 된 정보에 따라 달라진다.

강건 최적화(영어: robust optimization)는 불확실한 양이 속하는 집합 $U$를 정하고, 그 범위에서의 최악의 경우를 고려한다. 한 가지 형태는

$\min _{x\in C}\sup _{u\in U}f(x,u)$

이다. 제약에도 불확실성이 있으면 $u\in U$의 모든 경우에 제약을 만족하도록 요구할 수 있다. 기댓값과 최악의 경우 중 무엇을 기준으로 삼느냐에 따라 최적해가 달라질 수 있다. 가정한 확률 분포나 불확실성 집합도 해에 영향을 준다.

다목적 최적화

 파레토 최적 문서를 참고하십시오.

두 기준에 따른 파레토 최적해의 예. 한 기준에서 더 나은 값을 얻으려면 다른 기준의 값은 나빠져야 한다.

다목적 최적화(영어: multi-objective optimization)는 여러 목적함수를 함께 최적화하는 문제를 다룬다. 비용을 줄이면서 성능을 높이는 문제가 한 예이다. 한 목적함수를 줄이는 선택이 다른 목적함수를 키울 수 있으므로, 모든 목적함수를 동시에 최소화하는 해가 없을 수 있다. 이때 해를 비교하는 데 파레토 최적 개념을 쓴다. 최소화할 목적함수들이 $f_{1},\ldots ,f_{k}$일 때, 가능해 $x^{*}$에 대해

$f_{i}(x)\leq f_{i}(x^{*})\quad (i=1,\ldots ,k)$

를 모두 만족하면서 적어도 하나에서는 엄격한 부등식을 만족하는 다른 가능해 $x$가 없다면 $x^{*}$를 파레토 최적해라고 한다.

예를 들어 실수 $x$에 대해 $f_{1}(x)=x^{2}$와 $f_{2}(x)=(x-2)^{2}$를 함께 최소화하면, 각각의 최솟값을 주는 점은 0과 2로 다르다. $0\leq x\leq 2$에서는 한 목적함수를 줄이면 다른 목적함수가 커지므로 이 구간의 모든 점이 파레토 최적해이다. 구간 밖의 점은 더 가까운 끝점으로 옮겨 두 목적함숫값을 모두 줄일 수 있다.

여러 목적함수에 양의 가중치 $w_{i}$를 붙인 가중합 $\sum _{i}w_{i}f_{i}(x)$를 최소화할 수도 있다. 이 합의 전역 최적해는 파레토 최적해이다. 그러나 양의 가중치를 바꾸는 것만으로 모든 파레토 최적해를 얻는 것은 아니다. 앞의 예에서 가중합의 최적해는 $x=2w_{2}/(w_{1}+w_{2})$로 0과 2 사이에 있으므로 두 끝점은 얻을 수 없다.

최적해의 성질과 조건

존재성과 유일성

 최대 최소 정리 문서를 참고하십시오.

최대 최소 정리에 따르면 비어 있지 않은 콤팩트 집합 위의 연속 함수는 최솟값과 최댓값을 갖는다. 유한 차원 유클리드 공간에서는 집합이 닫혀 있고 유계이면 콤팩트하다. 따라서 가능 영역에 이 조건이 성립하고 목적함수가 연속이면 최적해의 존재가 보장된다. 이 조건들은 존재를 보장하는 충분조건이며, 필요조건은 아니다.

가능 영역이 유계가 아니어도 최적해가 존재할 수 있다. 예를 들어 $\mathbb {R}$에서 $f(x)=x^{2}$는 0에서 최소가 된다. 더 일반적으로, 비어 있지 않은 닫힌 집합 $C\subseteq \mathbb {R} ^{n}$에서 $f$가 연속이고, $x\in C$에 대해 $\|x\|_{2}\to \infty$일 때 $f(x)\to +\infty$이면 최솟값을 달성한다. 이 조건 아래에서는 정해진 값 이하의 함숫값을 갖는 점들이 유계인 집합을 이룬다.

최적해가 존재하더라도 여러 개일 수 있다. 볼록 함수의 정의에서 서로 다른 $x,y$와 $0<t<1$에 대해 항상 엄격한 부등식이 성립하면 엄격 볼록 함수라고 한다. 볼록 가능 영역에서 엄격 볼록 함수를 최소화할 때 최적해가 존재한다면 그것은 유일하다. 그러나 지수 함수 $e^{x}$처럼 엄격 볼록하면서 실수 전체에서 최솟값을 달성하지 않는 함수도 있다.

무제약 최적화의 조건

 극값 및 헤세 행렬 문서를 참고하십시오.

목적함수 $f$가 열린 근방에서 미분 가능하고 $x^{*}$가 그 내부의 국소 최소점이면

$\nabla f(x^{*})=0$

이 성립한다. $\nabla f$는 각 변수에 대한 편미분을 모은 기울기이다. 기울기가 0인 점을 정지점(영어: stationary point)이라고 한다. 정지점이 항상 최적해인 것은 아니다. 예를 들어 $f(x)=x^{3}$은 0에서 도함수가 0이어도 극값을 갖지 않는다.

함수가 두 번 연속 미분 가능하면 이차 편미분으로 구성된 헤세 행렬을 이용한다. 국소 최소점에서는 $\nabla ^{2}f(x^{*})$가 양의 준정부호여야 한다. 반대로 정지점에서 헤세 행렬이 양의 정부호이면 그 점은 엄격한 국소 최소점이다. 준정부호라는 조건만으로는 충분하지 않다. $x^{4}$와 $-x^{4}$는 모두 0에서 일차·이차 도함수가 0이지만, 0에서 각각 최솟값과 최댓값을 갖는다.

열린 볼록 집합에서 정의된 미분 가능한 볼록 함수에서는 기울기가 0인 점이 전역 최적해이다. 볼록 함수의 그래프는 접평면보다 아래로 내려가지 않고, 기울기가 0인 점의 접평면은 수평이기 때문이다. 비볼록 함수에서는 기울기가 0이라는 조건만으로 전역 최적성을 보장할 수 없다.

제약 최적화의 조건

 이 부분의 본문은 카루시-쿤-터커 조건입니다.

 라그랑주 승수법 문서를 참고하십시오.

제약이 있는 문제에서는 허용되지 않는 방향으로 목적함수가 감소할 수 있으므로, 최적해에서 목적함수의 기울기가 0일 필요는 없다. 예를 들어 $x\geq 1$에서 $f(x)=x^{2}$를 최소화하면 최적해는 1이지만 도함수는 2이다. 라그랑주 승수법은 제약 함수의 기울기를 함께 고려하며, 부등식까지 포함한 대표적인 조건이 카루시-쿤-터커 조건이다.

앞의 등식·부등식 제약 문제에서 함수들이 열린 정의역 $D$에서 연속 미분 가능하다고 하자. 라그랑주 함수를

$L(x,\lambda ,\nu )=f(x)+\sum _{i=1}^{m}\lambda _{i}g_{i}(x)+\sum _{j=1}^{p}\nu _{j}h_{j}(x)$

로 정의한다. KKT 조건은 $x^{*}\in D$와 승수 $\lambda ^{*},\nu ^{*}$에 대한 다음 조건들이다.

${\begin{aligned}\nabla f(x^{*})+\sum _{i=1}^{m}\lambda _{i}^{*}\nabla g_{i}(x^{*})+\sum _{j=1}^{p}\nu _{j}^{*}\nabla h_{j}(x^{*})&=0,\\g_{i}(x^{*})&\leq 0\quad (i=1,\ldots ,m),\\h_{j}(x^{*})&=0\quad (j=1,\ldots ,p),\\\lambda _{i}^{*}&\geq 0\quad (i=1,\ldots ,m),\\\lambda _{i}^{*}g_{i}(x^{*})&=0\quad (i=1,\ldots ,m).\end{aligned}}$

마지막 식은 상보성 조건으로, $g_{i}(x^{*})<0$인 부등식 제약의 승수는 0이어야 한다는 뜻이다. 등식 제약의 승수 $\nu _{j}^{*}$에는 부호 제한이 없다.

KKT 조건을 국소 최적해의 필요조건으로 사용하려면 제약에 대한 추가 가정이 필요하다. 대표적으로, 그 점에서 등식 제약의 기울기와 등호가 성립하는 부등식 제약의 기울기가 함께 일차 독립이면 이러한 승수가 존재한다. 반면 볼록 문제에서 $f,g_{i}$가 볼록하고 $h_{j}$가 아핀이면 KKT 조건은 전역 최적성의 충분조건이다.

쌍대성과 민감도 분석

라그랑주 함수로부터 쌍대함수와 쌍대 문제를

$q(\lambda ,\nu )=\inf _{x\in D}L(x,\lambda ,\nu ),\qquad d^{*}=\sup _{\lambda \geq 0,\nu }q(\lambda ,\nu )$

로 정의한다. 원래 문제의 가능해 $x$에서는 $L(x,\lambda ,\nu )\leq f(x)$이므로 $q(\lambda ,\nu )$는 원래 최적값 $p^{*}$의 하한이 된다. 따라서 $d^{*}\leq p^{*}$가 성립하며, 이를 약한 쌍대성이라고 한다. 쌍대 문제는 이러한 하한 가운데 가장 큰 값을 찾는다.

두 최적값이 같으면 강한 쌍대성이 성립한다고 한다. 볼록 최적화에서 이를 보장하는 대표적인 가정은 슬레이터 조건(영어: Slater's condition)이다. 목적함수와 부등식 제약 함수들이 열린 볼록 정의역에서 볼록하고, 등식 제약 함수들이 아핀이라고 하자. 이때 등식 제약을 만족하면서 모든 부등식 제약을 엄격히 만족하는 점이 존재하면 강한 쌍대성이 성립한다. 이 조건 아래에서 원래 최적값이 유한하면 최적의 쌍대 승수도 존재한다. 또한 원래 문제의 최적해가 존재하고 함수들이 미분 가능하면 그 최적해에 대응하는 KKT 승수를 얻을 수 있다.

쌍대 승수는 제약을 완화했을 때 최적값이 변하는 비율을 나타낼 수 있다. 위의 볼록 문제에서 슬레이터 조건이 성립하고 $p^{*}$가 유한하다고 하자. 부등식 제약을 $g_{i}(x)\leq u_{i}$로 바꾼 문제의 최적값을 $V(u)$라고 할 때, $V$가 $u=0$에서 미분 가능하면 원래 문제의 최적 쌍대 승수에 대해

${\frac {\partial V}{\partial u_{i}}}(0)=-\lambda _{i}^{*}$

이다. 양의 승수는 그 제약을 조금 완화했을 때 최적값이 감소하는 비율을 나타낸다. 예를 들어 $\min x$에 제약 $-x\leq u$를 두면 $V(u)=-u$이고 대응하는 승수는 1이다.

계산 방법

최적화 알고리즘은 목적함수와 제약의 구조, 이용할 수 있는 미분 정보, 요구하는 정확도 등에 따라 선택한다. 작은 문제는 수식이나 그림으로 직접 풀 수 있지만, 변수가 많거나 함수가 복잡한 문제는 주로 수치 계산으로 푼다. 연속 최적화의 계산 결과는 대개 유한한 정확도의 근사값이다. 이산 최적화에서도 계산 시간을 제한하면 알고리즘이 최적성을 증명하지 못한 채 가능해를 반환할 수 있다.

반복 계산과 종료 기준

반복 계산에서는 초기점에서 시작하여 $x_{0},x_{1},x_{2},\ldots$와 같은 수열을 만든다. 각 단계에서는 목적함숫값, 미분 정보, 제약 위반 정도 등을 이용해 다음 후보를 계산한다. 계산은 목적함숫값의 변화, 변수의 변화, 기울기나 최적성 조건의 잔차 등이 설정한 허용오차보다 작아지면 종료할 수 있다. 실행 시간과 반복 횟수에 상한을 둘 수도 있다.

작은 변화량이 곧 작은 오차를 뜻하지는 않는다. 예를 들어 이동 폭이 너무 작으면 최적해에서 멀리 있어도 연속한 두 후보가 거의 같을 수 있다. 비볼록 문제에서는 기울기가 작다는 사실만으로 전역 최적값에 가깝다고 결론 내릴 수 없다. 제약 문제에서는 목적함숫값과 더불어 제약을 어느 정도 만족하는지도 확인한다.

최적값의 하한 $\ell$과 가능해 ${\hat {x}}$를 알고 있으면

$0\leq f({\hat {x}})-p^{*}\leq f({\hat {x}})-\ell$

을 얻는다. 따라서 오른쪽 차이가 $\varepsilon$ 이하임을 확인하면 목적함숫값의 오차도 $\varepsilon$ 이하임을 보장할 수 있다. 쌍대 문제나 완화 문제는 이러한 하한을 얻는 데 사용된다. 다만 목적함숫값이 최적값에 가깝더라도, 구한 점이 어떤 최적해에 가까이 있다는 뜻은 아니다.

미분 정보를 이용하는 방법

 경사 하강법, 뉴턴 방법, 준뉴턴 방법 및 확률적 경사 하강법 문서를 참고하십시오.

경사 하강법의 반복점이 이동하는 예. 곡선은 목적함숫값이 같은 점들을 나타낸다.

경사 하강법은 목적함수의 기울기와 반대 방향으로 이동한다. 기본적인 갱신식은

$x_{k+1}=x_{k}-\alpha _{k}\nabla f(x_{k})$

이며, 양수 $\alpha _{k}$는 이동 폭을 정한다. 미분 가능한 함수에서 기울기가 0이 아니면, 그 반대 방향으로의 이동 폭을 충분히 작게 잡았을 때 함숫값이 감소한다. 그러나 이동 폭이 지나치게 크면 함숫값이 커지거나 반복점이 발산할 수 있다. 예를 들어 $f(x)=x^{2}/2$에 일정한 이동 폭을 쓰면 $x_{k+1}=(1-\alpha )x_{k}$이다. $\alpha =1/2$에서는 0으로 수렴하지만, $\alpha =3$이면 0이 아닌 초기점에서 크기가 계속 증가한다.

탐색 방향을 정한 뒤 그 방향을 따라 적절한 이동 폭을 선택하는 방법을 선 탐색(영어: line search)이라고 한다. 반드시 그 직선 위의 정확한 최솟값을 구할 필요는 없으며, 목적함수가 충분히 감소하는지 등의 조건으로 이동 폭을 정할 수 있다. 같은 경사 하강법을 사용하더라도 이동 폭의 선택에 따라 계산 속도와 수렴 여부가 달라진다.

뉴턴 방법은 기울기와 헤세 행렬로 함수를 국소적인 이차식으로 근사한다. 헤세 행렬이 가역일 때 뉴턴 방향 $d_{k}$는

$\nabla ^{2}f(x_{k})d_{k}=-\nabla f(x_{k})$

를 풀어 구한다. 헤세 행렬의 양의 정부호성 등의 조건이 성립하고 초기점이 최적해에 충분히 가까우면 빠르게 수렴한다. 그러나 임의의 초기점에서는 함숫값이 감소하지 않을 수 있다. 이를 보완하기 위해 이동 폭을 줄이거나 이차 근사에 쓰는 행렬을 수정하기도 한다.

준뉴턴 방법은 반복점과 기울기의 변화를 이용하여 헤세 행렬 또는 그 역행렬을 근사한다. 대표적인 BFGS 방법은 이차 미분을 직접 계산하지 않고 근사 행렬을 갱신한다. L-BFGS는 최근의 일부 갱신 정보만 저장하여 큰 행렬을 그대로 보관하는 데 드는 기억 공간을 줄인다.

목적함수가 많은 항의 평균으로 주어진 문제에서는 확률적 경사 하강법을 사용할 수 있다. 모든 항의 기울기를 계산하는 대신 무작위로 선택한 하나 또는 일부 항으로 전체 기울기를 추정한다. 예를 들어 $f(x)=N^{-1}\sum _{i=1}^{N}f_{i}(x)$에서 인덱스 $i$를 균등하게 선택하면 $\nabla f_{i}(x)$의 기댓값은 $\nabla f(x)$이다. 한 번의 계산 비용을 줄일 수 있지만, 무작위로 항을 선택하므로 매 단계에서 전체 목적함숫값이 감소하지는 않는다.

제약 조건의 처리

 내부점법 및 단체법 (알고리즘) 문서를 참고하십시오.

볼록 집합 $C\subseteq \mathbb {R} ^{n}$가 비어 있지 않고 닫혀 있으면, 임의의 점 $z$에서 유클리드 거리가 가장 짧은 $C$의 점 $P_{C}(z)$가 유일하게 정해진다. 이를 이용한 투영 경사법(영어: projected gradient method)은

$x_{k+1}=P_{C}{\bigl (}x_{k}-\alpha _{k}\nabla f(x_{k}){\bigr )}$

와 같이 제약을 만족하는 반복점을 만든다. 예를 들어 각 좌표가 음이 아니어야 하는 경우에는 음의 좌표를 0으로 바꾸는 것이 투영이다. 가능 영역으로의 투영을 쉽게 계산할 수 있을 때 유용하다.

벌점법(영어: penalty method)은 제약 위반의 크기를 목적함수에 더한다. 등식 $h(x)=0$을 처리하는 한 가지 방법은 $f(x)+\rho \|h(x)\|_{2}^{2}$를 최소화하는 것이다. 유한한 양수 $\rho$를 쓰면, 이 문제의 최적해가 원래 제약을 정확히 만족한다는 보장은 없다. 예를 들어 $x=1$이라는 제약 아래 $x^{2}$를 최소화하는 대신 $x^{2}+\rho (x-1)^{2}$를 최소화하면 해는 $\rho /(1+\rho )$이다. 증강 라그랑주 방법(영어: augmented Lagrangian method)은 라그랑주 승수 항과 벌점항을 함께 사용하고 승수를 갱신한다.

장벽법(영어: barrier method)은 가능 영역의 내부에서 경계에 가까워질수록 값이 커지는 장벽항을 목적함수에 더한다. 예를 들어 $g_{i}(x)<0$인 영역에서

$f(x)-\mu \sum _{i=1}^{m}\log(-g_{i}(x)),\qquad \mu >0$

를 사용하면 제약의 경계에 접근할 때 자연로그를 이용한 장벽항이 커진다. 볼록 문제에서는 적절한 가정 아래 $\mu$를 줄이며 이 문제를 풀어 원래 최적값에 접근할 수 있다. 이 방법은 내부점법에 쓰이며, 등식 제약은 별도로 유지하거나 변수를 제거하여 처리한다.

순차 이차 계획법(영어: sequential quadratic programming, SQP)은 현재 점에서 제약을 일차식으로 근사하고, 라그랑주 함수의 이차 미분 정보를 이용한 이차 부분 문제를 풀어 이동 방향을 정한다. 선 탐색 등을 결합하면 제약 위반과 목적함숫값을 함께 고려하여 이동 폭을 정할 수 있다.

선형 계획법의 대표적인 알고리즘인 단체법은 표준형 문제의 가능 영역에서 꼭짓점 사이를 이동하며 해를 찾는다. 퇴화가 있으면 한 번의 갱신으로 점이나 목적함숫값이 바뀌지 않을 수 있으므로 순환을 방지하는 규칙이 필요하다. 선형 계획 문제에는 내부점법도 사용된다.

이산 최적화의 계산

 분기 한정법, 분기 절단법 및 동적 계획법 문서를 참고하십시오.

정수 계획법에서는 정수 조건을 제거하는 완화(영어: relaxation)를 사용한다. 예를 들어 $x_{i}\in \{0,1\}$을 $0\leq x_{i}\leq 1$로 바꾸면 가능 영역이 커진다. 최소화 문제에서 완화 문제의 최적값은 원래 문제의 최적값보다 크지 않으므로 하한을 제공한다. 완화 문제의 최적해가 원래의 모든 정수 조건까지 만족하면 원래 문제의 최적해이기도 하다.

분기 한정법은 문제를 여러 부분 문제로 나누고 각 부분 문제의 최적값에 대한 상한이나 하한을 계산한다. 예를 들어 정수 변수의 완화해가 $x_{i}=2.4$이면 $x_{i}\leq 2$와 $x_{i}\geq 3$인 두 경우로 나눈다. 원래의 정수 가능해는 두 경우 중 하나에 속한다. 최소화에서 부분 문제가 실행 불가능하거나 그 최적값의 하한이 현재까지 찾은 가장 좋은 가능해의 값 이상이면, 더 좋은 해를 찾기 위해 그 부분을 탐색할 필요가 없다.

절단 평면법(영어: cutting-plane method)은 원래의 정수 가능해를 보존하면서 일부 비정수 해를 제외하는 부등식을 추가한다. 예를 들어 정수 $x,y$가 $2x+2y\leq 3$을 만족하면 $x+y\leq 1$도 만족한다. 이 부등식은 $(x,y)=(3/2,0)$ 같은 완화 문제의 해를 제외한다. 절단 평면을 분기 한정법과 결합한 방법을 분기 절단법이라고 한다.

동적 계획법은 문제를 작은 부분 문제로 나누어 푼 뒤, 그 결과를 저장해 재사용한다. 0–1 배낭 문제에서 물건 $i$의 무게를 양의 정수 $w_{i}$, 가치를 음이 아닌 정수 $v_{i}$라 하고, 음이 아닌 정수 용량 $b$ 안에서 처음 $i$개 물건으로 얻는 최대 가치를 $V_{i}(b)$라고 하자. $w_{i}\leq b$이면

$V_{i}(b)=\max\{V_{i-1}(b),\ v_{i}+V_{i-1}(b-w_{i})\}$

이다. 첫째 항은 물건 $i$를 제외하는 경우이고 둘째 항은 포함하는 경우이다. $w_{i}>b$이면 첫째 항만 쓰며, 초기값은 $V_{0}(b)=0$이다. 물건 수가 $n$, 전체 용량이 양의 정수 $W$이면 이 점화식을 $O(nW)$개의 상태로 계산할 수 있다. 이는 $W$의 수치에 대한 복잡도이므로, $W$를 이진수로 적는 데 필요한 자릿수에 대한 다항 시간과는 구별되는 의사 다항 시간이다.

전역 최적화와 휴리스틱

 메타휴리스틱 및 근사 알고리즘 문서를 참고하십시오.

전역 최적화는 가능 영역 전체에서의 최적성을 다룬다. 연속 비볼록 문제에도 분기 한정법을 적용할 수 있으며, 영역을 나누고 각 영역의 최적값에 대한 하한을 계산하여 탐색을 진행한다. 하한을 이용하면 목적함숫값의 오차가 허용 범위 안에 드는지 확인할 수 있지만, 이를 위해 많은 영역을 탐색해야 할 수 있다.

초기점에 따라 서로 다른 국소 최적해를 얻을 수 있으므로, 여러 초기점에서 알고리즘을 실행한 뒤 그중 목적함숫값이 가장 좋은 해를 택하기도 한다. 그러나 유한한 횟수의 시도만으로 일반적인 비볼록 문제의 전역 최적성이 보장되지는 않는다. 이산 국소 탐색에서도 여러 시작점이나 서로 다른 이웃을 사용할 수 있다.

휴리스틱은 문제의 구조나 경험적인 규칙을 이용하여 적은 계산으로 유용한 해를 얻으려는 방법이다. 최적성이나 오차의 상한이 증명되지 않은 경우가 많다. 메타휴리스틱은 여러 문제에 공통으로 적용할 수 있는 탐색 방법으로, 문제에 맞게 후보를 표현하는 방식과 이동 규칙 등을 정해 사용한다.

담금질 기법은 더 나쁜 후보로 이동할 가능성도 두어 국소 최적해의 주변을 벗어나도록 한다. 최소화에서 후보로 이동할 때 목적함숫값이 $\Delta >0$만큼 증가하면, 대표적인 수용 확률은 $\exp(-\Delta /T)$이다. 양수 $T$는 온도 매개변수이며, 이를 낮출수록 목적함숫값이 증가하는 이동을 받아들일 확률이 작아진다. 수렴 성질은 온도를 줄이는 방식과 허용하는 이동에 따라 달라진다.

유전 알고리즘은 여러 후보로 이루어진 집단을 유지하면서 선택·교차·돌연변이 등의 연산으로 다음 집단을 만든다. 미분 정보 없이 후보들의 목적함숫값을 비교하면서 탐색할 수 있다.

근사 알고리즘은 정해진 종류의 문제에 대해 계산 시간과 근사해의 정확도를 이론적으로 보장한다. 예를 들어 양의 최적값을 갖는 최소화 문제의 2-근사 알고리즘은 다항 시간에 최적값의 두 배 이하인 목적함숫값을 갖는 가능해를 반환한다.

역사

미적분학과 변분법

 미적분학 및 변분법 문서를 참고하십시오.

17세기 피에르 드 페르마의 극값 연구와 아이작 뉴턴, 고트프리트 빌헬름 라이프니츠의 미적분학은 함수의 극값을 체계적으로 구하는 토대가 되었다. 미분을 이용하면 곡선의 기울기를 조사하여 극값의 후보를 찾을 수 있었고, 이후 여러 변수를 가진 함수와 제약이 있는 문제로 연구가 확장되었다.

같은 두 점을 잇는 여러 경로를 따라 내려가는 입자의 비교. 균일한 중력 아래에서 정지 상태로 출발하고 마찰이 없을 때, 붉은 사이클로이드 경로를 따라간 입자가 가장 먼저 도착한다.

1696년 요한 베르누이가 제시한 최단시간 곡선 문제는 입자의 이동 시간을 최소화하는 경로를 찾는 문제이다. 입자는 균일한 중력 아래에서 정지 상태로 출발하여 마찰 없이 움직인다. 도착점이 출발점보다 낮고 두 점이 같은 수직선 위에 있지 않을 때, 해는 사이클로이드의 일부이다. 이러한 문제를 연구하면서 수치가 아닌 함수 자체를 최적화하는 변분법이 발전했다.

레온하르트 오일러는 1744년에 변분 문제를 체계적으로 다룬 저술을 출판했고, 이후 조제프루이 라그랑주는 변분 문제의 해석적 방법을 발전시켰다. 오일러-라그랑주 방정식은 적분값의 일차변분이 0이 되는 경로가 만족해야 할 방정식이다.

수리 계획법과 계산 방법의 발전

아드리앵마리 르장드르와 카를 프리드리히 가우스의 최소제곱법 연구는 관측 오차를 다루는 계산과 최적화를 연결했다. 1847년 오귀스탱 루이 코시는 최급강하 방법을 제시했다. 20세기에는 자원 배분과 생산·운송 계획 문제를 풀기 위한 수리 계획법이 발전했다. 계산기의 발달로 변수가 많은 문제도 다룰 수 있게 되었다.

선형 계획법의 발전에는 1939년 레오니트 칸토로비치의 생산 계획 연구와 1947년 조지 댄치그의 단체법 개발이 중요한 역할을 했다. 여기서 계획법이라는 말은 활동과 자원의 배분 계획을 뜻하며, 컴퓨터 프로그램을 작성한다는 뜻에서 유래한 것이 아니다.

비선형 제약 문제에서는 1939년 카루시의 연구와 1951년 쿤·터커의 연구가 오늘날의 카루시-쿤-터커 조건으로 이어졌다. 1950년대에는 리처드 E. 벨먼이 동적 계획법을 발전시켰고, 이후 기울기 정보로 곡률을 근사하는 준뉴턴 방법이 개발되었다. 1970년에 제안된 BFGS 갱신은 그 대표적인 예이다.

1979년 하치얀(영어: Leonid Khachiyan)은 유리수로 주어진 선형 계획 문제를 입력의 비트 수에 대한 다항 시간에 풀 수 있음을 보였다. 1984년 카르마르카르(영어: Narendra Karmarkar)의 선형 계획 알고리즘은 내부점법 연구를 크게 촉진했다.

응용과 관련 분야

운용 과학과 경제학

 운용과학, 소비자 이론 및 현대 포트폴리오 이론 문서를 참고하십시오.

운용과학에서는 생산·배치·운송 등의 의사결정을 최적화 문제로 표현한다. 예를 들어 여러 공장에서 여러 소비지로 제품을 보내는 운송 계획에서는 각 공장과 소비지 사이의 운송량을 결정 변수로 삼는다. 단위 운송 비용이 일정하고 운송량을 연속적인 양으로 취급하면, 공장의 공급 한도와 소비지의 수요를 만족하면서 총비용을 최소화하는 선형 계획 문제를 얻는다.

소비자 이론에서는 선호를 효용함수 $u(x)$로 나타내고 예산 제약 아래에서 효용을 최대화하는 모형을 사용한다. 재화의 가격이 $p_{i}>0$, 예산이 $M\geq 0$이면 제약은 $\sum _{i}p_{i}x_{i}\leq M$, $x_{i}\geq 0$이다. 예를 들어 $u(x_{1},x_{2})={\sqrt {x_{1}x_{2}}}$, $p_{1}=p_{2}=1$, $M=10$인 모형에서는 $x_{1}=x_{2}=5$일 때 효용이 최대이다.

현대 포트폴리오 이론에서는 자산별 투자 비중을 정하는 데 최적화를 사용한다. 자산 수익률의 기댓값과 공분산이 주어졌을 때, 기대 수익률을 정해진 수준 이상으로 유지하면서 포트폴리오 수익률의 분산을 최소화하는 문제가 한 예이다. 투자 비중이 음이 아니고 합이 1이라는 조건을 두면 볼록 이차 계획 문제로 나타낼 수 있다. 분산에는 개별 자산의 변동뿐 아니라 자산들 사이의 공분산도 반영된다.

통계학과 기계 학습

 최대가능도 방법, 경험적 위험 최소화 및 정칙화 문서를 참고하십시오.

관측 자료에 최소제곱법으로 직선을 맞춘 예. 관측값과 직선의 예측값 사이의 차이를 제곱하여 합한 값을 최소화한다.

통계학에서는 관측 자료로부터 모형의 매개변수를 추정하는 데 최적화를 이용한다. 최대가능도 방법은 관측 자료를 고정한 상태에서 가능도 함수를 최대화하는 매개변수를 구한다.

지도 학습에서는 입력과 정답으로 이루어진 학습 자료 $(x_{i},y_{i})$가 $N$개 주어졌을 때, 예측 모형 $h_{\theta }$의 매개변수 $\theta$를 정한다. 예측값과 정답 사이의 오차를 손실 함수 $\ell$로 나타내면, 학습 자료의 평균 손실을 최소화하는 경험적 위험 최소화 문제를 다음과 같이 쓸 수 있다.

$\min _{\theta \in \Theta }{\frac {1}{N}}\sum _{i=1}^{N}\ell {\bigl (}h_{\theta }(x_{i}),y_{i}{\bigr )}.$

여기서 $N$은 양의 정수이고, $\Theta$는 허용하는 매개변수의 집합이다. 예측값과 정답의 차이를 제곱한 손실을 사용하면 최소제곱법에 해당한다.

학습 자료에는 잘 맞지만 같은 확률 분포에서 얻은 새로운 자료에서는 예측 오차가 큰 과적합이 발생할 수 있다. 정칙화는 과적합을 줄이는 방법으로, 위 목적함수에 벌점항 $\lambda R(\theta )$를 더하는 방식이 있다. 여기서 $R$은 매개변수에 부과할 벌점을 정하는 함수이며, $\lambda \geq 0$는 벌점의 비중을 조절한다. 예를 들어 매개변수 성분들의 제곱합을 $R(\theta )$로 사용하면, 양의 $\lambda$에 대해 그 제곱합이 클수록 벌점항도 커진다.

공학·물리학과 최적 제어

 최적 제어, 변분법 및 해밀턴의 원리 문서를 참고하십시오.

공학의 설계 문제에서는 부품의 크기와 형상 등을 결정 변수로 삼아 무게나 비용을 최소화한다. 예를 들어 구조물을 구성하는 부재의 두께를 정할 때, 주어진 하중에서 발생하는 응력이 허용 범위를 넘지 않도록 제약하면서 전체 무게를 최소화할 수 있다.

최적 제어에서는 계의 움직임을 나타내는 미분방정식을 제약으로 삼고, 시간에 따른 제어 입력을 선택하여 비용을 최소화한다. 상태를 $x(t)$, 제어 입력을 $u(t)$라고 하자. 초기 상태 $x_{0}$와 종료 시각 $T>0$이 주어지면 다음과 같은 문제를 생각할 수 있다.

${\begin{aligned}\min _{x(\cdot ),u(\cdot )}\quad &\Phi (x(T))+\int _{0}^{T}c(x(t),u(t))\,dt\\{\text{subject to}}\quad &{\dot {x}}(t)=F(x(t),u(t))\quad (0\leq t\leq T),\\&x(0)=x_{0}.\end{aligned}}$

여기서 $F$는 상태의 변화를 정하는 함수이고, $c$는 단위 시간당 비용, $\Phi$는 종료 상태에 따른 비용이다. 로봇의 이동을 계획할 때는 장애물과 충돌하지 않아야 한다는 조건이나 제어 입력의 상한과 하한을 추가할 수 있다. 시간 구간을 나누어 미분방정식과 비용 적분을 근사하고, 각 시점의 상태와 입력을 변수로 삼으면 유한 차원 최적화 문제를 얻을 수 있다.

역학에서는 에너지의 최소화로 평형을 분석하기도 한다. 예를 들어 수직으로 고정된 원형 고리에 끼워져 마찰 없이 움직일 수 있는 구슬은 중력에 의한 위치 에너지가 최소인 고리의 맨 아래에서 안정된 평형을 이룬다.

운동 법칙을 변분법으로 나타내는 해밀턴의 원리에 따르면, 시작과 끝의 시각·위치를 고정한 채 경로를 변화시켰을 때 작용의 일차변분이 0이다. 이 조건만으로 그 경로에서 작용이 최소라고 할 수는 없다.

같이 보기

• 게임 이론
• 역문제

참고 문헌

교재와 강의 자료

• Dimitri P. Bertsekas (2016). 《Nonlinear Programming》 (PDF) 3판 (영어). 공개 발췌본. Athena Scientific. ISBN 9781886529052.  부록 A·B 및 참고문헌.
• Joaquim R. R. A. Martins; Andrew Ning (2022). 《Engineering Design Optimization》 (영어). Cambridge University Press. doi:10.1017/9781108980647. ISBN 9781108833417. 
  • 1. Introduction · 2. A Short History of Optimization.
• Stephen Boyd; Lieven Vandenberghe; Parth Nobel. “Convex Optimization: Lecture Slides” (영어). 개정 강의 자료. 《Stanford University》. 2026년 9월 13일에 확인함. 
  • 1. Introduction · 2. Convex Sets · 3. Convex Functions.
  • 4. Optimization Problems · 5. Duality.
  • 9. Unconstrained Minimization · 11. Interior-point Methods.
• Robert M. Freund (2004). “Optimality Conditions for Constrained Optimization Problems” (PDF) (영어). 《MIT OpenCourseWare》. 2026년 9월 13일에 확인함. 
• Robert M. Freund (2004). “Penalty and Barrier Methods for Constrained Optimization” (PDF) (영어). 《MIT OpenCourseWare》. 2026년 9월 13일에 확인함. 
• MIT OpenCourseWare (2009). 15.083J: Integer Programming and Combinatorial Optimization. 강의 자료 (영어, PDF).
  • 17강: Cutting Plane Methods I.
  • 19강: Enumerative Methods.
  • 20강: Heuristic Methods.
  • 21강: Approximation Algorithms I.
• “Lecture 21: Dynamic Programming III” (PDF) (영어). 《MIT OpenCourseWare, 6.006》. 2011. 2026년 9월 13일에 확인함. 
• “Branch and Bound Methods” (PDF) (영어). 《Stanford University, EE364b》. 2026년 9월 13일에 확인함. 
• Léon Bottou (2010). “Large-Scale Machine Learning with Stochastic Gradient Descent” (PDF) (영어). 2026년 9월 13일에 확인함. 
• Andrew Ng. “CS229 Lecture Notes” (PDF) (영어). 《Stanford University》. 2026년 9월 13일에 확인함. 
• David Autor (2016). “Lecture 4: Utility Maximization” (PDF) (영어). 《MIT OpenCourseWare》. 2026년 9월 13일에 확인함. 
• David Tong. “Classical Dynamics” (PDF) (영어). 《David Tong》. 2026년 9월 13일에 확인함. 

문제 유형과 알고리즘 자료

• “Guide to Optimization” (영어). 《NEOS Guide》. 2026년 9월 13일에 확인함. 
  • 문제 유형: Optimization Problem Types · Integer Programming · Quadratic Programming · Nonlinear Constrained Optimization.
  • 불확실성을 포함하는 문제: Stochastic Programming · Robust Optimization.
  • 계산 방법: Line Search Methods · Quasi-Newton Methods · Gradient Projection Methods.
  • 제약 조건의 처리: Augmented Lagrangian Methods · Sequential Quadratic Programming · Simplex Method.
• “The Traveling Salesman Problem” (영어). 《University of Waterloo》. 2026년 9월 13일에 확인함. 
• Paul E. Black (2004). “heuristic” (영어). 《Dictionary of Algorithms and Data Structures, NIST》. 2026년 9월 13일에 확인함. 
• Paul E. Black (2009). “metaheuristic” (영어). 《Dictionary of Algorithms and Data Structures, NIST》. 2026년 9월 13일에 확인함. 
• “minimize(method='SLSQP')” (영어). 《SciPy Documentation》. 2026년 9월 13일에 확인함. 
• “What Is the Genetic Algorithm?” (영어). 《MathWorks》. 2026년 9월 13일에 확인함. 

역사와 응용 자료

• J. J. O’Connor; E. F. Robertson (1996). “The Rise of Calculus” (영어). 《MacTutor History of Mathematics Archive》. 2026년 9월 13일에 확인함. 
• J. J. O’Connor; E. F. Robertson (2002). “The brachistochrone problem” (영어). 《MacTutor History of Mathematics Archive》. 2026년 9월 13일에 확인함. 
• “E65 — Methodus inveniendi lineas curvas maximi minimive proprietate gaudentes, sive solutio problematis isoperimetrici latissimo sensu accepti” (영어). 《Euler Archive, University of the Pacific》. 2026년 9월 13일에 확인함. 
• “Optimization (Mathematical Programming)” (영어). 《INFORMS》. 2026년 9월 13일에 확인함. 
• “A Transportation Problem” (영어). 《GAMS Model Library》. 2026년 9월 13일에 확인함. 
• “Portfolio Optimization” (영어). 《CVX Short Course》. 2026년 9월 13일에 확인함. 
• Russ Tedrake. “Trajectory Optimization” (영어). 《Underactuated Robotics》. 2026년 9월 13일에 확인함. 

외부 링크

• NEOS Guide — 최적화 문제와 알고리즘 안내 (영어)