아핀 스케일링

아핀 스케일링 방식은 내부 포인트 방식으로, 선형 프로그램의 실현 가능한 영역 내에서(실행 가능한 영역의 모서리를 걷는 심플렉스 알고리즘과는 반대로) 엄격히 포인트의 궤적을 형성한다는 것을 의미한다.

수학적 최적화에서 아핀 스케일링은 선형 프로그래밍 문제를 해결하기 위한 알고리즘이다.구체적으로는 소련의 수학자 1세가 발견한 인테리어 포인트 방법이다.I. 디킨은 1967년에 미국에서 재탄생했고 1980년대 중반에 미국에서 재탄생했다.

역사

아핀 스케일링은 다중 발견 이력이 있다.그것은 내가 처음 출판한 것이다.I. Dikin은 1967년 독레이디 아카데미 나우크 SSSR의 러시아 과학 아카데미 에너지 시스템 연구소(시베리아 에너지 연구소, 당시 USSR 아카데미)에서 그 뒤를 이어 1974년에 그 융합에 대한 증거를 제시하였다.^[1]디킨의 작업은 선형 프로그래밍을 위한 최초의 실용적 다항식 시간 알고리즘인 카르마르카 알고리즘이 1984년에 발견될 때까지 대부분 주목을 받지 못했다.카르마르카르의 방법의 중요성과 복잡성은 수학자들이 더 간단한 버전을 찾도록 자극했다.

그 후 여러 그룹이 독자적으로 카르마르카르의 알고리즘의 변형을 고안해냈다.IBM의 ^[2]E. R. R. R. Vanderbay가 이끄는 AT&^[3]T의 팀과 몇몇 다른 팀들은 Karmarkar가 아핀이 사용한 프로젝트적 변형을 대체했다.몇 년 후, "새로운" 어핀 스케일링 알고리즘은 사실 디킨의 수십 년 전의 결과를 재창조하는 것이라는 것을 깨달았다.^[1]^[4]재발견자 중 오직 반즈와 반데르베이 외만이 아핀 스케일링의 수렴 성질을 분석하는데 성공했다.이 시간대에 아핀 스케일링과 함께 온 카르마르카는 자신의 알고리즘처럼 빠르게 융합된다고 잘못 믿었다.^[5]^{: 346}

알고리즘.

아핀 스케일링은 두 단계로 이루어지는데, 첫 번째 단계에서는 최적화를 시작할 수 있는 실현 가능한 지점을 찾는 반면, 두 번째 단계에서는 실현 가능한 영역 내에 엄격히 머무르면서 실제 최적화를 한다.

두 단계 모두 같은 형태인 viz로 선형 프로그램을 해결한다.

c

⋅

x

를 최소화하다

Ax

=

b

,

x

≥

0

의 적용을 받는다.

이러한 문제들은 반복적인 방법을 사용하여 해결되는데, 개념적으로 문제의 실현 가능한 영역 내에서 점의 궤적을 엄격히 표시하여 문제의 재확대된 버전으로 예상 구배 강하 단계를 계산한 다음 원래의 문제로 다시 한 단계 확장한다.스케일링을 통해 고려 중인 지점이 실현 가능한 영역의 경계선에 가까운 경우에도 알고리즘이 큰 단계를 계속 수행할 수 있도록 보장한다.^[5]^{: 337}

형식적으로 아핀 스케일링의 심장부에 있는 반복 방법은 엄격하게 실현 가능한 입력 $A$ , $b$ , $c$ , $초기 0$ 추측 $x 0$ > $0$ , 공차 $ε$ , 스텝사이즈 $β$ 로 취한다.그런 다음 반복하여^[1]^{: 111} 진행한다.

