증강라그랑기법

증강 라그랑지안 방법은 제한된 최적화 문제를 해결하기 위한 특정 종류의 알고리즘이다.이들은 제약이 없는 최적화 문제를 일련의 제한 없는 문제로 대체하고 목표에 페널티 용어를 추가한다는 점에서 페널티 방법과 유사성을 가지고 있다. 차이점은 증강된 라그랑지안 방법이 라그랑지 승수를 모방하도록 설계된 또 다른 용어를 추가한다는 것이다.증강 라그랑지안은 라그랑지 승수의 방법과 관련이 있지만 동일하지는 않다.

다르게 보면 구속되지 않은 목표는 제약된 문제의 라그랑지안이며, 추가 벌칙 용어(증강)가 있다.

이 방법은 원래 승수법으로 알려졌으며, 벌칙방법의 좋은 대안으로 1970년대와 1980년대에 많이 연구되었다.처음에는 마그누스 헤스테네스가,^[1] 1969년에는 마이클 파월이 토론하였다.^[2]그 방법은 R에 의해 연구되었다. 펜셸 이중성과 관련된 Tyrrell Rockafellar, 특히 근위부 포인트 방법과 관련된 Morau–요시다 정규화 및 최대 단조 연산자:이러한 방법은 구조 최적화에 사용되었다.이 방법은 또한 디미트리 베르체카스(Dimitri Bertsekas)에 의해 연구되었는데, 특히 1982년 그의 저서에서,^[3] 2배의 상이한 증강 래그랑지안 함수로 불평등 제약을 처리하는 방법인 "승수의 우수한 방법"을 발생시키는 등 비수분적 정규화 기능을 포함하는 연장과 함께 연구되었다.

1970년대 이후 순차 2차 프로그래밍(SQP)과 내부 포인트 방식(IPM)은 주목도가 높아졌는데, 부분적으로 수치 소프트웨어 라이브러리에서 나오는 희박한 매트릭스 서브루틴을 더 쉽게 사용하기 때문이며, 부분적으로는 IPM이 자기 모순 기능 이론을 통해 복잡성 결과를 입증했기 때문이다.증강된 라그랑지안 방법은 최적화 시스템 랜슬롯, ALGENCAN^[4][5], ARMP에 의해 회춘되었는데, 이는 외관상 복잡하지만 "부분적으로 분리 가능한" 문제에 희소 행렬 기법을 사용할 수 있게 했다.그 방법은 몇몇 문제에 여전히 유용하다.^[6]2007년경에는 총분산 데노화, 압축 센싱 등의 분야에서 증강 라그랑기식의 부활이 있었다.특히 멀티플라이어 또는 ADMM의 교대 방향법으로 알려진 부분 업데이트(선형 방정식 해결을 위한 가우스-사이델 방법과 유사)를 사용하는 표준 증강 라그랑지안 방식의 변종이 어느 정도 주목을 받았다.

일반법

다음과 같은 제한된 문제를 해결하고 있다고 하자.

${\displaystyle \min f(\mathbf {x} )}$

의 대상이 되다

