Численные методы поиска оптиума функции с ограничениями

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

Общая задача нелинейного программирования:

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

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

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

Штрафная функция для метода внешней точки:

Штрафная функция для комбинированного метода:

1. Строим штрафную функцию и выбираем начальную точку и произвольный коэффициент штрафа.
2. С помощью любого метода безусловной оптимизации находим экстремум функции x¹(r¹). Начиная с точки x¹(r¹) с помощью метода безусловной оптимизации ищем экстремум функции U(x,r²), где r¹>r²>0.
3. Описанную процедуру продолжаем до тех пор, пока |U(x,r^k+1)-U(x,r^k)|<eps.

Алгоритм Пирсона относится к группе методов переменной метрики. Эти методы называют ещё квазиньютоновскими или градиентными с большим шагом. Они аппроксимируют матрицу Гессе или обратную к ей, но используют для этого только первые производные. В большинстве из методов применяются сопряжённые направления.

К методам переменной метрики относятся также метод Дэвидона-Флетчера-Пауэла и проективный алгоритм Ньютона-Рафсона.

Рисунок 1 - Пример оптимизации функции y=(x₂-x₁²)² +(1-x₁²)² без ограничесний методом Пирсона.

Рисунок 2 - Пример оптимизации функции y=2*x₁+4*x₂-x₁²-x₂² с ограничениями методом штрафных функций.

Литература.

1. Шенен П., Коснар М. Математика и САПР. –М: Мир, 1988.