$D$ 를_k 대각선 행렬로 $하고 k$ x는 대각선 행렬로 한다.
이중 변수의 벡터 계산:
$w^{k}=(AD_{k}^{2).}}A^{\operatorname {T}^{-1}AD_{k}^{2}c.$
이중에서 불평등 제약의 느슨함을 측정하는 감소된 비용의 벡터를 계산한다.
$r^{k}=c-A^{\operatorname {T} }w^{k}.$
$r^{k}>0$ $r^{k}>0$ > $r^{k}>0$ ${\displaystyle$ r $^{k}>0}$ 및 1 $r^{k}>0$ $\mathbf {1} ^{\operatorname {T} }D_{k}r^{k}<\varepsilon$ D $\mathbf {1} ^{\operatorname {T} }D_{k}r^{k}<\varepsilon$ $\mathbf {1} ^{\operatorname {T} }D_{k}r^{k}<\varepsilon$ $\mathbf {1} ^{\operatorname {T} }D_{k}r^{k}<\varepsilon$ < $\mathbf {1} ^{\operatorname {T} }D_{k}r^{k}<\varepsilon$ ${\displaystyle \mathbf {$ 1 $} ^{\operatorname {T}$ } $}D_{k}r^{k$ }{k $}}<\varepsilon$ $\mathbf {1} ^{\operatorname {T} }D_{k}r^{k}<\varepsilon$ 현재 솔루션 $x$ 는^k ε-최적임.
$-D_{k}r^{k}\geq 0$ $-D_{k}r^{k}\geq 0$ $-D_{k}r^{k}\geq 0$ $-D_{k}r^{k}\geq 0$ $-D_{k}r^{k}\geq 0$ $-D_{k}r^{k}\geq 0$ ${\displaystyle -D_{k_}r^{k}\geq$ 0 $-D_{k}r^{k}\geq 0$ 인 경우, 문제는 무한하다.
업데이트 $x^{k+1}=x^{k}-\beta {\frac {D_{k}^{2}r^{k}}{\|D_{k}r^{k}\|}}$ $x^{k+1}=x^{k}-\beta {\frac {D_{k}^{2}r^{k}}{\|D_{k}r^{k}\|}}$ + $x^{k+1}=x^{k}-\beta {\frac {D_{k}^{2}r^{k}}{\|D_{k}r^{k}\|}}$ = x $x^{k+1}=x^{k}-\beta {\frac {D_{k}^{2}r^{k}}{\|D_{k}r^{k}\|}}$ - $x^{k+1}=x^{k}-\beta {\frac {D_{k}^{2}r^{k}}{\|D_{k}r^{k}\|}}$ D $x^{k+1}=x^{k}-\beta {\frac {D_{k}^{2}r^{k}}{\|D_{k}r^{k}\|}}$ 2 $x^{k+1}=x^{k}-\beta {\frac {D_{k}^{2}r^{k}}{\|D_{k}r^{k}\|}}$ k $x^{k+1}=x^{k}-\beta {\frac {D_{k}^{2}r^{k}}{\|D_{k}r^{k}\|}}$ D $x^{k+1}=x^{k}-\beta {\frac {D_{k}^{2}r^{k}}{\|D_{k}r^{k}\|}}$ r $x^{k+1}=x^{k}-\beta {\frac {D_{k}^{2}r^{k}}{\|D_{k}r^{k}\|}}$ $x^{k+1}=x^{k}-\beta {\frac {D_{k}^{2}r^{k}}{\|D_{k}r^{k}\|}}$ ${\$ x $^{k+1}=x^{k}-\beta {\frac {d_{k}^{2}r^{k}}}}{$ k}}}}}{ $d_{k}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}$

초기화

초기화 1단계는 추가 변수 $u$ 로 보조 문제를 해결하고 그 결과를 사용하여 원래 문제의 초기 포인트를 도출한다. $x$ 는⁰ 임의적이고 엄격히 긍정적인 지점이 되도록 하라; 그것은 원래 문제에 대해 실현 가능하지 않을 필요가 있다. $x$ 의⁰ 실현 불가능성은 벡터에 의해 측정된다.

v=b-Ax^{0}

=

v=b-Ax^{0}

-

v=b-Ax^{0}

v=b-Ax^{0}

