인테리어 포인트 방식

내부 포인트 방법(방호벽 방법 또는 IPM이라고도 함)은 선형 및 비선형 볼록 최적화 문제를 해결하는 특정 종류의 알고리즘이다.

내부 포인트 방법은 소련의 수학자 I에 의해 발견되었다.I. 디킨은 1967년에 미국에서 재탄생했고 1980년대 중반에 미국에서 재탄생했다.1984년 나렌드라 카르마르카는 다항 시간대에 실행되며 실전에 있어서도 매우 효율적인 카르마르카의 알고리즘이라는 선형 프로그래밍 방법을 개발하였다.심플렉스(simplex) 방식으로는 감당할 수 없는 선형 프로그래밍 문제 해결이 가능했다.심플렉스 방식과는 달리 실현 가능한 지역의 내부를 횡단하여 최적의 해결책에 도달한다.이 방법은 볼록 세트를 인코딩하는 데 사용되는 자기반복 장벽 함수에 기초한 볼록 프로그래밍으로 일반화할 수 있다.

모든 볼록 최적화 문제는 비문 형태로 변환하여 볼록 집합에 걸쳐 선형 함수를 최소화(또는 최대화)하는 것으로 변환할 수 있다.^[1]장벽으로 실현 가능한 세트를 인코딩하고 장벽 방법을 설계하는 아이디어는 앤서니 V에 의해 연구되었다.1960년대 초 피코, 가르스 P. 매코믹 등.이러한 아이디어들은 주로 일반적인 비선형 프로그래밍을 위해 개발되었지만, 이 종류의 문제(예: 순차 2차 프로그래밍)에 대해 더 경쟁적인 방법들이 존재하기 때문에 나중에 폐기되었다.

유리 네스테로프와 아르카디 네미로프스키가 어떤 볼록세트를 인코딩하는 데 사용할 수 있는 그런 장벽의 특별한 계급을 고안해 냈다.이들은 알고리즘의 반복 횟수가 용액의 치수와 정확도에서 다항식으로 제한된다는 것을 보장한다.^[2]

카르마르카의 돌파구는 다항식 복잡성이 특징인 선형 프로그래밍 알고리즘을 만들 수 있고, 더욱이 심플렉스 방식과 경쟁할 수 있다는 것을 보여주면서 내부 포인트 방법과 장벽 문제에 대한 연구를 활성화시켰다.이미 카치얀의 타원형 방법은 다항식 시간 알고리즘이었지만, 실제적인 관심을 가지기에는 너무 느렸다.

원시-이중 경로 추종 인테리어 포인트 방식이 가장 성공적인 것으로 평가된다.Mehrotra의 예측 변수-코렉터 알고리즘은 이러한 종류의 방법 중 대부분의 구현에 대한 기초를 제공한다.^[3]

비선형 최적화를 위한 원시-이중 내부 포인트 방법

원시-이중 방법의 아이디어는 제한된 비선형 최적화에 대해 입증하기 쉽다.단순성을 위해 비선형 최적화 문제의 전체 품질 버전을 고려하십시오.

minimize ${\displaystyle f(x)}$ subject to ${\displaystyle c_{i}(x)\geq 0~{\text{for}}~i=1,\ldots ,m,~x\in \mathbb {R} ^{n},}$ where ${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} ,c_{i}:\mathbb {R} ^{n}$$\rightarrow$$\mathb {R} \quad(1)$$}$

이 불평등 구속적 최적화 문제는 우리가 효율적으로 찾기를 원하는 최소한의 구속력이 없는 객관적 기능으로 전환함으로써 해결된다.구체적으로 (1)과 관련된 로그 장벽 함수는 다음과 같다.

${\displaystyle B(x,\mu )=f(x)-\mu \sum _{i=1}^{m}\log(c_{i})(x)\cHB (2)}$

여기서 $[\displaystyle \mu }$은(는) 작은 양의 스칼라로, 때로는 "배리어 파라미터"라고 불리기도 한다.$[\displaystyle \mu }$이(가) 0으로 수렴됨에$$ 따라 최소 $B{\displaystyle }$(${\displaystyle x}$ ,$)[\displaystyle B(x,\mu )}$는 (1)의 해법으로 수렴해야 한다$$.

장애물 함수 구배는

${\displaystyle g_{b}(x,\mu )=\nabla B(x,\mu )=g(x)-\mu \sum \sum _{i=1}^{m}{c_{i}(x)}}}}}}{nabla c_{i}(x),\quad (3)}$

${\displaystyle \mathrm{여기}}$서 $g{\displaystyle }$( ${\displaystyle x}$) ${\displaystyle :=}$ ${\displaystyle \mathrm{\nabla }}$ f${\displaystyle }$( x${\displaystyle }$) ${\displaystyle g(x):$$=\displaystyle$ f$(x)}$는 원래 함수 $f{\displaystyle (x}$ ${\displaystyle )}$ ${\displaystyle f(x)}$의 그라데이션이고$,$ $\nabla {\displaystyle \mathrm{}{c}_{}}$ i ${\$는 $c{\displaystyle {}_{}}$ i ${\$의 그라데이션이다$.$

원래의$$ ("기본") 변수 $x{\displaystyle }$ ${\displaystyle x}$ 외에 라그랑주 곱셈에서 영감을 받은 이중 변수 $\lambda {\displaystyle {\mathbb{}}^{}}$ m ${\$^{$m}}}}}}$을(를) 도입한다.

