소분법

하위 단계적 방법은 볼록 최소화 문제를 해결하기 위한 반복적 방법이다.원래 Naum Z에 의해 개발되었다. 1960~70년대 쇼르 등은 차별성이 없는 객관적 기능에도 적용하면 하위학위 방식이 수렴된다.객관적 기능이 다를 경우 제한되지 않는 문제에 대한 하위 단계적 방법은 가장 가파른 하강 방법과 동일한 검색 방향을 사용한다.

연속적으로 두 번 다른 볼록함수를 최소화하기 위해 적용했을 때 하위 단계 방법은 뉴턴의 방법보다 느리다.그러나 뉴턴의 방법은 구별할 수 없는 꼬임 현상이 있는 문제들에 수렴하지 못한다.

최근 몇 년 동안 볼록한 최소화 문제에 대해 일부 내부 포인트 방법이 제안되었지만, 하위 단계 투영 방법과 관련 묶음 강하 방법은 여전히 경쟁력이 있다.치수가 매우 많은 볼록형 최소화의 경우 저장이 거의 필요 없기 때문에 하위분사 방법이 적합하다.

분해 기법의 대규모 문제에는 종종 하위 투영법이 적용된다.그러한 분해 방법은 종종 문제에 대해 간단한 분산 방법을 허용한다.

고전하급규칙

$f:\mathbb {R} ^{n}\to \mathbb {R}$ : $f:\mathbb {R} ^{n}\to \mathbb {R}$ $f:\mathbb {R} ^{n}\to \mathbb {R}$ → R ${\$ 를) 도메인 $\mathbb {R} ^{n}$ ${\$ 을(를) 가진 볼록함수가 되도록 $f:\mathbb {R} ^{n}\to \mathbb {R}$ 두십시오 $\mathbb {R} ^{n}$ 고전적인 하위 단계 방법은 반복한다.

x^{(k+1)}=x^{(k)}-\cHB _{k}g^{(k)}\

where $g^{(k)}$ denotes any subgradient of $f\$ at $x^{(k)}\$ , and $x^{(k)}$ is the $k^{th}$ iterate of $x$ . If $f\$ is differentiable, 그리고 그것의 유일한 하위학위는 그라데이션 벡터 $\nabla f$ $\nabla f$ $\nabla f$ 그 자체다 $\nabla f$ .- $-g^{(k)}$ ( $){\$ $x^{(k)}$ $)}}$ 는 x ( $x^{(k)}$ k $){\$ x $^{(k)}}}}$ 에서 $f \$ $f$ {\ $displaystyle f_{\rm {best}\}}}}}}$ 에 대한 하강 방향이 $-g^{(k)}$ 아닐 수 있다 $x^{(k)}$ 따라서 지금까지 발견된 최저 목표 함수 값을 추적하는 $f_{\rm {best}}\$ $f_{\rm {best}}\$ f b $f_{\rm {best}}\$ 를 유지한다.

