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

Версія за 14:06, 19 березня 2014

В ряді випадків при явно заданій множині К обчислення оператора проектування Неможливо розібрати вираз (невідома помилка): \pi_{K} ( x )

та визначення Неможливо розібрати вираз (невідома помилка):  x^{(s=1)}
 може достатньо спрощеним. Розглянемо декілька  таких випадків.

1. Нехай Неможливо розібрати вираз (невідома помилка): K= \left \{ x|x \geqslant {0} \right \}

В цьому випадку розв'язок задачі (3) записується у наступному вигляді:

Неможливо розібрати вираз (невідома помилка): y*= \pi_{K} ( x )=max\left \{0, x \right \} .

Тому процес (29.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 – лінійно незалежні.

В цьому випадку задача (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

-  множники Лагранжа.

Тому процес (29.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)
- опукла диференційована функція. Задача (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

Наведений результат слідує з правила оптимальності для задач оптимального програмування.

Процес (29.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}.

Створила: Дроздова Маргарита Вікторівна

Доповнила: Чуйкова Анна