4 ЧИСЛЕННЫЕ МЕТОДЫ ОПТИМИЗАЦИИ ФУНКЦИЙ НЕСКОЛЬКИХ ПЕРЕМЕННЫХ

4.1 МЕТОД ПОКООРДИНАТНОГО СПУСКА

В этом классе оптимизационных задач критерий зависит от нескольких переменных, образующих вектор Будем считать его размерность равной n. При n=2 речь идет об оптимизации функции двух переменных. Такую функцию можно изображать графически семейством ее линий уровня на плоскости чем удобно пользоваться для иллюстрации методов.

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

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

т. е. обращаются в нуль все n частные производные критерия. Значит, чтобы найти эту точку, достаточно решить эту систему уравнений с n неизвестными - компонентами вектора .

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

4.2 ГРАДИЕНТНЫЙ МЕТОД

НЕ нашли? Не то? Что вы ищете?

Выбираем любую точку - так называемое начальное приближение - и вычисляем - градиент функции в данной точке. Для этого можно вычислить значение функции точках: точке и в n точках, сдвинутых относительно нее на малый шаг d в направлении каждой из координатных осей пространства векторов y. Тогда приближенно

Напомним, что градиент задает в пространстве векторов y направление наибольшего возрастания функции, соответственно противоположное направление - будет направлением наибольшего ее убывания. Продвинемся в этом направлении, приближающем нас к точке минимума, на шаг h. Мы придем к точке

где

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

. (4.1)

Доказано, что, двигаясь с бесконечно малым шагом h, мы придем в точку . При этом траектория движения в каждой точке будет, очевидно, перпендикулярна проходящей через эту точку линии уровня f(y). Можно записать и уравнение этой траектории, перейдя в (4.1) к пределу ,

или

(4.2)

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

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

4.3 МЕТОД НАИСКОРЕЙШЕГО СПУСКА

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

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

Наглядная геометрическая иллюстрация метода возникает при оптимизации функции двух переменных. В этом случае ясно, что - точка касания прямой, идущей по антиградиенту из к некоторой линии уровня. Антиградиент же в точке будет перпендикулярен этой линии уровня, а следовательно, и предыдущему отрезку траектории. Таким образом, траектория достижения оптимума будет ломаной линией, отрезки которой попарно перпендикулярны. Этим можно воспользоваться, чтобы избежать вычисления градиента. Если первый отрезок будет параллелен одной из координатных осей, то тогда второй будет параллелен второй оси, третий - опять первой и т. д. Движение по траектории можно формально описать так. Выбирается любое начальное приближение , затем функция f(y) минимизируется лишь по переменной , а вторая переменная при этом имеет фиксированное значение . После того, как найдено оптимальное (на данном шаге алгоритма) значение , оно фиксируется и ищется минимум функции по переменной , затем снова минимум по первой переменной и т. д. Таким образом, метод наискорейшего спуска превращается в метод покоординатного спуска (при n>2 он, конечно, уже не будет совпадать с методом наискорейшего спуска).

4.4 МЕТОД НЬЮТОНА

