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

loading="lazy" src="http://xreferat.ru/image/33/1305949582_97.gif" alt="Нелинейное программирование" width="18" height="26" align="BOTTOM" border="0" /> не обязательно равна нулю, однако Нелинейное программирование, так как Нелинейное программирование. Таким образом,Нелинейное программирование для всех значений Нелинейное программирование.

Для того чтобы определить знак Нелинейное программирование (неявной цены, ассоциирован­ной с ограничением Нелинейное программирование), следует увеличить правую часть ограничения от 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

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

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: