4.5.4. Методы безусловной оптимизации первого и второго порядка. Методы безусловной оптимизации

Классические методы безусловной оптимизации

ТЕМА

Классические методы безусловной оптимизации

Введение

Как известно, классическая задача безусловной оптимизации имеет вид:

(1) (2)

Существуют аналитические и численные методы решения этих задач.

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

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

1. Необходимые условия для точки локального минимума (максимума)

Пусть т.

доставляет минимальные значения функции . Известно, что в этой точке приращение функции неотрицательно, т.е. . (1)

Найдем

, используя разложения функции в окрестности т. в ряд Тейлора. , (2)

где

, , - сумма членов ряда порядок которых относительно приращений (двум) и выше.

Из (2) имеем:

(3)

Далее предположим, что изменяется только одна переменная из множества переменных

. Например, , тогда (3) преобразуется к виду: (4)

Из (4) с очевидностью следует, что

(5)

Предположим, что

, тогда (6)

С учетом (6) имеем:

. (7)

Предположим, что

положительно, т.е. . Выберем при этом , тогда произведение , что противоречит (1).

Поэтому, действительно,

очевиден.

Рассуждая аналогично относительно других переменных

получаем необходимое условие для точек локального минимума функции многих переменных (8)

Легко доказать, что для точки локального максимума необходимые условия будут точно такими же, как и для точки локального минимуму, т.е. условиями (8).

Понятно, что итогом доказательства будет неравенство вида:

- условие неположительного приращения функции в окрестности локального максимума.

Полученные необходимые условия не дают ответ на вопрос: является ли стационарная точка

точкой минимума или точкой максимума.

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

2. Достаточные условия для точки локального минимума (максимума)

Представим разложение функции

в окрестности точки в ряд Тейлора с точностью до квадратичных по слагаемых. (1)

Разложение (1) можно представить более кратко, используя понятие: "скалярное произведение векторов" и "векторно-матричное произведение".

