Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Метод проектирования градиентов




Доверь свою работу кандидату наук!
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Градиент дает направление, в котором функция возрастает с наибольшей скоростью. Однако при условной оптимизации оно, как правило, не является возможным направлением. Поэтому используют не сам градиент (антиградиент), а его проекцию на поверхность ограничений, точнее, на плоскость, аппроксимирующую эту поверхность в текущей точке. Очевидно, что проекция градиента определяет направление наискорейшего изменения функции на поверхности ограничений. Метод применим, если целевая функция и все функции ограничений дифференцируемы. Пусть ограничения заданы в виде (5). Найдем возможное направление l, на кот. скорость изм-я целевой ф-и макс. (1):

В допустимой области D функции yj постоянны. Поэтому искомое направление должно удовлетворять системе равенств (2):

Из связи направления с координатами: или (3)

Для нахождения наилучшего возможного направления необходимо решить задачу оптимизации (1) – (3). Т.к условия имеют вид =, а ф-и дифференцируемы, для решения этой вспомогательной задачи воспользуемся методом Лагранжа. Функция Лагранжа:

. Неизвестные - векторы и L. Возьмем и приравняем к 0:

Отсюда выразим компоненты искомого вектора:

->

-> ↓

Так как направление ищется в конкретной точке, то все производные в последней формуле (4) – известные константы. Поэтому система уравнений (4) является линейной системой относительно lj. Ее решение не вызывает затруднений (при условии, что матрица системы не является особенной). Найдя значения lj, получаем компоненты проекции градиента. Движение осуществляется в направлении, противоположном проекции. Аналогично градиентному методу новая точка вычисляется по формуле (6):

Алгоритм.

1. Задать начальную точку, удовлетворяющую системе (5), начальное значение h0 и точность по величине проекции градиента e.

2. В текущей точке вычислить градиенты всех функций (f и yj) и решить систему (4).

3. Вычислить проекцию градиента.

4. Проверить: если завершить поиск.

5. Вычислить новую точку по формуле (6).

6. Проверить: если значение целевой функции улучшилось, перейти на шаг 2, иначе уменьшить hk в два раза и перейти на шаг 5.

Качественный характер работы алгоритма иллюстрирует рис. Здесь функции зависят от 2-х переменных, поэтому в каждой точке на линии ограничения может быть всего 2 направления, лучшее из которых определяет проекция градиента. В многомерной задаче таких направлений бесконечное множество. При ли­ней­ных ограни­чениях могут возник­ать проб­лемы поиска лишь при очень малых значе­ниях градиен­тов функций ограничений и совпадении их направлений, так как это приводит к вырожденности матрицы системы (4).







Дата добавления: 2015-04-19; просмотров: 809. Нарушение авторских прав; Мы поможем в написании вашей работы!

Studopedia.info - Студопедия - 2014-2022 год . (0.017 сек.) русская версия | украинская версия