Відмінності між версіями «Метод узагальнених стохастичних градієнтів для розв’язання двохетапної задачі СП. Загальний алгоритм.»
| Рядок 5: | Рядок 5: | ||
Застосування методу узагальнених стохастичних градієнтів базується на наступних міркуваннях. | Застосування методу узагальнених стохастичних градієнтів базується на наступних міркуваннях. | ||
Нехай потрібно мінімізувати опуклу вниз функцію <math>\ \varphi(\omega) </math> на опуклій множині <math>\ K </math>. | Нехай потрібно мінімізувати опуклу вниз функцію <math>\ \varphi(\omega) </math> на опуклій множині <math>\ K </math>. | ||
| − | Розглянемо наступний ітеративний процес випадкового пошуку розв’язання задачі <math>\ x^{s+1}=\pi_K \left ( x^{(s)}-\rho_s \gamma_s \xi^{(s)} \right ) </math>. | + | Розглянемо наступний ітеративний процес випадкового пошуку розв’язання задачі |
| + | |||
| + | <math>\ x^{s+1}=\pi_K \left ( x^{(s)}-\rho_s \gamma_s \xi^{(s)} \right ) </math>. | ||
| + | (29.1) | ||
| + | |||
| + | |||
Тут <math>\ x^{(0)} </math> - довільний n-вимірний вектор, який належить множені <math>\ K </math> - початкова точка процесу; | Тут <math>\ x^{(0)} </math> - довільний n-вимірний вектор, який належить множені <math>\ K </math> - початкова точка процесу; | ||
| + | |||
<math>\rho_s </math> - величина кроку на s-й ітерації; | <math>\rho_s </math> - величина кроку на s-й ітерації; | ||
| + | |||
<math> \gamma_s </math> - нормований множник; | <math> \gamma_s </math> - нормований множник; | ||
| + | |||
<math> \xi^{(s)} </math> - випадковий вектор, умовне математичне сподівання яке відносно <math> x^{(0)}, x^{(1)},..., x^{(s)}</math> залежить лінійно від узагальненого градієнта <math>\ \varphi_x </math> (субградієнта або опорного функціоналу) функції <math>\ \varphi(x) </math> в точці <math>\ x^{(s)} </math>: | <math> \xi^{(s)} </math> - випадковий вектор, умовне математичне сподівання яке відносно <math> x^{(0)}, x^{(1)},..., x^{(s)}</math> залежить лінійно від узагальненого градієнта <math>\ \varphi_x </math> (субградієнта або опорного функціоналу) функції <math>\ \varphi(x) </math> в точці <math>\ x^{(s)} </math>: | ||
Версія за 09:07, 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)}
