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

Южно-УральскийГосударственный Университет
Кафедра АиУ
реферат на тему:
Нелинейное программирование
Выполнил:Пушников А. А., ПС-263.
Проверил:Разнополов О.А.
Челябинск – 2003.

Оглавление
1.        Постановка задачи нелинейного программирования
2.        Критерии оптимальности в задачах с ограничениями
2.1.    Задачи с ограничением в виде равенств
2.2.    Множители Лагранжа
3.        Условия Куна-Таккера
3.1.    Условия Куна-Таккера и задача Куна-Таккера
3.2.    Интерпретация условий Куна-Таккера
3.3.    Теоремы Куна-Таккера
4.        Функции нескольких переменных
4.1.    Методы прямого поиска
4.1.1. Методпоиска по симплексу (S2 — метод)
4.1.2. Методпоиска Хука-Дживса

1. Постановка задачи нелинейногопрограммирования.
Взадаче нелинейного программирования (НЛП) требуется найти значение многомернойпеременной х=(/>), минимизирующеецелевую функцию f(x) при условиях, когда на переменную х наложеныограничения типа неравенств
/> ,   i=1,2,…,m                                 (1)
апеременные />, т.е. компоненты векторах, неотрицательны:
/>/>                                                          (2)
Иногдав формулировке задачи ограничения (1) имеют противоположные знаки неравенств.Учитывая, однако, что если  />, то /> , всегда можно свестизадачу к неравенствам одного знака. Если некоторые ограничения входят в задачусо знаком равенства, например />, то ихможно представить в виде пары неравенств />,/>, сохранив тем самымтиповую формулировку задачи.
2. Критерииоптимальности в задачах с ограничениями.
Рядинженерных задач связан с оптимизацией при наличии некоторого количества ограниченийна управляемые пере­менные. Такие ограничения существенно уменьшают размеры об­ласти,в которой проводится поиск оптимума. На первый взгляд может показаться, чтоуменьшение размеров допустимой области должно упростить процедуру поискаоптимума. Между тем, напро­тив, процесс оптимизации становится более сложным,поскольку установленные выше критерии оптимальности нельзя использовать приналичии ограничений. При этом может нарушаться даже ос­новное условие, всоответствии с которым оптимум должен достигаться в стационарной точке,характеризующейся нулевым гра­диентом. Например, безусловный минимум функции /> имеет место в стационарнойточке х=2. Но если задача минимиза­ции решается с учетом ограничения />, то будет найден условныйминимум, которому соответствует точка x=4. Эта точка не являетсястационарной точкой функции f, так как />(4)=4. Далее исследуются необходимые и достаточные условия оптимальностирешений задач с ограничениями. Изложение начинается с рассмот­рения задачоптимизации, которые содержат только ограничения в виде равенств. 2.1. Задачи с ограничениями в виде равенств
Рассмотримобщую задачу оптимизации, содержащую несколь­ко ограничений в виде равенств:
Минимизировать          /> 
приограничениях          /> ,  k=1,…,n
Этазадача в принципе может быть решена как задача безусловной оптимизации,полученная путем исключения из целевой функции k независимых переменных с помощью заданных равенств.Наличие ограничений в виде равенств фактически позволяет уменьшить размерность исходнойзадачи с n до n-k… Вкачестве иллюстрации рассмотрим следующий пример.
Пример1
Минимизировать         />
приограничении          />
Исключивпеременную />, с помощью уравнения />, получим
оптимизационнуюзадачу с двумя  переменными без ограничений
min /> 
Методисключения переменных применим лишь в техслучаях, когда уравнения, представляющие ограничения, можно разрешитьотносительно некоторого конкретного набора независимых пере­менных. При наличиибольшого числа ограничений в виде равенств, процесс исключения переменныхстановится весьма трудоемкой процедурой. Кроме того, возможны ситуации, когдауравнение не удается разрешить относительно переменной. В частности, если впримере 1 ограничение /> задать в виде
/>
тополучить аналитическое выражение какой-либо из переменных через другие непредставляется возможным. Таким образом, при решении задач, содержащих сложныеограничения в виде равенств, целесообразно использовать метод множителейЛагранжа, описа­ние которого дается в следующем разделе. 2.2. Множители Лагранжа
Спомощью метода множителей Лагранжа по существу устанавливаются необходимыеусловия, позволяющие идентифицировать точки оптимума в задачах оптимизации сограничениями в виде ра­венств. При этом задача с ограничениями преобразуется вэквива­лентную задачу безусловной оптимизации, в которой фигурируют некоторыенеизвестные параметры, называемые множителями Ла­гранжа.
Рассмотримзадачу минимизации функции n переменных с уче­том одного ограничения в видеравенства:
Минимизировать           />                                    (3)
приограничениях            />                                            (4)
Всоответствии с методом множителей Лагранжа эта задача преобразуется в следующуюзадачу безусловной оптимизации:
минимизировать L(x,u)=f(x)-u*h(x)                                               (5)
Функция L(х;u) называется функцией Лагранжа, u — неизвест­наяпостоянная, которая носит название множителя Лагранжа. На знак u никакихтребований не накладывается.
Пустьпри заданном значении u=u0безусловный минимум функ­ции L(x,u) по х достигается в точке /> и/> удовлетворяет урав­нению />. Тогда, как нетрудновидеть, x0минимизирует (1) с учетом (4), поскольку для всех значений х, удовлетворяющих(4), /> и  L(x,u)=min f(x).
Разумеется,необходимо подобрать значение u=u° таким обра­зом, чтобы координата точки безусловногоминимума х° удовлетво­ряла равенству (4). Это можно сделать, если, рассматриваяu как переменную, найти безусловный минимум функции (5)в виде функции u, а затем выбрать значение u, при котором выполняетсяравенство (4). Проиллюстрируем это на конкретном примере.
Пример2
Минимизировать /> 
приограничении   />=0
Соответствующаязадача безусловной оптимизации записывается в следующем виде:
минимизировать       L(x,u)= />-u/>
Решение. Приравняв две компоненты градиента L к нулю, получим
/>
/>
Длятого чтобы проверить, соответствует ли стационарная точка х° минимуму, вычислимэлементы матрицы Гессе функции L(х;u), рассматриваемой как функция х,
/>,
котораяоказывается положительно определенной. Это означает, что L(х,,u) — выпуклаяфункция х. Следовательно, координаты  /> ,/> определяют точкуглобального минимума. Оптималь­ное значение u находится путемподстановки значений /> и />  в урав­нение />=2, откуда 2u+u/2=2или />. Таким образом, условныйминимум достигается при /> и />/>  и равен min f(x)=4/5.
Прирешении задачи из примера 2 мы рассматривали L(х;u) как функциюдвух переменных /> и /> и, кроме того,предполагали, что значение параметра uвыбрано так, чтобы выполнялось ограни­чение.Если же решение системы
/>,    j=1,2,3,…,n
ввиде явных функций u получить нельзя, то значения х и u нахо­дятсяпутем решения следующей системы, состоящей из n+1 урав­нений с n+1 неизвестными:
/> ,     j=1,2,3,…,n        />
Длянахождения всех возможных решений данной системы можно использовать численныеметоды поиска (например, метод Ньютона). Для каждого из решений (/>) сле­дует вычислитьэлементы матрицы Гессе функции L, рассматри­ваемой как функция х, и выяснить, являетсяли эта матрица поло­жительно определенной (локальный минимум) или отрицательноопределенной (локальный максимум).
Методмножителей Лагранжа можно распространить на случай, когда задача имеетнесколько ограничений в виде равенств. Рас­смотрим общую задачу, в которойтребуется
Минимизировать f(x)
приограничениях />=0, k=1,2, ..., К.
ФункцияЛагранжа принимает следующий вид:
L(x,u)=f(x)-/>
Здесь/>—множители Лагранжа, т.е.неизвестные параметры, значения которых необходимо определить. Приравни­ваячастные производные L по х к нулю,получаем следующую систему n уравнениис n неизвестными:
/>
/>
………..
/>
Еслинайти решение приведенной выше системы в виде функций вектора u оказываетсязатруднительным, то можно расширить систему путем включения в нее ограничений ввиде равенств
/>
/>
/>
Решениерасширенной системы, состоящей из n+К уравнений с n+К неизвестными,определяет стационарную точку функции L. Затем реализуется процедурапроверки на минимум или максимум, которая проводится на основе вычисленияэлементов матрицы Гессе функции L, рассматриваемой как функция х, подобнотому, как это было проделано в случае задачи с одним ограничением. Длянекоторых задач расширенная система n+К уравнений с n+K неизвестными может не иметь решений, и методмножителей Лагранжа оказывается неприменимым. Следует, однако, отметить, чтотакие задачи на практике встречаются достаточно редко.
3. УсловияКуна-Таккера
Впредыдущем разделе было установлено, что множители Лаг­ранжа можно использоватьпри построении критериев оптималь­ности для задач оптимизации с ограничениями ввиде равенств. Кун и Таккер обобщили этот подход на случай общей задачи нели­нейногопрограммирования с ограничениями, как в виде равенств, так и в виденеравенств.   
Рассмотримследующую общую задачу не­линейного программирования:
минимизировать/>                                                  (0)
приограничениях />                           (1)
/>                                (2)
Определение:
Ограничениев виде неравенства /> называется активным,или связывающим, в точке />, если />, и неактивным, илинесвязывающим, если />
Еслисуществует возможность обнаружить ограничения, ко­торые неактивны в точкеоптимума, до непосредственного решения задачи, то эти ограничения можноисключить из модели и тем самым уменьшить ее размеры. Основная трудностьзаключается при этом в идентификации неактивных ограничений, предшествующей ре­шениюзадачи.
Куни Таккер построили необходимые и достаточные условия оптимальности для задачнелинейного программирования, исходя из предположения о дифференцируемостифункций />. Эти условияоптимальности, широко известные как условия Куна—Таккера, можно сформулироватьв виде задачи нахождения решения некоторой системы нелинейных уравнений инеравенств, или, как иногда говорят, задачи Куна—Таккера.3.1. Условия Куна—Таккера изадача Куна—Таккера
Найтивекторы  /> , удовлетворяющие следующимусловиям
/>(3)
/>(4)
/>(5)
/>(6)
/>(7)
Преждевсего проиллюстрируем условия  Куна — Таккера на примере.
Пример3
Минимизировать/> 
приограничениях />
Решение.
Записавданную задачу в виде задачи нелиней­ного  программирования (0)-(2), получим
/>/>
/>/>
/>/>
/>/>
Уравнение(3),  входящее в состав условий   Куна—Таккера, принимает следующий  вид:
/>
откуда
/>
Неравенства(4) и уравнения (5) задачи Куна — Таккера в данном случае записываются в виде
/>   />   />
Уравнения(5.16), известные как условие дополняющей нежесткости, принимают вид
/>      />
Заметим,что на переменные /> и /> накладывается требованиене­отрицательности, тогда как ограничение на знак /> отсутствует.
Такимобразом, этой задачи условия  Куна—Танкера записываются в следующем виде:
/> 3.2. Интерпретация условий Куна — Таккера
Длятого чтобы интерпретировать условия Куна — Таккера, рассмотрим задачу нелинейногопрограммирования с ограничения­ми в виде равенств:
минимизировать/>
приограничениях />
Запишемусловия Куна—Таккера
/> (8)
/>  (9)
Далеерассмотрим функцию Лагранжа для задачи нелинейного программирования сограничениями в виде равенств
/>
Дляэтой функции условия оптимальности первого порядка запи­сываются в виде
/>
Нетрудновидеть, что условия Куна-Таккера (8) и (9) совпадают с условиями оптимальностипервого порядка для задачи Лагранжа.
Рассмотримзадачу нелинейного программирования  с ограни­чениями  в виде неравенств:
минимизировать/>
приограничениях  />/>
Запишем условия  Куна—Таккера
/>
Соответствующаяфункция Лагранжа имеет вид
/>
Условияоптимальности первого порядка записываются как
/>
Заметим,что /> — множитель Лагранжа,соответствующий ограни­чению />. Раньшебыло показано, что /> представляетнеявную цену, ассоциированную с ограничением />;другими словами, вели­чина /> отражаетизменение минимального значения целевой функ­ции />,вызываемое единичным приращением правой части />-го ог­раничения.
Еслипредположить, что /> — е ограничениеявляется неактивным (т.е. /> Сдругой стороны, если />-е ограничениеактивное (т. е. />), тосоответствующая неявная цена /> необязательно равна нулю, однако />, таккак />. Таким образом,/> для всех значений />.
Длятого чтобы определить знак /> (неявнойцены, ассоциирован­ной с ограничением />),следует увеличить правую часть ограничения от 0 до 1. Ясно, что при этомобласть допустимых решений сужается, поскольку любое решение, удовлетворяющееограничению />, автоматическиудовлетворяет неравенству />. Следовательно,размеры допустимой области уменьша­ются, и минимальное значение /> улучшить невозможно (таккак вообще оно может только возрастать). Другими словами, неявная цена />, ассоциированная с />-м ограничением, должнабыть неотри­цательной, что соответствует условиям Куна—Таккера. 3.3. Теоремы Куна—Таккера
Впредыдущем разделе построены условия Куна—Таккера для задач условнойоптимизации. С помощью метода множителей Лагранжа получено интуитивноепредставление о том, что условия Куна — Танкера тесно связаны с необходимымиусловиями опти­мальности. В данном разделе рассматриваются строгие формули­ровкинеобходимых и достаточных условий оптимальности решения задачи нелинейногопрограммирования.
Теорема1. Необходимость условий Куна—Таккера
Рассмотримзадачу нелинейного программирования (0)-(2). Пусть />- дифференцируемые функции, а х* — допус­тимое решение данной задачи. Положим />. Далее пусть /> линейно неза­висимы.Если х* — оптимальное решение задачи нелинейного про­граммирования, тосуществует такая пара векторов />, что/>  является решением задачи Куна—Таккера (3)—(7).
Условие,согласно которому />должны бытьлинейно независимыми, известно как ус­ловие линейной независимости и посуществу представляет собой некоторое условие регулярности допустимой области,которое поч­ти всегда выполняется для встречающихся на практике задач опти­мизации.Однако вообще проверка выполнения условия линейной независимости весьмазатруднительна, так как требуется, чтобы оптимальное решение задачи былоизвестно заранее. Вместе с тем условие линейной независимости всегдавыполняется для задач нелинейного программирования, обладающих следующими свой­ствами.
1.Все ограничения в  виде равенств и  неравенств содержат линейные функции.
2.Все ограничения в виде неравенств содержат вогнутые функ­ции,  всеограничения-равенства — линейные функции, а также существует, по крайней мере,одна допустимая точка х, которая рас­положена во внутренней части области, определяемой ограниче­ниями-неравенствами. Другими словами, существует такаяточка х, что
/>
Еслиусловие линейной независимости в точке оптимума не вы­полняется, то задачаКуна—Таккера может не иметь решения.
Пример4
Минимизировать/>
приограничениях />
Решение.
Нарис.1 изображена область допустимых ре­шений сформулированной выше нелинейнойзадачи. Ясно, что оптимальное решение этой задачи есть />. Пока­жем, что условиелинейной независимости не выполняется в точке оптимума.
/>

Рис.1Допустимая область в задаче 4
Таккак
/>Легко видеть, что векторы />линейнозависимы, т. е. условие линейной независимости в точке />не выпол­няется.
Запишемусловия Куна—Таккера и проверим, выполняются ли они в точке (1, 0). Условия(3), (6) и (7) принимают сле­дующий вид;
/> (11)
/> (12)
/>(13)
/> (14)
/>  (15)
/>(16)
При/> из уравнения (11) следует,что />, тогда как уравнение (14)дает />, Следовательно, точкаоптимума не является точкой Куна — Таккера.
Заметим,что нарушение условия линейной независимости не обязательно означает, что точкаКуна—Таккера не существует. Для того чтобы подтвердить это, заменим целевуюфункцию из этого примера функцией/>. Приэтом оптимум по-прежнему достигается в точке (1,0), в которой условие линейнойнезависимости не выполняется. Условия Куна—Так­кера (12) — (16) остаютсянеизменными, а уравнение (11) принимает вид
/>
Нетруднопроверить, что точка /> является точкойКуна—Таккера, т. е. удовлетворяет условиям Куна—Таккера.
Теоремао необходимости условий Куна—Таккера позволяет идентифицировать неоптимальныеточки. Другими словами, тео­рему 1 можно использовать для доказательства того,что задан­ная допустимая точка, удовлетворяющая условию линейной неза­висимости,не является оптимальной, если она не удовлетворяет условиям Куна—Таккера. Сдругой стороны, если в этой точке условия Куна—Таккера выполняются, то нетгарантии, что най­дено оптимальное решение нелинейной задачи. В качествепримера рассмотрим следующую задачу нелинейного программирования.
Следующаятеорема устанавливает условия, при выполнении которых точка Куна—Таккераавтоматически соответствует оптимальному решению задачи нелинейногопрограммирования.
Теорема.2Достаточность условий Куна—Таккера
Рассмотримзадачу нелинейного программирования (0) — (2). Пусть целевая функция /> выпуклая, все ограниченияв виде неравенств содержат вогнутые функции />,а ограничения в виде равенств содержат линейные функции />. Тогда если существуетрешение />, удовлет­воряющее условиямКуна—Таккера (3) — (7), то х* — оп­тимальное решение задачи нелинейногопрограммирования.
Еслиусловия теоремы 2 выполняются, то нахождение точки Куна—Таккера обеспечиваетполучение оптимального решения задачи нелинейного программирования.
Теорему2 можно также использовать для доказательства оптимальности данного решениязадачи нелинейного программирования. В качестве иллюстрации опять рассмотримпример:
Минимизировать/>       
приограничениях />
Спомощью теоремы 2 докажем, что решение />являетсяоптимальным. Имеем
/>
Таккак матрица />положительно полуопределенапри всех х, функция /> оказываетсявыпуклой. Первое ограничение в виде неравенства содержит линейную функцию />, которая одновре­менноявляется как выпуклой, так и вогнутой. Для того
чтобыпоказать, что функция />являетсявогнутой, вычислим
/>
Посколькуматрица /> отрицательно определена,функция />является вогнутой. Функция /> входит в линейное ограни­чениев вяде равенства. Следовательно, все условия теоремы 2 выполнены; если мыпокажем, что /> - точка Куна-Так­кера, тодействительно установим оптимальность решения />.Условия Куна-Таккера для примера 2 имеют вид
/>(22)
/> (23)
/>  (24)
/> (25)
/>,  (26)
/>, (27)
/> (28)
/>(29)
Точка/>удовлетворяет ограничениям(24) — (26) и, следовательно, является допустимой. Уравнения (22) и (23)принимают следующий вид:
/>
Положив/> , получим />и/>. Таким образом, реше­ние х*=(1,5), /> удовлетворяет условиямКуна—Таккера. Поскольку условия теоремы 2 выполнены, то /> оптимальное решение задачииз примера 3. Заметим, что существуют также и другие значения />и />, которые удов­летворяют системе (22) -(29).
Замечания
1.Для встречающихся на практике задач условие линейной независимости,   как  правило,   выполняется.   Если   в  задаче   все функции  дифференцируемы,  тоточку   Куна—Таккера  следует рассматривать как возможную точку оптимума. Такимобразом, многие из методов нелинейного программирования сходятся к точкеКуна—Таккера. (Здесь уместно провести аналогию со случаем безусловнойоптимизации, когда соответствующие алгоритмы позволяют определить стационарнуюточку.)
2.Если условия теоремы 2 выполнены, точка Куна—Таккера в то же время оказываетсяточкой глобального минимума. К сожа­лению, проверка достаточных условий весьмазатруднительна, и, кроме того, прикладные задачи  часто не обладают требуемымисвойствами. Следует отметить, что наличие хотя бы одного нелиней­ногоограничения в виде равенства приводит к нарушению предпо­ложений теоремы 2.
3.Достаточныеусловия, установленные теоремой 2, можно обобщить на случай задач с невыпуклымифункциями, входящими в ограничения в виде неравенств, невыпуклыми целевыми функ­циямии нелинейными ограничениями-равенствами. При этом ис­пользуются такие обобщениявыпуклых функций, как квазивыпук­лые и псевдовыпуклые функции.
4. Функции нескольких переменных
Ограниченныевозможности симплексного метода, заключенные в задачах со сложными видамиограничений и произвольным видом целевой функции, привели к широкомуиспользованию итеративных методов поиска оптимального решения. 
Сначаларассмотрим вопрос анализа «в статике» с использова­нием положений линейнойалгебры и дифференциального исчисле­ния, а также условия, которые (в достаточнообщих возможных ситуациях) позволяют идентифицировать точки опти­мума. Такиеусловия используются для проверки выбранных точек и дают возможность выяснить,являются ли эти точки точками ми­нимума или максимума. При этом задача вы­борауказанных точек остается вне рамок проводимого анализа; основное вниманиеуделяется решению вопроса о том, соответствуют ли исследуемые точки решенияммногомерной задачи безусловной оптимизации, в которой требуется минимизировать f(x)    x/>   при отсутствии ограничений на x, где x — вектор управляемых переменных размерности n, f —скалярная целевая функция. Обыч­но предполагается, что xi (для всех значений i=1,2, …, n) могут принимать любые значения, хотя в рядепрактических при­ложений область значений x выбирается в виде дискретного мно­жества. Кроме того,часто оказывается удобным предполагать, что функция f и еепроизводные существуют и непрерывны всюду, хотя известно, что оптимумы могутдостигаться в точках разрыва f или ее градиента
/>
Градиентомфункции  f(х) называют вектор, величина которого определяетскорость изменения функции f(x), а направление совпадает с направлением наибольшеговозрастания этой функции.
Следуетпомнить, что функция f может принимать минимальное значение в точке x, в которой f или /> претерпеваютразрыв. Кроме того, в этой точке /> можетне существовать. Для того чтобы по­строить систему конструктивных критериевоптимальности, необ­ходимо (по крайней мере на первой стадии исследования)исключить из рассмотрения подобные ситуации, которые весьма усложня­ют анализ. 4.1. Методы прямого поиска
Нижерассматривается вопрос анализа «в динамике» для функций нескольких переменных,т. е. исследуются методы и алгоритмы, позволяющие на итерацион­ной основеполучать оценки х*— вектора управляемых переменных, которому соответствуетминимальное значение функции f(x). Ука­занные методы применимы также к задачаммаксимизации, в кото­рых целевую функцию следует заменить на -f(х).Методы, ориен­тированные на решение задач безусловной оптимизации, можноразделить на три широких класса в соответствии с типом используе­мой приреализации того или иного метода информации.
1.Методы прямого поиска, основанные на вычислении только значений целевойфункции.
2.Градиентные методы, в которых используются точные значе­ния  первых производных f(x).
3.Методы второго порядка, в которых наряду с первыми про­изводными используютсятакже вторые производные функции f(x).
Нижерассматриваются методы, относящиеся к каждому из пере­численных классов,поскольку ни один метод или класс методов не отличается высокой эффективностьюпри решении оптимизационных задач различных типов. В частности, возможныслучаи, когда про­исходит переполнение памяти ЭВМ; в других ситуацияхвычисление значений целевой функции требует чрезмерных затрат времени; внекоторых задачах требуется получить решение с очень высокой степенью точности.В ряде приложений либо невозможно, либо весьма затруднительно найтианалитические выражения для произ­водных целевой функции. Поэтому еслипредполагается использо­вать градиентные методы, следует применить процедуруразностной аппроксимации производных. В свою очередь это приводит к необ­ходимостиэкспериментального определения длины шагов, позво­ляющего установить надлежащеесоответствие между ошибкой округления и ошибкой аппроксимации. Таким образом,инженер вынужден приспосабливать применяемый метод к конкретным ха­рактеристикамрешаемой задачи.
Методырешения задач безусловной оптимизации отличаются относительно высоким уровнемразвития по сравнению с другими методами нелинейного программирования. Нижеречь идет о методах прямого поиска, для реализации которых требуются толькозначения целевой функции; в следующем разделе рассматриваются градиентныеметоды и методы второго порядка. Здесь предполагается, что f(x) непрерывна,а /> может как существовать,так и не существовать, поскольку соответствующие числовые значения неиспользуются. Однако следует отметить, что методы прямого поиска можно приме­нятьдля решения задач, в которых /> существует,и они часто используются в тех случаях, когда /> представляетсобой сложную векторную функцию управляемых переменных. Наконец, в этом ипоследующих разделах предполагается, что функция f(х) унимо­дальнав рассматриваемой области. Если же изучаемые методы применяются для анализамультимодальных функций, то приходит­ся ограничиваться идентификацией локальныхминимумов.
Многомерныеметоды, реализующие процедуру поиска оптиму­ма на основе вычисления значенийфункции, с общих позиций можно разделить на эвристические и теоретические.Эвристические методы, как это следует из названия, реализуют процедуры поиска спомощью интуитивных геометрических представлений и обеспечи­вают получениечастных эмпирических результатов. С другой сто­роны, теоретические методыоснованы на фундаментальных математических теоремах и обладают такимиоперационными свойствами, как сходимость (по крайней мере при выполнениинекоторых опре­деленных условий). Ниже подробно рассматриваются три методапрямого поиска:
1)поиск по симплексу, или S2-метод;
2)метод поиска Хука—Дживса;
3)метод сопряженных направлений Пауэлла.
Первыедва из перечисленных методов относятся к категории эвристических и реализуютпринципиально различающиеся стра­тегии поиска. В процессе поиска по S2-методу последовательно опе­рируют регулярнымисимплексами в пространстве управляемых переменных, тогда как при реализацииметода Хука-Дживса используется фиксированное множество (координатных) направле­ний,выбираемых рекурсивным способом. Метод Пауэлла основан на теоретическихрезультатах и ориентирован на решение задач с квадратичными целевыми функциями;для таких задач метод сходится за конечное число итераций. К числу общихособенностей всех трех методов следует отнести относительную простоту соответ­ствующихвычислительных процедур, которые легко реализуются и быстро корректируются. Сдругой стороны, реализация указанных  методов может требовать (и часто требует)более значительных затрат времени по сравнению с методами с использованиемпроизводных. 4.1.1.Метод поиска по симплексу(S2-метод)
Первыепопытки решения оптимизационных задач без ограниче­ний на основе прямого поискасвязаны с использованием одномер­ных методов оптимизации. Как правило, приреализации таких методов допустимая область определения показателя качествафункционирования системы (целевой функции) заменяется дискрет­ным множеством(решеткой) точек пространства управляемых пере­менных, а затем используютсяразличные стратегии уменьшения области, которая содержит решение задачи. Частоэта процедура оказывается эквивалентной равномерному поиску в узлах решетки и,следовательно, непригодной для решения задач с числом пере­менных, превышающим2. Более полезная идея заключается в выбо­ре базовой точки и оцениваниизначений целевой функции в точках, окружающих базовую точку. Например, прирешении задачи с дву­мя переменными можно воспользоваться квадратным образцом,изображенным на рис.2
/>