(1') - матрица двух производных от целевой функции по соответствующим переменным. ,

Приращение функции

на основании (1') можно записать в виде: (3)

Учитывая необходимые условия:

, (4)

Подставим (3) в виде:

(4') (5)

Квадратичная форма

называется дифференциальной квадратичной формой (ДКФ).

Если ДКФ положительно определена, то

и стационарная точка является точкой локального минимума.

Если же ДКФ и матрица

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

Итак, необходимое и достаточное условие для точки локального минимума имеют вид

(эти же необходимые условия можно записать так: , , ) - достаточное условие.

Соответственно, необходимое и достаточное условие локального максимума имеет вид:

, (), .

Вспомним критерий, позволяющий определить: является ли квадратичная форма и матрица, ее представляющая, положительно определенной, или отрицательно определенной.

3. Критерий Сильвестра

Позволяет ответить на вопрос: является ли квадратичная форма и матрица, ее представляющая, положительно определенной, или отрицательно определенной.

Далее изложение будет относительно ДКФ и матрицы

ее определяющей, т.е. ДКФ вида . , - называется матрицей Гессе.

Главный определитель матрицы Гессе

mirznanii.com

Методы безусловной оптимизации

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

Вятский государственный университет

Вечерне-заочный факультет

Решение задач многомерной оптимизации

Пояснительная записка

Курсовая работа по дисциплине

«Методы оптимизации»

ТПЖА.220201.623 ПЗ

Разработал студент гр. 21-УТ _________________________________ / Фандеев Е.А./

(подпись)

Руководитель работы _________________________________ / Микрюкова В.И./

(подпись)

Киров 2012

Содержание

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

1 Методы безусловной оптимизации…………….…………………..….............................4

1.1 Методы прямого поиска…..…….....…………………………………………......4

1.1.1 Нахождение стационарной точки…………………………………….4

1.1.2 Метод поиска по симплексу………………………..............................5

1.1.3 Метод Хука-Дживса…………………………………………………...12

1.1.4 Метод сопряженных направлений Пауэлла………………………….17

1.2 Градиентные методы………………………….…………………........................21

1.2.1 Метод Коши……………………………………………………………21

1.2.2 Метод Ньютона………………………………………………………..24

1.2.3 Метод сопряженных градиентов ……………...................................25

1.2.4 Квазиньютоновский метод.………………….....................................28

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

Список литературы………………………………………………………………………….31

Введение

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

Задачи нахождения оптимального решения являются самыми распространенными на сегодняшний день. Из-за увеличения объемов производства, люди вынуждены решать сколько потратить ресурсов на тот или иной проект, ведь на все задуманное ресурсов стало не хватать. Во многих странах производится строгий учет потребления природных и человеческих ресурсов, а следовательно необходимо каждый день находить новые способы решения задач по оптимизации различных процессов. Особо остро стоит проблема коммуникаций в городах. Под коммуникациями можно рассматривать не только телефоны, факсы и прочие устройства, но также и транспортные коммуникации и компьютерные сети. Для последних особенно характерна проблема «трафика», так как существующие линии не способны обеспечить передачу необходимых объемов информации.

Оптимальная задача – экономико-математическая задача, содержащая критерий оптимальности и ограничения, то есть направленная на поиск лучшего в определенных условиях (оптимального) значения показателя.

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

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

Данная работа рассматривает некоторые методы нахождения безусловного экстремума (метод Коши, Хука-Дживса, Ньютона и др.) для функции двух переменных.

1 Методы безусловной оптимизации

Методы прямого поиска

1.1.1 Нахождение стационарной точки

Целевая функция:

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

Найдем для данной целевой функции частные производные

по и :

Приравняв полученные выражения к нулю, получим систему уравнений:

Решение системы уравнений даёт результат:

Таким образом, экстремум целевой функции является точка с координатами х* = Т, значение целевой функции, в которой: .

Для определения характера стационарной точки составим определитель матрицы Гессе. Под определителем Гессе понимается определитель, составленный из вторых производных исходной целевой функции.

Так как гессиан функция - положительно определенная матрица (выполняются условия Сильвестра: все диагональные элементы матрицы Гессе - положительные величины, все ведущие главные определители положительные величины), стационарная точка является точкой минимума.

Рисунок.1-Линии уровня функции и стационарная точка

1.1.2 Метод поиска по симплексу

Суть метода заключается в исследовании целевой функции в вершинах некого «образца», построенного в пространстве переменных вокруг «базовой» точки. Вершина, давшая наибольшее значение целевой функции отображается относительно двух других вершин и таким образом становится новой базовой точкой, вокруг которой строится новый образец и снова выполняется поиск. В рассматриваемом методе таким образцом является регулярный симплекс. В случае двух переменных симплексом является равносторонний треугольник, в трёхмерном пространстве – тетраэдр.

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

Процедура продолжается до тех пор, пока не будет накрыта точка минимума.

Некоторые правила:

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

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

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

При заданной начальной точке х(0) и масштабном множителе a, координаты остальных N вершин симплекса в N–мерном пространстве вычисляются по формуле:

xj(0) + d1, если i = j;

x(i) =

xj(0) + d2, если i ¹ j.

Приращения d1 и d2 определяются по формулам:

Величина α выбирается исследователем, исходя из характеристики решаемой задачи. При α=1 ребро симплекса имеет единичную длину.

Вычисление центра тяжести:

Если х(i) – точка, подлежащая отражению, то координаты центра тяжести определяется по формуле:

Координаты новой вершины удовлетворяют уравнению

xнов( j ) = x( j ) + λ·(xc – x( j )).

Для того, чтобы симплекс обладал свойством регулярности, отображение должно быть симметричным, т.е. λ = 2.

xнов( j ) = 2·xc – x( j )

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

Нахождение минимума целевой функции симплекс-методом

Задание:

Найти минимум функции

Решение:

Для построения исходного симплекса необходимо задать начальную точку и масштабный множитель. Пусть .

Тогда:

Вычисляем координаты двух других вершин симплекса

Значения целевой функции в этих точках соответственно равны:

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

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

В полученной точке . Новый симплекс образован вершинами , причём точке соответствует максимальное значение целевой функции. Следует отразить точку относительно центра тяжести точек и .

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

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

Уменьшаем размер симплекса.

В качестве новой базисной точки, примем точку . Вычислим координаты остальных двух вершин базиса:

stud24.ru

Методы безусловной оптимизации - Справочник химика 21

Методы безусловной оптимизации [c.79]

Интерактивный режим позволяет пользователю выбрать вариант постановки задачи термоэкономической оптимизации (из заданной пользователем совокупности критериев оптимальности и соответствующих наборов оптимизирующих переменных) выбрать варианты расчета технологических подсистем (по уровню детализации моделей) выбрать вариант расчета каждой из энергетических подсистем (эксергетическая производительность подсистемы, обобщенная термоэкономическая модель подсистемы данного типа, традиционная математическая модель) выбрать метод безусловной оптимизации из имеющихся в библиотеке и задать его параметры выбрать и задать параметры метода условной оптимизации применить метод декомпозиционной релаксации, сократив число оптимизирующих переменных провести выборочное сканирование области поиска по одной или группе переменных выбрать варианты печати результатов моделирования в начальной и конечной точке поиска, промежуточных результатов оптимизации. [c.418]

Поиск локального оптимума методами безусловной оптимизации. [c.536]

Основное преимущество рассмотренного метода по сравнению с методом динамического программирования состоит в том, что при вычислительном процессе не требуется запоминания в ЦВМ про- межуточных результатов счета на каждом шаге итерационного процесса. Однако динамическое программирование неизбежно обеспечивает онределение глобального экстремума, в то время как описанный метод позволяет находить лишь стационарное значение функции цели. Еслп же эта функция имеет не один экстремум, решение с помощью данного метода значительно усложняется, поскольку приходится исследовать всю область, где определен критерий оптимизации, для нахождения глобального экстремального значения. К тому же вид уравнений (VI,32) определяет безусловный экстремум функции цели, что не характерно для реальных ХТС, в которых всегда существуют ограничения технологического характера. [c.311]

Рассмотрим методы безусловной оптимизации (блок Е), использующие итерационные процедуры, которые характеризуют [c.178]

Дэннис Дж., Шнабель P. Численные методы безусловной оптимизации и решения нелинейных уравнений Пер. с англ. М. Мир, 1988. 440 с. [c.557]

Рассмотрим алгоритмы оптимизации ХТС, не учитывающие ограничения на варьируемые параметры. Конечно, в любой практической задаче существуют ограничения на эти параметры. Однако на методах безусловной минимизации имеет смысл остановиться по следующим причинам [c.79]

Рассмотрим теоретически некоторые особенности совместного применения методов уровней и штрафов и квадратичных методов безусловной минимизации, ориентируясь на эффективность алгоритма оптимизации в целом. Результаты такого рассмотрения могут оказаться полезными при анализе практического применения этих алгоритмов в каждом конкретном случае. [c.122]

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

Соотношения (I, 10) учитываются с помощью методов условной минимизации. Таким образом, в данном случае процедура оптимизации ХТС является трехуровневой (рис. 20) первый соответствует решению системы уравнений материального и теплового баланса схемы — системы (I, 65) — при фиксированных значениях поисковых переменных и, на втором переменные и изменяются в соответствии с каким-либо методом безусловной минимизации [возможно, учитывающим ограничения (I, 9) ], т р е т и й соответствует изменению штрафного коэффициента в методе условной минимизации, который используется для выполнения ограничений (I, 10). [c.127]

В случае отсутствия ограничений (I, 10) для решения задачи 1 могут быть использованы методы безусловной минимизации, модифицированные для учета простейших ограничений (I, 9), и оптимизационная процедура будет состоять только из 1-го и 2-го уровней (рис. 20). В этом большое преимущество данного метода. Введение же ограничений (I, 10) существенно усложняет задачу, поскольку вследствие этого придется применять методы условной минимизации (появляется третий уровень в численной процедуре оптимизации). [c.127]

Настоящая задача преобразована в последовательность задач безусловной оптимизации с целевыми функциями, использующими квадратичные штрафы [2]. Алгоритм решения каждой из таких задач работал по методу градиентного спуска [3]. Компоненты вектора рассчитьшались по первым разностным аппроксимациям производных целевой функции. При расчете Х( , Р) использовался метод Рунге-Кутта четвертого порядка с автоматическим выбором шага интегрирования по заданной абсолютной погрешности вычислений (ш = 10- ). [c.89]

Анализ приведенных способов выбора шага в градиентном методе спуска к точке минимума не позволяет сделать однозначного заключения о безусловных преимуществах какого-либо одного из них. Причины этого достаточно очевидны. С одной стороны, от выбранного способа определения шага зависят сходимость вычислительного процесса, выражающаяся через число шагов, необходимых для достижения точки оптимума, и соответственно время счета на ЭВМ. С этой точки зрения более целесообразными являются два последних из рассмотренных способов, обеспечивающие решение задачи оптимизации за минимальное число шагов. Но, с другой стороны, эти последние способы определения шага весьма сложны и могут потребовать значительного времени для расчета на ЭВМ собственно шага. Поэтому выбор способа определения шага должен осуществляться в каждом конкретном случае решения той или иной задачи с учетом инженерной специфики объекта оптимизации, объема задачи, требований к точности решения, характеристик используемой ЭВМ и других факторов. [c.133]

Способы выбора длины шага при покоординатном спуске совпадают со способами, рассмотренными применительно к градиентному методу. Последовательность, в которой выбираются координатные оси, может быть различной. Обычно они берутся в фиксированном циклическом порядке (чаще всего просто поочередно). Иногда вначале определяется, какие из переменных X,, Х2, хз,. .., х оказывают большее влияние на изменение функции цели 3, в соответствии с чем и строится последовательность спуска по отдельным параметрам. Такое предварительное исследование и расстановка параметров в порядке их значимо сти безусловно повышают эффективность метода, улучшая его сходимость. Однако указанное предварительное исследование в свою очередь требует определенного усложнения алгоритма оптимизации и дополнительного времени счета на ЭВМ. [c.134]

Присутствие ограничений первой группы существенно усложняет задачу оптимизации и требует применения наиболее универсальных методов решения задач с ограничениями — методов последовательной безусловной минимизации. Эти методы изложены в следующем разделе. С другой стороны, если в задаче имеются только линейные ограничения второго типа, то здесь более эффективными могут оказаться методы оптимизации, специально разработанные на случай наличия линейных ограничений. Такие методы рассмотрены в последнем разделе данной главы. [c.144]

Установленный таким образом факт, что точка 2 (х ) есть крайняя точка пересечения оси О/ с множеством Л, позволяет сформулировать для ее определения некоторые задачи оптимизации в пространстве 2 значений функций критерия и ограничений. Методы решения этих задач, как увидим, и составляют суть так называемой последовательной безусловной минимизации. [c.146]

Решение задачи оптимизации. Задача оптимизации, сформулированная как задача определения условного экстремума функции девяти переменных, сводится к задаче на безусловный экстремум с помощью метода уровней (см. гл. IV). Целевая функция в данном случае будет иметь вид [c.174]

Задачи оптимизации проектирования процессов полимеризации еще только начинают решаться. Пока известен лишь один процесс инициированной полимеризации стирола, интенсивное исследование которого ведется практически параллельно в ряде стран. Этот процесс полностью спроектирован с использованием методов математического моделирования. Число таких процессов безусловно будет расти, как и доля расчетов с использованием моделей при проектировании полимеризационных установок. Переход от традиционных эмпирических методов проектирования к математическим задерживается по следующим причинам ввиду отсутствия математических моделей ряда процессов, особенно для учета изменения качественных показателей вследствие неприспособленности многих моделей для решения проектных задач, ибо они не содержат легко трансформируемых элементов (например, при смене типа реактора требуется создание новой модели) из-за отсутствия соответствующего математического и алгоритмического обеспечения для решения задач проектирования, учитывающего необходимость использования вычислительной техники. [c.133]

Результаты оптимизации контактного аппарата с помощью метода уровней (цо = —1,2 = а,, = 10" = 10" = = Ю ) на основе различных алгоритмов безусловной минимизации приведены в табл. 31. Начальная точка выбрана следующей (а1,. . ., а,) = (0,061538 0,6462 0,0923 0,95 0,61389 0,0923) разрывные переменные — = 363 (°С) он = 444 =501 2 (т ) = 0,97. Соотношения (IV,82) при таком выборе значений разрывных переменных не выполнены. Отметим, что общая [c.186]

Итак, в данном случае поиск ведется в пространстве перченных и, х при каждом фиксированном значении переменных и, х переменные х находятся из системы уравнений (, 80), а ограничение (I, 81) удовлетворяются с помощью методов условной минимизации. Преимущества и недостатки сведения задачи оптимизации ХТС к сформулированным задачам будут рассмотрены нами в гл. IV после изучения методов условной и безусловной минимизации. Здесь мы только отметим, что в большинстве случаев задача оптимизации ХТС сводится либо к задаче 1, либо (реже) к задаче 4. [c.24]

В СВЯЗИ С ЭТИМ потребуются специальные меры, для получения разреженного гессиана. Воспользуемся подходом, при котором оптимизация ХТС сводится к задаче 1 [см. соотношения (I, 64)—(I, 66)]. В этом случае число поисковых переменных равно г [см. выражение (1,52)]. Для учета ограничений на выходные переменные применим один из методов последовательной безусловной минимизации (для определенности —метод штрафа ). Тогда модифицированный критерий будет иметь вид [c.172]

В случае задания распределения расходов задача оптимизации параметров МКС перестает быть многоэкстремальной и становится задачей выпуклого программирования. Для ее решения при учете ограничений только в виде равенств (законов Кирхгофа) можно воспользоваться классическими методами условной и безусловной минимизации. Именно подоб- [c.169]

Если обратиться к математическим методам оптимизации, которые могут быть применены для решения сформулированных выше сетевых задач на условный и безусловный экстремум с вогнутой или более сложной многоэкстремальной минимизируемой функцией, то их можно разбить на следующие три группы [c.183]

Книга посвящена проблеме оптимизации, имико-технологических процессов, возникающей при проектировании новых процессов и интенсификации действующих производств, а также при разработке автоматизированных систем управления технологическими процессами (АСУ ТП). Б ней рассматриваются основные этапы этой задачи (расчет стационарных режимов химико-технологических систем, методы безусловной минимизации, алгоритмы учета ограничений), приводятся многочисленные примеры использования описанных методов при решении тестовых и реальных задач оптимизации химико-технологиче-ских процессов. Большое внимание уделено проблеме синтеза хнмико-технологических систем — новому и быстро развивающемуся разделу теории математического моделирования. [c.2]

Предположим, что ХТС разбита на подсистемы (блоки), каждая из которых описывается уравнениями типа 2.34—2.48. Для оптимизации ХТС может быть выбран, например, двухуровневый декомпозиционный метод. Первому уровню будет соответствовать алгоритм локальной оптимизации отдельных блоков ХТС, а второму уровню - алгоритм коррекции локальных задач оптимизации. При решении задачи оптимизации необходимо прежде всего учесть взаимное влияние блоков ХТС при проведении оптимизации отдельных частей или подсистем на первом уровне. Для этого можно использовать алгоритм, который сводит задачи условной минимизации к последовательности задач безусловной минимизации. [c.77]

В большинство общепринятых алгоритмов метода наименьших квадратов для расчета констант устойчивости входит уравнение (5.9) алгоритмы основаны на методах Ньютона — Гаусса — Рафсона. Эти методы подразделяются на две группы в зависимости от способа, которым обеспечивается уменьшение суммы квадратов 5 на каждой итерации. В первой группе масштабная корректировка или оптимизация поправочного вектора выполняется таким образом, чтобы обеспечить максимальное уменьшение S на каждой итерации. Это безусловно обеспечивает сходимость. [c.91]

Без удобрений высокую производительность сельского хозяйства обеспечить невозможно, но для исключения вредных последствий их применения оно должно регулироваться результатами научных и практических исследований и координироваться с другими агротехническими мероприятиями. Тезис — чем больше удобрений, тем лучше — безусловно вреден. Удобрения должны использоваться в оптимальных дозах при сбалансированных соотношениях питательных веществ, зависящих от вида и сорта растения, его потребности в тех или иных элементах питания, от вида почвы, от водного режима, климата и многих других условий. Важен и правильный выбор сроков и методов внесения удобрений. Именно множество таких условий и делает задачу оптимизации применения удобрений очень сложной. Но эта задача должна быть решена агрохимической наукой. [c.23]

Рассмотрим основные подходы к решению задач оптимизации и этапы, на которые распадается процесс решения. Основное внимание уделим пояснению логической сущности тех или иных методов и практической методике их использования. Остановимся только на методах решения задач условной оптимизации в предположении, что читатель знаком с основными понятиями и подходами к оптимизации безусловной. [c.47]

В табл. 26 приведены результаты сравнения двух способов вычисления производных целевой функции [критерий (IV, 147) ]. Использовались следующие три метода безусловной оптимизации без-градиентный Гаусса—Зейделя, наиекорейшего спуска и ОРР. Применение метода сопряженного процесса позволяет сократить число вычислений целевой функции приблизительно в четыре раза. Для учета ограничений использовался метод штрафов, при котором проводилась безусловная минимизация функции (IV, 47) для некоторой последовательности значений параметров а, где г —номер итерации метода штрафов (г = О, 1,2,. ..) а = да [c.162]

В книге рассмотрены лишь задачи условной оптимизации, при этом предполагалось, что основные сведения, связанные с определением безусловного максимума функции, читателю известны. Часть книги (гл. 1—3) посвящена понятию о расши-рении экстремальных задач и демонстрации возможностей его использования в задачах условной оптимизации функций и функционалов, другая часть (гл. 4, 5) — применению методов оптимизации к расчету оптимальных режимов аппаратов в классе нестационарных установившихся режимов (циклических). [c.5]

Одно из направлений научного управления в добыче газа — применение методов оптимизации для поиска оптимальных режимов эксплуатации установок газопромысловой технологии. Данное направление, безусловно, относится к перспективным, поскольку экономически оправдано, так как в процессе эксплуатации объектов ГДП система управления стремится к достижению поставленной перед ней цели. Одновременно повышается оперативность принятия решений по управлению установками обработки природного газа и ГДП в целом. Такой принцип многоуровневого управления базируется на системном подходе, позволяющем увязать локальные критерии управления процессами газопромысловой технологии таким образом, чтобы реализовывался глобальный критерий оптимальности ГДП. Сформулированные задачи оптимизации относятся к классу задач оптимального управления качеством промысловой обработки природного газа, которое должно удовлетворять требованиям ОСТ 51.40—83. В связи с этим один из важнейших путей повышения качества промысловой обработки газа — создание на ГДП автоматизированных систем управления технологическими процессами (АСУ ТП), позволяющих на базе широкого применения средств вычислительной техники, систем телемеханики и средств автоматизации решать задачи оптимизации процессов газопромысловой технологии. Поскольку обустройство ГДП в настоящее время осуществляется индустриальными методами на основе типовых блочно-модульных автоматизированных технологических установок, то расчеты, проводимые в промысловых условиях, тоже носят типовой характер. Приведенные в книге алгоритмы оптимизации являются типовыми как по постановкам задач, так и по алгоритмам их решения, что в значительной мере сокращает сроки внедрения их на тех ГДП, где эксплуатируются ЭВМ. [c.193]

Другим примером может послужить выбор шага, т. е. величины коэффициента в соотношении (I, 39) при линейном поиске в методе безусловной минимизации, т. е. на втором уровне (см. рис. 20). При применении методов безусловной оптимизации справедливо следующее чем больше шаг вдоль направления, тем лучше. В том случае, когда первый уровень (расчет схемы) является безытерационным (з адача 4), это справедливо и для многоуровневых процедур. В случае, когда первый уровень (расчет схемы) является итерационным (задача 1 для замкнутой схемы), это правило, вообще говоря, неверно. Действительно, при увеличении шага вдоль поискового направления действуют следующие противоположно направленные тенденции. С одной стороны увеличение шага вдоль направления дает хорошие результаты, поскольку уменьшается число итераций на втором уровне, но с другой стороны, увеличение шага ухудшает начальное приближение при решении системы (1, 65), что может привести к уве-л ичению числа итераций на первом уровне. (При очень большом шаге квазиньютоновский метод на этом уровне вообще может перестать сходиться.) Должен существовать некоторый компромисс, при котором шаг вдоль направления будет наилучшим с точки зрения общего числа итераций на первом и втором уровнях. [c.130]

Во втором разделе излагаются. методы решения задач опти изации, которые обычно называются методами нелинейного программирования, связанные с решением задач как условной, так и безусловной оптимизации функций. многих переменны х. При этом и целевая функция и ограничения нелинейньг по независимым переменны.м. При изложении этого раздела мы в основном придерживаемся работ [4 , 5], [6]. [c.4]

В системе предусмотрено оперативное вмешательство в ход вычислений путем внешних прерываний с инженерного пульта ЕС ЭВМ, обработка которых позволяет выйти на режим диалога и изменить параметры задания на оптимизацию например, сменить метод бузусловной минимизации, провести декомпозиционную релаксацию области поиска, вывести на печать более полную информацию о моделируемой ЭТС и т. п. Библиотеки алгоритмов условной и безусловной минимизации построены по принципу взаимного дополнения включенных в них методов, что позволяет в каждом конкретном случае выбрать метод, наиболее адекватный решаемой задаче. [c.420]

Присутствие ограничений первой группы существенно усложняет задачу оптимизации. В этой главе будут рассмотрены методы последовательной безусловной минимизации и методы с непосредственным учетом ограничений. Последние представлены методом обобщенного приведенного градиента (МОПГ) и рядом методов с линейными ограничениями. [c.106]

ПОТОК возвращаемый на вход схемы с выхода блока изомеризации. Рецикл можно учесть двумя способами на уровне расчета схемы при итерациях по Xi [см. задачу 1, выражения (I, 64)—(I, 66) ] и при оптимизации, рассматривая его как ограничение типа равенства на разрываемую переменную Xi [см. задачу 4, выражения (I, 79)— (1,81)]. При решении был применен второй способ. Оптимизация проводилась с применением методов последовательной безусловной минимизации метода модифицированной функции Лагранжа (AL) и штрафных функций (PEN), на нижнем уровне которых использовались квазиньютоновские алгоритмы DFP, SSVM. Расчет производных выполнялся разностным способом [см. выражение (1,49)]. В процессе оптимизации для удержания значений варьируемых переменных Xi (напомним, что лг — коэффициенты разделения газовых потоков) между нулем и единицей применялись замены переменных с использованием функции ar tg. Функции, участвующие в постановке задачи оптимизации, наиболее чувствительны (в окрестности л ) к изменению Xi, Xs, л ,. В связи с этим для повышения стабильности получаемых результатов применялось преобразование сжатия по осям л .,, Xi, Xj, Хв, что можно сравнить с процедурой [11, с. 82—83]. В табл. 23 приведены результаты решения рассматриваемой задачи [c.140]

Эквивалентная задача (впрочем, как и исходная) представляет собой задачу на условный экстремум, для решения которой использовалась условная оптимизация метод уровней и метод модифицированной функции Лагранжа. Для выполнения безусловной минимизации составной функции (нижний уровень оптимизации) применялись методы квазиньютоновского типа — DFP, BFGS, SSVM [см. (III, 81), (111,84)1. Расчет производных минимизируемой функции выполнялся как аналитически — с привлечением сопряженного процесса [3, с. 142], так и методом конечных разностей, что позволило провести сравнение результатов оптимизации по эффективности и точности решения . [c.146]

Задачи общего вида минимизировать (максимизировать) /( ) при указанных ограничениях, наэ. оптимизац. задачами с ограничениями, или задачами условной О. Задачи, в к-рых ограничения отсутствуют, носят назв. задач без ограничений, или задач безусловной О. Последние особенно важны, поскольку мн. методы решения условных задач основаны на сведении их к безусловным. [c.390]

Конкретный вид функции Р Х, Р) следует согласовывать с методами минимизации ее, т. е. учитывать гладкость штрафа, простоту вычисления функций и ее производных, свойства выпуклости и т.д. Уязвимой стороной метода является овражность функции Р Х, р), даже если исходная функция для критерия оптимизации 1 Х) не имела оврагов , что существенно затрудняет задачу поиска оптимальных параметров. Из других приемов сведения к задаче безусловного экстремума упомянем методы уровней и множителей Лагранжа [20]. [c.152]

Рассмотренный метод расчета новых и оптимизации существующих полимеризационных процессов на основе ряда эмгарических и полуэмпирических данных путем моделирования на ЭВМ, безусловно, представляет интерес как инженерный метод расчета. Особую ценность он должен иметь при проектировании новых процессов с недостаточно изученным механизмом. Если в приведенном примере характеристика свойств продукта сведена к минимуму (учитывался только средневязкостный молекулярный вес), то в общем случае число параметров, характеризующих свойства, может быть увеличено. [c.321]

chem21.info

4.5.3. Методы безусловной оптимизации

Введем следующие обозначения: X[i,k] – вектор координатi-йвершины многогранника наk-мшаге поиска,i=1,2,…n+1,k=1,2,…;h – номер вершины, в которой значение целевой

функции максимально: f (X[h,k])= maxf (X[i,k]);l		– номер вер-
i
шины, в которой значение целевой	функции	минимально:
f (X[h,k])= minf (X[i,k]);X[n+2,k] –	центр тяжести всех вер-
i

шин, за исключением X[h,k]. Координаты центра тяжести вычис-

	xj [n+ 2,k]=	1	n+1
ляют по формуле	xj [n+ 2,k]=	1	∑xj [i,k]− xj [h,k]	, j=1,2,…n.
		n
			j=1

Примерный алгоритм метода деформируемого многогранника состоит в следующем:

1.Задаются коэффициентами отражения α, растяженияγ>1, сжатияβ<1, допустимой погрешностью определения координат

точки минимума ε. Выбирают координаты вершин исходного многогранникаX[i,k],i=1,2,…n+1,k=1.

2.Вычисляют значения целевой функции во всех вершинах f(X[i,k]),i=1,2,…n+1, и находят точкиX[h,k],X[l,k] (на рис. 28,б точки соответственноX2 иX1), а такжеX[n+2,k].

3.Осуществляют проецирование точки X[h,k] через центр тя-

жести: X[n+3,k]=X[n+2,k]+α(X[n+2,k]–X[h,k]).

4.Если f(X[n+3,k])≤X[l,k], выполняют операцию растяже-

ния: X[n+4,k]=X[n+2,k]+γ(X[n+3,k]–X[n+2,k]).В противном случае переходят к п. 6.

5.Строят новый многогранник: если f(X[n+4,k])<X[l,k], то

заменой X[h,k] наX[n+4,k], в противном случае – заменойX[h,k] наX[n+3,k]. Продолжают вычисления с п. 2 приk=k+1.

6. Если X[h,k]>f(X[n+3,k])>X[i,k] для всехi, не равныхh,

выполняют операцию сжатия: X[n+5,k]=X[n+2,k]+β(X[h,k]–X[n+2,k]). Строят новый многогранник заменойX[h,k] наX[n+5,k] и продолжают вычисления с п. 2 приk=k+1.

7. Если f(X[n+3,k])>X[h,k], то, сохраняя вершинуX[l,k], строят новый многогранник, подобный текущему, уменьшением длин всех ребер в два раза:X[i,k]=X[l,k]+0,5(X[i,k]–X[l,k])и продолжают вычисления с п. 2 приk=k+1.

В пп. 6, 7 перед переходом к п. 2 необходима проверка выполнения условия завершения поиска минимума, например, по усло-

studfiles.net

6.7. Методы безусловной оптимизации

программирования общего вида (116) не существует. В САПР поиск глобального экстремума осуществляется путем локальной оптимизации из нескольких исходных точек, выбираемых случайным образом в пределах области, задаваемой прямыми ограничениями. В многоэкстремальных задачах возможно получение нескольких локальных экстремумов, из которых выбирается наилучший. Вероятность определения глобального экстремума при подобном подходе тем меньше, чем меньше объем области притяжения глобального экстремума. Малый объем этой области, как правило, свидетельствует о низкой стабильности выходных параметров в точке экстремума, следовательно, глобальный экстремум может оказаться малополезным. Поэтому оптимизация на основе небольшого числа вариантов локального поиска является достаточной.

Способ выбора направления поиска gk является определяющим для методов безусловной оптимизации, которые бывают нулевого, первого и второго порядков. Вметодах нулевого порядка для определенияgk производные целевой функцииF(X ) по управляемым параметрамХ не используются. Вметодах первого и второго порядков используются соответственно первые и вторые производныеF(X ) поХ.

Способ выбора величины шага hk бывает двух видов. В способе

оптимального шага на каждом				k -мшаге поиска экстремума исходной задачи
min F(X )		решается вспомогательная задача одномерной оптимизации:
x		решается вспомогательная задача одномерной оптимизации:
				min F(X k 1 hk gk ).	(130)
				hk
	Решением (130) является оптимальная величина шага				hk,
минимизирующая F(X )			на луче, выходящем в направлении gk из точкиX k 1.
В	способе задаваемого		шага	величина hk является постоянной на	всей

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

Нормирование управляемых параметров осуществляется способом логарифмической нормализации параметров

	uiln(xi/ i)				(131)
или способом линейной нормализацииui x i / i , где ui и x i					– соответственно
нормализованный	и ненормализованный		управляемый	параметр; i –
константа, равная единице измерения величины				x i .	Преимущество
логарифмической	нормализации	–	оперирование		относительными

приращениями параметров.

В качестве условия попадания в заданную окрестность оптимальной точки Х* принимается условие малости расстояния, на которое произошло продвижение в пространстве управляемых параметров в результате последнихr шагов. Это расстояние является нормой разности векторов нормированных

управляемых параметров U k иU k r :
	U kU k r	,	(132)

где – заданная положительная константа.
Критерием прекращения поиска являются условия (132) и			hk hmin , где

hmin – нижний пределhk в способе задаваемого шага. Вместо (132) иногда

используется F(X k ) F(X k r ) .

(133)

6.7.1. Методы нулевого порядка

Стратегия поиска в методах нулевого порядка основывается на переборе ограниченного множества избранных направлений поиска или на случайном выборе.

Метод покоординатного спуска (метод Гаусса Зейделя) характеризуется тем, что в нем избранное множество направлений поиска составляют направления вдоль n координатных осей пространства управляемых параметров. Для определенияhk используется способ оптимального шага. В условии (132)r принимается равнымn, т.е. поиск заканчивается, если в цикле изn шагов вдоль каждой из координатных осей пройдено расстояние, меньшее . Метод покоординатного спуска малонадежен. Так, если целевая функция имеет овражный характер и линия дна оврага не параллельнакакой-либоиз координатных осей, то все разрешенные направления (вдоль координатных осей) в точках дна оврага могут оказаться неудачными – вести по склону оврага вверх. Например, из точкиА (рис.46) невозможно продолжать покоординатный спуск, хотя она находится далеко от точки минимумаХ*. Числами8, 10, 12, 14 отмечены значения целевой функции, соответствующие линиям равного уровня.

A 141210

studfiles.net

4.5.4. Методы безусловной оптимизации первого и второго порядка

Вектор-градиентнаправлен в сторону наискорейшего возрас-

тания функции в данной точке. Вектор – f(X[k]), противоположный градиенту, называется антиградиентом и направлен в сторону наискорейшего убывания функции. В точке минимума градиент функции равен нулю. На свойствах градиента основаны методы поиска первого порядка, называемые также градиентными методами минимизации.

Очевидно, что если нет дополнительной информации, то из точки X[k] разумно перейти в точкуX[k+1], лежащую в направлении антиградиента. Это приводит к итерационному процессу вида

X[k+1]=X[k]–ak . f(X[k]), гдеa>0 – шаг,k=0,1,2,...

В координатной форме этот процесс записывается следующим образом:

x	[k+1]= x[k]− a		∂f	X = X[k]	, i=0,1,...,n;k=0,1,2,...
x	[k+1]= x[k]− a		∂x		, i=0,1,...,n;k=0,1,2,...
i	i	k	∂x
			i

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

X[k +1]− X k ≤ ε , либо выполнение условия малости градиента

f (X[k +1]) ≤ γ . Здесьε иγ – заданные малые величины. Возмо-

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

Градиентные методы отличаются друг от друга способами выбора величины шага ak .

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

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

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

studfiles.net

4.5.4. Методы безусловной оптимизации первого и второго порядка

Вектор-градиентнаправлен в сторону наискорейшего возрас-

X[k+1]=X[k]–ak . f(X[k]), гдеa>0 – шаг,k=0,1,2,...

В координатной форме этот процесс записывается следующим образом:

x	[k+1]= x[k]− a		∂f	X = X[k]	, i=0,1,...,n;k=0,1,2,...
x	[k+1]= x[k]− a		∂x		, i=0,1,...,n;k=0,1,2,...
i	i	k	∂x
			i

X[k +1]− X k ≤ ε , либо выполнение условия малости градиента

f (X[k +1]) ≤ γ . Здесьε иγ – заданные малые величины. Возмо-

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

Градиентные методы отличаются друг от друга способами выбора величины шага ak .

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

studfiles.net