Методы одномерной оптимизации

Аналитические методы решения.

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

Стационарные точки непрерывной функции.

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

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

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

Теорема 1(необходимое и достаточное условие существования экстремума функций одной переменной).

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

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

Понятие о численных методах оптимизации.

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

Любой численный метод имеет два этапа:

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

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

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

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

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

нулевого порядка — в них используется информация только о значениях минимизируемой функции;

первого порядка — использующие информацию также и о значениях первых производных;

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

и так далее.

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

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

В пассивных алгоритмах все точки выбираются одновременно до начала вычислений.

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

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

при этом.

На практике обычно используются наиболее простые виды зависимости, например:

то есть выбор точки очередного вычисления зависит лишь от точки предыдущего вычисления и полученного результата или.

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

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

заданием точки ;

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

условием остановки.

Правила выбора и чисел могут предусматривать вычисления характеристик не только в точках, но и в других точках, отличных от. Именно поэтому в формулах (3 и (4) употреблены различные индексы.

Вектор определяет направлениего шага метода минимизации, а коэффициент — длину этого шага.

Обычно название метода минимизации определяется способом выбора, а его различные варианты связываются с разными способами выбора .

Наряду с термином шаг метода мы будем пользоваться также термином итерация метода.

Среди методов минимизации можно условно выделить:

конечношаговые методы;

бесконечношаговые методы.

Конечношаговыми (или конечными) называются методы, гарантирующие отыскание решения задачи за конечное число шагов.

Для бесконечно шаговых методов достижение решения гарантируется лишь в пределе.

Сходимость методов оптимизации.

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

Метод сходится если, где — решение задачи .

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

Пример:

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

В случае, когда точка минимума не единственна, под сходимостью метода понимается сходимость к множеству точек минимума функции .

Пусть .

Говорят, что:

• 1) последовательность сходится к точке линейно (с линейной скоростью, со скоростью геометрической прогрессии), если существуют такие константы и, что при (5)
• 2) последовательность сходится к точке сверхлинейно (со сверхлинейной скоростью), если:

при (6).

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

при.

Иногда, сохраняя ту же терминологию, неравенства (5) — заменяют соответственно на неравенства.

при.

при ,.

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

Для невыпуклых задач численные методы оптимизации позволяют отыскивать лишь локальные решения.

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

На практике часто используют следующие условия остановки:

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