Министерство путей сообщения РФ
Дальневосточный государственный университет
путей сообщения
по численным методам
«Минимизация функций нескольких переменных.
Метод спуска.»
Выполнили: Косолапов А.Г. Терехов А.А.
Проверил: Смагин С.И.
Хабаровск 2003
Содержание:
I. Методы спуска (Общая схема) _________________________ 3
II. Метод покоординатного спуска._____________________ 4
III. Метод градиентного спуска.________________________________ 7
IV. Метод наискорейшего спуска.______________________________ 9
V. Описание программы._____________________________________10
IX. Приложение B
(Исследование функции U=A*x1^3+B*x2^2-C*x1-D*x2 (изменение шага))_____ 25
Методы спуска
Все методы спуска решения задачи безусловной минимизации различаются либо выбором направления спуска, либо способом движения вдоль направления спуска. Это позволяет написать общую схему методов спуска.
Решается задача минимизации функции j(x) на всём пространстве En . Методы спуска состоят в следующей процедуре построения последовательности {xk }. В качестве начального приближения выбирается любая точка x0 ÎEn . Последовательные приближения x1 , x2 , … строятся по следующей схеме:
1) в точке xk выбирают направление спуска - Sk ;
2) находят (k+1)-е приближение по формуле xk+1 =xk -hk Sk .
Направление Sk выбирают таким образом, чтобы обеспечить неравенство f(xk+1 )<f(xk ) по крайней мере для малых значений величины hk . На вопрос, какому из способов выбора направления спуска следует отдать предпочтение при решении конкретной задачи, однозначного ответа нет.
Число hk определяет расстояние от точки xk до точки хk+1 . Это число называется длиной шага или просто шагом. Основная задача при выборе величины hk - это обеспечить выполнение неравенства j(xk+1 )<j(xk ).
Величина шага сильно влияет на эффективность метода. Большей эффективностью обладает вариант метода, когда шаг по каждой переменной определяется направляющими косинусами градиента(в градиентных методах).
xk+1 =xk -hk cos
где - cos=
В этом случаи величина рабочего шага не зависит от величины модуля градиента, и ею легче управлять изменением h . В районе оптимума может возникать значительное «рыскание», поэтому используют различные алгоритмы коррекции h.
Наибольшее распространение получили следующие алгоритмы:
1. (без коррекции);
2. если ; если
3. , если ; , если; ,если ,
где –угол между градиентами на предыдущем и текущем шаге;
и – заданные пороговые значения выбираются субъективно
(например, ).
Вдали от оптимума направление градиента меняется мало, поэтому шаг можно увеличить (второе выражение), вблизи от оптимума направление резко меняется (угол между градиентами R(x) большой), поэтому h сокращается (третье выражение).
Метод покоординатного спуска.
Пусть нужно найти наименьшее значение целевой функции
u=f(M)=f(x 1 , x 2 , . . . ,xn ). Здесь через М обозначена точка n-мерного пространства с координатами x 1 , x 2 , . . . ,xn : M=(x 1 , x 2 , . . . ,xn ). Выберем какую-нибудь начальную точку М 0 = (x 1 0 , x 2 0 , . . . ,xn 0 ) и рассмотрим функцию f при фиксированных значениях всех переменных, кроме первой: f(x 1 , x 2 0 ,x 3 0 , . . . ,xn 0 ). Тогда она превратится в функцию одной переменной x 1 . Изменяя эту переменную, будем двигаться от начальной точки x 1 =x 1 0 в сторону убывания функции, пока не дойдем до ее минимума при x 1 =x 1 1 , после которого она начинает возрастать. Точку с координатами ( x 1 1 , x 2 0 ,x 3 0 , . . . ,xn 0 ) обозначим через М 1 , при
этом f(M0 ) >= f(M 1 ).
Фиксируем теперь переменные: x 1 =x 1
Одними из наиболее популярных услуг на рынке IT-технологий являются создание и продвижение лендингов. Они способны положительно влиять на деятельность любого бизнес-проекта в интернете. Судя по многочисленным отзывам, заказавшие создание лендингов люди ни разу не пожалели о потраченных деньгах. Они вложили в будущее, которое неразрывно связано с интернетом. Всё больше и больше предпринимателей обращаются к услугам разных агентств, веб-студий, чтобы заказать создание лендинга у профессионалов.