Метод узагальнених стохастичних градієнтів для розв’язання двохетапної задачі СП. Загальний алгоритм.
Метод узагальнених стохастичних градієнтів не припускає диференціювання цільової функції задачі і не вимагає завдання статистичних характеристик випадкових параметрів умов задачі. Метод стохастичних градієнтів є загальним методом стохастичної апроксимації. Для ітеративного розв’язання задачі використовується послідовність реалізації матриці Неможливо розібрати вираз (невідома помилка): \ 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_i^{(s)}
і
Неможливо розібрати вираз (невідома помилка): \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 ) \right \A}.
Тому для обчислення попереднього плану Неможливо розібрати вираз (невідома помилка): x^{*}
двохетапної задачі, або, те ж саме що і для розв’язку еквівалентної детермінованої задачі
Неможливо розібрати вираз (невідома помилка): \min Q(x)=\minM \left \{ cx+z^{*} \left ( A,b,x \right ) \right \left ( b-Ax \right )\}
