Численные методы нахождения экстремума функции многих переменных с ограничениями в форме равенств и неравенств. Их сравнительный анализ.

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

 Постановка задачи.Дана функция y=f(X), на которую накладываются ограничениями в форме равенств и неравенств.

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

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

Этот метод применяется для решения задач условной оптимизации с ограничениями в форме равенств и неравенств, то есть ищется

Сведем исходную задачу к задаче безусловной минимизации функции

, где функция штрафа

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

Алгоритм метода штрафных функций.

1. Введем , к=0.

2. Запомним := и вычислим и его норму.

3. Пока норма > , найти  в соответствии с градиентным методом.

4. Вычислить  и увеличить .

5. Если , закончить вычисления, иначе возврат на пункт 2.

Метод барьерных функций.

Этот метод применяется для решения задач условной оптимизации с ограничениями типа неравенств, то есть

Сведем исходную задачу к задаче безусловной минимизации функции .

Присоединенная функция  выбирается таким образом, чтобы она неограниченно возрастала при приближении точки Xк границе области R.

.

Существенным в данном методе является то, что начальный коэффициент штрафа    задается большим. Начальная точка задается только внутри области R, поэтому этот метод называется методом внутренней точки. Коэффициент уменьшается с каждой итерацией . При этом

Минимизации функции происходит на основе любого метода безусловной минимизации( прямые методы, градиентные методы). Примем за основу градиентный метод

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

1. Начальная точка  задается внутри области R. Выбираемый коэффициент  достаточно большой.

2. На каждом k-ом шаге ищется точка , которая считается в качестве начальной на следующем этапе, выполняемом при уменьшающемся значении параметра .

3. При  последовательность точек  к точке условного .

При этом барьерные функции как бы препятствуют выходу из множества R.

Выход из процесса решения тот же, что и в методе штрафных функций.

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

Методы штрафных функций и барьерных функций.

Метод штрафных функций

Этот метод применяется для решения задач условной оптимизации с ограничениями в форме равенств и неравенств, то есть ищется

Сведем исходную задачу к задаче безусловной минимизации функции

, где функция штрафа

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

Алгоритм метода см. вопрос 24.

Метод барьерных функций.

Этот метод применяется для решения задач условной оптимизации с ограничениями типа неравенств, то есть

Сведем исходную задачу к задаче безусловной минимизации функции .

Присоединенная функция  выбирается таким образом, чтобы она неограниченно возрастала при приближении точки Xк границе области R.

.

Существенным в данном методе является то, что начальный коэффициент штрафа    задается большим. Начальная точка задается только внутри области R, поэтому этот метод называется методом внутренней точки. Коэффициент уменьшается с каждой итерацией . При этом

Минимизации функции происходит на основе любого метода безусловной минимизации( прямые методы, градиентные методы). Примем за основу градиентный метод (см. вопрос 22-23)

Алгоритм метода см. вопрос 24.