Градиентные методы

Рассмотрим функцию n переменных f(x₁,x₂,...,x_n)=f(X).

Градиент – вектор компонентов , обозначаемый обычно .

В методе покоординатного спуска осуществляется поиск минимума по фиксированным направлениям. Кажется разумным попытаться модифицировать этот метод таким образом, чтобы на каждом шаге поиск точки оптимума производился вдоль «наилучшего» направления. При этом известно, что направление градиента является направлением наискорейшего возрастания функции. Следовательно, противоположное направление является направлением наискорейшего убывания функции (направление проекции градиента в любой точке перпендикулярно линии постоянного уровня целевой функции) (рис. 3.9).

Если задана начальная точка b₁, то переход в точку b₂ производится по направлению противоположному направлению градиента (в точке b₁), которое можно вычислить аналитически или численно. Задача состоит в определении частных производных и формировании вектора смещений по осям D(X)=Dx₁, Dx₂,..., Dx_n пропорционально их величине, b₂=b₁+D(X). Повторяя данную процедуру, можно придти в точку минимума по кратчайшему пути (рис. 3.10).

Рис. 3.9. Проекции градиента и антиградиента

Рис. 3.10. Градиентный метод

3.4. Оптимизация с ограничениями

Общая задача оптимизации с ограничениями является очень сложной и до сих пор не имеет общего решения (решена для частных случаев).

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

Рис 3.11. Выпуклая и невыпуклая допустимые области

Для выпуклых (вогнутых) целевых функций существует единственное оптимальное решение. При выпуклой допустимой области изменения управляемых переменных единственность оптимального решения сохраняется и его можно найти.

При невыпуклой допустимой области даже выпуклая целевая функция, имеющая одну точку минимума при отсутствии ограничений, может стать многоэкстремальной (точки А и В на рис. 3.11.б), что существенно осложняет решение оптимизационной задачи.

Метод штрафных функций. Основная идея метода штрафных функций состоит в преобразовании задачи минимизации функции F(X) с соответствующими ограничениями, наложенными на X, в задачу поиска минимума без ограничений функции F(X)+P(X).

Функция P(Х) является штрафной. Необходимо, чтобы при нарушении ограничений она «штрафовала» функцию F(X), то есть увеличивала ее значение. В этом случае минимум F(X) +P(X)будет находиться внутри области ограничений.

Функцию P(Х) можно представить различным образом, например:

,

где r - положительное число, - нарушение ограничения по i -й переменной.

Если X принимает только допустимые значения, для которых P(X)=0, то функция Z принимает значения, равные соответствующим значениям F (истиной целевой функции данной задачи). Но если X принимает значения, которые не являются допустимыми, значения функции Z и, следовательно, значения функции F становятся очень велики.

Влияние функции P(X) состоит в создании «гребня с крутым краем» вдоль каждой границы области ограничений (рис. 3.12). Если поиск минимума функции Z без ограничений начинается из допустимой точки, то этот минимум будет достигаться внутри допустимой области для задачи с ограничениями. Таким образом, можно сделать точку минимума функции Z без ограничений точкой минимума функции F с ограничениями.

Рис. 3.12. Влияние «штрафной» функции на поиск минимума функции с ограничениями. Точка B - минимум функции F(x_i) без ограничений, A - то же, с ограничениями

Первоначально считалось, что метод штрафных функций позволяет решать все вычислительные проблемы, однако при его практической реализации столкнулись с серьезными трудностями: медленная сходимость, ненадежность и грубость результатов.

При этом для ряда задач оптимизации в силу характерных особенностей целевой функции и ограничений можно реализовать поиск оптимального решения и без выхода за границу допускаемой области (применения штрафных функций не требуется).

Для задач такого типа (очень распространенных) были разработаны специальные методы оптимизации.

3.5. Линейное программирование

Наиболее известной задачей математического программирования является задача линейного программирования[5], в которой целевая функция и все ограничения линейны:

Рис. 3.13. Оптимальное решение в линейном программировании

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

Точку минимума (максимума) в задаче линейного программирования (планирования) нужно искать среди вершин допустимой области. Возникает идея перебрать по очереди все вершины, в каждой из них вычислить значение целевой функции и выбрать вершину, в которой оно минимально (максимально).