Рис2. Квадратный образец (частный случай кубического образца)
За­тем«наилучшая» из пяти исследуемых точек выбирается в ка­честве следующей базовойточ­ки, вокруг которой строится аналогичный образец. Если ни одна из угловыхточек не имеет преимущества перед базовой, размеры образца следует уменьшить,после чего продолжить поиск.
Этоттип эволюционной опти­мизации был использован Бок­сом  и другимиисследователями для анализа функционирования промышленных предприятий, когдаэффект варьирования значений переменных, описывающих производственные процессы,измеряется с ошибкой. В задачах большой размерности вычисление значений целевойфункции проводится во всех вершинах, а также в центре тяжести гиперкуба (гиперкуб– куб в n-мерном евклидовом пространстве, т.е. множество S={x=(/>)/>| />}, где а и b –заданные числа ), т. е. в точках так называемого кубического образца. Есликоличество переменных (размерность пространства, в котором ведется поиск) равноn, то поиск по кубическому образцу требует />+1 вычислений значенияфункций для одного образца. При увеличении размерности задачи необходимоеколичество вы­числений значения целевой функции возрастает чрезвычайно быст­ро.Таким образом, несмотря на логическую простоту поиска по кубическому образцу,возникает необходимость использования более эффективных методов прямого поискадля решения возникаю­щих на практике задач оптимизации.
Однаиз вызывающих особый интерес стратегий поиска положе­на в основу метода поискапо симплексу, предложенного Спендли, Хекстом и Химсвортом. Следует отметить,что указанный метод и другие подобные методы не имеют отношения ксимплекс-методу линейного программирования, а сходство названий носит случай­ныйхарактер. Процедура симплексного поиска Спендли, Хекста и Химсворта базируетсяна том, что экспериментальным образцом, содержащим наименьшее количество точек,является регулярный симплекс. Регулярный симплекс в n-мерномпространстве пред­ставляет собой многогранник, образованный n+1равностоящими друг от друга точками-вершинами. Например, в случае двух пере­менныхсимплексом является равносторонний треугольник; в трех­мерном пространствесимплекс представляет собой тетраэдр. В алго­ритме симплексного поискаиспользуется важное свойство симплек­сов, согласно которому новый симплексможно построить на любой грани начального симплекса путем переноса выбраннойвершины на надлежащее расстояние вдоль прямой, проведенной через центр тяжестиостальных вершин начального симплекса. Полученная та­ким образом точка являетсявершиной нового симплекса, а выбран­ная при построении вершина начальногосимплекса исключается. Нетрудно видеть, что при переходе к новому симплексутребуется одно вычисление значения целевой функции. Рис 3 иллюстрирует процесспостроения нового симплекса на плоскости.