${\displaystyle c_{i}(\mathbf {x} )=0~\모든 i\in {\mathcal {E},}$

여기서 $E{\displaystyle \mathcal{}}$ ${\$은(는) 동등 제약조건에 대한 지수를 나타낸다$$.이 문제는 일련의 제약 없는 최소화 문제로 해결될 수 있다.참고로 먼저 패널티 방법 접근법의 k번째 단계를 열거한다.

${\displaystyle \min \Phi \{k}(\mathbf {x} )=f(\mathbf {x})+\mu _{k}~\sum _{i\in {E}~c_{i}(\mathbf {x} )^{2}.}}$

벌칙 방법은 이 문제를 해결한 다음, 다음 반복 시 더 큰 값인 ${\displaystyle {\mu k}_{}}$ ${\$를 사용하여 문제를 다시 해결한다($$그리고 이전 솔루션을 초기 추측 또는 "warm-start"로 사용).

증강된 라그랑지안 방법은 다음과 같은 제한되지 않은 목적을 사용한다.

${\displaystyle \min \Phi _{k}(\mathbf {x} )=f(\mathbf {x} )+{\frac {\mu _{k}}{2}}~\sum _{i\in {\mathcal {E}}}~c_{i}(\mathbf {x} )^{2}+\sum _{i\in {\mathcal {E}}}~\lambda _{i}c_{i}(\mathbf {x} )}$

그리고 각 반복 후에 ${\displaystyle {\mu k}_{}}$ ${\$ 업데이트 외에 규칙대로 변수 $\lambda {\displaystyle }${\$displaystyle \dada$}도 업데이트된다$.$

${\displaystyle \putarrow \{i}\{i}+\mu _{k}c_{i}(\mathbf {x} _{k})}$

${\displaystyle {}_{}}$서 $x{\displaystyle {\mathbf{}}_{}}$ k ${\$은(는) k번째 단계에서 제약되지 않는 문제에 대한 해결책이다$$. 즉, ${\displaystyle {}_{}}$ k${\displaystyle {}_{}}$= ${\displaystyle \text{argmin}}$ ${\displaystyle \phi {\mathrm{}}_{}}$ ${\displaystyle k_{}}$( ${\displaystyle x\mathbf{}}$) ${\displaysty \mathbf {x} _{k}={\text}}\argmin}\\\\\\\$$Phi _{k}(\mathbf {x} )}$

변수 $\lambda {\displaystyle }$ ${\displaystyle \lambda }$은 라그랑주 승수의 추정치로서$$, 이 추정치의 정확도는 단계마다 향상된다.이 방법의 큰 장점은 벌칙 방식과 달리 원래 제약된 문제를 해결하기 위해$$ $\mu {\displaystyle }$ →${\displaystyle }$μ → $∞[\디스플레이$ 스타일 $\mu \rightarrow \infit }$을(를) 취할 필요가 없다는 점이다.대신 라그랑주 곱셈기 용어가 존재하기 때문에 $\mu {\displaystyle }$ ${\displaystyle \mu$}은(는) 훨씬 더 작은 상태를 유지할$$ 수 있기 때문에 좋지 않은 상태를 피할 수 있다.^[6]그럼에도 불구하고, 대규모 경계 집합(안전장치)에서 멀티플라이어 추정치를 투영하는 것이 실무적 구현에서 일반적이며, 수치적 불안정성을 피하고 강력한 이론적 수렴을 유도한다.^[5]

이 방법은 불평등 제약을 다루기 위해 확장될 수 있다.실질적인 개선사항에 대한 자세한 내용은 항목을 참조하십시오.^[6][5]

승수의 교대 방향법

ADMM(Autternative direction method)은 이중 변수에 부분 업데이트를 사용하는 증강 라그랑지안 방식의 변형이다.이 방법은 흔히 다음과 같은 문제를 해결하기 위해 사용된다.

${\displaystyle \min _{x}f(x)+g(x).}$

이것은 제한된 문제와 같다.

${\displaystyle \min _{x,y}f(x)+g(y),\properties {\text{data}}\property x=y.}$

이러한 변화가 사소해 보일 수 있지만, 문제는 이제 제약된 최적화 방법(특히 증강된 라그랑지식 방법)을 이용하여 공격할 수 있으며, 객관적 함수는 x와 y로 분리할 수 있다.이중 업데이트를 위해서는 근접 기능을 x와 y로 동시에 해결해야 하는데, ADMM 기법은 y로 고정된 x로 먼저 해결한 다음 x로 고정하여 y로 풀면 대략적으로 이 문제를 해결할 수 있다.(자코비 방법과 마찬가지로) 수렴까지 반복하기보다는 알고리즘이 직접 이중 변수를 업데이트한 다음 과정을 반복한다.이것은 정확한 최소화와 동일하지는 않지만, 이 방법이 일부 가정 하에서 정답을 향해 수렴한다는 것을 여전히 보여줄 수 있다.이 근사치 때문에 알고리즘은 순수한 증강 라그랑지안 방법과 구별된다.

ADMM은 Douglas-Rachford 분할 알고리즘의 적용으로 볼 수 있으며, Douglas-Rachford 알고리즘은 차례로 Proximal point 알고리즘의 한 인스턴스가 된다. 자세한 내용은 여기에서 확인할 수 있다.^[7]베이시스 추구와 변형을 해결하고 ADMM을 사용하는 몇 가지 현대 소프트웨어 패키지가 있다; 그러한 패키지에는 YALL1^[8](2009), SpaRSA(2009), Salsa^[10](2009)가 있다.또한 ADMM을 사용하여 보다 일반적인 문제를 해결하는 패키지도 있으며, 그 중 일부는 다중 컴퓨팅 코어인 SNAPVX^[11](2015), PARADM^[12](2016)을 이용할 수 있다.

확률적 최적화

이 절에는 광고처럼 쓰여진 내용이 수록되어 있다. 홍보 콘텐츠 및 부적절한 외부 링크를 제거하고 중립적인 관점에서 작성된 백과사전 콘텐츠를 추가하여 개선하십시오.(2019년 4월) (이 템플릿 메시지 제거 방법 및 시기 학습)

확률적 최적화는 (점진적) 함수의 노이즈 샘플에 대한 접근으로 손실 함수를 최소화하는 문제를 고려한다.목표는 새 표본당 최적 모수(미니마이저)의 추정치를 갖는 것이다.ADMM은 원래 배치 방법이다.그러나 일부 개조 시에는 확률적 최적화에 사용할 수도 있다.확률적 환경에서는 시끄러운 경사도의 샘플에만 접근할 수 있기 때문에, 우리는 라그랑지안의 부정확한 근사치를 다음과 같이 사용한다.

${\displaystyle {\hat {\mathcal {L}}}_{\rho ,k}=f_{1}(x_{k})+\langle \nabla f(x_{k},\zeta _{k+1}),x\rangle +g(y)-z^{T}(Ax+By-c)+{\frac {\rho }{2}}\Vert Ax+By-c\Vert ^{2}+{\frac {\Vert x-x_{k}\Vert ^{2}}{2\eta _{k+1}}},}$

여기서 ${\displaystyle {\eta k}_{}}$+ ${\displaystyle 1_{}}$ ${\$1}은$($는) 시간 경과에 따른 단계 크기입니다$$.^[13]

온라인과 유통을 최적화를 위해 더 큰 scale,[14]에 multipliers의 교류 방향 관측 법(ADMM)은 인기 있는 방식과 여러 용도에서 사용된다면, e.g.[15][16][17]ADMM은 기능을 최적화 및 정례화 로컬에 그때 globa을 조절해 나간다regularized의 문제 해결 능력에 적용된다.constrai을 통해 llynts. 정규화된 최적화 문제는 특히 고차원적 체계에 관련된다. 정규화는 예를 들어 첨탑성 및 낮은 등급과 같은 최적의 솔루션에서 부조화를 촉진하는 자연스러운 메커니즘이기 때문이다.정규화된 문제를 해결하는 데 있어 ADMM의 효율성이 높기 때문에 높은 차원에서도 확률적 최적화의 가능성이 크다.

대체 접근 방식

• 순차 2차 프로그래밍
• 순차 선형 프로그래밍
• 순차 선형 2차 프로그래밍

소프트웨어

향상된 라그랑지식 방법의 오픈 소스 및 비자유/상업적 구현:

• 어코드.NET(증강 래그랑지안 최적화 도구 C# 구현)
• ALGLIB(사전 정의된 증강 라그랑지안 해결사의 C# 및 C++ 구현)
• PENNON(GPL 3, 상용 라이센스 사용 가능)
• 랜슬롯(무료 "내부 사용" 라이센스, 유료 상업 옵션)
• MINOS(일부 유형의 문제에 대해 증강된 라그랑지안 방법을 사용하기도 함).
• Apache 2.0 라이센스 사유에 대한 코드는 온라인에서 사용할 수 있다.^[18]
• ALGENCAN(안전장치로 증강 라그랑지안식 방법의 Fortran 구현).온라인으로 이용 가능.^[19]

참고 항목

• 장벽 함수
• 인테리어 포인트 방식
• 라그랑주 승수
• 벌칙법

참조

참고 문헌 목록

• Bertsekas, Dimitri P. (1999), Nonlinear Programming (2nd ed.), Belmont, Mass: Athena Scientific, ISBN 978-1-886529-00-7
• Birgin, E. G.; Martínez, J. M. (2014), Practical Augmented Lagrangian Methods for Constrained Optimization, Philadelphia: Society for Industrial and Applied Mathematics, doi:10.1137/1.9781611973365, ISBN 978-1-611973-35-8
• Nocedal, Jorge; Wright, Stephen J. (2006), Numerical Optimization (2nd ed.), Berlin, New York: Springer-Verlag, ISBN 978-0-387-30303-1