Программа дисциплины (syllabus) (стр. 5 )

Рассмотрим задачу нелинейного программирования

(6)

(7)

(8)

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

Говорят, что множество допустимых решений задачи (6) – (8) удовлетворяет условию регулярности, или условию Слейтера, если существует по крайней мере одна точка , принадлежащая области допустимых решений такая, что . Задача (6) – (8)  называется задачей выпуклого программирования, если функция  является вогнутой (выпуклой), а функции  – выпуклыми. Функцией Лагранжа задачи выпуклого программирования (6) – (8)  называется функция

где  – множители Лагранжа.

Точка  называется седловой точкой функции Лагранжа, если

для всех  и .

Теорема  (Куна – Таккера). Для задачи выпуклого программирования (6) – (8), множество допустимых решений которой обладает свойством регулярности, является оптимальным решением тогда  и только тогда, когда существует такой вектор  , что  – седловая точка функции Лагранжа.

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

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

Тема 3 Нелинейное программирование.

План

1) постановка задачи, экономическая интерпретация,

2) двойственность,

3) теорема Куна-Таккера,

4) условия оптимальности,

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

6) негладкая оптимизация.

Краткое изложение материала

Частным случаем задачи нелинейного программирования является задача квадратичного программирования, в которой ограничения

являются линейными, а функция  представляет собой сумму линейной и квадратичной функции (квадратичной формы)

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

Функция  представляет собой сумму линейной функции (которая является и выпуклой, и вогнутой) и квадратичной формы. Если последняя является вогнутой (выпуклой), то задачи отыскания максимума (минимума) целевой функции могут быть успешно решены. Вопрос о том, будет ли квадратичная форма вогнутой или выпуклой, зависит от того, является ли она отрицательно-определенной, отрицательно-полуопределенной, положительно-определенной, положительно-полуопределенной или вообще неопределенной.

Рассмотрим задачу нелинейного программирования

(1)

(2)

(3)

где  – выпуклые функции.

Вместо того, чтобы решать эту задачу, находят максимум функции

,

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

,

где

а  – некоторые постоянные числа, представляющие собой весовые коэффициенты.

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

,

Где λ – шаг вычислений (0 < λ < 1).

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

Тема 4 Численные методы оптимизации,

План

1)методы безусловной и условной оптимизации.

Краткое изложение материала

Мы будем рассматривать задачу безусловной оптимизации

f(x) → min,

(1)

где f: Rm → R. Точка x* ∈ Rm называется решением задачи (1) (или точкой глобального безусловного минимума функции f), если

f(x*) ≤ f(x)

(2)

при всех x ∈ Rm. Если неравенство (2) выполнено лишь для x, лежащих в некоторой окрестности Vx* точки x*, то точка x* называется локальным решением задачи (1), или точкой локального безусловного минимума функции f. Если неравенство (2) строгое при всех x ≠ x*, то говорят о строгом глобальном и, соответственно, строгом локальном минимумах. Решение задачи (1) иногда обозначают argmin f(x) (или, более полно, argminx∈Rm f(x); когда речь идет о задачах безусловной оптимизации в обозначениях argminx∈Rm f(x) и minx∈Rm f(x) мы будем всегда опускать индекс "x ∈ Rm"). Обычно из контекста ясно о каком минимуме (локальном, глобальном и т. д.) идет речь.

Аналогичные понятия (максимумов) определяются для задачи

f(x) → max. Метод золотого сечения

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