Нелинейное программирование. Метод Хука-Дживса

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

    5.  Пусть функция f(x) - выпуклая функция, заданная на выпуклом множестве X, и, кроме того, она непрерывна вместе со своими частными производными первого порядка во всех внутренних точках X. Пусть - точка, в которой . Тогда в точке достигается локальный минимум, совпадающий с глобальным минимумом.

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

    

4. ЗАДАЧА  ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ

 

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

           (6)

    при ограничениях

     ,    (7)

     .    (8)

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

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

     ,

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

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

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

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

      

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

    Пример 3

      Минимизировать  

      при ограничениях 

      Решение. 

      Записав данную задачу в виде  задачи нелинейного  программирования, получим 

     

     

     

     

      Уравнение  ,  входящее в состав условий   Куна—Таккера, принимает следующий вид:

     

      откуда 

     

      Неравенства  и уравнения задачи Куна — Таккера в данном случае записываются в виде

             Уравнения, известные как условие  дополняющей нежесткости, принимают  вид 

          

      Заметим, что на переменные  и накладывается требование неотрицательности, тогда как ограничение на знак отсутствует.

      Таким образом, этой задачи условия  Куна—Танкера записываются в следующем виде:

      

    

5. КВАДРАТИЧНОЕ   ПРОГРАММИРОВАНИЕ

 

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

     ,

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

    

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

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

    

6. ГРАДИЕНТНЫЕ   МЕТОДЫ

 

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

    К первой группе относятся методы, при  использовании которых исследуемые  точки не выходят за пределы области допустимых решений задачи. В данном случае наиболее распространенным является метод Франка - Вульфа. Ко второй - методы, при использовании которых исследуемые точки могут как принадлежать, так и не принадлежать области допустимых решений. Однако в результате реализации итерационного процесса находится точка области допустимых решений, определяющая приемлемое решение. Наиболее часто используются метод штрафных функций и метод Эрроу - Гурвица. При  нахождении   решения   задачи    градиентными   методами   итерационный    процесс    продолжается   до  тех   пор,   пока   градиент  функции в очередной точке   не станет равным нулю или же пока не выполнится неравенство , где (точность полученного решения).

    Метод Франка - Вульфа. Пусть требуется найти максимальное значение вогнутой функции

         (9)

    при условиях

     ,    (10)

             (11)

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

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

     ,

    строят  линейную функцию

     .    (12)

    Находят максимум функции (12) при ограничениях (10) и (11). Пусть решение данной задачи определяется точкой . За новое допустимое решение исходной задачи принимают координаты точки , которые находят по формулам

     ,

    где - некоторое число, называемое шагом вычислений . За принимают наименьший корень уравнения или выбирают произвольно, если он не принадлежит интервалу (0; 1).

    Метод штрафных функций. Рассмотрим задачу нелинейного программирования (6) -(8), где  - выпуклые функции.

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

     ,

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

     ,

    где        

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

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

     ,

    где - шаг вычислений .

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

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

    

    В качестве начальных значений   берут произвольные неотрицательные числа. 

    

7. ОСОБЕННОСТИ ЗАДАЧ  НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

 

• Задачи  нелинейного программирования значительно  ближе к реальным ситуациям, чем линейные.
• Задачи нелинейного программирования могут быть с ограничениями или без них.
• Решение задач нелинейного программирования намного сложнее, чем задач линейного программирования. Не существует универсального метода решения задач нелинейного программирования.
• В задачах нелинейного программирования могут существовать локальные и глобальные минимумы (максимумы).
• Наличие нескольких экстремумов целевой функции обуславливает множественность решений задачи выбора, что существенно затрудняет вещественную интерпретацию результатов.
• При создании нелинейных моделей в интересах обоснования рациональных решений целесообразно предусмотреть возможность уменьшения числа локальных решений: число закладываемых в модель ограничений m должно соотноситься с размерностью задачи n как 2<=m<=(n+1), модели должны строиться так, чтобы обеспечить возможность применения методов выпуклого анализа.

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

    II Краткая характеристика метода конфигураций Хука-Дживса. Алгоритм Хука-Дживса. Задача на данный алгоритм. 

    

1. МЕТОД КОНФИГУРАЦИЙ ХУКА-ДЖИВСА.

 

    Стратегия поиска. Метод представляет собой комбинацию исследующего поиска с циклическим изменением переменных и ускоряющего поиска по образцу. Цель исследующего поиска – выявление локального поведения целевой функции и определение направления ее убывания. Эта информация используется при поиске по образцу вдоль направления убывания целевой функции.

    Исследующий поиск начинается из некоторой начальной  точки  , называемой старым базисом. В качестве множества направлений поиска выбирается множество координатных направлений. Задается величина шага, которая может быть различной для разных координатных направлений. Фиксируется первое координатное направление и делается шаг в сторону увеличения соответствующей переменной. Если значение исходной функции f(x) в пробной точке меньше значения функции в исходной точке, то шаг считается удачным. В противном случае из исходной точки делается шаг в противоположном направлении с последующей проверкой поведения функции. Если и в этом случае не происходит уменьшения функции, то происходит уменьшение шага и процедура повторяется. Исследующий поиск по данному направлению заканчивается, когда текущая величина шага становится меньше некоторой величины. После перебора всех координат исследующий поиск завершается, полученная точка называется новым базисом.