Количество таких вершин равно количеству вариантов выбора n ограничений из общего числа m ограничений: .

Рис. 3.14. Вершины допускаемой области

Вершины A, B, C, D, E – допустимые, F, G – не допустимые (рис. 3.14).

При m = 10, n = 5 это число равно 252, при m = 20, n = 10 это число равно 184756. При m = 50, n = 25 это число примерно равно 10¹⁴.

Не все вершины будут допустимыми (рис. 3.14) [6].

При оптимизации параметров сети автомобильных дорог Нидерландов было выделено 2500 звеньев (неизвестные векторы параметров каждого звена подлежащие оптимизации). На величину неизвестных было наложено 700000 ограничений. На первом этапе расчетов использовался метод линейного программирования [7].

Для решения задачи применяется симплекс-метод (Дж. Б. Данциг, 1949), который обеспечивает нахождение оптимального решения за конечное число шагов (если оно существует).

Данциг доказал, что множество решений системы линейных неравенств – это n-мерный многогранник. Отсюда и название метода – simplex (латынь) – многогранник.

Основная идея симплекс-метода [5]:

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

Все эти задачи: нахождение первой допустимой вершины (начальное приближение), переход в вершину с меньшим (большим) значением целевой функции (если такой вершины нет – задача решена) решены в симплес-методе.

Все системы компьютерной математики имеют средства для решения задачи линейного программирования.

Пример:Цех малого предприятия должен изготовить 100 изделий трех типов. Каждого изделия нужно сделать не менее 20 штук. На изделия уходит соответственно 4, 3.4 и 2 кг металла при общем запасе 340 кг, а также по 4.75, 11 и 2 кг пластмассы при ее общем запасе 700 кг. Сколько изделий каждого типа x1, x2 и x3 нужно изготовить для максимального объема выпуска в денежном выражении, если цена изделий составляет по калькуляции 4, 3 и 2 рубля?

Задача сводится к вычислению максимума функции [3]. Решение задачи в системе MathCad приведено на рис. 3.15. Математическое решение очень логично – самых ресурсоемких изделий 2 типа выпускается минимальное число, самых дорогих изделий 1 типа – максимальное, остаток ресурсов расходуется на изготовление дешевых изделий 3 типа.

Рис. 3.15. Пример решения задачи линейного программирования в системе MathCad

Целочисленное линейное программирование [5]

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

При попытке просто округлить полученное решение можно получить решение далекое от оптимума и/или не удовлетворяющее заданным ограничениям.

При округлении координат точки А (рис. 3.16), которая является решением задачи без учета требований целочисленности, получается недопустимое решение. Оптимальной является точка В, а не ближайшие к точке А узлы сетки с целочисленными координатами.

Рис. 3.16. Округление решений в целочисленном программировании

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

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

3.6. Нелинейное программирование

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

В отличие от задачи линейного программирования, где оптимум всегда лежит на границе допустимой области в одной из ее вершин, в задаче квадратичного программирования такая определенность отсутствует и ее нельзя решить перебором определенных и заранее известных комбинаций значений управляемых переменных (рис. 3.16).

Рис. 3.16. Задача нелинейного программирования

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

Для решения задачи могут использоваться различные методы.

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

При этом известно, что любое направление, составляющее острый угол с направлением наискорейшего спуска, является улучшающим. Практически это сводится к проекции вариации управляемых переменных на границу допустимой области (рис.3.17).

Рис. 3.17. Минимальная поправка

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

Задача автоматизированного проектирования продольного профиля железных и автомобильных дорог с минимизацией профильного объема земляных работ обычно ставится как задача нелинейного (квадратичного) программирования и реализована практически во всех известных системах автоматизированного проектирования этих объектов.

3.7. Многошаговые процессы на графах [8]

В математике существует раздел теория графов, особенность которого – геометрический подход к изучению объектов и формализованных задач. Основное понятие теории – граф – задается множеством вершин (точек) и множеством ребер (связей), соединяющих вершины графа. Когда ребро ориентировано (имеет направление) оно называется дугой (рис. 3.18).

Рис. 3.18. Граф

Существует ряд задач, решение которых можно реализовать при помощи теории графов.

В качестве вершин графа могут выступать реальные объекты: города, железнодорожные станции, предприятия, склады и т.п. Ребра графа в этом случае показывают возможные связи между объектами: существующие железные и автомобильные дороги, торговые связи между предприятиями, складами и т.п.

