Задачи по курсу (1125232), страница 4
Текст из файла (страница 4)
спуск: α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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
