Основы теории оптимизации (стр. 11 )

  Эвристический метод.

, где k=0,1,2,… 

x0 - произвольно выбранная точка

 ∆ - шаг, определяется путём сравнения значений f(x0) ,

,

Если  то x0 правее, чем x* и ∆>0.

Если  то x0 левее, чем x* и ∆<0.

Если  то x* лежит между точками  и  и поиск завершён.

Если при поиске минимума оказывается, что  , то функция не унимодальна.

  Этап  установления интервала

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

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

Длина остающегося после исключения интервала всегда равна τ. Пусть исключается правый интервал.

Для того, чтобы симметрия образца сохранилась расстояние 1- τ должно составлять τ часть от длинны интервала, который, в свою очередь составляет τ. 1-τ =τ2 (Золотое сечение можно вычислить как )

Если исходный интервал имеет единичную длину, длина интервала после N вычислений равна τ N-1.

Если правая и левая границы интервала определены как xR и xL соответственно, то координаты всех последующих пробных точек вычисляются по формулам: x= xR- τ N или x= xL - τ N в зависимости от того, какой интервал был отброшен. N – количество вычислений.

2.2. Одномерная оптимизация

2.2.1. Mинимизация функций одной переменной

Рассмотрим общие вопросы постановки и методов решения одномерных задач оптимизации. С математической точки зрения такую задачу можно сформулировать следующим образом.
Найти наименьшее (или наибольшее) значение целевой функции f(х), заданной на множестве X. Определить значение переменной х Î X, при котором она принимает свое экстремальное значение.
В математическом анализе при изучении свойств функций, непрерывных на отрезке, доказывается следующая теорема.
Теорема Вейерштрасса. Всякая функция f(х), непрерывная на отрезке [а, b], принимает на этом отрезке свое наименьшее и наибольшее значения, т. е. на отрезке [а, b] существуют такие точки х1, x2, что для любого х Î [а, b]выполняются неравенства

f(х1)<=f(x)<=f( x2).  (1)

Не исключается, в частности, возможность того, что наименьшее или наибольшее значение достигается сразу в нескольких точках. Вы легко можете убедиться в этом, рассмотрев в качестве примера функцию y=sin х на отрезке [0, 4p]. Она достигает своего наименьшего значения, равного - 1, сразу в двух точках: х=3p/2, х=7p/2. Наибольшее значение, равное 1, достигается тоже в двух точках: х=p/2, х=5p/2.
Теорема Вейерштрасса играет в данном случае роль теоремы существования: согласно этой теореме задача оптимизации, в которой целевая функция f(х) задана и непрерывна на отрезке, всегда имеет решение.
Теперь нам предстоит обсудить методы решения задач оптимизации. Рассмотрим наиболее простой класс задач. При их исследовании мы будем предполагать, что  целевая функция f(х) дифференцируема на отрезке [a, b] и имеется возможность найти явное выражение для ее производной f'(х).
Точки, в которых производная обращается в нуль, называются критическими или стационарными точками функции f(х). Если интерпретировать производную как скорость изменения функции, то в критических точках эта скорость равна нулю, изменение функции на мгновение "останавливается". Функция f(х) может достигать своего наименьшего (наибольшего) значения либо в одной из двух граничных точек отрезка [а, b], либо в какой-нибудь его внутренней точке. В последнем случае такая точка обязательно должна быть критической, это необходимое условие экстремума. Учитывая изложенное, можем сформулировать следующее правило решения задачи оптимизации для рассматриваемого класса функций.
Для того чтобы определить наименьшее и наибольшее значения дифференцируемой функции f (х) на отрезке [а, b], нужно найти все ее критические точки на данном отрезке, присоединить к ним граничные точки а и b, и во всех этих точках сравнить значения функции. Наименьшее и наибольшее из них дадут наименьшее и наибольшее значения функции для всего отрезка. 
Поскольку граничные точки а и b искать не нужно, то с технической точки зрения все сводится к определению критических точек, которые являются корнями уравнения 

    f ' (x)=0.  (2)

Для иллюстрации изложенного правила решения задачи оптимизации  рассмотрим на отрезке [-2, 3] функцию 

  f(x)= 3x4- 4x3- 12х2+2.  (3)

Вычислим ее производную: f'(x)=12x3-12x2-24x.Таким образом, уравнение (2) для определения критических точек в данном  случае принимает вид 

    x3-x2-2x=0.    (4)

Все корни этого уравнения: х1= -1, х2=0, х3=2 принадлежат исхному отрезку. Добавляя к ним граничные точки: а=-2, b=3, вычислим соответствующие значения функции (3): 

f(-2) = 34, f(-1) = -3, f(0) = 2, f(2) = -30, f(3)= 29.

Из сравнения этих чисел следует, что наименьшее значение функции f(х) достигается в одной из критических точек x=2, а наибольшее - в граничной точке х= -2, причем 

fmin=f( 2)= -30,

fmax=f(-2)= 34.

График функции (3), иллюстрирующий проведенное исследование, показан на рис.1.

Рис. 1. График функции  f(x)= 3x4- 4x3- 12х2+2.

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

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

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

Из математического анализа известны следующие условия локального экстремума функции f(x), дифференцируемой достаточное число раз.

1. Если функция f(x) дифференцируема в точке и достигает в этой точке локального экстремума, то f '() = 0 (необходимое условие экстремума).

2. Пусть функция f(x) n раз дифференцируема в точке f и в этой точке все производные f(x) до п-1-го порядка включительно равны нулю, а f (п)(х) ≠0. Тогда, если п - нечетно, то не является точкой локального экстремума функции f(x). Если же п - четное число, то:

a) при f (п) ()>0 - точка локального минимума f(x);

b) при f(п)()<0 - точка локального максимума f(x) (достаточное условие экстремума).

Перечисленные условия позволяют предложить следующий путь решения задачи минимизации: