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

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

    Содержание: 

    Введение. ……..………………………………………………………………………………...3

    I Классификация методов решения задач нелинейного программирования. Особенности задач не линейного программирования. Примеры. ………………………………………………..4

1. Общая задача нелинейного программирования. …………………………………………….4

2. Метод множителей Лагранжа. ………………………………………………………………..5

3. Выпуклое программирование. ………………………………………………………………..6

4. Задача выпуклого программирования. ………………………………………………………7

5. Квадратичное программирование. …………………………………………………………...9

6. Градиентные методы. …………………………………………………………………………9

7. Особенности задач нелинейного программирования. …………………………………….11

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

1. Метод Конфигураций Хука-Дживса. ……………………………………………………….12

2. Алгоритм метода Хука-Дживса. ………………………………………………………….....12

 Заключение. ………………………………………………………………………………..…15

 Список  используемой литературы. ………………………………………………………....16  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Введение 

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

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

    I Классификация методов решения задач нелинейного программирования. Особенности задач не линейного программирования. Примеры. 

    

1. ОБЩАЯ ЗАДАЧА НЕЛИНЕЙНОГО  ПРОГРАММИРОВАНИЯ

 

    В общем виде задача нелинейного программирования состоит в определении максимального (минимального) значения функции       (1)

    при условии  ,    (2)

    где и   - некоторые известные функции n переменных, а - заданные числа.

    Класс задач нелинейного программирования шире класса задач линейного программирования. Подробное изучение практических задач, которые условились считать линейными, показывает, что они в действительности являются нелинейными. Существующие методы позволяют решать узкий класс задач, ограничения которых имеют вид , а целевая функция является сепарабельной (суммой n функций ), или квадратической. Даже если область допустимых решений - выпуклая, то в ряде задач целевая функция может иметь несколько локальных экстремумов. С помощью большинства же вычислительных методов можно найти точку локального оптимума, но нельзя установить, является ли она точкой глобального (абсолютного) оптимума или нет. Если задача содержит нелинейные ограничения, то область допустимых решений не является выпуклой, и кроме глобального оптимума могут существовать точки локального оптимума. 

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

      В задаче нелинейного программирования (НЛП) требуется найти значение многомерной переменной х=( ), минимизирующее целевую функцию f(x) при условиях, когда на переменную х наложены ограничения типа неравенств

     ,   i=1,2,…,m    (1а)

      а переменные , т.е. компоненты вектора х, неотрицательны:

•    (2а)

      Иногда в формулировке задачи  ограничения (1а) имеют противоположные знаки неравенств. Учитывая, однако, что если , то , всегда можно свести задачу к неравенствам одного знака. Если некоторые ограничения входят в задачу со знаком равенства, например , то их можно представить в виде пары неравенств , , сохранив тем самым типовую формулировку задачи.  

      Критерии оптимальности в задачах с ограничениями.

      Ряд инженерных задач связан  с оптимизацией при наличии  некоторого количества ограничений на управляемые переменные. Такие ограничения существенно уменьшают размеры области, в которой проводится поиск оптимума. На первый взгляд может показаться, что уменьшение размеров допустимой области должно упростить процедуру поиска оптимума. Между тем, напротив, процесс оптимизации становится более сложным, поскольку установленные выше критерии оптимальности нельзя использовать при наличии ограничений. При этом может нарушаться даже основное условие, в соответствии с которым оптимум должен достигаться в стационарной точке, характеризующейся нулевым градиентом. Например, безусловный минимум функции имеет место в стационарной точке х=2. Но если задача минимизации решается с учетом ограничения , то будет найден условный минимум, которому соответствует точка x=4. Эта точка не является стационарной точкой функции f, так как (4)=4. Далее исследуются необходимые и достаточные условия оптимальности решений задач с ограничениями. Изложение начинается с рассмот­рения задач оптимизации, которые содержат только ограничения в виде равенств.

    Задачи  с ограничениями  в виде равенств

      Рассмотрим общую задачу оптимизации,  содержащую несколько ограничений  в виде равенств:

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

      при ограничениях    ,  k=1,…,n

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

      Пример 1

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

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

      Исключив переменную , с помощью уравнения , получим оптимизационную задачу с двумя переменными без ограничений min

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

    

2. МЕТОД МНОЖИТЕЛЕЙ ЛАГРАНЖА

 

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

     , 

    находят частные производные 

    и рассматривают систему n+m  уравнений

                           (3) 

    с n+m неизвестными , . Решив систему уравнений (3), получают все точки, в которых функция (1) может иметь экстремальные значения. Дальнейшее исследование найденных точек проводят так же, как и в случае безусловного экстремума. Метод множителей Лагранжа имеет ограниченное применение, так как система (3), как правило, имеет несколько решений. 

    Пример 2

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

      при ограничении   =0

      Соответствующая задача безусловной  оптимизации записывается в следующем  виде:

      минимизировать        L(x,u)= -u

      Решение. Приравняв две компоненты  градиента L к нулю, получим 

     

     

      Для того чтобы проверить, соответствует  ли стационарная точка х° минимуму, вычислим элементы матрицы Гессе функции L(х;u), рассматриваемой как функция х, ,

      которая оказывается положительно  определенной. Это означает, что  L(х,,u) — выпуклая функция х.  Следовательно, координаты  ,  определяют точку глобального минимума. Оптимальное значение u находится путем подстановки значений  и   в уравнение =2, откуда 2u+u/2=2 или . Таким образом, условный минимум достигается при и   и равен min f(x)=4/5.  

    

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

 

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

         (4)                              

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

        (5)

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

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

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

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

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

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

    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) в пробной точке меньше значения функции в исходной точке, то шаг считается удачным. В противном случае из исходной точки делается шаг в противоположном направлении с последующей проверкой поведения функции. Если и в этом случае не происходит уменьшения функции, то происходит уменьшение шага и процедура повторяется. Исследующий поиск по данному направлению заканчивается, когда текущая величина шага становится меньше некоторой величины. После перебора всех координат исследующий поиск завершается, полученная точка называется новым базисом.