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

Задача нелинейного программирования формулируется следующим образом: найти вектор X = (x₁,x₂,...,x_n), удовлетворяющий системам ограничений

56

и доставляющий экстремум функции

Системы ограничений (1),(2) могут быть линейными и нелинейными, функция (3) является нелинейной.

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

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

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

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

Однако для метода Хука-Дживса характерны большие затраты времени на поиск экстремума функции.

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

где- текущее приближение к точке экстремума;

- величина шага;

- направление поиска;

■ следующее приближение к точке экстремума.

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

где⁾ - вектор-столбец первых производных;

- вектор-столбец приращений переменных;

симметричная матрица вторых производных (гессиан) функции;

- сумма производных, начиная с третьего порядка и выше.

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

и второе слагаемое в (5) принимает вид

Тогда соотношение (4) принимает вид:

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

Если величина шага изменяется от итерации к итерации, тогда

речь идет о вычислительной схеме метода наискорейшего спуска или метода Коши. Величина шаганаходится из условия минимизации целевой функции в выбранном направлении -Формальным признаком

правильности реализации методов является выполнение неравенства:

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

Рис.2.12.

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

где- заданные параметры точности.

Использование квадратичной аппроксимации в разложении (5) позволяет построить более эффективные по быстродействию вычислительные схемы, которые получили название методов Ньютона:

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

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

где- величина шага.

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

в выбранном направленииЭто гарантирует выполнение

неравенства

Модифицированный метод Ньютона надежен и эффективен, однако достаточно трудоемок в применении.

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

Направление поиска на каждом шаге по методу Флетчера-Ривса, сопряженное с предыдущим, вычисляется в соответствии с выражением:

где- текущее и предыдущее направления;

- градиент в к-й точке.

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

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

строится по рекуррентной формуле:

гдекорректирующая матрица.

Задача заключается в построении матрицытаким образом, чтобы

последовательностьдавала последовательное

приближение к матрице- точка экстремума функции.

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

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

При создании АИУС для решения задач нелинейного программирования с ограничениями используются три группы методов:

- методы линейной аппроксимации;

- методы скользящего допуска;

-методы на основе преобразования задачи (методы штрафных функций).

Методы последней группы нашли наибольшее распространение в системах. Суть методов этой группы заключается в сведении задач условной оптимизации к задачам безусловной оптимизации с последующим использованием известных методов безусловной оптимизации. Если задана целевая функция (3) и ограничения (1), (2), то строится функция вида:

где А - штрафной параметр;

Ω - штрафная функция.

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

В случае ограничений-неравенств могут быть использованы логарифмический штраф:

штраф типа обратной функции:

штраф типа квадрата срезки:

Если необходимо учесть разнородные ограничения, то формируется, например, функция вида:

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

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

где f (x) - целевая функция;

φ_j (x) - система линейных ограничений.

К такому виду сводится достаточно большое число задач в рамках создаваемых информационно-управляющих систем.

Для решения задач такого вида можно использовать все перечисленные выше методы. Однако особенность вида целевой функции (функция квадратична) и ограничений (ограничения линейны) позволяют свести решение задачи с использованием аппарата линейного программирования. Если взять производную от квадратичной функции, то получим линейную функцию. Ограничения также линейны. Следовательно, имеем задачу линейного программирования. И для решения задач квадратичного программирования используются методы, построенные на основе симплекс-метода: методы проектирования градиентов, метод Билла, метод Дорфмана-Баранкина, метод Франка-Вульфа и другие.

Задачи такого типа часто встречаются на практике.

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

Помимо этого при выборе методов руководствуются рядом критериев, основными из которых считаются следующие:

1. Точность получаемого решения по отношению к искомому.

2. Быстродействие (число итераций, время, затрачиваемое на получение решения и т.п.).

3. Сложность реализации вычислительной схемы по отысканию оптимума.

4. Объем подготовительной работы и др.