Лекция 12. Задачи с линейными ограничениями


Содержание лекционного занятия:

· Этапы развития информационных систем

· Задачи с ограничениями-равенствами

· Задачи с ограничениями-неравенствами

§ Метод проекции градиента

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

Ограничения в задачах оптимизации являются отраже­нием реальных ситуаций, имеющих место в технических, экономических, социальных и др. сложных системах. Огра­ничены различные виды ресурсов, наличествуют связи, за­висимости между теми или иными переменными, описы­вающими реальные процессы и т.д.

Линейные ограничения — это частный случай ограни­чений. Но многие задачи сводятся к задачам оптимизации именно с линейной системой ограничений. Относительно допустимой области при наличии линейной системы ограничений справедливо все, что сказано об ОДР в раз­деле «Линейное программирование». Однако наличие нелинейной целевой функции приводит к тому, что тео­рия линейного программирования уже не применима. В частности, точкой минимума может быть и внутренняя точка допустимой области, а крайние точки (вершины многогранника) уже не играют той исключительной роли, как в линейных задачах. Минимум может достигаться во внутренней или в граничной точке, как в вершине, так и на граничных линейных многообразиях различной раз­мерности.

1.Задачи с ограничениями-равенствами

Если линейная система ограничений содержит только ограничения-равенства, то задача записывается в следую­щем виде.

Найти: min F(x) при Ах = b, где А — заданная матрица (m х n), b — заданный вектор, а х — неизвестный вектор с координатами хi (i = 1, 2, ...,n). Относительно F(x) сохра­ним все те же предположения гладкости, что и в задачах безусловной оптимизации. Число строк матрицы А меньше числа ее столбцов (m < n) и строки предполагаются линейно независимыми, так как их линейная зависимость означала бы либо несовместность системы (отсутствие решений), либо наличие лишних ограничений, которые можно отбро­сить, не изменив решение задачи. Рассматриваемая нами задача может быть сведена к за­даче безусловной минимизации с помощью множителей Лагранжа. При этом ограничения исчезают, но для каждого из них вводится неизвестный множитель Лагранжа λi (i = 1, 2,..., m) и целевая функция приобретает вид:

Здесь аi, i-ая строка матрицы А, так что ((aiT,x) – bi) — это фактически левая часть i-oro ограничения-равенства, ес­ли систему переписать в виде Ах - b = 0. Конечно, как и при линейной целевой функции, можно было бы попытаться ис­ключить m переменных из системы и подставить их выраже­ния через оставшиеся переменные в целевую функцию. При этом уменьшилась бы размерность задачи и исчезли бы ограничения. Но для этого требуется большой объем вычис­лений, и нелинейная целевая функция не становится проще.

Введение множителей Лагранжа увеличивает число пе­ременных (их стало n + m), но дает возможность применить любой из методов безусловной минимизации.

2. Задачи с ограничениями-неравенствами

Если в системе ограничений есть неравенства, то ее можно представить в виде Ах <= b. При этом число строк матрицы А может быть и меньше и больше числа ее столб­цов. Но мы будем рассматривать случай ограниченной ОДР, и поэтому для нас m > n.

В точке минимума х* некоторые ограничения могут вы­полняться как строгие неравенства (относительно них точка х* является внутренней); такие ограничения называются неактивными. А некоторые ограничения могут выполнять­ся как равенства (относительно них точка х* является гра­ничной); такие ограничения называются активными. Во внутренних точках ОДР все ограничения неактивны, а каж­дому граничному линейному многообразию соответствует свой набор активных ограничений. Вспомним, что в верши­нах многогранника в отсутствии вырожденности активно ровно n ограничений (но в каждой вершине это свой набор ограничений).

Существует много методов решения задач с линейными ограничениями. Они являются обобщением соответствую­щих методов безусловной оптимизации. В частности, как и для задач без ограничений, существуют методы первого и второго порядка. Мы рассмотрим только некоторые методы первого порядка.

2.1.Метод проекции градиента

Предположим, что нам известна некоторая внутренняя точка допустимой области х0. В этой точке нет активных ограничений и ничто не мешает нам выполнить шаг по ан­тиградиенту до точки минимума. Если эта точка опять ока­жется внутренней, то из нее снова можно сделать шаг по антиградиенту, как в методе наискорейшего спуска, или по сопряженному с антиградиентом направлению, как в методе сопряженных градиентов и т.д. Очевидно, что возможно два исхода такого процесса.

1. Мы остановимся вблизи точки безусловного миниму­ма целевой функции, так и не встретив границу. Это означает, что минимум достигается внутри допустимой облас­ти и все ограничения просто лишние.

