Відмінності між версіями «Метод узагальнених стохастичних градієнтів для розв’язання двохетапної задачі СП. Загальний алгоритм.»

Версія за 21:35, 11 квітня 2013

Метод узагальнених стохастичних градієнтів не припускає диференціювання цільової функції задачі і не вимагає завдання статистичних характеристик випадкових параметрів умов задачі. Метод стохастичних градієнтів є загальним методом стохастичної апроксимації. Для ітеративного розв’язання задачі використовується послідовність реалізації матриці Неможливо розібрати вираз (невідома помилка): \ A(\omega)

і векторів  Неможливо розібрати вираз (невідома помилка): \ b(\omega) 
та Неможливо розібрати вираз (невідома помилка): \ c(\omega) 

.

Метод стохастичних градієнтів може бути використаний також для розв’язання нелінійної двохетапної стохастичної задачі. Застосування методу узагальнених стохастичних градієнтів базується на наступних міркуваннях. Нехай потрібно мінімізувати опуклу вниз функцію Неможливо розібрати вираз (невідома помилка): \ \varphi(\omega)

  на опуклій множині Неможливо розібрати вираз (невідома помилка): \ K 

. Розглянемо наступний ітеративний процес випадкового пошуку розв’язання задачі

Неможливо розібрати вираз (невідома помилка): \ x^{s+1}=\pi_K \left ( x^{(s)}-\rho_s \gamma_s \xi^{(s)} \right ) . (29.1)

Тут Неможливо розібрати вираз (невідома помилка): \ x^{(0)}

- довільний n-вимірний вектор, який належить множені Неможливо розібрати вираз (невідома помилка): \ K 
- початкова точка процесу;

Неможливо розібрати вираз (невідома помилка): \rho_s

- величина кроку на s-й ітерації;

Неможливо розібрати вираз (невідома помилка): \gamma_s

- нормований множник;

Неможливо розібрати вираз (невідома помилка): \xi^{(s)}

- випадковий вектор, умовне математичне сподівання яке відносно Неможливо розібрати вираз (невідома помилка):  x^{(0)}, x^{(1)},..., x^{(s)}
залежить лінійно від узагальненого градієнта Неможливо розібрати вираз (невідома помилка): \ \varphi_x 
(субградієнта або опорного функціоналу) функції Неможливо розібрати вираз (невідома помилка): \ \varphi(x) 
в точці Неможливо розібрати вираз (невідома помилка): \ x^{(s)} 

Неможливо розібрати вираз (невідома помилка): ~M \left (\xi^{(s)}\mid x^{(0)}, x^{(1)},..., x^{(s)} \right ) = a_s \varphi_x(x^{(s)}) +m^{(s)}

(29.2)

В формулі (29.2) Неможливо розібрати вираз (невідома помилка): a_s

- деяке число, Неможливо розібрати вираз (невідома помилка):  m^{(s)}
- n-вимірний вектор.

Неможливо розібрати вираз (невідома помилка): \pi_{K}(x)

- оператор проектування на множині Неможливо розібрати вираз (невідома помилка):  K 

, тобто такої, що

Неможливо розібрати вираз (невідома помилка): \pi_{K}(x) \in K

і Неможливо розібрати вираз (невідома помилка):  \left \| x- \pi_{K}(x) \right \|^2 \le \left \| y-x \right \|^2 
для будь-якого Неможливо розібрати вираз (невідома помилка):  y \in K 

.

Іншими словами, оператор проектування Неможливо розібрати вираз (невідома помилка): y=\pi_K(x)

являє собою розв’язок наступної задачі опуклого програмування з квадратичною цільовою функцією: 

Неможливо розібрати вираз (невідома помилка): inf \left \| x-y \right \|^2, y\in K

(29.3)

Значення Неможливо розібрати вираз (невідома помилка): a_s

і Неможливо розібрати вираз (невідома помилка):  m^{(s)} 
в (29.2) можуть залежати від Неможливо розібрати вираз (невідома помилка):  x^{(0)}, x^{(1)},..., x^{(s)} 

. Проте пропонується, що існують постійні Неможливо розібрати вираз (невідома помилка): l_s

і Неможливо розібрати вираз (невідома помилка):  r^{(s)}= \left \{r_j^{(s)} \right  \}

, такі, що

Неможливо розібрати вираз (невідома помилка): \left | a_s \left ( x^{(0)}, x^{(1)},..., x^{(s)} \right ) \right | \le l_s

Неможливо розібрати вираз (невідома помилка): \left \| m^{(s)} \left ( x^{(0)}, x^{(1)},..., x^{(s)} \right ) \right \| \le r^{(s)}

Нехай Неможливо розібрати вираз (невідома помилка): min \varphi(x)= \varphi(x^{*})>-\mathcal {1}

Теорема. Нехай

а) відома величина Неможливо розібрати вираз (невідома помилка): h_s\left ( x^{(0)}, x^{(1)},..., x^{(s)} \right ) , така що Неможливо розібрати вираз (невідома помилка): ~M \left ( \left \| \xi^{(s)} \right \|^2 \mid x^{(0)}, x^{(1)},..., x^{(s)} \right ) \le h^2_s \le \sigma^2_ \beta < \mathcal {1}

(29.4)

При Неможливо розібрати вираз (невідома помилка): \left \| x^{k} \right \| \le \beta < \mathcal {1} , k=0,1,...,s , де Неможливо розібрати вираз (невідома помилка): \sigma_{\beta}

- деякі константи;

б) нормуючий множник Неможливо розібрати вираз (невідома помилка): \gamma_s

задовольняє умову 

Неможливо розібрати вираз (невідома помилка): 0< \underline{\gamma_s} \le \gamma_s \left ( \tau_s \left \| x^{(s)} \right \| + h_s \right ) \le \overline{\gamma} < \mathcal {1} , де

Неможливо розібрати вираз (невідома помилка): \tau_s = \begin{cases}1, \left \| m^{(s)} \right \|>0 ,\\ 0, \left \| m^{(s)} \right \|=0 \end{cases}

в) величини Неможливо розібрати вираз (невідома помилка): \rho_s, a_s, l_s, r^{(s)}

такі, що 

Неможливо розібрати вираз (невідома помилка): \rho_s \ge 0, a_s \ge 0,

Неможливо розібрати вираз (невідома помилка): \sum^{\mathcal {1}}_{s=0} {\rho_s r^{(s)}}< \mathcal {1}; \sum^{\mathcal {1}}_{s=0} {\rho^2_s }< \mathcal {1} ; \sum^{\mathcal {1}}_{s=0} {\rho_s l_s } =\mathcal {1}

Тоді майже для кожного Неможливо розібрати вираз (невідома помилка): \omega

 послідовність Неможливо розібрати вираз (невідома помилка):  x^{(s)}(\omega) 
збігається до розв’язку задачі Неможливо розібрати вираз (невідома помилка):   \min \varphi (x)

. Зауважимо, що Неможливо розібрати вираз (невідома помилка): ~M \left ( \left \| \xi^{(s)} \right \|^2 \mid x^{(0)}, x^{(1)},..., x^{(s)} \right )= \sum^{n}_{i=1} {D \left (\xi_i^{(s)}\mid x^{(0)}, x^{(1)},..., x^{(s)} \right )} + a^2_s \left \| \varphi_x(x^{(s)}) \right \| ^2 +2a_s \left ( \varphi_x(x^{(s)}){,}m^{(s)} \right ) + \left \| m^{(s)} \right \| ^2

Звідси випливає, що якщо сума дисперсій компонент вектора Неможливо розібрати вираз (невідома помилка): \xi^{(s)}= \left \{\xi_i^{(s)}\right \}

і 

Неможливо розібрати вираз (невідома помилка): \left \| \varphi_x(x^{(s)}\right \|

обмежені на

Неможливо розібрати вираз (невідома помилка): K , то Неможливо розібрати вираз (невідома помилка): h_s=const

і умова (29.4) виконується.

При явно заданій множині Неможливо розібрати вираз (невідома помилка): K

 процес (29.1) може бути використаний для розв’язку двохетапної задачі стохастичного програмування.

Згідно теореми субградієнт в точці Неможливо розібрати вираз (невідома помилка): x_0

цільового функціоналу детермінованої задачі, еквівалентній двохетапної задачі стохастичного програмування, дорівнює 

Неможливо розібрати вираз (невідома помилка): \varphi_x (x_0) = M \left \{ c- z^{*} \left ( A, b, x_0 \right ) A \right \}

Тому для обчислення попереднього плану Неможливо розібрати вираз (невідома помилка): x^{*}

двохетапної задачі, або, те ж саме що і для розв’язку еквівалентної детермінованої задачі Неможливо розібрати вираз (невідома помилка): \min Q(x) = \min M \left \{ cx + z^{*} \left ( A, b, x \right ) \left ( b-Ax \right ) \right \}

може бути використаний наступний алгоритм. Виберемо послідовність Неможливо розібрати вираз (невідома помилка): \rho _s

і 

Неможливо розібрати вираз (невідома помилка): \gamma _s , які задовольняють умовам теореми (в нашому випадку Неможливо розібрати вираз (невідома помилка): a_s=1, m^{(s)}=0

і отже

Неможливо розібрати вираз (невідома помилка): l^{(s)}=1, r^{(s)}=0 )

Нехай на s-му кроці обчислений вектор Неможливо розібрати вираз (невідома помилка): x^{(s)}

- чергове наближення попереднього плану двохетапної задачі. Для отримання 

Неможливо розібрати вираз (невідома помилка): (s+1)-го

 наближення треба:

а) обрати відповідно з заданою ймовірнісною мірою випадкову реалізацію параметрів умов задачі Неможливо розібрати вираз (невідома помилка): A^{(s)}= A(\omega^{(s)}) , Неможливо розібрати вираз (невідома помилка): b^{(s)}=b(\omega^{(s)}) , Неможливо розібрати вираз (невідома помилка): c^{(s)}=c(\omega ^{(s)})

б) обчислити розв’язок Неможливо розібрати вираз (невідома помилка): z^{*} \left ( A^{(s)}, b^{(s)}, x^{(s)} \right )

задачі  двоїстої до задачі другого етапу при   Неможливо розібрати вираз (невідома помилка):  x=x^{(s)}, A=A^{(s)}, b=b^{(s)} 

в) визначити Неможливо розібрати вираз (невідома помилка): x^{(s+1)}

за формулою (29.1). При цьому

Неможливо розібрати вираз (невідома помилка): \xi^{(s)}= c^{(s)}- z^{*} \left ( A^{(s)}, b^{(s)}, x^{(s)} \right ) A^{(s)} .

В відповідності з теоремою вказаний процес призводить з ймовірністю 1 до розв’язку двохетапної задачі.