ТЕОРИЯ ЭКСТРЕМАЛЬНЫХ ЗАДАЧ

Теория экстремальных задач изучает проблемы, связанные с экстремумом функционала J[x) в различных функциональных пространствах. Частью этой теории являются: вариационное исчисление, выпуклое программирование, динамическое программирование, дискретное программирование, квадратичное программирование, линейное программирование, математическое программирование, математическая теория оптимальных процессов, целочисленное программирование. Особое место в ней занимают задачи со многими критериями.

Экстремум — термин, объединяющий понятия максимума и минимума функции (функционала). Различают глобальный экстремум функции на множестве X. т.е. частное значение функции, удовлетворяющие соотношению для всех X є X (глобальный минимум) или для всех хе X (глобальный максимум), и

локальный экстремум. В последнем случае неравенства выполняются в некоторой окрестности U(x)czX точки экстремума X . Глобальный экстремум функции называют также оптимумом функции или оптимальным значением функционала. Соответственно экстремальные задачи называют задачами оптимизации. В более общем случае речь идет об отыскании на множестве X (используется также символика ). Множество Xназывают допустимым множеством экстремальной задачи, аДх) — критерием экстремальной задачи (целевой функцией (функционалом) экстремальной задачи). Так как при изменении знака критерия имеем , то можно вести изложение

только для случая минимизации критерия. Если существует вектор

такой, что , т. е. , то называют (глобальным) минимумом функционала (функции) /(х), т.е.

, а X — точкой глобального минимума.

В теории экстремальных задач представляют интерес:

  • • существование глобального экстремума;
  • • необходимые и достаточные условия существованиия глобального экстремума для различных задач;
  • • методы поиска глобального экстремума;
  • • алгоритмы численного решения экстремальных задач.

Однако основные результаты теории экстремальных задач можно

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

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

0й = 0 , не принадлежащая классу допустимых. Разбив отрезок [0,1] на 2N — 1 частей (N>1) с допустимым управлением

, далее чередуя значения и(Л,)(0 = +1, — 1 на интервалах длины , и

получают в качестве x(N ) ломаную, такую, что

При N -> °о интервал стремится к нулю, т.е. построенная последовательность допустимых решений {х(N > (t), и{ N) (t)}, 0 < t < 1 — минимизирующая. В задаче отыскания глобального экстремума непрерывной функции конечного числа переменных /(х), X = (х,,.. .,хп) є X a Rn (X — замкнутое ограниченное пространство) существование (глобального) минимума (и глобального максимума) Дх) на этом множестве X гарантируется теоремой Вейерштрасса.

Под задачей поиска экстремума (минимума) функции (функционала) понимают:

а) нахождение самого экстремума

б) нахождение точки минимума х , если / достигается на допустимом множестве X, т.е. X є %, /(х) = /, или минимизирующей последовательности {x(N)}, такой, что Ит/(х(ЛГ)) = /·

/v-»~

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

Если X = Rn, т.е. ограничения на аргумент х отсутствуют, то говорят о задаче без ограничений отыскания экстремума функции, если же X с R", то имеют дело с задачей с ограничениями.

Задачи с ограничениями сводятся к задаче без ограничений следующими приемами. Когда множество Xзадано ограничениями типа равенств и неравенств, то, используя фигурирующие в них функции, нетрудно строить «штрафы» Ьк(х X) такие, что имеет место

Тогда задача min/(x) эквивалентна задаче

хеХ

Если последовательность ?*(?|??) построена так, что операции минимума и предела перестановочны, то получается последовательность задач без ограничений, т.е. задач безусловной минимизации , Пределом решений которых XW При /: —» со

будет точка X минимума функции /(х) на множестве X. Функции /(?) + ?,(?|?) называются штрафными функциями. Различают внутренние (барьерные) и внешние штрафные функции. Барьерная функция неограниченно возрастает при приближении х к границе X. Например, в задаче

барьерная функция вида , где число

г(к) > 0 , называемое параметром штрафа, неограниченно растет с ростом к. Внешняя штрафная функция обычно строится так, что штраф равен нулю на допустимом множестве X и возрастает при удалении от