Описанные выше методы использовали существование первых производных критерия. Поэтому их называют методами первого порядка. Если использовать существование вторых производных, можно увеличить скорость отыскания оптимума, так как при этом мы получаем дополнительную информацию о поведении оптимизируемой функции. Соответствующие методы называют методами второго порядка. Однако прежде чем переходить к их изложению, укажем, что уменьшение количества точек, проходимых на пути к точке оптимума, следует соизмерять с увеличением количества вычисляемых значений функции в окрестности каждой точки. Для того, чтобы перейти от одной точки к другой, в методах первого порядка нужно вычислить n+1 значение функции (для отыскания первых производных), а в методах второго порядка - 2n+1 (для отыскания вторых производных, например, по приближенной формуле

Дважды дифференцируемую выпуклую функцию в окрестности точки оптимума можно приближенно представить в виде

где - k - е приближение,

- градиент функции в точке ,

- матрица вторых производных функции в точке ,

- скалярное произведение векторов a и b.

Для этой аналитически заданной функции можно найти точку минимума, используя необходимые условия оптимальности:

Они приведут к уравнению (векторному)

откуда

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

4.5 ОБОБЩЕННЫЙ И МОДИФИЦИРОВАННЫЙ

МЕТОДЫ НЬЮТОНА

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

где h - шаг. Величину h можно выбрать их тех же соображений, что в градиентном методе или методе наискорейшего спуска.

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

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

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

4.6 МЕТОД СЕТЕЙ

Пусть f(y) - липшицевая функция, т. е.

где расстояние определяется так называемой Чебышевской метрикой

и область Y поиска минимума ограничена условиями

Без ограничения общности их можно заменить условиями

Разместим в Y равномерную сеть Y1 из точек (n – размерность вектора y, а m – число точек сети, определяющее расстояние по каждой координате между двумя соседними точками ). Сеть , очевидно, обладает тем свойством, что расстояние от любой точки Y до ближайшей к ней точки не превосходит . Соответственно, ввиду липшицевости, разность значений критерия в этих точках не превосходит . Вычислим

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

В каждой точке сети вычисляется значение оптимизируемой функции и подсчитывается

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

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

4.7 МЕТОД ШТРАФНЫХ ФУНКЦИЙ

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

и p неравенствам

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

Здесь - вектор с положительными компонентами

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

4.8 ЗАДАЧА О ПРОЕКТИРОВАНИИ АНГАРА

Рассмотрим задачу о проектировании ангара максимального объема, который можно изготовить из заданного количества материала. Ангар прямоугольный, открытый с одной стороны. Если обозначить его размеры через a, b, c, то объем ангара а расход материала

Имеем

или, переходя к безразмерным

Итак, задача свелась к оптимизации функции двух переменных. Решите ее всеми описанными выше методами

4.9 ЗАДАЧА О ПРОЕКТИРОВАНИИ КРОНШТЕЙНА

Рассмотрим задачу проектирования двухстержневого кронштейна минимального веса, о котором известно следующее:

- крепление стержней со стеной и между собой шарнирное, сечения стержней постоянны ( площади соответственно равны F1 и F2);

- задано расстояние L от стены до точки приложения нагрузки P, которая направлена под углом b к вертикали;

- задано допустимое напряжение R.

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

где l1 и l2 - длины стержней.

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

где N1 и N2 - усилия в стержнях, запишем целевую функцию в следующем виде:

Конструкция должна находиться в равновесии - это является требованием того, что она выдержит приложенную нагрузку. Запись условий равновесия (равенство нулю сумм проекций усилий и нагрузки на координатные оси) дает систему линейных уравнений относительно N1 и N2:

Из ее решения получаем выражения для N1 и N2 через известные параметры P и b и искомые a1 и a2:

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

4.10 ЗАДАЧА О ПРОЕКТИРОВАНИИ КАНАЛА

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

(). Требуется провести прямолинейный канал, соединяющий русла рек, так, чтобы его длина была минимальна.

Рассмотрим две точки с координатами x1, y1 и x2, y2, принадлежащие соответственно первой и второй кривой. Если рассматривать их как начало и конец канала, то его длина определится как

где , вычисляются в зависимости от из уравнений русел рек. Таким образом, L превращается в функцию двух переменных, , легко оптимизируемую численными методами.

4.11 ЗАДАЧА О ЖЕСТКОМ БРУСЕ

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

следует

или

Переходя к безразмерному , получим

например, при

Поэтому рассмотрим брус более сложной формы, где из внешнего прямоугольного контура допускается прямоугольный вырез с размерами b', h' (рис.4.1).

Рис. 4.1

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

Выражая b и b' из соответствующих уравнений

получим оптимизируемую функцию в виде

или, переходя к безразмерным

( последнее неравенство следует из ,т. е.

Постройте семейство линий уровня оптимизируемой функции (их уравнение легко получить):

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