Відмінності між версіями «Метод узагальнених стохастичних градієнтів для розв’язання двохетапної задачі СП. Часткові випадки.»
(Створена сторінка: В ряді випадків при явно заданій множині К обчислення оператора проектування <math> \pi_{K} ( x )...) |
9167500 (обговорення • внесок) м |
||
| (не показані 6 проміжних версій 3 учасників) | |||
| Рядок 2: | Рядок 2: | ||
1. Нехай <math> K= \left \{ | 1. Нехай <math> K= \left \{ | ||
| − | x|x \geqslant {0} \right \}</math> В цьому випадку розв'язок задачі (3) записується у наступному вигляді: | + | x|x \geqslant {0} \right \}</math> В цьому випадку розв'язок задачі (1.3) записується у наступному вигляді: |
<math> y*= \pi_{K} ( x )=max\left \{0, x | <math> y*= \pi_{K} ( x )=max\left \{0, x | ||
\right \}</math>. | \right \}</math>. | ||
| − | Тому процес (1) при <math> K= \left \{ | + | Тому процес (1.1) при <math> K= \left \{ |
x|x \geqslant {0} \right \}</math> має вигляд | x|x \geqslant {0} \right \}</math> має вигляд | ||
| Рядок 14: | Рядок 14: | ||
2. Нехай <math> K= \left \{ | 2. Нехай <math> K= \left \{ | ||
| − | x|\alpha_j \leqslant x \leqslant \beta_j \right \}</math> | + | x|\alpha_j \leqslant x \leqslant \beta_j \right \}</math> |
<math> x_i^{(s+1)} \begin{cases} \alpha_j,{ } x_i^{(s)}- \rho_s \gamma_s \xi^{(s)} \leqslant \alpha_j\\ x_i^{(s)}- \rho_s \gamma_s \xi^{(s)},{ } \alpha_j \leqslant x_i^{(s)}- \rho_s \gamma_s \xi^{(s)} \leqslant \beta_j\\ \beta_j,{ } x_i^{(s)}- \rho_s \gamma_s \xi^{(s)} \geqslant \alpha_j \end{cases}</math> | <math> x_i^{(s+1)} \begin{cases} \alpha_j,{ } x_i^{(s)}- \rho_s \gamma_s \xi^{(s)} \leqslant \alpha_j\\ x_i^{(s)}- \rho_s \gamma_s \xi^{(s)},{ } \alpha_j \leqslant x_i^{(s)}- \rho_s \gamma_s \xi^{(s)} \leqslant \beta_j\\ \beta_j,{ } x_i^{(s)}- \rho_s \gamma_s \xi^{(s)} \geqslant \alpha_j \end{cases}</math> | ||
| − | |||
3. Нехай <math> K= \left \{ | 3. Нехай <math> K= \left \{ | ||
| Рядок 23: | Рядок 22: | ||
x|d^{(i)},x)=g_i, i=1,...,m \right \}</math> , де вектори <math>d^{(1)},...,d^{(m)}</math> рядки матриці D – лінійно незалежні. | x|d^{(i)},x)=g_i, i=1,...,m \right \}</math> , де вектори <math>d^{(1)},...,d^{(m)}</math> рядки матриці D – лінійно незалежні. | ||
| − | + | В цьому випадку задача (1.3) записується у вигляді: | |
| − | В цьому випадку задача (3) записується у вигляді: | + | |
<math>(x-y,x-y)\rightarrow min,</math> | <math>(x-y,x-y)\rightarrow min,</math> | ||
| Рядок 35: | Рядок 33: | ||
Де <math>\lambda_i </math> - множники Лагранжа. | Де <math>\lambda_i </math> - множники Лагранжа. | ||
| − | Тому процес (1) приймає вигляд: | + | Тому процес (1.1) приймає вигляд: |
<math>y*= \pi_{K} ( x^{(s)} - \rho_s \gamma_s \xi^{(s)} )=x^{(s)}- \rho_s \gamma_s \xi^{(s)} \sum^{m}_{i=1}\lambda_i d^{(i)}</math> (7) | <math>y*= \pi_{K} ( x^{(s)} - \rho_s \gamma_s \xi^{(s)} )=x^{(s)}- \rho_s \gamma_s \xi^{(s)} \sum^{m}_{i=1}\lambda_i d^{(i)}</math> (7) | ||
| Рядок 44: | Рядок 42: | ||
4. Нехай <math> K= \left \{ | 4. Нехай <math> K= \left \{ | ||
| − | x|g(x)\leqslant 0 \right \}</math> де <math> g(x)</math> - опукла диференційована функція. Задача (3), яка визначає оператор проектування, в такому випадку має розв'язок: | + | x|g(x)\leqslant 0 \right \}</math> де <math> g(x)</math> - опукла диференційована функція. Задача (29.3), яка визначає оператор проектування, в такому випадку має розв'язок: |
<math> y=\pi_{K} ( x)= \begin{cases}x, { } g(x)\leqslant 0 \\ \tilde{x}, { } g(x)>0\end{cases}</math> | <math> y=\pi_{K} ( x)= \begin{cases}x, { } g(x)\leqslant 0 \\ \tilde{x}, { } g(x)>0\end{cases}</math> | ||
| − | Де <math> \tilde{x}</math> обчислюється з умов | + | Де <math> \tilde{x}</math> обчислюється з умов: |
<math> | <math> | ||
| Рядок 57: | Рядок 55: | ||
| − | Процес (1) прийме вигляд: | + | Процес (1.1) прийме вигляд: |
<math> x^{(s+1)}= \begin{cases} x_i^{(s)}- \rho_s \gamma_s \xi^{(s)}, { } g(x^{(s)}- \rho_s \gamma_s \xi^{(s)})\leqslant 0 \\ \tilde{x}, { }g(x^{(s)}- \rho_s \gamma_s \xi^{(s)})> 0 \end{cases}</math> (8) | <math> x^{(s+1)}= \begin{cases} x_i^{(s)}- \rho_s \gamma_s \xi^{(s)}, { } g(x^{(s)}- \rho_s \gamma_s \xi^{(s)})\leqslant 0 \\ \tilde{x}, { }g(x^{(s)}- \rho_s \gamma_s \xi^{(s)})> 0 \end{cases}</math> (8) | ||
| − | Якщо обмеження <math>g(x)\leqslant 0</math> лінійне, <math>(a,x)\leqslant a </math> то <math> \tilde{x}=x^{(s)}- \rho_s \gamma_s \xi^{(s)}-\lambda a</math> | + | Якщо обмеження <math>g(x)\leqslant 0</math> лінійне, <math>(a,x)\leqslant a </math> то <math> \tilde{x}=x^{(s)}- \rho_s \gamma_s \xi^{(s)}-\lambda a</math> то <math> \lambda </math> обчислюється з умови <math> (a,\tilde{x})=a</math> . |
Якщо обмеження <math>g(x)\leqslant 0</math> має вигляд <math>||x||\leqslant a</math> то | Якщо обмеження <math>g(x)\leqslant 0</math> має вигляд <math>||x||\leqslant a</math> то | ||
| − | |||
<math>\tilde{x}=\frac{a(x^{(s)}- \rho_s \gamma_s \xi^{(s)} )}{||x- \rho_s \gamma_s \xi^{(s)}||}</math> | <math>\tilde{x}=\frac{a(x^{(s)}- \rho_s \gamma_s \xi^{(s)} )}{||x- \rho_s \gamma_s \xi^{(s)}||}</math> | ||
| + | |||
| + | 5. Нехай К- випуклий многогранник <math> K= \left \{ x|g(x)\leqslant d \right \}</math> | ||
| + | |||
| + | В цьому випадку оператор проєктування зводиться до розв'язання задачі квадратичного програмування: | ||
| + | |||
| + | <math>{||x- y||^{2}} \rightarrow min,</math> | ||
| + | |||
| + | <math>Dy \leqslant d,</math> | ||
| + | |||
| + | і ітераційний процес (29.1) потребує на кожному кроці розв'язання задачі квадратичного програмування | ||
| + | |||
| + | <font size=4> <math>x^{(s+1)}=min ||x^{s}-\rho_s \gamma_s \xi^{(s)}-y||^{2}.</math> </font> | ||
| + | |||
| + | |||
| + | Створила: [[Користувач:Маргаритка Дроздова|Дроздова Маргарита Вікторівна]] | ||
| + | |||
| + | Доповнила: [[Користувач:Чуйкова Анна|Чуйкова Анна]] | ||
| + | [[category: Ймовірнісні методи в дослідженні операцій]] | ||
Поточна версія на 22:55, 25 червня 2021
В ряді випадків при явно заданій множині К обчислення оператора проектування Неможливо розібрати вираз (невідома помилка): \pi_{K} ( x )
та визначення Неможливо розібрати вираз (невідома помилка): x^{(s=1)}
може достатньо спрощеним. Розглянемо декілька таких випадків.
1. Нехай Неможливо розібрати вираз (невідома помилка): K= \left \{ x|x \geqslant {0} \right \}
В цьому випадку розв'язок задачі (1.3) записується у наступному вигляді:
Неможливо розібрати вираз (невідома помилка): y*= \pi_{K} ( x )=max\left \{0, x \right \} .
Тому процес (1.1) при Неможливо розібрати вираз (невідома помилка): K= \left \{ x|x \geqslant {0} \right \}
має вигляд
Неможливо розібрати вираз (невідома помилка): x^ {(s+1)} = {max} \left \{ 0, x^{(s)}- \rho_s \gamma_s \xi^{(s)} \right \}
(5)
2. Нехай Неможливо розібрати вираз (невідома помилка): K= \left \{ x|\alpha_j \leqslant x \leqslant \beta_j \right \}
Неможливо розібрати вираз (невідома помилка): x_i^{(s+1)} \begin{cases} \alpha_j,{ } x_i^{(s)}- \rho_s \gamma_s \xi^{(s)} \leqslant \alpha_j\\ x_i^{(s)}- \rho_s \gamma_s \xi^{(s)},{ } \alpha_j \leqslant x_i^{(s)}- \rho_s \gamma_s \xi^{(s)} \leqslant \beta_j\\ \beta_j,{ } x_i^{(s)}- \rho_s \gamma_s \xi^{(s)} \geqslant \alpha_j \end{cases}
3. Нехай Неможливо розібрати вираз (невідома помилка): K= \left \{ x|Dx=g\right \}= \left \{ x|d^{(i)},x)=g_i, i=1,...,m \right \}
, де вектори Неможливо розібрати вираз (невідома помилка): d^{(1)},...,d^{(m)}
рядки матриці D – лінійно незалежні.
В цьому випадку задача (1.3) записується у вигляді:
Неможливо розібрати вираз (невідома помилка): (x-y,x-y)\rightarrow min,
Неможливо розібрати вираз (невідома помилка): (d^{(i)},y)=g_i, i=1,...,m
Розв'язок цієї задачі (по методу Лагранжа) визначає вектор проектування:
Неможливо розібрати вираз (невідома помилка): y*=\pi_{K} ( x )=x-\sum^{m}_{i=1}\lambda_i d^{(i)} ,
Де Неможливо розібрати вираз (невідома помилка): \lambda_i
- множники Лагранжа.
Тому процес (1.1) приймає вигляд:
Неможливо розібрати вираз (невідома помилка): y*= \pi_{K} ( x^{(s)} - \rho_s \gamma_s \xi^{(s)} )=x^{(s)}- \rho_s \gamma_s \xi^{(s)} \sum^{m}_{i=1}\lambda_i d^{(i)}
(7)
Домножаючи обидві частини рівності скалярно на Неможливо розібрати вираз (невідома помилка): d^{(i)}
та враховуючи, що Неможливо розібрати вираз (невідома помилка): x^{(s+1)}
та Неможливо розібрати вираз (невідома помилка): x^{(s)}
- точки множини К, отримаємо систему лінійних рівнянь, визначаючих множники Лагранжа:
Неможливо розібрати вираз (невідома помилка): \rho_s \gamma_s ( \xi^{(s)}, d^{(i)} ) = - \sum^{m}_{i=1}\lambda_i (d^{(i)},d^{(j)}), j=1,....,m
4. Нехай Неможливо розібрати вираз (невідома помилка): K= \left \{ x|g(x)\leqslant 0 \right \}
де Неможливо розібрати вираз (невідома помилка): g(x) - опукла диференційована функція. Задача (29.3), яка визначає оператор проектування, в такому випадку має розв'язок:
Неможливо розібрати вираз (невідома помилка): y=\pi_{K} ( x)= \begin{cases}x, { } g(x)\leqslant 0 \\ \tilde{x}, { } g(x)>0\end{cases}
Де Неможливо розібрати вираз (невідома помилка): \tilde{x}
обчислюється з умов:
Неможливо розібрати вираз (невідома помилка): x=\tilde{x}+\lambda \frac{d g(\tilde{x})}{dx} ; { } \lambda \geqslant 0; { }g(\tilde{x})=0
Наведений результат слідує з правила оптимальності для задач оптимального програмування.
Процес (1.1) прийме вигляд:
Неможливо розібрати вираз (невідома помилка): x^{(s+1)}= \begin{cases} x_i^{(s)}- \rho_s \gamma_s \xi^{(s)}, { } g(x^{(s)}- \rho_s \gamma_s \xi^{(s)})\leqslant 0 \\ \tilde{x}, { }g(x^{(s)}- \rho_s \gamma_s \xi^{(s)})> 0 \end{cases}
(8)
Якщо обмеження Неможливо розібрати вираз (невідома помилка): g(x)\leqslant 0
лінійне, Неможливо розібрати вираз (невідома помилка): (a,x)\leqslant a
то Неможливо розібрати вираз (невідома помилка): \tilde{x}=x^{(s)}- \rho_s \gamma_s \xi^{(s)}-\lambda a
то Неможливо розібрати вираз (невідома помилка): \lambda
обчислюється з умови Неможливо розібрати вираз (невідома помилка): (a,\tilde{x})=a
.
Якщо обмеження Неможливо розібрати вираз (невідома помилка): g(x)\leqslant 0
має вигляд Неможливо розібрати вираз (невідома помилка): ||x||\leqslant a то
Неможливо розібрати вираз (невідома помилка): \tilde{x}=\frac{a(x^{(s)}- \rho_s \gamma_s \xi^{(s)} )}{||x- \rho_s \gamma_s \xi^{(s)}||}
5. Нехай К- випуклий многогранник Неможливо розібрати вираз (невідома помилка): K= \left \{ x|g(x)\leqslant d \right \}
В цьому випадку оператор проєктування зводиться до розв'язання задачі квадратичного програмування:
Неможливо розібрати вираз (невідома помилка): {||x- y||^{2}} \rightarrow min,
Неможливо розібрати вираз (невідома помилка): Dy \leqslant d,
і ітераційний процес (29.1) потребує на кожному кроці розв'язання задачі квадратичного програмування
Неможливо розібрати вираз (невідома помилка): x^{(s+1)}=min ||x^{s}-\rho_s \gamma_s \xi^{(s)}-y||^{2}.
Створила: Дроздова Маргарита Вікторівна
Доповнила: Чуйкова Анна
