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

• Название: Нелинейное программирование
• Дата: 21.12.2022
• Размер: 220.65 Kb.
• Имя файла: kazedu_132142.docx
• Тип: Реферат; #857585
• страница: 5 из 7

4. Функции нескольких переменных

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

Сначала рассмотрим вопрос анализа «в статике» с использова­нием положений линейной алгебры и дифференциального исчисле­ния, а также условия, которые (в достаточно общих возможных ситуациях) позволяют идентифицировать точки опти­мума. Такие условия используются для проверки выбранных точек и дают возможность выяснить, являются ли эти точки точками ми­нимума или максимума. При этом задача вы­бора указанных точек остается вне рамок проводимого анализа; основное внимание уделяется решению вопроса о том, соответствуют ли исследуемые точки решениям многомерной задачи безусловной оптимизации, в которой требуется минимизировать f(x) x при отсутствии ограничений на x, где x — вектор управляемых переменных размерности n, f — скалярная целевая функция. Обыч­но предполагается, что x_i (для всех значений 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) поиск по симплексу, или S²-метод;

2) метод поиска Хука—Дживса;

3) метод сопряженных направлений Пауэлла.

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