На каком-то из шагов точка минимума в направлении пуска не удовлетворяет одному или нескольким ограниче­ниям, т.е. лежит за пределами ОДР. Это означает, что был сделан слишком большой шаг из последней внутренней точки и шаг нужно было делать не до точки минимума, а до встречи с границей

Встретив границу, мы не можем далее не считаться с ограничениями и будем действовать в рамках идей рас­смотренного выше метода возможных направлений. Теперь возможными являются направления, которые при достаточ­но малом шаге не выводят за пределы допустимой области. Среди них будем искать подходящие направления, т.е. такие направления, которые дают при соответствующем выборе шага уменьшение целевой функции. Мы уже знаем, что це­левая функция уменьшается в заданном направлении р, ес­ли оно составляет острый угол с антиградиентом -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 (вершине), в которой активны ограничения, не имеющие отношения к активному набору в точке минимума.

Таким образом, равенство нулю проекции градиента — это необходимое, но не достаточное условие минимума. Нужно еще, чтобы в активном наборе были представлены ограничения, активные в неизвестной нам точке минимума. Другими словами, необходимо выйти на нужную грань, не застревая в посторонних точках. Активный набор надо не только пополнять, но и исключать из него ограничения, мешающие дальнейшему движению к точке минимума. Ограничение может быть исключено из активного набо­ра, если проекция антиградиента на грань, определяемую оставшимися в активном наборе ограничениями, не нару­шает отброшенное ограничение.

Если проекция градиента равна нулю и ни одно ограни­чение нельзя исключить из активного набора, то минимум достигнут.

Это и есть необходимое и достаточное условие мини­мума.

Чтобы исключить ограничение из активного набора, не обязательно ждать, когда проекция станет равной нулю. Это можно сделать на любом шаге. Однако существует опас­ность «зигзагов», когда отброшенное ограничение снова попадает в активный набор, затем исключается и снова по­падает и т.д. При этом нарушается сходимость алгоритма. Для борьбы с «зигзагами» рекомендуется допускать повторное исключение ограничений только после заданного числа итераций.

В целом алгоритм метода проекции градиента состоит из следующих пунктов.

1. Построение допустимого начального приближения х0.

2. Вычисление антиградиента-g.

3. Формирование активного набора и построение проекции антиградиента р. Здесь возможно исключение одного из
ограничений и повторное вычисление проекции антиградиента.

4. Проверка условий окончания счета. Если они выполне­ны (проекция равна нулевому вектору и ни одно активное ограничение нельзя исключить), решение получено, иначе выполняем следующий пункт.

5. Поиск шага по направлению проекции антиградиента как минимального из шагов до границы и до точки ми­нимума.

6. Переход в новую точку. Далее к пункту 3, если антигра­диент в новой точке уже вычислялся, иначе к пункту 2.

В качестве начального приближения может использо­ваться любая точка допустимой области.

2.2. Метод приведенного градиента

Зададимся вопросом: что, если забыть, что базис не орто­нормальный, и при вычислении проекции антиградиента -g вместо р =-C(CTC)-1CTg брать просто p* = -CCTg? К чему приведет такая ошибка? Понятно, что р* вычислить просто. Не нужно даже вычислять произведение матриц ССТ, а про­сто сначала вычислить CTg, а потом умножить С на резуль­тат. Достаточно хранить только базисные векторы.

Но имеет ли смысл такое упрощение сложной формулы Для вычисления проекции р? При неортонормальном базисе это упрощение не будет давать проекцию. Это оче­видно. Тем не менее рассмотрим какой вектор р мы полу­чили бы.

Во-первых, это допустимое направление, так как вектор представлен в виде Су*, где у* =-CTg это вектор коэффи­циентов разложения р* по базисным векторам.

Во-вторых, и это самое интересное, р это подходящее направление, т.е. направление уменьшения целевой функ­ции, так как скалярное произведение р на антиградиент по­ложительно. Действительно,

Вектор CCTg, где g градиент, называется приведенный градиент, а р* можно было бы назвать приведенный анти­градиент.

Важно отметить, что при таком построении дополни­тельных базисных векторов имеется возможность исклю­чать не одно, а сразу несколько ограничений из активного набора. Если принять меры по предотвращению «зигза­гов», это открывает возможность быстрее выйти на нужную грань, т.е. сформировать нужный набор активных ограничений, ускорить сходимость и сократить время счета.

Вопросы для самоконтроля:

1.Метод наискорейшего подъема и спуска (для задач без ограничений)

2.Метод проекции градиента.

3.Метод условного градиента. Условные методы Ньютона.

Рекомендуемая литература:

1.Измаилов А.Ф., Солодов М.В. Численные методы оптимизации. М.: Физматлит, 2003.

2.Банди Б. Методы оптимизации. Вводный курс. М.: Радио и связь, 1988.