Сложность задач оптимизации

     (2.3)

Аналогично,

                (2.4)

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

На  втором шаге отрезок также делится в соотношении золотого сечения. При этом одной из точек деления будет точка . Покажем это:

Последнее равенство следует из соотношения

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

По аналогии с соотношениями (2.3), (2.4) можно записать координаты точек деления и отрезка на k-м шаге оптимизация :

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

           (2.5)

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

                         (2.6)

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

2.4 Метод Ньютона.

 

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

                     (2.7)

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

Пусть - решение уравнения (2.7), а некоторое начальное

приближение к  . Применим для решения (2.7) метод Ньютона решения уравнения , которое эквивалентно уравнению (2.7) при . Для этого в формулу для -го приближения метода Ньютона

подставим вместо производную и получим тем самым формулу для  -го приближения к решению уравнения (2.7):

             (2.8)

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

или близости значений целевой функции  на этих приближениях

.

Достаточное условие сходимости метода Ньютона (2.8) можно получить. А именно, справедлива следующая теорема.

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

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

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

(2.9)

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

 что совпадает с (2.8). Разложение (2.9) в окрестности точки , на котором график функции заменяется параболой графиком функции .

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

3. Многомерные задачи оптимизации

3.1 Минимум функции нескольких переменных.

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

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

             (3.1)

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

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

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

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

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

3.2 Метод покоординатного спуска.

 

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

                             (3.2)

  Зафиксируем теперь все координаты кроме , и рассмотрим функцию при переменной . Снова осуществляем спуск теперь по координате , в сторону убывания функции от точки до точки . Значение можно найти

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

На любом k-том шаге этот процесс можно прервать. И значение функции в точке k принимается в качестве наименьшего значения целевой функции в рассматриваемой области.

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

3.3 Метод градиентного спуска.

 

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

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

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

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

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

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

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

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

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

4. Задачи с ограничениями

4.1 Линейное Программирование.

 

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

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

1. удовлетворяют системе линейных уравнений

                 (4.1)

      2) являются неотрицательными, т. е.

              (4.2)

      3) обеспечивают наименьшее значение линейной целевой функции

          (4.3)

Всякое решение системы уравнений (4.1), удовлетворяющее системе неравенств (4.2), называется допустимым решением. Допустимое решение, которое минимизирует целевую функцию (4.3), называется оптимальным решением.

4.2 Геометрический метод.

 

Областью решения линейного  неравенства с двумя переменными

                  (4.4)

является полуплоскость. Для того чтобы определить, какая из двух полуплоскостей соответствует этому неравенству, нужно привести его к виду или . Тогда искомая полуплоскость в первом случае расположена выше прямой , во втором - ниже нее. Если , то неравенство (4.4) имеет вид ; в этом случае получим либо - правую полуплоскость, либо - левую полуплоскость.