электронный учебник

"Экономико-математические методы"

 

На главную страницу

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

В конец страницы

15.3.  ВЫПУКЛОЕ   ПРОГРАММИРОВАНИЕ

       Функция , заданная на выпуклом множестве Х, называется  выпуклой,  если  для любых двух точек  из Х и любого  выполняется соотношение

         . (15.4)

Функция , заданная на выпуклом множестве Х, называется  вогнутой,  если  для любых  двух  точек  из Х и любо-

го  выполняется соотношение

          . (15.5)

Если  неравенства  (15.4)  и  (15.5)  считать  строгими  и  они  выполняются при , то функция  является строго выпуклой (строго вогнутой). Выпуклость и вогнутость функций определяется только относительно выпуклых множеств.

 

         

                                                                    Рисунок 15.1.

 Если , – выпуклые (вогнутые) функции на некотором выпуклом множестве , то функция  ‑ также выпуклая (вогнутая) на Х.

Основные свойства выпуклых и вогнутых функций:

          1. Множество точек минимума выпуклой функции, заданной на выпуклом множестве, ‑ выпукло.

2. Пусть  ‑ выпуклая функция, заданная на замкнутом выпуклом множестве . Тогда локальный минимум  на Х является и глобальным.

3. Если глобальный минимум достигается в двух различных точках, то он достигается и в любой точке отрезка, соединяющего данные точки.

4. Если  ‑ строго выпуклая функция, то ее глобальный минимум на выпуклом множестве Х достигается в единственной точке.

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

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

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

                                                                           (15.6)

                                                                   (15.7)

                                                                                         (15.8)

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

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

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

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

       для всех  и .

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

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

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

 

Назад     К началу страницы     Вперед