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

Минимизировать (максимизировать)

                              (5.5)

при условиях

          (5.6)

Для решения этой задачи в такой общей постановке не существует универсальных методов. Однако для отдельных классов задач, в которых имеются дополнительные ограничения относительно свойств функций f и g_i, разработаны эффективные методы их решения. В частности, ряд таких методов имеется для решения задач при условии, что f – выпуклая (вогнутая) функция и область допустимых решений, определяемая (5.6) и (5.7) – выпуклая.

Дадим определения и понятия, необходимые нам в дальнейшем.

5.3.1 Основные определения и теоремы

ОПРЕДЕЛЕНИЕ 5.1. Непустое множество S из Е_n называется выпуклым, если отрезок прямой, соединяющий две любые точки множества S также принадлежит этому множеству. Иными словами, если точки и  лежат в S, то точка  также должна принадлежать S для всех .

На рисунке 5.3 приведены примеры множеств.

Рисунок 5.3 – Примеры множеств:

а) – выпуклое; б) – невыпуклое

ОПРЕДЕЛЕНИЕ 5.2. Пусть , где S – непустое выпуклое множество в E_n Говорят, что функция f выпукла на S, если

                (5.7)

для любых , S  и .

При этом, если имеет место строгое неравенство, то говорят о строгой выпуклости.

Функция f называется вогнутой, если −f выпукла на S.

На рисунке 5.4 приведены примеры выпуклых и вогнутых функций.

 а)                                б)                   в)

Рисунок 5.4 – Функции : а) – выпуклая функция;

б) – вогнутая функция; в) – функция, не являющаяся ни вогнутой, ни выпуклой.

Замечания.1.Из определения квазивыпуклой функции в п.4.1 очевидно следует, что выпуклая функция является также и квазивыпуклой, причем строго квазивыпуклой. Таким образом,предположение о квазивыпуклости исследуемой функции является существенно более слабым, чем выпуклость этой функции.

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

выпуклом множестве соответственно являются глобальными минимумом и максимумом.

ОПРЕДЕЛЕНИЕ 5.3. Говорят, что множество допустимых решений задачи (5)−(6) удовлетворяет условию регулярности, если существует по крайней мере одна точка , принадлежащая области допустимых решений такая, что

.

ОПРЕДЕЛЕНИЕ 5.4.Задача (5)−(6) называется задачей выпуклого программирования, если функция f является вогнутой (выпуклой), а функции g_i – выпуклыми.

ОПРЕДЕЛЕНИЕ 5.5. Пусть . Если  для всех  из Е_n, то  называется точкой глобального минимума функции f. Если существует ε − окрестность  точки  такая, что  для всех , то  называется точкой локального минимума. При обратных неравенствах соответственно имеют место точки глобального максимума и локального максимума.

ОПРЕДЕЛЕНИЕ 5.6. Функцией Лагранжа задачи выпуклого программирования называется функция

      ,        (5.8)

где  - неопределенные множители Лагранжа.

ОПРЕДЕЛЕНИЕ 5.7. Точка

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

для всех  и .

ТЕОРЕМА 5.1. Любой локальный минимум (максимум) задачи выпуклого программирования является глобальным минимумом (максимумом).

ТЕОРЕМА 5.2. (Теорема Куна-Таккера). Для задачи выпуклого программи­рования (5.5)−(5.6), множество допустимых решений которой обладает свойст­вом регулярности, точка  является оптимальным решением тогда и только тогда, когда существует такой вектор , что ( , ) – седловая точка функции Лагранжа.

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

                                (5.9)   

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

ОПРЕДЕЛЕНИЕ 5.8. Квадратичной формой относительно переменных  называется скалярная функция от этих переменных, имеющая вид:

                      .                                                       (5.10)

ОПРЕДЕЛЕНИЕ 5.9. Квадратичная форма f называется положительно (отрицательно)−определенной, если  для всех значений переменных  кроме . Если же имеют место нестрогие равенства, то квадратичная форма f называется положительно (отрицательно)-полуопределенной.

ТЕОРЕМА 5.3. Квадратичная форма является выпуклой функцией, если она положительно−полуопределенная, и вогнутой функцией, если она отрицательно − полуопределенная.

ОПРЕДЕЛЕНИЕ 5.10. Задача, состоящая в определении минимального (максимального) значения функции

                                    (5.11)

при условиях

,                 (5.12)

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