него. Например, функция вида , где

(#;(*))+ = max{0,^7 (x)}. Одним из недостатков численных методов отыскания экстремума, использующих штрафные функции, является потеря точности при перемножении больших величин г(к) на близкие к нулю для существенных ограничений величины ?у(х) . Поэтому применяют модифицированные штрафные функции со сдвигом значений

где уj > О, j = 1,..., т, и выбираются при построении последовательности ?(?) пропорционально невязке в выполнении ограничений

. В этом случае к увеличению г(к) приходится прибегать крайне редко (когда сумма невязок ограничений не уменьшается). Последнее утверждение следует из того, что при г(к) —> °о модифицированная функция штрафа переходит в функцию Лагранжа задачи с ограничениями. В частности, для задачи (2.5.1) в

, где множители yj>0, j = носят

название множителей Лагранжа. Так как

то задача (1.4.1) эквивалентна задаче . Задачу

называют двойственной по отношению к исходной

(прямой) задаче (2.5.1). Двойственные задачи играют большую роль в теории экономического равновесия. В случае, когда

, говорят, что функция L(x,y) имеет

седловую точку. Пару (х,у ) называют седловой точкой функции L(x,y), если имеют место неравенства

(в общем случае только для (х, у), у > 0, лежащих в некоторой окрестности (х,у)).

Необходимые условия экстремума обычно связывают для задачи (2.5.1) с седловыми точками ее функции Лагранжа. Необходимые условия минимума для задачи (2.5.1) следуют из неравенств (2.5.2) при использовании разложения Тейлора

66

В экономической трактовке это означает наличие в точке минимума X штрафных расценок >0, j = 1,...,/и, отличных от нуля ТОЛЬКО ДЛЯ существенных ограничений, где gj (х) = 0 (второе условие (2.5.4)), таких, что малое дополнительное снижение ущерба при изменении любой компоненты Xj, приводящее к нарушению ограничений задачи (2.5.1), вызывает компенсирующий это снижение штраф (условие (2.5.3)). В случае задач без ограничений у = 0 и (2.5.3) переходит в известное необходимое условие экстремума

функции . Точки, удовлетворяющие необходимым

условиям экстремума (как локально, так и глобально), называются стационарными.

Достаточные условия оптимальности получают заменой критерия /(х) некоторым выражением ?(?), оценивающим его снизу (в задаче на минимум), таким, что

в области определения f(x), и релаксацией (ослаблением) ограничений задачи (расширением X). В частности, для задачи на экстремум (как локальный, так и глобальный) функции fix), х є Rn, оценивая ее квадратичной формой по формуле Тейлора, получаем известное условие положительной определенности матрицы вторых производных f"(x) в стационарной точке х .

Классические (непрямые) методы поиска экстремума используют необходимые условия экстремума. Нули частных производных

вычисляются одним из многочисленных методов последовательных приближений. Вместе с тем каждую задачу решения системы уравнений (р7(х,,...,хи) = 0, j = т<п можно свести

к задаче поиска экстремума (минимума), например, функции

. Прямые методы поиска основаны на непосредственном сравнении fix) в двух или нескольких точках и итеративных пересчетах прямых и сопряженных переменных (множителей Лагранжа). Так как задача на экстремум с ограничениями сводится к задаче без ограничений, то ниже излагаются алгоритмы поиска экстремума задачи без ограничений. Применяют алгоритмы построения последовательности значений {xw}, использующие линейное

приближение минимизируемой функции, например, метод градиентного спуска

использующий квадратичное приближение, метод Ньютона

где I — единичная матрица (метод градиентного спуска и метод Ньютона получаются при ?(?) =0 или а(к) =0 соответственно).

Методы поиска экстремума, использующие первую производную, называют методами первого порядка, а использующие вторую — методами второго порядка. Параметры а(к), ?(?) выбираются так, чтобы для всех к (условие релаксации). В некоторых предположениях доказывается сходимость алгоритмов, чаще всего в смысле

Если имеет место неравенство , то при

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

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

и другие методы, учитывающие инерцию при построении последовательности {х(А)}.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >