Б. Задачи НВП с нелинейными ограничениями.

(1)

- НВП, - нелинейные выпуклые функции .

 

ЛК №14

03.12.2003

 

- условие коллинеарности векторов в точке максимума.

Условие коллинеарности является условием окончания вычисления.

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

 

О задаче квадратичного программирования (КП) и методе ее решения.

Задача КП занимает особое место среди задач НВП.

Как известно, целевая функция в этой задача – квадратичная форма (квадратичная функция переменных , а функции , представляющие ОДР - линейные формы (линейные функции переменных ).

(1)

- элементы матрицы квадратичной формы, матрицы симметричной, положительно определенной.

Точка минимума в задаче КП в отличие от задачи ЛП, может находиться как на границе области , так и внутри этой области.

Задача КП достаточно эффективно решается ММЛ (обобщенным ММЛ).

Функция Лагранжа для задачи КП имеет вид.

(4)

(5)

, (6)

 

См. [5].

 

 

В соответствии с обобщенным ММЛ далее необходимо записать условия Куна-Таккера, воспользовавшись теоремой Куна-Таккера:

1) - условие неотрицательности; (7)

, ; (8)

2) - условие ортогональности; (9)

; (9')

3) ; (10)

4) - условие неположительности; (11)

; (12)

5) ; (13)

; (13')

6) (14)

Как видно, из выражений (8), (9'), (12), (12') исходная нелинейная задача ВП (1), (2), (3) с помощью условий Куна-Таккера представлена как линейная задача (все вышеуказанные уравнения содержат переменную , ). В дальнейшем простые преобразования позволяют (8), (9'), (10), (12), (13'), (14) представить в виде задачи ЛП и решить ее известным СМ.

 

О решении задачи НВП методом кусочно-линейной аппроксимации.

Этот метод применим к случаям, когда целевая функция и функции относятся к классу сепорабельных функций, т.е. функций, представимых в виде:

(1)

, (2)

(3)

 

 

См. [5].

 

ЛК №15

10.12.2003

 

(4)

Дальнейшая задача состоит в том, что все функции , и аппроксимировать линейными функциями. Тогда задача (3), (4) будет представлена как задача ЛП. Метод решения последней общеизвестен – СМ.

Вспомним основное выражение кусочно-линейной аппроксимации. Пусть функция - непрерывная функция, заданная на некотором отрезке , , , тогда, как известно, имеет место выражение:

. (5)

- линейная функция, аппроксимирующая непрерывную функцию на отрезке .

Если функция , , , , заменить соответственно линейными функциями в их областях определения, используя (5), то задача НВП (3), (4) преобразуется в задачу ЛП вида:

(6)

(7)

- кусочно-линейная аппроксимация функции , .

- кусочно-линейная аппроксимация функции , .

Задача (6), (7) является задачей ЛП и решается, как известно, универсальным СМ.

 

Метод штрафных функций (МШФ) и метод барьерных функций (МБФ).

Этот метод позволяет исходную задачу НВП преобразовать в последовательность задач МБО, методы решения которых известны.

В МШФ целевая функция исходной задачи НВП и ограничений функции , представляется в виде одной обобщенной функции вида:

(1)

где и называется коэффициентом штрафа;

- штрафная функция, это непрерывная функция, которая

 

 

удовлетворяет условию:

, ( - ОДР задачи НВМ);

,

формируется из ограничений функций , .

В МБФ обобщенная функция формируется аналогично.

(2)

где - барьерный коэффициент;

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

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

 

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

Пусть задача НВП имеет вид:

(3)

- нелинейная выпуклая функция.

На основании (3), (4), (5) составляем обобщенную функцию , используя (1).

Наиболее распространенными считаются штрафные функции вида:

; (6)

(7)

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

 

 

См. [6].

 

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

Заметим, что точки лежат вне области , а точка находится на границе . В связи с этим, МШФ называется методом внешних точек.

 

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

 

 

ЗАКЛЮЧЕНИЕ.

1. В курсе " Методы оптимизации" изучены:

а) аналитико-численные методы и численные методы многомерной безусловной оптимизации;

б) методы решения классической задачи условной оптимизации;

в) универсальный эффективный метод решения задач ЛП – симплексный метод;

г) методы решения задач НВП.

2. Вышеупомянутые методы в сочетании с современными ЭВМ позволяют сформулировать и решить сколь угодно сложную оптимизационную задачу в рамках детерминированного подхода. Существует и вероятностный (стохастический) подход к решению оптимизационных задач, изучаемых в курсе " Стохастическое программирование".

⇐ Предыдущая45678910111213

Поделиться: