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

Метод узагальнених стохастичних градієнтів не припускає диференціювання цільової функції задачі і не вимагає завдання статистичних характеристик випадкових параметрів умов задачі. Метод стохастичних градієнтів є загальним методом стохастичної апроксимації. Для ітеративного розв’язання задачі використовується послідовність реалізації матриці Неможливо розібрати вираз (невідома помилка): \ 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 

.