수학적 최적화

수학적 최적화(대체 철자 최적화) 또는 수학적 프로그래밍은 사용 가능한 대안 ^[1]집합에서 일부 기준과 관련하여 최적의 요소를 선택하는 것이다.최적화 문제는 컴퓨터 공학에서^[2] 운영 연구 및 경제학에 이르기까지 모든 양적 분야에서 발생하며, 솔루션 방법의 개발은 ^[3]수세기 동안 수학에서 관심을 보여 왔습니다.

가장 간단한 경우에서 최적화 문제는 허용된 집합 내에서 체계적으로 입력값을 선택하고 함수의 값을 계산함으로써 실제 함수를 최대화 또는 최소화하는 것으로 구성된다.최적화 이론과 기술을 다른 공식으로 일반화하는 것은 응용 수학의 큰 영역을 구성한다.보다 일반적으로 최적화는 정의된 도메인(또는 입력)에 따라 다양한 유형의 객관적 함수 및 다양한 유형의 도메인을 포함하여 일부 객관적 함수의 "최상 이용 가능한" 값을 찾는 것을 포함한다.

최적화 문제

최적화 문제는 다음과 같은 방법으로 나타낼 수 있습니다.

주어진 값: 함수 f : A → 일부 집합 A에서 실수까지의 값

필요한 요소₀: 모든 x µ A에 대해 f(x₀) µ f(x) 또는 모든 x µ A에 대해 f(x₀) µ f(x) µ f(x)가 되도록 한다.

이러한 공식은 최적화 문제 또는 수학적 프로그래밍 문제(컴퓨터 프로그래밍과 직접 관련이 없지만 선형 프로그래밍에서 여전히 사용되는 용어 - 아래 역사 참조)라고 불립니다.이 일반적인 프레임워크에서는 많은 현실적 및 이론적 문제를 모델링할 수 있습니다.

다음 사항이 유효하기 때문에

$\displaystyle f(\mathbf {x} _{0})\geq f(\mathbf {x})\leq -f(\mathbf {x} ),$

최소화 문제만 해결하면 됩니다.그러나 최대화 문제만을 고려하는 반대의 시각도 유효할 것이다.

물리학 분야에서 이 기술을 사용하여 공식화된 문제는 이 기술을 에너지 최소화라고 하며, 함수 f의 값을 모델링되는 시스템의 에너지를 나타내는 것으로 언급할 수 있습니다.기계학습에서는 항상 최소값이 최적(최저) 오차를 가진 최적의 매개변수 집합을 암시하는 비용 함수를 사용하여 데이터 모델의 품질을 지속적으로 평가할 필요가 있다.

전형적으로, A는 유클리드 공간 δ의ⁿ 일부 부분집합이며, 종종 A의 구성원들이 만족시켜야 하는 제약, 등식 또는 부등식의 집합으로 지정된다.f의 도메인 A는 서치 스페이스 또는 선택 세트라고 불리며, A의 요소는 후보 솔루션 또는 실현 가능한 솔루션이라고 불립니다.

함수 f는 다양한 방법으로 목적 함수, 손실 함수 또는 비용 함수(^[4]최소화), 효용 함수 또는 적합성 함수(최대화), 또는 특정 분야에서는 에너지 함수 또는 에너지 함수라고 불린다.목적 함수를 최소화하는(또는 목표인 경우 최대화하는) 실현 가능한 솔루션을 최적 솔루션이라고 합니다.

수학에서, 전통적인 최적화 문제는 보통 최소화의 관점에서 언급된다.

로컬 최소 x*는 다음과 같이 >0 이 존재하는 요소로 정의됩니다.

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

