Алгоритм определения минимума методом аппроксимирующего программирования.

1)Задаются Вычисляется . Полагается .

2)Осуществляется линеаризация исходной задачи в окрестности точки . Получаем задачу линейного программирования.

3)Находим решение задачи линейного программирования.

4)Полагается

5)Вычисляется

6)Проверяется условие выбора

Если одно из трех условий не выполнилось, то остальные можно и не проверять. Если все три условия выполняются, то осуществляется переход к пункту 7. если нет, то и переход к пункту 5.

7)Проверяются условия окончания вычислений для исходной задачи.

Если условия выполняются, то решения завершаются. Если нет, то полагается переход к пункту 2.

Ответ: ,.

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

Для этого в пунктах алгоритма:

1)

4)вместо использовать .

2 способ определения .

Решаем задачу линейного программирования. Проверяем условия:

Если условия не выполняются, то вычисляется покомпонентно.

(4.5)

Выбирается так, чтобы выполнялись условия (4.2)

– начальное значение

– коэффициент дробления шага.

1)

2)

Недостаток: для существенно нелинейных функций этот метод сходится медленно, а может и вообще не сходится.

Для устранения этого недостатка может использоваться следующая модификация МАПа (сходимость гарантируется)

Добавляем ограничение:

, где

– некоторый параметр

Находится решение и проверяется условие:

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

Недостаток: на каждой итерации приходится решать не одну, а несколько задач линейного программирования, хотя метод и сойдется.