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

3.  Если f(x1) > f(x2), то  иначе .

4.  Вычислить f(x3);

5.  Найти .

6.  Проверка на окончание поиска. Если условия выполняются, то поиск окончен, иначе перейти к п. 7.

7.  Принять за x1 наилучшую из точек  и Xmin. Перейти к п. 2.

Метод Ньютона-Рафсона

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

Пусть f(x) - непрерывная и дважды дифференцируемая функция.

Требуется найти корень уравнения f′(x)=0 .

Зададим x1 – начальную точку поиска. Построим линейную аппроксимацию функции f′(x) в точке x1. Для этого разложим f′(x) в ряд Тейлора в точке x1 и отбросим все члены второго порядка и выше.

Сходимость метода зависит от выбора начальной точки и вида функции.

Условие выхода не сходится

Метод средней точки

Определяются две точки L, R  в которых производные имеют разные знаки f′(L) <0, f′(R) >0. Искомый оптимум находится между ними. Делим интервал пополам:

 .

Если f′(Z) >0 то исключаем (Z, R). Если f′(Z) <0 то исключаем (L, Z).

  Алгоритм поиска минимума на (a, b).

1. 

2.  Вычислить Z; f′(Z) 

3.  Если , то закончить поиск.

4.  Исключить соответствующий интервал. Перейти к п. 2.

Метод секущих

Метод ориентирован на нахождение решения уравнения f′(x) =0 на заданном  интервале (a, b). Метод похож на метод Ньютона, но строится не касательная, а секущая.

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

Метод с использованием кубической аппроксимации

Функция f(x) апроксимируется полиномом третьего порядка. Находится стационарная точка  этого полинома. Эта точка заключается в интервал (x1, x2) такой, что производные в x1, x2  имеют разные знаки.

Построим полином

 находятся так, чтобы значения функции и значения производной были: q(x) и q′(x) , и совпадали бы с f(x) и f′(x) соответственно в точках x1 и x2.

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

Для значений M, заключённых в интервале от 0 до 1 формула для  гарантирует, что  всегда будет между x1 и x2.

Метод с использованием кубической аппроксимации

Алгоритм

1. Задать x0 – начальное приближение, ∆ -шаг поиска и ε1, ε2 погрешности по функции и аргументу.

2. Вычислить f′ в x0. Если f′( x0)<0, то ∆>0 и , иначе ∆<0 и какая-нибудь своя формула для вычисления .

3. Вычислять  до тех пор, пока не получим xm в которой .

Вычислить  .

4.  Вычислить  (см. выше).

5.  Если , то перейти к п. 6 иначе  и так вычислять, пока не выполнится условие .

6. Проверка на окончание  и  . Если выполняется, то конец вычислений, иначе если ,то x2=  или, если ,то x1=  и перейти к п. 4.

Сравнение методов

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

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

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

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

Если функция квадратичная или близка к таковой, то следует использовать метод Пауэлла

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

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

6. Методы многомерной безусловной оптимизации

6.1. Введение в  методы многомерной оптимизации

6.1.1. Основные понятия и определения

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

На первый взгляд может показаться, что отличие между методами многомерного и одномерного поиска заключается лишь в том, что первые требуют большего объема вычислений, и, что в принципе методы, которые пригодны для функций одной переменной, можно применять и для функций многих переменных. Однако это не так, поскольку многомерное пространство качественно отличается от одномерного. Прежде всего с увеличением числа измерений уменьшается вероятность унимодальности целевой функции. Кроме того, множество элементов, которые образовывают многомерное пространство, значительно мощнее множества элементов одномерного пространства. Объем вычислений, которые необходимы для сужения интервала неопределенности в многомерном пространстве, является степеневой функцией, показатель которой равен размерности пространства. Так, если в случае одномерного пространства для достижения f=0,1 требуется вычислить 19 значений целевой функции, то в случае двухмерного пространства это число составляет 361, трехмерного – 6859, четырехмерного – 130321, а пятимерного – 2476099! Поскольку при выборе оптимальной конструкции нередко нужно иметь дело с пятью и больше переменными, серьезность трудностей, обусловленных многомерностью, становится очевидной. Вначале рассмотрим вопрос анализа (в статике) с использованием положения линейной алгебры и дифференционного вычисления, а также условий, которые (в достаточно общих возможных случаях) позволяют идентифицировать точки оптимума. Такие условия используют для проверки избранных точек и дают возможность выяснить, есть ли эти точки точками минимума или седловыми точками. При этом задача выбора указанных точек остается за пределами этого анализа; основное внимание отдается решению вопроса о том, отвечают ли исследуемые точки решению многомерной задачи безусловной оптимизации, в которой необходимо минимизировать f(x) , xÎRN, (1) когда ограничения отсутствуют на х , где х - вектор управляемых переменных размерности N, f — скалярная целевая функция. Обычно допускается, что хі (для всех значений і= 1,2,3,...,N) могут принимать любые значения, хотя иногда в практических целях область значений х выбирается в виде дискретного множества. Кроме того, часто удобно допускать, что функция f и ее производные существуют и непрерывны везде, хотя мы знаем, что оптимумы могут достигаться в точках разрыва f или ее градиента.