식 f(x*) ( f(x)는 유지된다.

즉, x* 주변의 일부 영역에서 모든 함수 값이 해당 요소의 값보다 크거나 같습니다.로컬 최대값도 마찬가지로 정의됩니다.

로컬 최소값은 적어도 인근 요소만큼 양호하지만 글로벌 최소값은 적어도 모든 실현 가능한 요소만큼 양호합니다.일반적으로, 최소화 문제에서 목적 함수가 볼록하지 않은 한, 여러 국소 최소치가 있을 수 있다.볼록형 문제에서 내부(가능 요소 집합의 가장자리가 아닌) 국소 최소값이 존재하는 경우, 그 역시 글로벌 최소값이지만 비볼록형 문제에는 글로벌 최소값이 모두 글로벌 최소값일 필요는 없는 여러 국소 최소값이 있을 수 있습니다.

비볼록 문제를 해결하기 위해 제안된 알고리즘(상업적으로 이용 가능한 해결사의 대다수를 포함)은 국소적으로 최적의 솔루션과 글로벌하게 최적의 솔루션을 구별할 수 없으며, 전자를 원래 문제에 대한 실제 해결책으로 취급할 것이다.글로벌 최적화는 비볼록 문제의 실제 최적 해법에 대한 유한한 시간 내 수렴을 보장할 수 있는 결정론적 알고리즘의 개발에 관련된 응용 수학과 수치 분석의 한 분야이다.

표기법

최적화 문제는 종종 특별한 표기법으로 표현됩니다.다음은 몇 가지 예입니다.

함수의 최소값과 최대값

다음 표기법을 고려해 주십시오.

$\displaystyle \min _{x\in \mathbb {R}}\;\left(x^{2}+1\right)}$

이는 실수 집합에서 x를 선택할 때 목적 함수² x + 1의 최소값을 나타낸다.이 경우 최소값은 1이며 x = 0에서 발생합니다.

마찬가지로 표기법도

$\displaystyle \max _{x\in \mathbb {R}\; 2x}$

는 목적 함수 2x의 최대값을 요구합니다.여기서 x는 임의의 실수입니다.이 경우, 목적 함수에 제한이 없기 때문에 답은 "infinite" 또는 "undefined"입니다.

최적 입력 인수

다음 표기법을 고려해 주십시오.

${\displaystyle {x\in(-\infty,-1]){\operatorname {param,min}}\;x^{2}+1,}$

또는 동등하게

${\displaystyle {\underset {x}{\operatorname {display,min}}}\;x^{2}+1,\;{\text{:}}\;x\in(-\infty,-1)}.}$

이는 목표함수² x + 1을 최소화(또는 최소화)하는 간격(-'-1')의 인수 x 값(또는 값)을 나타냅니다(이 함수의 실제 최소값은 문제가 요구하는 값이 아닙니다).이 경우 답은 x = -1입니다.x = 0은 실행할 수 없기 때문에 실현 가능한 집합에 속하지 않습니다.

유사하게,

${\displaystyle {x\in [-5,5],\y\in \mathbb {R}{\operatorname {arg,max}}}\;x\cos y,}$

또는 동등하게

${{displaystyle {x,\;y}{\operatorname {arg,max}}}\;x\cos y,\;{\text {subject to:}}\;x\in [-5,5],\;y\in \mathbb {R},}}$

는 목적함수 x cos y의 값을 최대화(또는 최대화)하는 {x, y}쌍(또는 쌍)을 나타내며 x가 [-5,5]구간에 있다는 제약조건이 추가되었습니다(이것도 식의 실제 최대값은 중요하지 않습니다).이 경우 해는 {5, 2k}} 및 {-5, (2k + 1)},} 형식의 쌍입니다. 여기서 k는 모든 정수에 걸쳐 있습니다.

연산자 arg min 및 arg max는 argmin 및 argmax로도 표기되며 minimum 인수와 maximum 인수를 나타냅니다.

역사

페르마와 라그랑주는 최적화를 식별하기 위한 미적분 기반 공식을 발견한 반면, 뉴턴과 가우스는 최적화를 위해 반복적인 방법을 제안했다.

특정 최적화 사례에 대한 "선형 프로그래밍"이라는 용어는 조지 B에 기인했다. 비록 이론의 많은 부분이 1939년에 레오니드 칸토로비치에 의해 소개되었지만, 이 맥락에서 프로그래밍은 컴퓨터 프로그래밍을 말하는 것이 아니라, 제안된 훈련과 물류 일정을 참조하기 위한 미군의 프로그램 사용에서 비롯되었다.1947년 단치히가 심플렉스 알고리즘을 발표했고, 같은 해 존 폰 ^{[citation needed]}노이만이 이원성 이론을 개발했다.

수학적 최적화의 다른 주목할 만한 연구자에는 다음이 포함된다.

주요 서브필드

