3. Определяется величина шага ak, путем одномерной минимизации по а функции j(a) = f(x[k] - af'(x[k])).

4. Определяются координаты точки х[k+1]:

хi[k+1] = xi[k] – аkf’i(х[k]), i = 1 ,..., п.

5. Проверяются условия останова стерационного процесса. Если они выполняются, то вычисления прекращаются. В противном случае осуществляется переход к п. 1.

В рассматриваемом методе направление движения из точки х[k] касается линии уровня в точке x[k+1] (Рис. 2.9). Траектория спуска зигзагообразная, причем соседние звенья зигзага ортогональны друг другу. Действительно, шаг ak выбирается путем минимизации по а функции φ(a) = f(x[k] - af'(x[k])). Необходимое условие минимума функции dj(a)/da = 0. Вычислив производную сложной функции, получим условие ортогональности векторов направлений спуска в соседних точках:

dj(a)/da = -f’(x[k+1]f’(x[k]) = 0.

Градиентные методы сходятся к минимуму с высокой скоростью (со скоростью геометрической прогрессии) для гладких выпуклых функций. У таких функций наибольшее М и наименьшее m собственные значения матрицы вторых производных (матрицы Гессе)

мало отличаются друг от друга, т. е. матрица Н(х) хорошо обусловлена. Напомним, что собственными значениями li, i =1, …, n, матрицы являются корни характеристического уравнения

Однако на практике, как правило, минимизируемые функции имеют плохо обусловленные матрицы вторых производных (т/М << 1). Значения таких функций вдоль некоторых направлений изменяются гораздо быстрее (иногда на несколько порядков), чем в других направлениях. Их поверхности уровня в простейшем случае сильно вытягиваются, а в более сложных случаях изгибаются и представляют собой овраги. Функции, обладающие такими свойствами, называют овражными. Направление антиградиента этих функций (см. Рис. 2.10) существенно отклоняется от направления в точку минимума, что приводит к замедлению скорости сходимости.

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

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

f(x) = (х, Нх) + (b, х) + а

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

По определению, два n-мерных вектора х и у называют сопряженными по отношению к матрице H (или H-сопряженными), если скалярное произведение (x, Ну) = 0. Здесь Н - симметрическая положительно определенная матрица размером пхп.

Одной из наиболее существенных проблем в методах сопряженных градиентов является проблема эффективного построения направлений. Метод Флетчера-Ривса решает эту проблему путем преобразования на каждом шаге антиградиента -f(x[k]) в направление p[k], H-сопряженное с ранее найденными направлениями р[0], р[1], ..., р[k-1]. Рассмотрим сначала этот метод применительно к задаче минимизации квадратичной функции.

Направления р[k] вычисляют по формулам:

p[k] = -f’(x[k])+bk-1p[k-l], k >= 1;

p[0] = -f’(x[0]).

Величины bk-1 выбираются так, чтобы направления p[k], р[k-1] были H-сопряженными:

(p[k], Hp[k-1])= 0.

В результате для квадратичной функции

,

итерационный процесс минимизации имеет вид

x[k+l] =x[k] +akp[k],

где р[k] - направление спуска на k-м шаге; аk - величина шага. Последняя выбирается из условия минимума функции f(х) по а в направлении движения, т. е. в результате решения задачи одномерной минимизации:

f(х[k] + аkр[k]) = f(x[k] + ар [k]).

Для квадратичной функции

Алгоритм метода сопряженных градиентов Флетчера-Ривса состоит в следующем.

1. В точке х[0] вычисляется p[0] = -f’(x[0]).

2. На k-м шаге по приведенным выше формулам определяются шаг аk. и точка х[k+1].

3. Вычисляются величины f(x[k+1]) и f’(x[k+1]).

4. Если f’(x[k+1]) = 0, то точка х[k+1] является точкой минимума функции f(х). В противном случае определяется новое направление p[k+l] из соотношения

и осуществляется переход к следующей итерации. Эта процедура найдет минимум квадратичной функции не более чем за п шагов. При минимизации неквадратичных функций метод Флетчера-Ривса из конечного становится итеративным. В таком случае после (п+1)-й итерации процедуры 1-4 циклически повторяются с заменой х[0] на х[п+1] , а вычисления заканчиваются при , где - заданное число. При этом применяют следующую модификацию метода:

x[k+l] = x[k] +akp[k],

p[k] = -f’(x[k])+bk-1p[k-l], k >= 1;

p[0] = -f’(x[0]);

f(х[k] + akp[k]) = f(x[k] + ap[k];

.

Здесь I- множество индексов: I = {0, n, 2п, Зп, ...}, т. е. обновление метода происходит через каждые п шагов.

Геометрический смысл метода сопряженных градиентов состоит в следующем (Рис. 2.11). Из заданной начальной точки х[0] осуществляется спуск в направлении р[0] = -f'(x[0]). В точке х[1] определяется вектор-градиент f'(x [1]). Поскольку х[1] является точкой минимума функции в направлении р[0], то f’(х[1]) ортогонален вектору р[0]. Затем отыскивается вектор р [1], H-сопряженный к р [0] . Далее отыскивается минимум функции вдоль направления р[1] и т. д.

Рис. 2.11. Траектория спуска в методе сопряженных градиентов

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

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

Основная задача выпуклого программирования

Пусть задано выпуклое и замкнутое множество . Рассмотрим множество

={}, =(,…,), Î.

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

Формальная постановка задачи выпуклого программирования

Задачу

,

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

Определение означает, что ставится задача:

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

==

при этом число  называют значением задачи.

Если оптимального плана не существует, то требуется

·        либо найти значение задачи как точную нижнюю грань значений функции  на множестве :

=

·        либо убедиться, что  неограничена снизу на множестве ;

·        либо убедиться в том, что множество допустимых планов  пусто.

Для решения предложенной оптимизационной задачи следует выполнить следующие действия:

·        Определить множество .

·        Определить вектор-функцию =(,…,) и вектор Î.

·        Определить множество допустимых планов ={}.

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

·        Проверить, является ли полученная оптимизационная задача ЗВП, для этого

·        проверить на выпуклость множество ;

·        проверить на выпуклость функцию .

В случае успеха п. 5

·        Построить функцию Лагранжа полученной ЗВП.

·        С помощью дифференциальных условий Куна-Таккера найти седловые точки построенной функции Лагранжа.

В случае неудачи п. 5 попытаться найти другие методы решения задачи.

Методы субградиентной оптимизации. Эти итеративные процедуры формируют последовательность векторов {lk}. Начиная с некоторого начального значения l0 эти вектора меняются по следующему правилу

lk+1 = lk + tk (A xk -  b),

где xk — оптимальное решение задачи , а tk — размер шага. Фундаментальный теоретический результат заключается в  том, что [14]

.

Размер шага  на практике обычно выбирают, следуя [11],

где q k — скаляр, 0 < q k 2  и z* — верхняя граница для n(D). Обычно z* получают эвристикой для P. В методе ветвей и границ z* — текущий рекорд. Последовательность q k, как правило, начинается с q  0=2 и затем q k делится пополам, через фиксированное число итераций, зависящее от размерности задачи.

Элементы функционального анализа. Метрические, линейные и нормированные пространства. Эвклидово пространство. Гильбертово пространство. Линейные операторы и функционалы в линейных нормированных пространствах

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

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

1. Линейные пространства. Базис

Одно из основных понятий современной математики - линейное пространство.

Пусть L - некоторое множество объектов произвольной природы, а C - множество комплексных чисел. Множество L называют линейным пространством, если на нем определены две операции: 1) операция сложения любых двух элементов этого множества и 2) операция умножения элементов этого множества на комплексное число, причем эти операции удовлетворяют некоторым естественным аксиомам. Более точно:

Определение. Множество L называется линейным пространством над полем комплексных чисел C, если

1. каждой паре элементов x, y из этого пространства поставлен в соответствие элемент z этого пространства, называемый суммой элементов x и y (обозначение: );
2. каждому элементу x из L и каждому комплексному числу поставлен в соответствие элемент из L, называемый произведением и x (и обозначаемый или x);
3. указанные операции удовлетворяют следующим аксиомам:
4. для любых ,
5. для любых ,
6. существует "нулевой" элемент , такой, что для любого ,
7. для каждого существует "противоположный" ему элемент , такой, что ,
8. для любого ,
9. для любого и любых ,
10. для любого и любых ,
11. для любого и любых .

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

Иногда рассматривают линейное пространство не над полем комплексных, а над полем действительных чисел R (т.е. вместо операции умножения на комплексные числа рассматривается операция умножения на действительные числа). Аксиомы линейного пространства при этом не меняются.

Приведем некоторые типичные примеры линейных пространств.

Пример 1. Линейное пространство векторов на плоскости (или в трехмерном пространстве) с обычными операциями сложения векторов и умножения вектора на действительное число. Нулевым элементом является нулевой вектор.

Пример 2. Линейное пространство всевозможных последовательностей комплексных чисел с операциями

.

Нулевой элемент - последовательность (0, 0, ..., 0, ...).

Пусть теперь - некоторые элементы линейного пространства L, а - произвольные комплексные (или действительные) числа. Элемент пространства L, равный , называется линейной комбинацией элементов .

Определение. Система (набор) элементов пространства L называется линейно независимой, если линейная комбинация равна нулевому элементу пространства только в случае .

Иными словами, система называется линейно независимой, если из равенства следует, что .

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

Таким образом, система называется линейно зависимой, если она не является линейно независимой.

Определение. Линейное пространство имеет размерность n (или, коротко, n-мерно), если в нем найдется n линейно независимых элементов, но любые (n+1) элемент линейно зависимы. Линейное пространство называется бесконечномерным, если в нем можно указать любое наперед заданное число линейно независимых элементов.

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

Как мы убедились, в n-мерном пространстве любая линейно независимая система из n элементов образует базис.

Определение. Множество M называется метрическим пространством, если каждым двум элементам x, y этого множества поставлено в соответствие действительное число, обозначаемое и называемое расстоянием между элементами x и y, причем выполнены следующие аксиомы:

1. для любых , причем в том и только в том случае, когда ;
2. для любых ;
3. для любых .

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

Определение. Линейное пространство называется нормированным, если каждому элементу x этого пространства поставлено в соответствие действительное число (норма x ), причем выполнены следующие аксиомы:

1. для любого x, причем тогда и только тогда, когда ;
2. для любого x и любого комплексного ;
3. для любых x, y из данного пространства.

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

Неравенство, фигурирующее в третьей аксиоме, называется неравенством Минковского.

Простейшими примерами нормированных пространств могут служить множества действительных чисел R и комплексных чисел C, где в качестве нормы числа рассматривается его модуль, а также пространство векторов на плоскости (или в пространстве) с нормой, равной длине вектора.

В пространстве непрерывных функций на (действительном или комплексном) норму можно ввести, например, следующими способами:

, .

Отметим теперь следующий важный факт. В любом линейном нормированном пространстве можно ввести метрику следующим образом:

При этом выполнение первой аксиомы метрического пространства следует из первой аксиомы нормированного пространства. Выполнение второй аксиомы также очевидно:

.

Наконец, выполнение третьей аксиомы метрического пространства следует из неравенства Минковского:

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

Пусть  -- вещественное -мерное пространство, в котором задан базис . Тогда векторы и из задаются своими координатами:

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