Лекция 3. Методы одномерной минимизации

Основные понятия

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

— числовая функция вещественной переменной. Под задачей одномерной минимизации на отрезке понимается поиск такого, что.

— наименьшее значение на ;

удовлетворяющее (0) называется точкой минимума на ;

— множество точек минимума на ;

может быть пустым, содержать конечное или бесконечное число точек.

Замечание. Задача поиска максимума сводится к задаче поиска минимума :

Задача одномерной минимизации состоит из двух частей:

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

поиска точки минимума на заданном отрезке при наличии информации о том, что на этом отрезке заведомо существует единственный минимум.

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

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

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

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

Затем, если, определяют следующие точки до тех пор, пока не будет получено В этом случае полученный интервал «накрывает» искомую точку минимума.

Если же, то выбирается противоположное направление. Точки строятся по правилу до тех пор, пока не будет получено.

Основной проблемой при применении описанной процедуры является правильный выбор величины s. Во многих прикладных задачах переменная изменяется в пределах многих степеней десятки (например, от 0,001 до 10 000). Тогда при неправильном выборе величины s минимизация может потребовать слишком больших затрат (при очень малом s — на «накрытие» точки минимума, а при большом — на последующее за «накрытием» сужение отрезка до требуемой точности).

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

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

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