• 볼록 프로그래밍은 목적 함수가 볼록(최소화) 또는 오목(최대화)이고 제약 조건 집합이 볼록한 경우를 연구합니다.이것은 비선형 프로그래밍의 특정 경우 또는 선형 또는 볼록 2차 프로그래밍의 일반화라고 볼 수 있다.
  • 볼록 프로그래밍의 일종인 선형 프로그래밍(LP)은 목적 함수 f가 선형이며 선형 등식과 부등식만을 사용하여 제약조건을 규정하는 경우를 연구한다.이러한 제약 조건 집합을 다면체 또는 다면체라고 합니다.
  • 2차 콘 프로그래밍(SOCP)은 볼록한 프로그램으로 특정 유형의 2차 프로그램을 포함합니다.
  • SDP(Semifinite Programming)는 볼록 최적화의 하위 필드이며, 기본 변수는 반무한 행렬입니다.그것은 선형 및 볼록 2차 프로그래밍의 일반화이다.
  • 원뿔형 프로그래밍은 볼록형 프로그래밍의 일반적인 형태입니다.LP, SOCP 및 SDP는 모두 적절한 원뿔형 프로그램으로 볼 수 있습니다.
  • 기하학적 프로그래밍은 양의미얼로 표현되는 객관적 및 부등식 제약과 모노미얼로 표현되는 평등 제약이 볼록한 프로그램으로 변환될 수 있는 기술이다.
• 정수 프로그래밍은 일부 또는 모든 변수가 정수 값을 취하도록 제한된 선형 프로그램을 연구합니다.이것은 볼록하지 않고 일반적으로 일반 선형 프로그래밍보다 훨씬 더 어렵습니다.
• 2차 프로그래밍을 사용하면 목적 함수가 2차 항을 가질 수 있지만, 실현 가능한 집합은 선형 등식과 부등식으로 지정되어야 합니다.2차 항의 특정 형태에 대해, 이것은 볼록 프로그래밍의 한 종류이다.
• 부분 프로그래밍은 두 비선형 함수의 비율 최적화를 연구합니다.오목 부분 프로그램의 특수 클래스는 볼록 최적화 문제로 변환될 수 있습니다.
• 비선형 프로그래밍은 목적 함수나 제약 조건 또는 둘 다 비선형 부품을 포함하는 일반적인 경우를 연구합니다.이것은 볼록한 프로그램일 수도 있고 아닐 수도 있다.일반적으로 프로그램이 볼록한지 아닌지가 해결의 난이도에 영향을 미칩니다.
• 확률 프로그래밍은 일부 제약 조건이나 매개변수가 랜덤 변수에 의존하는 경우를 연구합니다.
• 강력한 최적화는 확률적 프로그래밍과 마찬가지로 최적화 문제의 기초가 되는 데이터의 불확실성을 포착하려는 시도이다.강력한 최적화는 불확실성 집합에 의해 정의된 불확실성의 가능한 모든 실현에서 유효한 해결책을 찾는 것을 목표로 한다.
• 조합 최적화는 실현 가능한 솔루션 집합이 이산적이거나 이산적인 것으로 축소될 수 있는 문제와 관련이 있다.
• 확률적 최적화는 검색 프로세스에서 랜덤(소음) 함수 측정 또는 랜덤 입력과 함께 사용됩니다.
• 무한 차원 최적화는 실현 가능한 솔루션의 집합이 함수의 공간과 같은 무한 차원 공간의 하위 집합인 경우를 연구합니다.
• 휴리스틱스와 메타 휴리스틱스는 최적화되는 문제에 대해 거의 또는 전혀 가정하지 않습니다.일반적으로 휴리스틱스에서는 최적의 솔루션을 찾을 필요가 없습니다.한편, 휴리스틱스는 많은 복잡한 최적화 문제에 대한 대략적인 해결책을 찾기 위해 사용됩니다.
• 제약 만족도는 목적 함수 f가 일정한 경우를 연구한다(이는 인공지능, 특히 자동화된 추론에 사용된다).
  • 제약 프로그래밍은 변수 간의 관계가 제약의 형태로 기술되는 프로그래밍 패러다임입니다.
• 분리 프로그래밍은 하나 이상의 제약 조건을 충족해야 하지만 전부가 아닌 경우에 사용됩니다.이것은 스케줄에 특히 도움이 됩니다.
• 공간 매핑은 물리적으로 의미 있는 적절한 거친 모델 또는 대리 모델을 이용하여 엔지니어링 시스템을 높은 충실도(미세) 모델 정확도로 모델링 및 최적화하기 위한 개념입니다.

많은 서브필드에서 이 기술은 주로 다이내믹콘텍스트(즉, 시간에 따른 의사결정)에서의 최적화를 위해 설계되어 있습니다.

