Еднопараметрична (едномерна) оптимизация
Оптимизацията с един параметър (намиране на екстремумите на функции на една променлива) е независим и често срещан проблем. Освен това много по-трудна задача се свежда до нея - намиране на екстремума на функция от много променливи.
1. Метод на дихотомия
Нека разгледаме най-простия еднопараметричен метод на неограничена оптимизация - методът на дихотомия. Този метод е метод на директно търсене. В него при търсене на екстремума на целевата функция се използват само изчислените стойности на целевата функция.
Дадена е функция F (x). Трябва да се намери
, доставяне на минимум (или максимум)
функция F (x) на интервала [a, b] с дадена точност, т.е. да намеря
Нека напишем словесен алгоритъм на метода.
1) На всяка стъпка от процеса на търсене разделяме сегмента [a, b] наполовина, x = (a + b)/2 - координатата на средата на сегмента [a, b] .
2) Изчислете стойността на функцията F (x) в близост до изчислената точка x, т.е.
3) Сравнете F1 и F2 и изхвърлете едната половина на сегмента [a, b] (фиг. 1).
Когато търсите минимум:
Ако F1 R, както е показано на фиг. 3 и тези стойности ще бъдат фиксирани, ако са известни x 1, x 2 и x 3. Ако x 4 е в интервала (x 1; x 2), тогава:
Въведение в математическото програмиране
1. ако f (x 4) f (x 2), тогава новият интервал на несигурност ще бъде (x 4, x 3) дължина x 3 - x 4 .
Тъй като не е известно коя от тези ситуации ще се случи, изберете x 4 по такъв начин, че да минимизирате най-дългата от дължините x 3-x 4 и x 2 -x 1. Това може да се постигне чрез изравняване на дължините x 3 - x 4 и x 2 - x 1, т.е. чрез поставяне на x 4 вътре в интервала симетрично около точката x 2, която вече е вътре в интервала. Всяко друго положение на точката x 4 може да доведе до получения интервал по-голям от L. Поставяйки x 4 симетрично по отношение на x 2, ние в никакъв случай не рискуваме. Ако се окаже, че е възможно да се извърши още едно изчисление на функцията, тогава описаната процедура трябва да се приложи към интервала (x 1, x 2), в който вече има стойност на функцията, изчислена в точката x 4 или към интервала (x 4, x 3), в който вече има стойност на функцията, изчислена в точка x 2 .