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

Для определенности будем считать, что решаем задачу отыскания минимума функции y = f(x) на интервале (a; b).
Пути решения:

1. Метод сканирования

Интервал поиска (a; b) разбивается на несколько равных участков, каждый из которых равен шагу поиска h(рис. 1).
Рис. 1. Метод локализации.

Далее последовательно определяются значения функции f(x) во всех точках разбиения аргумента и в точках a и b и запоминается наименьшее значение. Таким образом, минимум может быть найден с точностью до h.
Достоинства метода: простота, возможность нахождения глобального минимума.
Недостаток метода: большой объем вычислений.

1. Метод локализации

Алгоритм метода:

1. Интервал поиска минимума (a; b) разбивается на четыре равные части точками x1, x2, x3.
2. Вычисляются значения функции y = f(x) во всех точках разбиения и в точках x = a, x = b.
3. Полученные значения f(x) сравниваются между собой, и из них выбирается наименьшее.
4. Локализуется минимум, причем новый интервал поиска равен двум старым подинтервалам с наименьшим значением f(x) на их общей границе (на рис. 2 это соответствует интервалу (a, x2)).
5. Интервал, в котором локализован минимум, опять делится на четыре равных подынтервала ( на рис. 2 точками x4, x5) и снова вычисляются значения функции y = f(x) в точках деления. Они сравниваются между собой, находится наименьшее, локализуется минимум в меньшем интервале ( на рис. 2 в интервале (x4, x5)) и так далее до тех пор, пока минимум не будет локализован в интервале, размер которого соответствует заданной точности поиска.

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

1. Метод золотого сечения

Алгоритм метода золотого сечения для минимизации функции.

1. Вычисляется значение функции f(x1), где x1 = a + 0,382(b - a).
2. Вычисляется значение функции f(x2), где x2 = b - 0,382(b - a).
3. Определяется новый интервал (a, x2) или (x2, b), в котором локализован минимум.
4. Внутри полученного интервала находится новая точка (x1 в случае 1) или (x2в случае 2), отстоящая от его конца на расстоянии, составляющем 0,382 от его длины. В этой точке рассчитывается значение f(x). Затем вычисления повторяются,начиная с пункта 3, до тех пор, пока величина интервала неопределенности станет меньше или равна ε, где ε - заданное сколь угодно малое положительное число.