• 변이의 미적분 특정 곡선이지만 가능한 최소 면적을 가진 표면을 찾는 것과 같은 목표를 달성하기 위한 최선의 방법을 찾는 것과 관련이 있습니다.
• 최적 제어 이론은 제어 정책을 도입하는 변동의 미적분을 일반화한 것입니다.
• 동적 프로그래밍은 확률적, 무작위성 및 알려지지 않은 모델 매개변수로 확률적 최적화 문제를 해결하기 위한 접근법이다.최적화 전략이 문제를 더 작은 하위 문제로 분할하는 것을 기반으로 하는 경우를 연구합니다.이러한 하위 문제 간의 관계를 설명하는 방정식을 벨만 방정식이라고 합니다.
• 평형 제약이 있는 수학적 프로그래밍은 제약이 변동 부등식 또는 상보성을 포함하는 경우이다.

다목적 최적화

최적화 문제에 여러 목표를 추가하면 복잡성이 증가합니다.예를 들어 구조 설계를 최적화하려면 가볍고 견고한 설계를 원할 것입니다.두 가지 목표가 상충될 경우 균형을 맞춰야 합니다.무게와 강성을 어느 정도 절충한 가장 가벼운 디자인, 가장 단단한 디자인, 그리고 무한한 수의 디자인이 있을 수 있습니다.다른 기준을 희생시키면서 한 기준을 개선하는 트레이드오프 설계의 집합을 파레토 집합이라고 한다.최상의 설계의 강성에 대해 생성된 플롯 웨이트를 파레토 프런티어라고 합니다.

디자인은 다른 설계에 의해 지배되지 않는 경우 "Pareto optimal"(동등하게 "Pareto efficient" 또는 "Pareto set")로 판단됩니다.어떤 면에서는 다른 디자인보다 나쁘고 어떤 면에서는 더 낫지 않다면, 그것은 지배적이고 파레토 최적은 아니다.

"Pareto optimal" 솔루션 중 "favorite 솔루션"을 결정하는 선택은 의사결정자에게 위임됩니다.즉, 문제를 다목적 최적화로 정의하면 일부 정보가 누락되어 있음을 알 수 있습니다.즉, 바람직한 목표가 제시되지만 이들 조합은 서로 상대적으로 평가되지 않습니다.경우에 따라서는 누락된 정보를 의사결정자와의 대화형 세션으로 도출할 수 있다.

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

멀티모달 또는 글로벌 최적화

최적화 문제는 많은 경우 멀티모달입니다.즉, 여러 가지 좋은 해결책을 가지고 있습니다.이러한 솔루션은 모두 글로벌하게 우수하거나(비용 함수의 가치는 동일), 글로벌하게 우수한 솔루션과 로컬로 우수한 솔루션이 혼재할 수 있습니다.멀티모달 옵티마이저의 목표는 멀티솔루션의 모든(또는 적어도 일부)을 취득하는 것입니다.

알고리즘의 여러 실행에서 다른 시작점이 있더라도 다른 솔루션을 얻을 수 있다는 보장이 없기 때문에 반복적인 접근으로 인한 고전적인 최적화 기법은 여러 솔루션을 얻기 위해 사용될 때 만족스럽게 수행되지 않는다.

복수의 국소 극단점이 존재할 수 있는 글로벌 최적화 문제에 대한 일반적인 접근법에는 진화 알고리즘, 베이지안 최적화 및 시뮬레이션 어닐링이 포함된다.

임계점과 극단점의 분류

실현 가능성 문제

실현 가능성 문제라고도 불리는 만족성 문제는 객관적 가치에 관계없이 실현 가능한 해결책을 찾는 문제일 뿐이다.이는 수학적 최적화의 특별한 경우로 간주할 수 있습니다. 즉, 모든 해법에 대해 목표값이 같기 때문에 어떤 해법도 최적입니다.

많은 최적화 알고리즘은 실현 가능한 지점에서 시작해야 합니다.이러한 점을 얻는 한 가지 방법은 느슨한 변수를 사용하여 실현 가능성 조건을 완화하는 것입니다. 충분한 느슨함만 있으면 모든 시작점이 가능합니다.그런 다음 slack이 null 또는 negative가 될 때까지 slack 변수를 최소화합니다.

존재.

Karl Weierstrass의 극한값 정리는 콤팩트 집합의 연속 실수값 함수가 최대값과 최소값을 얻는다고 말한다.보다 일반적으로 콤팩트 세트의 하위 반연속 함수는 최소값에 도달하고 콤팩트 세트의 상위 반연속 함수는 최대점에 도달한다.

