2. Лекции Практические и лабораторные занятия
жүктеу/скачать 0,77 Mb.
|
УМКД метод матер МО и Исл опер
| 2.1. Метод проекции градиента
Предположим, что нам известна некоторая внутренняя точка допустимой области х0. В этой точке нет активных ограничений и ничто не мешает нам выполнить шаг по антиградиенту до точки минимума. Если эта точка опять окажется внутренней, то из нее снова можно сделать шаг по антиградиенту, как в методе наискорейшего спуска, или по сопряженному с антиградиентом направлению, как в методе сопряженных градиентов и т.д. Очевидно, что возможно два исхода такого процесса. Мы остановимся вблизи точки безусловного минимума целевой функции, так и не встретив границу. Это означает, что минимум достигается внутри допустимой области и все ограничения просто лишние. На каком-то из шагов точка минимума в направлении пуска не удовлетворяет одному или нескольким ограничениям, т.е. лежит за пределами ОДР. Это означает, что был сделан слишком большой шаг из последней внутренней точки и шаг нужно было делать не до точки минимума, а до встречи с границей Встретив границу, мы не можем далее не считаться с ограничениями и будем действовать в рамках идей рассмотренного выше метода возможных направлений. Теперь возможными являются направления, которые при достаточно малом шаге не выводят за пределы допустимой области. Среди них будем искать подходящие направления, т.е. такие направления, которые дают при соответствующем выборе шага уменьшение целевой функции. Мы уже знаем, что целевая функция уменьшается в заданном направлении р, если оно составляет острый угол с антиградиентом -g, т.е. (g, р) < 0. Одно из подходящих направлений — это проекция антиградиента на ту грань (точнее, на соответствующее подпространство), которую мы встретили при движении из внутренней точки, если, конечно, при этом проекция не равна нулевому вектору, что будет рассмотрено отдельно. При любом наборе активных ограничений проекцию можно вычислить по формуле (2.5), подставив в нее вместо матрицы А матрицу, составленную из строк, соответствующих активным ограничениям, а вместо вектора f антиградиент -g. В итоге получим (1) где Р — матрица проектирования. Направление р является не только допустимым (мы идем по нему вдоль границы, не нарушая ограничений), но и подходящим, так как (-g, р) = (р + n, р) = (р, р) > 0. Таким образом, можно идти в направлении проекции антиградиента и уменьшить значение целевой функции при правильном выборе шага. При выборе шага мы не должны выйти за пределы допустимой области. Поэтому нужно прежде всего найти такой максимальный шаг (соответственно λmax). при котором все ограничения выполнены. Это соответствует минимальному шагу, при котором луч х1 + λр встречает границу. Для определения такого λ надо поочередно подставить х1 + λр вместо х во все неактивные ограничения, из каждого уравнения определить λ и из всех найденных положительных значений взять наименьшее. Например, i-oe ограничение (аiТ, х) <= biв точке х1 неактивно. Оно станет активно при (аiТ,х1 + λiр)=bi, т.е. при (2) Если получили λi< 0, то это означает, что в данном направлении мы соответствующую границу не встретим. Поэтому начинать надо со знаменателя и при (аiТ, p) <= 0 λi вычислять вообще не надо. Пройдя по всем неактивным ограничениям, найдем минимальное λ, при котором встречаем границу (рис. 25, точка х2). Это и будет максимальный шаг из точки х1. Но этот шаг может быть больше, чем до точки минимума в направлении р, и тогда его нельзя использовать. Другими словами, из двух значений шага — до границы и до точки минимума — надо взять наименьший. Сначала надо выяснить, действительно ли шаг до границы больше, чем для точки минимума. Для этого не надо определять шаг до точки минимума, так как мы рассматриваем выпуклую целевую функцию. Достаточно выяснить знак скалярного произведения вектора спуска р и нового антиградиента в точке х2. Если это скалярное произведение неотрицательно, то нужно перейти в точку х2, а если отрицательно, то нужно искать точку минимума целевой функции на отрезке [х1, х2]. Возникает в Точности та же задача одномерной оптимизации, что и при 1решении задач без ограничений. Здесь даже задача несколько проще, так как интервал поиска известен (по λ это 0 < λ < λmax). В новой точке вычисляем новый антиградиент и его проекцию и т.д. Этот процесс остановится, когда проекция градиента на очередную грань станет равна нулю. Но это еще не означает, что получено решение задачи, т.е. найден минимум функции при ограничениях в виде неравенств. На каждом шаге число активных ограничений могло только увеличиваться (при шаге до очередной границы) и мы могли попасть в вершину ОДР. В этом случае проекция антиградиента (на точку!) равна нулю, но минимум может быть совсем в другой точке и при другом наборе активных ограничений. На рис. 26 представлен случай, когда процесс останавливается в точке х1 (вершине), в которой активны ограничения, не имеющие отношения к активному набору в точке минимума. Таким образом, равенство нулю проекции градиента — это необходимое, но не достаточное условие минимума. Нужно еще, чтобы в активном наборе были представлены ограничения, активные в неизвестной нам точке минимума. Другими словами, необходимо выйти на нужную грань, не застревая в посторонних точках. Активный набор надо не только пополнять, но и исключать из него ограничения, мешающие дальнейшему движению к точке минимума. Ограничение может быть исключено из активного набора, если проекция антиградиента на грань, определяемую оставшимися в активном наборе ограничениями, не нарушает отброшенное ограничение. Если проекция градиента равна нулю и ни одно ограничение нельзя исключить из активного набора, то минимум достигнут. Это и есть необходимое и достаточное условие минимума. Чтобы исключить ограничение из активного набора, не обязательно ждать, когда проекция станет равной нулю. Это можно сделать на любом шаге. Однако существует опасность «зигзагов», когда отброшенное ограничение снова попадает в активный набор, затем исключается и снова попадает и т.д. При этом нарушается сходимость алгоритма. Для борьбы с «зигзагами» рекомендуется допускать повторное исключение ограничений только после заданного числа итераций. В целом алгоритм метода проекции градиента состоит из следующих пунктов. Построение допустимого начального приближения х0. Вычисление антиградиента-g. Формирование активного набора и построение проекции антиградиента р. Здесь возможно исключение одного из ограничений и повторное вычисление проекции антиградиента. Проверка условий окончания счета. Если они выполнены (проекция равна нулевому вектору и ни одно активное ограничение нельзя исключить), решение получено, иначе выполняем следующий пункт. Поиск шага по направлению проекции антиградиента как минимального из шагов до границы и до точки минимума. Переход в новую точку. Далее к пункту 3, если антиградиент в новой точке уже вычислялся, иначе к пункту 2. В качестве начального приближения может использоваться любая точка допустимой области. жүктеу/скачать 0,77 Mb. Достарыңызбен бөлісу:
|