f_{\rm {best}^{(k)}=\min\{f_{\rm {best}^{(k-1)}f(x^{(k)}}}

단계 크기 규칙

많은 다른 유형의 단계 크기 규칙이 하위 단계적 방법에 의해 사용된다.이 기사에서는 수렴 증명서가 알려진 다섯 가지 고전적 단계 크기 규칙을 주목한다.

일정 단계 크기, $\alpha _{k}=\alpha .$ $\alpha _{k}=\alpha .$ = $\alpha _{k}=\alpha .$ $\alpha _{k}=\alpha .$
Constant step length, $\alpha _{k}=\gamma /\lVert g^{(k)}\rVert _{2}$ , which gives $\lVert x^{(k+1)}-x^{(k)}\rVert _{2}=\gamma .$
정사각형 종합 단계 크기(즉, 만족스러운 모든 단계 크기) $\jeq 0,\qquad \sum \sum \sum \{k=1}^{k=1}{k=1}{k=1}{k=\ft.$
측정 불가능한 감소, 즉 모든 스텝 크기 만족 $\jeq 0,\qquad \lim _{k\to \infit }\property_{k=1}^{\infit _{k}=\inft.$
축소 불가능한 단계 길이, 즉 α k = $\alpha _{k}=\gamma _{k}/\lVert g^{(k)}\rVert _{2}$ / $\alpha _{k}=\gamma _{k}/\lVert g^{(k)}\rVert _{2}$ $\alpha _{k}=\gamma _{k}/\lVert g^{(k)}\rVert _{2}$ ( $\alpha _{k}=\gamma _{k}/\lVert g^{(k)}\rVert _{2}$ k $\alpha _{k}=\gamma _{k}/\lVert g^{(k)}\rVert _{2}$ ) $\alpha _{k}=\gamma _{k}/\lVert g^{(k)}\rVert _{2}$ $\alpha _{k}=\gamma _{k}/\lVert g^{(k)}\rVert _{2}$ ${\$ }}, 여기서 $\jeq 0,\qquad \lim _{k\to \infit }\property_{k=1}^{\infit _{k}=\inft.$

다섯 가지 규칙 모두에 대해, 단계 크기는 방법이 반복되기 전에 "오프라인"으로 결정된다. 단계 크기는 이전의 반복에 의존하지 않는다.하위 단계적 방법의 이 "오프라인" 특성은 다른 기능의 하강 방법에 사용되는 "온라인" 단계 크기 규칙과 다르다.서로 다른 기능을 최소화하기 위한 많은 방법들은 통합에 충분한 조건을 만족시킨다. 일반적으로 단계적 크기는 현재 지점과 현재 검색 방향에 따라 결정된다.증분 버전을 포함한 하위 단계적 방법에 대한 단계적 규칙에 대한 광범위한 논의는 베르체카스와^[1] 베르체카스, 네디치, 오즈다글러에 의해 저서에 제시된다.^[2]

수렴 결과

유클리드 규범이 1과 동일한 일정한 스텝 길이 및 스케일 하위 중진의 경우, 하위 중분법에서는 최소값에 임의로 가까운 근사치 즉, 다음과 같은 근사치로 수렴한다.

\lim _{k\to \infty }f_{\rm {best}}^{(k)}-f^{*}<\epsilon

im

\lim_{k\to\infty} f_{\rm{best}}^{(k)} - f^* <\epsilon

\lim _{k\to \infty }f_{\rm {best}}^{(k)}-f^{*}<\epsilon

→

\lim _{k\to \infty }f_{\rm {best}}^{(k)}-f^{*}<\epsilon

\lim _{k\to \infty }f_{\rm {best}}^{(k)}-f^{*}<\epsilon

\lim _{k\to \infty }f_{\rm {best}}^{(k)}-f^{*}<\epsilon

\lim _{k\to \infty }f_{\rm {best}}^{(k)}-f^{*}<\epsilon

t

\lim _{k\to \infty }f_{\rm {best}}^{(k)}-f^{*}<\epsilon

(

\lim _{k\to \infty }f_{\rm {best}}^{(k)}-f^{*}<\epsilon

) -

\lim _{k\to \infty }f_{\rm {best}}^{(k)}-f^{*}<\epsilon

\lim _{k\to \infty }f_{\rm {best}}^{(k)}-f^{*}<\epsilon

<

\lim _{k\to \infty }f_{\rm {best}}^{(k)}-f^{*}<\epsilon

{\displaystyle \lim

\

to \inflt

^[3]

}f_{\rm {best}^{{(k)-f^{*}<\psilon }}}}.

이러한 고전적인 하위 단계 방법은 성능이 저하되어 더 이상 일반 용도로 권장되지 않는다.^[4]^[5]그러나 그것들은 간단하고 당면한 문제의 특수한 구조를 이용하기 위해 쉽게 적응할 수 있기 때문에 여전히 전문화된 어플리케이션에서 널리 사용되고 있다.

하위 단계-투영 & 번들 방법

1970년대 클로드 르마레찰과 필 울프는 볼록 최소화 문제를 위해 "번들 방식"을 제안했다.^[6]이때부터 번들번들 방법이라는 용어의 의미가 크게 달라졌다.현대판과 완전한 융합 분석은 키위엘이 제공했다.^[7] 현대의 번들-방법들은 종종 보리스 T의 "하위-투영" 방법으로부터 기술을 개발하면서 단계적 크기를 선택할 때 "레벨 컨트롤" 규칙을 사용한다.폴리아크(1969년).그러나, 번들 방법이 하위 단계별 방법보다 거의 유리하지 않은 문제가 있다.^[4]^[5]

제약 최적화

계획하급

하위 단계 방법의 확장 중 하나는 제한된 최적화 문제를 해결하는 하위 단계 계획 방법이다.

다음 조건에 따라

f(x)\

f(x)\

(

f(x)\

)

{\

최소화

x\in {\mathcal{C}

여기서 ${\mathcal {C}}$ ${\$ 은(는) 볼록 집합이다 ${\mathcal {C}}$ .계획 하위 단계 방법은 반복을 사용한다.

x^{(k+1)}=P\왼쪽(x^{(k)-\알파 _{k}g^{(k)}\오른쪽)

여기서 $P$ $P$ 은 $P$ (는) ${\mathcal {C}}$ ${\$ 에 ${\mathcal {C}}$ $g^{(k)}$ 되며 g $g^{(k)}$ ( $g^{(k)}$ ) $g^{(k)}$ {\ $displaystyle$ g $^{(k$ $)}}}$ 은 $g^{(k)}$ ( $x^{(k)}.$ 에서 $f \$ f $f\$ ${\displaystystyle$ $f\}$ 의 하위 단계인 것이다 $.$

일반 제약 조건

하위 단계 방법은 불평등 제약 문제를 해결하기 위해 확장될 수 있다.

f_{0}(x)\

f_{0}(x)\

에 따라

f_{0}(x)\

0

f_{0}(x)\

x ) {\

displaystyle f_{0}(

x)\

}

최소화

f_{i}(x)\leq 0,\properties i=1,\properties,m

$f_{i}$ 서 $f_{i}$ f ${\$ 는 볼록하다.알고리즘은 제한되지 않은 사례와 동일한 형태를 취함

x^{(k+1)}=x^{(k)}-\cHB _{k}g^{(k)}\

여기서 $\alpha _{k}>0$ $\alpha _{k}>0$ > $\alpha _{k}>0$ $\alpha _{k}}0$ 은 $\alpha_k>0$ (는) 단계 크기이며, $g^{(k)}$ ( $g^{(k)}$ k ) {\ $displaystyle g$ ^{(k $)}}}}$ 은(는) 목적의 하위 단계 또는 $g^{(k)}$ x $x.\$ . ${\$ x $.\}$ 에서 $x. \$ 구속조건 함수 중 하나이다.

g^{(k)}={\begin{cases}\partial f_{0}(x)&{\text{ if }}f_{i}(x)\leq 0\;\forall i=1\dots m\\\partial f_{j}(x)&{\text{ for some }}j{\text{ such that }}f_{j}(x)>0\end{cases}}

여기서 $\partial f$ $\partial f$ $\partial f$ 은 $f\$ ${\$ f $\}$ 의 하위 차분을 나타낸다 $\partial f$ $f\$ 현재 포인트가 실행 가능한 경우 알고리즘은 객관적 하위 세분화를 사용하고, 현재 포인트가 실행 불가능한 경우, 위반된 제약 조건의 하위 세분화를 선택한다.

참조

^ Bertsekas, Dimitri P. (2015). Convex Optimization Algorithms (Second ed.). Belmont, MA.: Athena Scientific. ISBN 978-1-886529-28-1.
^ Bertsekas, Dimitri P.; Nedic, Angelia; Ozdaglar, Asuman (2003). Convex Analysis and Optimization (Second ed.). Belmont, MA.: Athena Scientific. ISBN 1-886529-45-0.
^ 일정한 계단 크기(척도) 하위 단계 방법의 대략적인 수렴은 베르체카스(636페이지)의 연습 6.3.14(a)로 명시된다.Bertsekas, Dimitri P. (1999). Nonlinear Programming (Second ed.). Cambridge, MA.: Athena Scientific. ISBN 1-886529-00-0. 636페이지에서 베르체카스는 이 결과를 Shor에게 다음과 같이 귀속시킨다.
^ ^a ^b Lemaréchal, Claude (2001). "Lagrangian relaxation". In Michael Jünger and Denis Naddef (ed.). Computational combinatorial optimization: Papers from the Spring School held in Schloß Dagstuhl, May 15–19, 2000. Lecture Notes in Computer Science. Vol. 2241. Berlin: Springer-Verlag. pp. 112–156. doi:10.1007/3-540-45586-8_4. ISBN 3-540-42877-1. MR 1900016.
^ ^a ^b Kiwiel, Krzysztof C.; Larsson, Torbjörn; Lindberg, P. O. (August 2007). "Lagrangian relaxation via ballstep subgradient methods". Mathematics of Operations Research. 32 (3): 669–686. doi:10.1287/moor.1070.0261. MR 2348241.
^ Bertsekas, Dimitri P. (1999). Nonlinear Programming (Second ed.). Cambridge, MA.: Athena Scientific. ISBN 1-886529-00-0.
^ Kiwiel, Krzysztof (1985). Methods of Descent for Nondifferentiable Optimization. Berlin: Springer Verlag. p. 362. ISBN 978-3540156420. MR 0797754.

추가 읽기

Bertsekas, Dimitri P. (1999). Nonlinear Programming. Belmont, MA.: Athena Scientific. ISBN 1-886529-00-0.
Bertsekas, Dimitri P.; Nedic, Angelia; Ozdaglar, Asuman (2003). Convex Analysis and Optimization (Second ed.). Belmont, MA.: Athena Scientific. ISBN 1-886529-45-0.
Bertsekas, Dimitri P. (2015). Convex Optimization Algorithms. Belmont, MA.: Athena Scientific. ISBN 978-1-886529-28-1.
Shor, Naum Z. (1985). Minimization Methods for Non-differentiable Functions. Springer-Verlag. ISBN 0-387-12763-1.

Ruszczyński, Andrzej (2006). Nonlinear Optimization. Princeton, NJ: Princeton University Press. pp. xii+454. ISBN 978-0691119151. MR 2199043.

외부 링크

스탠포드의 볼록 최적화 과정 순서인 EE364A와 EE364B.

[1] Bertsekas, Dimitri P. (2015). Convex Optimization Algorithms (Second ed.). Belmont, MA.: Athena Scientific. ISBN 978-1-886529-28-1.

[2] Bertsekas, Dimitri P.; Nedic, Angelia; Ozdaglar, Asuman (2003). Convex Analysis and Optimization (Second ed.). Belmont, MA.: Athena Scientific. ISBN 1-886529-45-0.

[3] 일정한 계단 크기(척도) 하위 단계 방법의 대략적인 수렴은 베르체카스(636페이지)의 연습 6.3.14(a)로 명시된다.Bertsekas, Dimitri P. (1999). Nonlinear Programming (Second ed.). Cambridge, MA.: Athena Scientific. ISBN 1-886529-00-0. 636페이지에서 베르체카스는 이 결과를 Shor에게 다음과 같이 귀속시킨다.

[Lem-4] Lemaréchal, Claude (2001). "Lagrangian relaxation". In Michael Jünger and Denis Naddef (ed.). Computational combinatorial optimization: Papers from the Spring School held in Schloß Dagstuhl, May 15–19, 2000. Lecture Notes in Computer Science. Vol. 2241. Berlin: Springer-Verlag. pp. 112–156. doi:10.1007/3-540-45586-8_4. ISBN 3-540-42877-1. MR 1900016.

[KLL-5] Kiwiel, Krzysztof C.; Larsson, Torbjörn; Lindberg, P. O. (August 2007). "Lagrangian relaxation via ballstep subgradient methods". Mathematics of Operations Research. 32 (3): 669–686. doi:10.1287/moor.1070.0261. MR 2348241.

[6] Bertsekas, Dimitri P. (1999). Nonlinear Programming (Second ed.). Cambridge, MA.: Athena Scientific. ISBN 1-886529-00-0.

[7] Kiwiel, Krzysztof (1985). Methods of Descent for Nondifferentiable Optimization. Berlin: Springer Verlag. p. 362. ISBN 978-3540156420. MR 0797754.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Search

소분법

네임스페이스

더

목차