최적화에 필요한 조건

페르마의 이론 중 하나는 구속되지 않은 문제의 최적화가 목적 함수의 첫 번째 도함수 또는 기울기가 0인 정지점에서 발견된다고 기술한다(첫 번째 도함수 검정 참조).보다 일반적으로 목적 함수의 첫 번째 도함수 또는 기울기가 0이거나 정의되지 않은 임계점 또는 선택 집합의 경계에서 찾을 수 있다.내부 최적에서 1차 도함수가 0임을 나타내는 방정식(또는 일련의 방정식)을 '1차 조건' 또는 1차 조건 집합이라고 한다.

라그랑주 승수법에 의해 균등 제한 문제의 최적화를 찾을 수 있다.평등 및/또는 불평등 제약과 관련된 문제의 최적성은 'Karush-Kuhn-Tucker 조건'을 사용하여 찾을 수 있다.

최적화를 위한 충분한 조건

첫 번째 도함수 검정에서는 극단점일 수 있는 점을 식별하지만, 이 검정에서는 최소점인 점을 최대점 또는 둘 다 아닌 점을 구분하지 않는다.목적함수가 2배 미분 가능한 경우, 이러한 경우들은 제약되지 않은 문제에서는 2차 미분 또는 2차 미분 행렬(헤시안 행렬이라고 함)을 확인하거나, 제약된 문제에서는 2차 미분 행렬과 경계 헤시안이라고 하는 제약 조건을 확인함으로써 구별될 수 있다.최대값 또는 최소값을 다른 정지점과 구별하는 조건을 '2차 조건'이라고 한다('2차 미분 검정' 참조).후보 솔루션이 1차 조건을 만족하는 경우, 2차 조건의 만족도도 적어도 국소 최적성을 확립하기에 충분하다.

최적화의 감도 및 연속성

엔벨로프 정리는 기본 매개변수가 변경될 때 최적 솔루션의 값이 어떻게 변화하는지를 설명합니다.이 변화를 계산하는 과정을 비교 통계학이라고 합니다.

Claude Berge(1963)의 최대정리는 최적의 솔루션의 연속성을 기본 매개변수의 함수로서 설명한다.

최적화의 미적분

두 번 미분 가능한 함수의 제약되지 않은 문제의 경우, 목표 함수의 기울기가 0인 점(즉, 정지점)을 찾아 일부 임계점을 찾을 수 있습니다.보다 일반적으로 0 서브그레이디언트는 볼록함수 및 기타 로컬 립시츠 함수의 최소화 문제에 대한 로컬 최소값이 발견되었음을 증명한다.

또한, 임계점은 헤시안 행렬의 정의도를 사용하여 분류할 수 있습니다.헤시안 행렬이 임계점에서 양의 확정점일 경우 지점은 국소 최소점이 되고, 음의 확정점일 경우 국소 최대점이 되며, 마지막으로 무한점일 경우 지점은 일종의 안장점이 됩니다.

제한된 문제는 종종 Lagrange 승수의 도움으로 제한되지 않은 문제로 변환할 수 있습니다.라그랑지안 이완은 또한 어려운 제약된 문제에 대한 대략적인 해결책을 제공할 수 있다.

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

글로벌 컨버전스

보다 일반적으로, 목적 함수가 2차 함수가 아닌 경우, 많은 최적화 방법들은 반복의 일부 연속이 최적의 해로 수렴되도록 하기 위해 다른 방법을 사용한다.컨버전스를 보증하기 위한 최초의 일반적인 방법은 1차원을 따라 함수를 최적화하는 라인 검색에 의존합니다.컨버전스를 확실히 하기 위한 두 번째 방법으로, 신뢰 영역을 사용합니다.라인 검색과 신뢰 영역은 모두 비차별 최적화 최신 방법에서 사용됩니다.통상 글로벌 옵티마이저는 고도의 로컬옵티마이저(BFGS 등)보다 훨씬 느리기 때문에 로컬옵티마이저를 다른 시작점에서 기동함으로써 효율적인 글로벌옵티마이저를 구축할 수 있습니다.

계산 최적화 기술

문제를 해결하기 위해, 연구자들은 제한된 수의 단계로 끝나는 알고리즘이나 해결책에 수렴하는 반복 방법(특정된 특정 종류의 문제에 대해) 또는 일부 문제에 대한 대략적인 해결책을 제공할 수 있는 휴리스틱스를 사용할 수 있다(반복할 필요가 없음).