v=b-Ax^{0}

{\

$v$ = $0$ 이면 $x$ 가⁰ 가능하다.그렇지 않으면 1단계에서 보조 문제를 해결한다.

u

를 최소화하다

Ax

+

uv

=

b

,

x

≥

0

,

u

≥

0

의 적용을 받는다.

이 문제는 위의 반복 알고리즘에 의해 해결의 올바른 형태를 가지고 있다.^[a]

{\pmatrix}x^{0}\\1\end{pmatrix}}

그것을 위한 실현 가능한 초기 지점이다.보조 문제를 해결하면

{\begin{pmatrix}x^{*}\\u^{*}\end{pmatrix}}

{\begin{pmatrix}x^{*}\\u^{*}\end{pmatrix}}

{\begin{pmatrix}x^{*}\\u^{*}\end{pmatrix}}

{\begin{pmatrix}x^{*}\\u^{*}\end{pmatrix}}

{\begin{pmatrix}x^{*}\\u^{*}\end{pmatrix}}

)

{\

$u *$ = $0$ 이면 $x * \geq0$ 은 원래의 문제(꼭 내부적인 것은 아니지만)에서 실현 가능한 반면, $u *$ = $0$ 이면 원래의 문제는 실현 불가능한 것이다.^[5]^{: 343}

분석

말하기 쉽지만, 아핀 스케일링은 분석하기 어려운 것으로 밝혀졌다.그것의 수렴은 스텝 크기인 $β$ 에 따라 달라진다.단계 크기는≤.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output.sfrac.tion,.mw-parser-output.sfrac .tion{디스플레이:inline-block, vertical-align:-0.5em, font-size:85%;text-align:센터}.mw-parser-output.sfrac.num,.mw-parser-output.sfrac .den{디스플레이:블록, line-height:1em, 마진:00.1em}.mw-parser-output.sfrac .den{border-top:1px sββ하는 동안 Olid}.mw-parser-output .sr-only{국경:0;클립:rect(0,0,0,0), 높이:1px, 마진:-1px, 오버 플로: 숨어 있었다. 패딩:0;위치:절대, 너비:1px}2/3, affine 스케일링의 Vanderbei의 변형 융합할 수 있습니다;0.995를 예 문제 잘 알려 져는 차선의 값에 전진을 증명하였다.[5]:342알고리즘의 다른 변형들은 $2 / 3$ 이상일 때 작은 문제에도 혼란스러운 행동을 보이는 것으로 나타났다.^[6]^[7]

메모들

^ 보조 문제의 구조는 공식을 다소 단순화할 수 있다.^[5]^{: 344}

참조

^ ^a ^b ^c Vanderbei, R. J.; Lagarias, J. C. (1990). "I. I. Dikin's convergence result for the affine-scaling algorithm". Mathematical developments arising from linear programming (Brunswick, ME, 1988). Contemporary Mathematics. Vol. 114. Providence, RI: American Mathematical Society. pp. 109–119. doi:10.1090/conm/114/1097868. MR 1097868.
^ Barnes, Earl R. (1986). "A variation on Karmarkar's algorithm for solving linear programming problems". Mathematical Programming. 36 (2): 174–182. doi:10.1007/BF02592024.
^ Vanderbei, Robert J.; Meketon, Marc S.; Freedman, Barry A. (1986). "A Modification of Karmarkar's Linear Programming Algorithm" (PDF). Algorithmica. 1 (1–4): 395–407. doi:10.1007/BF01840454.
^ Bayer, D. A.; Lagarias, J. C. (1989). "The nonlinear geometry of linear programming I: Affine and projective scaling trajectories" (PDF). Transactions of the American Mathematical Society. 314 (2): 499. doi:10.1090/S0002-9947-1989-1005525-6.
^ ^a ^b ^c ^d ^e Vanderbei, Robert J. (2001). Linear Programming: Foundations and Extensions. Springer Verlag. pp. 333–347.
^ Bruin, H.; Fokkink, R.J.; Gu, G.; Roos, C. (2014). "On the chaotic behavior of the primal–dual affine–scaling algorithm for linear optimization" (PDF). Chaos. 24 (4): 043132. arXiv:1409.6108. Bibcode:2014Chaos..24d3132B. doi:10.1063/1.4902900. PMID 25554052.
^ Castillo, Ileana; Barnes, Earl R. (2006). "Chaotic Behavior of the Affine Scaling Algorithm for Linear Programming". SIAM J. Optim. 11 (3): 781–795. doi:10.1137/S1052623496314070.

추가 읽기

Adler, Ilan; Monteiro, Renato D. C. (1991). "Limiting behavior of the affine scaling continuous trajectories for linear programming problems" (PDF). Mathematical Programming. 50 (1–3): 29–51. doi:10.1007/bf01594923.
Saigal, Romesh (1996). "A simple proof of a primal affine scaling method" (PDF). Annals of Operations Research. 62: 303–324. doi:10.1007/bf02206821. hdl:2027.42/44263.
Tseng, Paul; Luo, Zhi-Quan (1992). "On the convergence of the affine-scaling algorithm" (PDF). Mathematical Programming. 56 (1–3): 301–319. CiteSeerX 10.1.1.94.7852. doi:10.1007/bf01580904. hdl:1721.1/3161.

외부 링크

"15.093 Optimization Methods, Lecture 21: The Affine Scaling Algorithm" (PDF). MIT OpenCourseWare. 2009.
Mitchell, John (November 2010). "Interior Point Methods". Rensselaer Polytechnic Institute.
"Lecture 6: Interior point method" (PDF). NCTU OpenCourseWare. Archived from the original (PDF) on 2016-10-11. Retrieved 2016-02-06.

[6] 보조 문제의 구조는 공식을 다소 단순화할 수 있다.^[5]^{: 344}

[vanderbei90-1] Vanderbei, R. J.; Lagarias, J. C. (1990). "I. I. Dikin's convergence result for the affine-scaling algorithm". Mathematical developments arising from linear programming (Brunswick, ME, 1988). Contemporary Mathematics. Vol. 114. Providence, RI: American Mathematical Society. pp. 109–119. doi:10.1090/conm/114/1097868. MR 1097868.

[2] Barnes, Earl R. (1986). "A variation on Karmarkar's algorithm for solving linear programming problems". Mathematical Programming. 36 (2): 174–182. doi:10.1007/BF02592024.

[3] Vanderbei, Robert J.; Meketon, Marc S.; Freedman, Barry A. (1986). "A Modification of Karmarkar's Linear Programming Algorithm" (PDF). Algorithmica. 1 (1–4): 395–407. doi:10.1007/BF01840454.

[4] Bayer, D. A.; Lagarias, J. C. (1989). "The nonlinear geometry of linear programming I: Affine and projective scaling trajectories" (PDF). Transactions of the American Mathematical Society. 314 (2): 499. doi:10.1090/S0002-9947-1989-1005525-6.

[lpfe-5] Vanderbei, Robert J. (2001). Linear Programming: Foundations and Extensions. Springer Verlag. pp. 333–347.

[7] Bruin, H.; Fokkink, R.J.; Gu, G.; Roos, C. (2014). "On the chaotic behavior of the primal–dual affine–scaling algorithm for linear optimization" (PDF). Chaos. 24 (4): 043132. arXiv:1409.6108. Bibcode:2014Chaos..24d3132B. doi:10.1063/1.4902900. PMID 25554052.

[8] Castillo, Ileana; Barnes, Earl R. (2006). "Chaotic Behavior of the Affine Scaling Algorithm for Linear Programming". SIAM J. Optim. 11 (3): 781–795. doi:10.1137/S1052623496314070.

[1]

[2]

[3]

[4]

[5]

[a]

[6]

[7]

Search

아핀 스케일링

네임스페이스

더

목차

역사

알고리즘.

초기화

분석

메모들

참조

추가 읽기

외부 링크