Македонов Р.А.

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

Задача одномерной оптимизации

Рассмотрим задачу поиска минимума одномерной функции f( ), определенной на интервале .

Постановка задачи

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

Методы решения

а) Классический метод.

Достоинства: простота.

Недостатки: 1) имеет ограниченное применение при решении практических задач (практически не имеет применения!); 2) сложность решения уравнения - производная может не существовать, описание функции нельзя получить; 3) некоторые уравнения решаются только графически – решение – график (рисунок).

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

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

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

Условия применения – функция должна быть унимодальной. Унимодальной называется функция, имеющая на заданном отрезке [a,b] один максимум или минимум.

Основные представители: метод перебора, метод дихотомии (деления отрезка пополам), метод золотого сечения

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

Разобьем отрезок [a,b] на n равных частей точками деления:

xi=a+i(b-a)/n, i=0,...n

Вычислив значения F(x) в точках xi, путем сравнения найдем точку xm, где m - это число от 0 до n, такую, что

F(xm) = min F(xi) для всех i от 0 до n.

Погрешность определения точки минимума xm функции F(x) методом перебора не превосходит величены Eps=(b-a)/n.

Деление пополам.

Рассмотрим функцию F, которую требуется минимизировать на интервале [a1, b1]. Предположим, что F строго квазивыпукла. Очевидно, что наименьшее число вычислений значений функции , которые необходимы для сокращения интервала неопределенности, равно двум. Одной из стратегий является выбор этих двух точек симметрично на расстоянии eps>0 от середины интервала. Здесь число eps настолько мало, чтобы длина нового интервала неопределенности eps+(b1-a1)/2 являлась достаточно близкой к теоретическому значению (b1-a1)/2, и в то же время такое, чтобы значение функции в этих двух точках были различимы.

Алгоритм дихотомического поиска

Алгоритм дихотомического метода для минимизации строго квазивыпуклой фунции на интервале [a1,b1].

Начальный этап. Выбрать константу различимости 2еps > 0 и допустимую конечную длину интервала неопределенности l > 0. Пусть [a1,b1] - начальный интервал неопределенности. Положить k=1 и перейти к основному этапу.

Основной этап.

Шаг 1. Если bk-ak < l, то остановиться; точка минимума принадлежит интервалу [ak,bk]. В противном случае вычислить pk=(ak+bk)/2-eps qk=(ak+bk)/2+eps и перейти к шагу 2.

Шаг2. Если F(pk) < F(qk), положить a[k+1]=ak и b[k+1]=qk. В противном случае положить a[k+1]=pk и b[k+1]=bk. Заменить k на k+1 и перейти к шагу 1.