최적화 알고리즘

• 선형 프로그래밍용으로 설계된 George Dantzig의 Simplex 알고리즘
• 2차 프로그래밍 및 선형 프랙션 프로그래밍용으로 설계된 심플렉스 알고리즘의 확장
• 네트워크 최적화에 특히 적합한 심플렉스 알고리즘의 변종
• 조합 알고리즘
• 양자 최적화 알고리즘

반복적 방법

비선형 프로그래밍의 문제를 해결하는 데 사용되는 반복 방법은 헤시안, 구배 또는 함수 값만 평가하느냐에 따라 달라집니다.헤시안(H)과 구배(G)를 평가하면 수렴 속도가 개선되지만, 이러한 수량이 충분히 매끄럽게 변화하는 함수의 경우, 그러한 평가는 각 반복의 계산 복잡성(또는 계산 비용)을 증가시킨다.경우에 따라서는 계산 복잡도가 지나치게 높을 수 있습니다.

최적기에 대한 한 가지 주요 기준은 필요한 함수 평가의 수이며, 이는 대개 N개의 변수에 대해 주로 작동해야 하는 최적화 도구 자체보다 훨씬 더 많은 계산 작업이기 때문이다.이러한 최적기에 대한 세부 정보를 제공하지만, 계산하기가 더욱 어렵다. 예를 들어, 구배를 근사하는 데는 적어도 N+1의 함수 평가가 필요하다.2차 도함수 근사치(헤시안 행렬에 수집됨)의 경우 함수 평가의 수는 N²입니다.뉴턴의 방법에는 2차 도함수가 필요하기 때문에 각 반복에 대해 함수 호출의 수는 N²의 순서가 되지만, 보다 단순한 순수 구배 최적화 도구의 경우 N에 불과합니다.그러나 경사 최적기는 보통 뉴턴의 알고리즘보다 더 많은 반복을 필요로 한다.함수 호출의 수와 관련하여 어떤 것이 가장 좋은지는 문제 자체에 따라 달라집니다.

• 헤시안(또는 유한한 차이를 사용하여 근사 헤시안)을 평가하는 방법:
  • 뉴턴의 방법
  • 순차 2차 프로그래밍: 소규모의 제약 문제에 대한 뉴턴 기반의 방법입니다.일부 버전은 큰 차원의 문제를 처리할 수 있습니다.
  • 내부 점 방법:이것은 제한된 최적화를 위한 큰 클래스의 방법이며, 일부는 (하위) 단계적 정보만을 사용하고 나머지는 헤시안 평가를 필요로 한다.
• 경사 또는 대략적인 경사도(또는 하위 경사도)를 평가하는 방법:
  • 하강 방법 조정:각 반복에서 단일 좌표를 업데이트하는 알고리즘
  • 켤레 그라데이션 방법:큰 문제에 대한 반복적인 방법.(이론적으로, 이 방법들은 2차 목적 함수를 가진 유한한 수의 단계로 끝납니다만, 이 유한한 끝은 유한 정밀도 컴퓨터에서는 실제로 관찰되지 않습니다.
  • 경사 강하(또는 "강경 강하" 또는 "강경 강하"): 역사적 및 이론적 관심의 (느린) 방법으로서, 엄청난 문제의 대략적인 해결책을 찾는 데 새로운 관심을 가지고 있다.
  • 하위 단계적 방법:일반화된 구배를 사용하여 로컬에서 큰 Lipschitz 함수에 대한 반복 방법입니다.보리스 T에 이어.폴리악, 준구배 투영법은 켤레-구배법과 유사합니다.
  • 번들 강하 방법:로컬 립시츠 함수의 중소형 문제에 대한 반복 방법, 특히 볼록 최소화 문제에 대한 반복 방법(공역 구배 방법과 유사).
  • 타원체 방법:특히 일부 조합 최적화 문제의 다항식 시간 복잡성을 확립하는 데 있어 이론적으로 큰 관심을 갖는 준볼록 목적 함수의 작은 문제에 대한 반복적인 방법.준뉴턴 방식과 유사하다.
  • 선형 제약, 특히 트래픽네트워크에서 특별히 구조화된 문제를 대략적으로 최소화하기 위한 조건부 그라데이션 방식(Frank-Wolfe).제약이 없는 일반적인 문제의 경우 이 방법은 (거의 모든 문제에 대해) 구식으로 간주되는 그라데이션 방식으로 축소됩니다.
  • 준뉴턴 방식:중대형 문제에 대한 반복적 방법(예: N < 1000).
  • 확률적 최적화를 위한 동시 섭동 확률 근사(SPSA) 방법. 무작위(효율적) 구배 근사 사용.
• 함수 값만 평가하는 방법:문제가 연속적으로 미분 가능한 경우, 한정된 차이를 사용하여 구배를 근사할 수 있으며, 이 경우 구배 기반 방법을 사용할 수 있다.
  • 보간법
  • 패턴 검색 방법: 아래에 나열된 Nelder-Mead 휴리스틱(간단함 포함)보다 수렴 특성이 우수합니다.
  • 거울 강하

휴리스틱스

(최종 종료) 알고리즘과 (컨버전트) 반복 방법 외에 휴리스틱스가 있습니다.휴리스틱은 (수학적으로) 해답을 찾을 수 없는 알고리즘이지만, 그래도 특정 실제 상황에서 유용합니다.잘 알려진 휴리스틱 목록:

적용들

메카닉스

여기 계신 제약 조건 매니폴드에 평범한 미분 방정식을 풀려고 할 역할을 하지 않고"이 두점 alw야 한다 같은 제약이 다양한 비선형 기하학적 제약 조건[5]강체 역학을 볼 수 있강체 역학 관계는 문제들은 자주, 수학적 프로그래밍 기술이 필요한(특히 강체 역학을 선언한).ays일치", "이 표면은 다른 면을 통과해서는 안 된다" 또는 "이 점은 항상 이 곡선상의 어딘가에 있어야 한다".또, QP(Quadratic Programming)의 문제로도 볼 수 있는 선형보완성 문제를 푸는 것으로, 접촉력의 연산 문제를 실시할 수 있다.

많은 설계상의 문제는 최적화 프로그램으로도 표현될 수 있습니다.이 어플리케이션은 디자인 최적화라고 불립니다.한 가지 서브셋은 엔지니어링 최적화이며, 최근 이 분야에서 증가하고 있는 또 다른 서브셋은 다분야 설계 최적화입니다. 이는 많은 문제에서 유용하지만 특히 항공우주 공학 문제에 적용되어 왔습니다.

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

경제 및 금융

경제학은 에이전트의 최적화와 충분히 밀접하게 관련되어 있어 영향력 있는 정의는 경제학 쿼사이언스를 대안적인 ^[7]용도와 함께 "목표와 희소한 수단 사이의 관계로서 인간 행동의 연구"라고 설명한다.현대 최적화 이론은 전통적인 최적화 이론을 포함하지만 게임 이론과 경제 균형 연구와도 겹친다.경제 문헌 저널 코드는 수학 프로그래밍, 최적화 기법 및 관련 주제를 JEL:C61-C63으로 분류한다.

미시경제학에서, 효용 극대화 문제와 그 이중 문제인 지출 최소화 문제는 경제 최적화 문제이다.그들이 일관되게 행동하는 한, 소비자들은 효용을 극대화하는 것으로 가정되는 반면, 기업들은 보통 그들의 이익을 극대화하는 것으로 가정된다.또한 약제는 종종 위험을 회피하는 것으로 모델링되므로 위험을 회피하는 것을 선호합니다.자산 가격도 최적화 이론을 사용하여 모델링되지만, 기초 수학은 정적 최적화보다는 확률적 과정의 최적화에 의존한다.국제무역이론은 또한 국가 간의 무역 패턴을 설명하기 위해 최적화를 사용한다.포트폴리오의 최적화는 경제학에서 다목적 최적화의 한 예이다.

1970년대 이후, 경제학자들은 시간이 ^[8]지남에 따라 제어 이론을 이용하여 역동적인 결정을 모델링해 왔다.예를 들어, 동적 검색 모델은 노동 시장의 ^[9]행동을 연구하는 데 사용됩니다.결정적인 차이는 결정론적 모델과 확률론적 ^[10]모델 사이의 차이이다.거시경제학자들은 근로자, 소비자, 투자자 및 ^[11][12]정부의 상호의존적 최적화 결정의 결과로 경제 전체의 역학을 설명하는 동적 확률적 일반 평형(DSGE) 모델을 구축합니다.

전기 공학

전기 공학에서 최적화 기술의 일반적인 응용 분야에는 능동 필터 설계,^[13] 초전도 자기 에너지 저장 시스템의 부유 전계 감소, 마이크로파 ^[14]구조의 공간 매핑 설계, 핸드셋 안테나,^[15][16][17] 전자기학 기반 설계가 포함됩니다.전자적으로 검증된 마이크로파 구성 요소와 안테나의 설계 최적화는 1993년 ^[18][19]공간 매핑 발견 이후 적절한 물리 기반 또는 경험적 대리 모델과 공간 매핑 방법론을 광범위하게 사용해 왔다.

토목 공학

최적화는 토목 공학에서 널리 사용되어 왔습니다.건설 관리 및 운송 엔지니어링은 최적화에 크게 의존하는 토목 공학의 주요 부문 중 하나입니다.최적화를 통해 해결되는 가장 일반적인 토목 문제는 도로의 절단 및 메우기, 구조물 및 ^[20]인프라의 수명 주기 분석, 자원 ^[21][22]평준화, 수자원 할당, 교통 관리^[23] 및 일정 최적화입니다.

운용 조사

최적화 기술을 광범위하게 사용하는 또 다른 분야는 운영 ^[24]연구입니다.운영 연구에서도 확률적 모델링과 시뮬레이션을 사용하여 의사 결정을 개선할 수 있습니다.운영 연구는 사건에 적응하는 동적 의사 결정을 모델링하기 위해 확률적 프로그래밍을 사용하는 경우가 늘고 있습니다. 이러한 문제는 대규모 최적화 및 확률적 최적화 방법을 통해 해결할 수 있습니다.

제어 엔지니어링

수학적 최적화는 매우 현대적인 컨트롤러 설계에서 사용됩니다.모델 예측 제어(MPC) 또는 실시간 최적화(RTO)와 같은 고급 컨트롤러는 수학적 최적화를 사용합니다.이러한 알고리즘은 온라인으로 실행되며 제어되는 시스템의 모델을 포함한 수학적 최적화 문제를 반복적으로 해결함으로써 프로세스 플랜트의 초크 개구부 등의 의사결정 변수 값을 반복적으로 결정합니다.

지구물리학

최적화 기법은 지구물리학적 매개변수 추정 문제에 정기적으로 사용된다.지진 기록과 같은 일련의 지구물리학적 측정이 주어지면 기초 암석과 유체의 물리적 특성과 기하학적 형태를 해결하는 것이 일반적이다.지구물리학에서 대부분의 문제는 결정론적 방법과 확률적 방법 모두 널리 사용되고 있어 비선형적이다.

분자 모델링

비선형 최적화 방법은 구조 분석에서 널리 사용됩니다.

계산 시스템 생물학

최적화 기술은 모델 구축, 최적의 실험 설계, 대사 공학 및 합성 ^[25]생물학과 같은 컴퓨터 시스템 생물학의 많은 측면에 사용됩니다.선형 프로그래밍은 발효 ^[25]생성물의 최대 가능한 수율을 계산하고, 다중 마이크로 어레이^[26] 데이터 세트로부터 유전자 조절 네트워크와 높은 처리량 ^[27]데이터로부터 전사 조절 네트워크를 추론하기 위해 적용되었다.비선형 프로그래밍은 에너지 대사를^[28] 분석하기 위해 사용되었으며, 생화학 ^[29]경로의 대사 공학 및 매개변수 추정에 적용되어 왔다.

기계 학습

해결사

「 」를 참조해 주세요.

메모들

추가 정보

• Boyd, Stephen P.; Vandenberghe, Lieven (2004). Convex Optimization. Cambridge: Cambridge University Press. ISBN 0-521-83378-7.
• Gill, P. E.; Murray, W.; Wright, M. H. (1982). Practical Optimization. London: Academic Press. ISBN 0-12-283952-8.
• Lee, Jon (2004). A First Course in Combinatorial Optimization. Cambridge University Press. ISBN 0-521-01012-8.
• Nocedal, Jorge; Wright, Stephen J. (2006). Numerical Optimization (2nd ed.). Berlin: Springer. ISBN 0-387-30303-0.
• Snyman, J. A.; Wilke, D. N. (2018). Practical Mathematical Optimization : Basic Optimization Theory and Gradient-Based Algorithms (2nd ed.). Berlin: Springer. ISBN 978-3-319-77585-2.

외부 링크

• "Decision Tree for Optimization Software". 최적화 소스 코드 링크
• "Global optimization".
• "EE364a: Convex Optimization I". Course from Stanford University.
• Varoquaux, Gaël. "Mathematical Optimization: Finding Minima of Functions".