Е. Корныхин - Задачи по курсу Методы оптимизации (1125258), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Теорема двойственности выполнена.25Глава 4. Экзаменационные задачи26Для самостоятельного решения:1. max (3x + 5).2x42. min(2 − x). Указание: min x = − max(−x).x13. min(2 − x).x1x34.5.max (x + y + 2). Указание: для решения системы линейных неравенств использовать симплекс-метод2x−3y1xyx+y−4min (x + y + 2).2x−3y1xyx+y−4Ответы: 17, ∞, -1, 0, -2.4.2 Применение градиентного методаПостановка задачи. Записать градиентный метод решения задачиmin(x2 + y 2 )a) с постоянным шагом α =14б) наискорейшим спускомВыписать несколько итераций с начальным приближением x1 = 1, y1 =1.Решение.

Градиентный метод:zt+1 = zt − αt · (∇f )(zt)⎛∂ 2⎛ ⎞⎛ ⎞2 ⎞(x+y)xt2x∂x22⎠ = ⎝ ⎠, zt = ⎝ ⎠f = (x + y ), ∇f = ⎝∂22(x + y )yt2y∂yГлава 4. Экзаменационные задачи27⎛⎞ ⎛ ⎞⎛ ⎞xt+1xt2xt⎠ = ⎝ ⎠ − αt ⎝ ⎠ или в виде системы:Тогда ⎝yt+1yt2ytxt+1 = xt − αt 2xt = (1 − 2αt )xtyt+1 = yt − αt 2yt = (1 − 2αt )ytДля постоянного шага: αt = 14 . Тогдаxt+1 = (1 − 2 14 )xt = 12 xtt = 1, 2, ...yt+1 = (1 − 2 14 )yt = 12 ytВыпишем несколько итераций:txtyt111234121214141818Видно, что сходимость происходит со скоростью геометрической прогрессии с q = 12 , что подтверждается соответствующим устверждением оскорости сходимости градиентного метода из лекций.Наискорейшийt : f (zt+1 ) → min. спуск: αxt(1 − 2αt )= (1 − 2αt )2(x2t + yt2 ). Получился квадратныйf (zt+1) = fyt (1 − 2αt )трехчлен (αt - переменная, xt , yt - константы).

Он достигает своего минимума в точке 1 − 2αt∗ = 0, т.е. αt∗ = 12 . Тогда градиентный метод с такимшагом запишется так:xt+1 = (1 − 2 12 )xt = 0t = 1, 2, ...yt+1 = (1 − 2 12 )yt = 0Несколько замечаний. Получилось, что на всех итерациях, кроме первой,zt = 0. Т.е. в данном случае метод сойдётся за одну итерацию. Интересно,Глава 4. Экзаменационные задачи28что наискорейший спуск получился с постоянным шагом! Не часто такоеслучается. Несколько итераций:txtyt111200300400Для самостоятельного решения:1.

min(x3 + y 3 ). x1 = y1 = −1. Постоянный шаг αt = 13 , αt = 23 , αt = 1. Что Вы можете сказатьотносительно сходимости метода при разных αt ? Насколько существенно начальное приближениеx1 , y1 - как оно влияет на сходимость метода? на скорость сходимости? Исследуйте наискорейшийспуск.2. min(x+y). x1 = y1 = −1. Постоянный шаг αt = 13 , αt = 23 , αt = 1.

Что Вы можете сказать относительносходимости метода при разных αt ? Насколько существенно начальное приближение x1 , y1 - как оновлияет на сходимость метода? на скорость сходимости? Исследуйте наискорейший спуск. Предложитесходящийся метод решения этой задачи МП.Ответы: сходится, сходится за одну итерацию, расходится; расходитсяЛитература[1] Новикова Н.М. Основы оптимизации. Курс лекций в МГУ.

1999[2] Гери М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М.: Мир, 1982.[3] Пападимитриу К.Х., Стайглиц К. Комбинаторная оптимизация: алгоритмы и сложность. — М.: Мир, 1984.29.

Характеристики

Список файлов книги