Вершинами графа могут быть различные состояния одной и той же системы, например, техническое состояние железнодорожной линии (однопутная, однопутная с двухпутными вставками, двухпутная). Ребра – возможные переходы между состояниями: строительство двухпутных вставок или вторых путей.

В зависимости от вида критерия, использующегося при решении задачи, ребра графа могут соответствовать некоторые характеристики: расстояние между объектами, время движения или длительность процесса, стоимость перехода из одного состояния в другое, надежность работы системы, количество потребной энергии и др. Формально ребру графа присваивается некоторая длина, соответствующая этой характеристике.

Решение большинства задач с помощью графа сводится к нахождению оптимального пути. Под оптимальностью может пониматься соответствие пути определенным требованиям. Это может быть кратчайший путь между двумя вершинами графа, критический (самый длинный) путь или путь, обязательно включающий проход через определенные вершины графа.

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

Одна из наиболее важных задач современной системы планирования и управления состоит в определении критических путей, то есть последовательности отдельных работ, ограничивающих время выполнения работы в целом по некоторому фактору (критерию). Задача отыскания критического пути сводится к выбору пути наибольшей длины. Эта задача эквивалентна задаче о кратчайшем пути при замене критерия оптимальности с минимума на максимум.

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

К отдельному классу задач относится «задача о коммивояжере», в которой требуется определить оптимальный маршрут движения «коммивояжера» (бродячего торговца), цель которого состоит в том, чтобы посетить все нужные ему объекты (вершины графа) за кратчайший срок с наименьшими затратами. Если в графе n вершин и все вершины попарно соединены между собой ребрами (такой граф называется полным), то число путей, проходящих через все вершины, равно

Это единственная задача из рассмотренных, в которой все эффективные (сокращающие полный перебор) методы решения задачи коммивояжёра – методы эвристические. В эвристических методах находится не самый эффективный маршрут, а приближённое решение[6].

3.8. Динамическое программирование

Возникновение динамического программирования связано с исследованием многошаговых процессов, возникающих в теории создания запасов (Р.Беллман, начало 50-х годов). Первоначально метод предлагался для решения сравнительно узкого класса задач, возникающих в процессах, которые развиваются во времени. Отсюда и название: динамическое программирование.

Метод не является универсальным в отличие, например, от симплекс-метода Данцига для решения задач линейного программирования. Его реализация для каждого многошагового процесса принятия решений, как правило, требует разработки нового алгоритма [5].

Рассмотрим некоторую операцию, состоящую из m шагов (этапов). Пусть эффективность операции характеризуется некоторым показателем W (критерием). Данный показатель складывается из показателей на отдельных шагах w_i:

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

Любую многошаговую задачу можно решать по-разному: либо искать сразу все решения на всех шагах, либо строить оптимальное управление шаг за шагом, на каждом этапе расчета оптимизируя только один шаг. Оптимизация одного шага, как правило, проще оптимизации всего процесса: легче много раз решить простую задачу, чем один раз сложную.

С первого взгляда задача может показаться тривиальной – если трудно оптимизировать операцию в целом, нужно разбить ее на шаги. Каждый такой шаг будет отдельной операцией, оптимизировать которую не трудно.

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

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

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

Однако из этого правила есть одно исключение. Последний шаг не имеет продолжения. Поэтому процесс динамического программирования разворачивается от конца к началу – прежде всего, планируется последний m-й шаг.

Планируя последний шаг, нужно сделать различные предположения о том, как кончился предпоследний (m-1)-й шаг, и для каждого из этих предположений найти условное оптимальное управление на m-м шаге (управление, не зависящее от результата предшествующих шагов, тех которые еще не сделаны, "предыстории"). Такая процедура нахождения условного оптимального управления должна быть проделана последовательно для каждого шага от конца к началу операции.

После этого, двигаясь от начала к концу операции, можно выбрать из условных оптимальных управлений действительно оптимальное. Таким образом, в процессе оптимизации управления методом динамического программирования многошаговый процесс выполняется дважды: первый раз от конца к началу, в результате чего находятся условные оптимальные управления; второй раз – от начала к концу, когда нужно из условных оптимальных управлений выделить, безусловно оптимальное.

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