${\displaystyle c_{i}(x)\\da _{i}=\mu,\all i=1,\ldots,m.\cHB (4)}$

(4)는 KKT 조건의 "완전 느슨함"과 유사하기 때문에 때때로 "완전된 보완성" 조건이라고 불린다.

우리는 장벽 함수의 구배가 0인${\displaystyle }$(${\displaystyle {x\mu }_{}}$ ,${\displaystyle {}_{}{}_{}{\mu }_{}}$ ) ${\displaystyle$ ($x_{\$mu $},\lambda _${\mu$$}})을$$ 찾으려고 한다.

(3)에 (4)를 적용하면 구배 방정식이 나온다.

$G-A^{{displaystyle g-A^{T}\lambda =0,\quad (5)}$

여기서 행렬 $A{\displaystyle }$ ${\displaystyle A}$은 제약 $조건{\displaystyle }$ c${\displaystyle }$( ${\displaystyle x}$) ${\displaystyle c(x)}$의 Jacobian이다$.$

(${\displaystyle 5}$) 뒤의 직관은 $f{\displaystyle }$( x${\displaystyle }$) ${\displaystyle f(x)}$의 구배가 제약 조건의 구배 범위에 걸쳐 있는 하위 공간에 있어야 한다는$$ 것이다.$[\displaystyle \mu }$ (4)$$를 가진 "완충된 보완성"은 솔루션이 경계 ${\displaystyle c_{}}$ $i{\displaystyle {}_{}}$ (${\displaystyle {}_{}\mathrm{x}}$)${\displaystyle }$= 0 ${\displaystyle c_{i}($${\displaystyle x}$$)=0}$ 또는$$제약조건$$ $구성요소{\displaystyle {}_{}}$ i${\displaystyle {}_{}}$( ${\displaystyle x_{}}$ )${\displaystyty$ g$}$의 경사로의$$투영으로 이해할 수 있다.$e c_{i}(x)}$ 정상값은$$ 거의 0이어야 한다.

(4)와 (5)에 뉴턴의 방법을 적용하면${\displaystyle }$(${\displaystyle x}$ ,${\displaystyle \lambda }$) ${\displaystyle (x,\lambda )}$ 업데이트$$ $({\displaystyle {}_{}}$ ${\displaystyle x_{}}$, ${\displaystyle {}_{}}$ ${\displaystyle {\lambda }_{}}$) ${\displaystyle (p_{x},p_{\lambda }}}}$에 대한 방정식이 나온다$.$

${\displaystyle {\begin{pmatrix}W&-A^{T}\\\\\lamba A&C\end{pmatrix}{pmatrix}{pmatrix}}}{\begin{pmatrix}-g+A^{{{pmatrix}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}{\\begnd.T}\lambda \\mu 1-C\lambda \end{pmatrix},}$

where ${\displaystyle W}$ is the Hessian matrix of ${\displaystyle B(x,\mu )}$, ${\displaystyle \Lambda }$ is a diagonal matrix of ${\displaystyle \lambda }$, and ${\displaystyle C}$ is a diagonal matrix with ${\displaystyle C_{ii}=c_{i}(x)}$.

(1)로 인해 (4) 조건

$\displaystyle \lambda \geq 0}$

각 단계에서 시행되어야 한다.이는 적절한 $\alpha {\displaystyle }$ ${\displaystyle \alpha }$을(를) 선택하여 수행할 수 있다$.$

$(x,\displaystyle)(x,\displayda )\to(x+\paffa p_{x},\pairda +\pair p_{\pairda }).}$

미디어 재생

내부 포인트 방법을 사용한 x의 반복 궤적

참고 항목

• 아핀 스케일링
• 증강라그랑기법
• 벌칙법
• 카루시-쿤-터커 조건

참조

참고 문헌 목록

• Dikin, I.I. (1967). "Iterative solution of problems of linear and quadratic programming". Dokl. Akad. Nauk SSSR. 174 (1): 747–748.
• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude; Sagastizábal, Claudia A. (2006). Numerical optimization: Theoretical and practical aspects. Universitext (Second revised ed. of translation of 1997 French ed.). Berlin: Springer-Verlag. pp. xiv+490. doi:10.1007/978-3-540-35447-5. ISBN 978-3-540-35445-1. MR 2265882.
• Karmarkar, N. (1984). "A new polynomial-time algorithm for linear programming" (PDF). Proceedings of the sixteenth annual ACM symposium on Theory of computing – STOC '84. p. 302. doi:10.1145/800057.808695. ISBN 0-89791-133-4. Archived from the original (PDF) on 28 December 2013.
• Mehrotra, Sanjay (1992). "On the Implementation of a Primal-Dual Interior Point Method". SIAM Journal on Optimization. 2 (4): 575–601. doi:10.1137/0802028.
• Nocedal, Jorge; Stephen Wright (1999). Numerical Optimization. New York, NY: Springer. ISBN 978-0-387-98793-4.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Section 10.11. Linear Programming: Interior-Point Methods". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8.
• Wright, Stephen (1997). Primal-Dual Interior-Point Methods. Philadelphia, PA: SIAM. ISBN 978-0-89871-382-4.
• Boyd, Stephen; Vandenberghe, Lieven (2004). Convex Optimization (PDF). Cambridge University Press.