/>

Рис.3.Построениенового симплекса.
а– начальный симплекс />
б– новый симплекс  />
 
Работаалгоритма симплексного поиска начинается с построения регулярного симплекса впространстве независимых переменных и оценивания значений целевой функции вкаждой из вершин симп­лекса. При этом определяется вершина, которойсоответствует наибольшее значение целевой функции. Затем найденная вершинапроецируется через центр тяжести остальных вершин симплекса в новую точку,которая используется в качестве вершины нового симплекса. Если функция убываетдостаточно плавно, итерации продолжаются до тех пор, пока либо не будет накрытаточка мини­мума, либо не начнется циклическое движение по двум или болеесимплексам. В таких ситуациях можно воспользоваться следую­щими тремяправилами.
Правило1. «Накрытие» точки минимума
Есливершина, которой соответствует наибольшее значение це­левой функции, построенана предыдущей итерации, то вместо нее берется вершина, которой соответствуетследующее по величине значение целевой функции.
Правило2. Циклическое движение
Еслинекоторая вершина симплекса не исключается на протя­жении более чем М итераций,то необходимо уменьшить размеры симплекса с помощью коэффициента редукции ипостроить новый симплекс, выбрав в качестве базовой точку, которойсоответствует минимальное значение целевой функции. Спендли, Хекст и Химс-вортпредложили вычислять М по формуле
M=1,65n+0,05/>
гдеn — размерность задачи, а М округляется до ближайшегоцелого числа. Для применения данного правила требуется уста­новить величинукоэффициента редукции.
Правило3. Критерий окончания поиска
Поискзавершается, когда или размеры симплекса, или разности между значениями функциив вершинах становятся достаточно ма­лыми. Чтобы можно было применять эти правила,необходимо за­дать величину параметра окончания поиска.
Реализацияизучаемого алгоритма основана на вычислениях двух типов: (1) построениирегулярного симплекса при заданных базовой точке и масштабном множителе и (2)расчете координат отраженной точки. Построение симплекса является достаточнопростой процедурой, так как из элементарной геометрии известно, что призаданных начальной (базовой) точке /> и масштабноммно­жителе /> координаты остальных nвершин симплекса в n-мерном пространстве вычисляются по формуле
/>                 (7)
дляi  и j=1,2,3,…,n
Приращения/> и />,зависящие только от n и выбранного мас­штабного множителя/>, определяются по формулам
/>                          (8)
/>                        (9)
Заметим,что величина масштабного множителя />выбираетсяис­следователем, исходя из характеристик решаемой задачи. При />=1 ребра регулярногосимплекса имеют единичную длину. Вычисления второго типа, связанные сотражением относи­тельно центра тяжести, также представляют несложнуюпроцедуру. Пусть />— точка,подлежащая отражению. Центр тяжести осталь­ных n точек расположен в точке
/>                       (10)
Всеточки прямой, проходящей через /> и хс,задаются формулой
/>                (11)
При/>=0 получаем исходную точку />, тогда как значение />=1 соответствует центрутяжести хс. Для того чтобы построенный симп­лекс обладал свойствомрегулярности, отражение должно быть сим­метричным. Следовательно, новая вершинаполучается при />=2. Такимобразом,
/>                    (12)
Проиллюстрируемвычислительную схему метода следующим при­мером.
Пример5. Вычисления в соответствии с методом поиска по симплексу
Минимизироватьf(x)=/>
Решение.
Дляпостроения исходного симплекса требуется задать начальную точку и масштабныймножитель. Пусть x/> =/>и />=2. Тогда
/>
/>
Используяэти два параметра, вычислим координаты двух остальных вершин симплекса:
/>
/>
которымсоответствуют значения целевой функции, равные />=0,2374и />3,0658. Так как />5, необходимо отразитьточку />относительно центра тяжестидвух остальных вершин симплекса
/>
Используяформулу (12),  получаем
/>
/>
Вполученной точке />2,3027, т. е.наблюдается уменьшение целевой функции. Новый симплекс образован точками />и/>. В соответствии салгоритмом следует отразить точку х(2), ко­торой соответствуетнаибольшее значение целевой функции, отно­сительно центра тяжести точек />и х(3). Итерациипродолжаются до тех пор, пока не потребуется применение правил 1, 2 и 3,которые были сформулированы выше.
Изложенныйвыше алгоритм /> — метода имеетнесколько очевид­ных преимуществ.
1.Расчеты и логическая структура метода отличаются сравни­тельной простотой, и,следовательно, соответствующая программа для ЭВМ оказывается относительнокороткой.
2.Уровень требований к объему памяти ЭВМ невысокий, мас­сив имеет размерность (n+1, n+2).
3.Используется сравнительно небольшое число заранее уста­новленных  параметров: масштабныймножитель />, коэффициент уменьшениямножителя />(если применяется правило2) и параметры окончания поиска.
4.Алгоритм оказывается эффективным даже в тех случаях, когда ошибка вычислениязначений целевой функции велика, по­скольку при его реализации оперируютнаибольшими значениями функции в вершинах, а не наименьшими.
Перечисленныефакторы характеризуют метод поиска по симплек­су как весьма полезный при проведениивычислений в реальном времени.
Алгоритмобладает также рядом существенных недостатков.
1.Не исключено возникновение трудностей, связанных с масштабированием, посколькувсе координаты вершин симплекса за­висят от одного и того же масштабного множителя/>. Чтобы обойти трудноститакого рода, в практических задачах следует промасштабировать все переменные стем, чтобы их значения были сравнимыми по величине.
2.Алгоритм работает слишком медленно, так как полученная на предыдущих итерацияхинформация не используется для уско­рения поиска.
3.Не существует простого способа расширения симплекса, не требующего пересчетазначений целевой функции во всех точках образца. Таким образом, если />по какой-либо причинеуменьшается (например, если встречается область с узким «оврагом» или «хреб­том»),то поиск должен  продолжаться с уменьшенной величиной шага. 4.1.2.Метод поиска Хука-Дживса.
Метод,разработанный Хуком и Дживсом, является одним из первых алгоритмов, в которыхпри определении нового направления поиска учитывается информация, полученная напредыдущих итерациях. По существу процедура Хука—Дживса представляет собойкомбинацию «исследующего» поиска с циклическим изменением переменных иускоряющегося поиска по образцу с использованием определенных эвристическихправил. Исследующий поиск ориентирован на выявление характера локальногоповедения целевой функции и определение направлений вдоль «оврагов». Полученнаяв результате исследующего поиска информация затем используется в процессепоиска по образцу при движении по «оврагам».
Исследующийпоиск.
Дляпроведения исследующего поиска необходимо задать величину шага, которая можетбыть раз­личной для разных координатных направлений и изменяться в про­цессепоиска. Исследующий поиск начинается в некоторой исходной точке. Если значениецелевой функции в пробной точке не превы­шает значения функции в исходнойточке, то шаг поиска рассматри­вается как успешный. В противном случаенеобходимо вернуться в предыдущую точку и сделать шаг в противоположномнаправлении с последующей проверкой значения целевой функции. После пере­боравсех N координат исследующий поиск завершается. Получен­ную в результате точкуназывают базовой точкой.
Поискпо образцу.
Поискпо образцу заключается в реализации единственного шага из полученной базовойточки вдоль-прямой, соединяющей эту точку с предыдущей базовой точкой. Новаяточка образца определяется в соответствии с формулой
/>
Кактолько движение по образцу не приводит к уменьшению целе­вой функция, точка /> фиксируется в качествевременной базо­вой точки и вновь проводится исследующий поиск. Если в резуль­татеполучается точка с меньшим значением целевой функции, чем в точке />, то она рассматриваетсякак новая базовая точка />. Сдругой стороны, если исследующий поиск неудачен, необходимо вернуться в точку /> и провести исследующийпоиск с целью вы­явления нового направления минимизации. В конечном счете, воз­никаетситуация, когда такой поиск не приводит к успеху. В этом случае требуетсяуменьшить величину шага путем введения неко­торого множителя и возобновитьисследующий поиск. Поиск завер­шается, когда величина шага становитсядостаточно малой. После­довательность точек, получаемую в процессе реализацииметода, можно записать в следующем виде:
/>-   текущая базовая точка,
/> — предыдущая базовая точка,
/>-  точка, построенная при движении по образцу,
/> — следующая (новая) базовая точка.
Приведеннаяпоследовательность характеризует логическую струк­туру поиска по методу Хука —Дживса.
Структураметода поиска Хука — Дживса
Шаг 1. Определить:
начальную точку /> ,
приращения />
коэффициент уменьшения шага />,
параметр окончания поиска />.
Ша г 2.  ровести исследующий поиск.
Ша г 3. Был ли исследующий поиск удачным(найдена ли точ­ка с меньшим значением  
целевойфункции)?
Да: перейти к шагу 5.
Нет: продолжать.
Ша г 4. Проверка на окончание поиска.
Выполняетсяли неравенство />?
Да: прекратить поиск; текущая точка аппроксимирует точкуоп­тимума/>.
Нет: уменьшить приращения по формуле
/>
Перейтик шагу 2.
Ша г 5. Провести поиск по образцу:
/>
Шаг6. Провести исследующий поиск, используя /> в ка­честве базовой точки;
пусть/> полученная в результатеточка.
Ша г 7. Выполняется  ли  неравенство />?
Да: положить /> Перейтик шагу 5.
Нет: перейти к шагу 4.
Пример6  Поиск по методу Хука — Дживса
Найтиточку минимума функции  /> используяначальную точку />.
Решение.
Длятого чтобы применить метод прямого поиска.Хука — Дживса,  необходимо задатьследующие величины:
/> векторная величина приращения = />,
/>  коэффициент уменьшения шага = 2,
/> параметр окончания поиска = 10-4.
Итерацииначинаются с исследующего поиска вокруг точки />,которой соответствует значение функции />Фиксируя/>, дадим приращениепеременной />:
/>
/>Успех.
Следовательно,необходимо зафиксировать /> и датьприраще­ние переменной />:
/>
/> Успех.
Такимобразом, в результате исследующего поиска найдена точка
/>
Посколькуисследующий поиск был удачным, переходим к поиску по образцу:
/>
/>
Далеепроводится исследующий поиск вокруг точки />,который оказывается удачным при использовании положительных прираще­нийпеременных х1 и х2. В результате получаем точку
/>
Поскольку/>, поиск по образцу следуетсчитать успеш­ным, и /> становится новойбазовой точкой при следующем про­ведении поиска по образцу. Итерациипродолжаются, пока умень­шение величины шага не укажет на окончание поиска вокрестности точки минимума. Последовательные шаги реализации метода показаны нарисунке.
  Из примера  следует, что метод Хука — Дживса характери­зуется несложнойстратегией поиска, относительной простотой вычислений и невысоким уровнемтребований к объему памяти ЭВМ, который оказывается даже ниже, чем в случаеиспользования ме­тода поиска по симплексу.
/>

Итерациипоиска по методу Хука-Дживса на примере