Свойство параллельного подпространства

Пусть заданы квадратичная функция q(x), две произвольные не­совпадающие точки x⁽¹⁾ и х⁽²⁾, а также направление d. Если точка y⁽¹⁾ минимизирует q(x⁽¹⁾+λ d), a точка y⁽²⁾ минимизирует q(x⁽¹⁾+ λ d), то направление (y⁽²⁾ - y⁽¹⁾) сопряжено с d.

Рис. 3.10 иллюстрирует сформулированное свойство для случая двух переменных. Нетрудно видеть, что поиск, проводимый из точки y⁽¹⁾ или y⁽²⁾ в направлении (y⁽²⁾ - y⁽¹⁾), обеспечивает получение точки минимума. Таким образом, в случае двух переменных реализация трех одномерных поисков позволяет построить систему сопряженных направлений и, кроме того, найти точку оптимума квадратичной функции. Прежде чем продолжать алгоритмические построения, докажем теорему о свойстве параллельного подпространства.

Рис. 3.10. Сопряженные направления на плоскости.

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

Т CТ = D (3.32)

Поскольку все внедиагональные элементы D равны нулю, отсюда следует, что

(3.33)

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

 

Сопряженные направления

Пусть С — симметрическая матрица порядка N N; направления s⁽¹⁾, s⁽²⁾, s⁽³⁾,..., s , r ≤ N, называются С -сопряженными, если эти направления линейно независимы и

s C s = для всех i ≠ j. (3.34)

Опять обратимся к квадратичной функции общего вида

q(x) = a + b^Tx+(¹/_t)x^T C x.

Точки прямой, исходящей из х⁽¹⁾ в направлении d, задаются формулой

x = x +λ d.

Минимум q(x) вдоль направления d определяется путем нахождения значения λ *, при котором q/ λ =0. Вычислим эту производную по правилу дифференцирования сложной функции:

= = b + x C d. (3.35)

По предположению теоремы минимум достигается в точке y⁽¹⁾ следовательно,

[(y⁽¹⁾ ) C b ] d = 0. (3.36)

Аналогично, так как минимум q(x) при движении из точки х⁽²⁾ в направлении d достигается в точке y⁽²⁾ имеем

[(y⁽²⁾ ) C b ] d = 0. (3.37)

Вычитая (3.36) из (3.37), получаем

(y⁽²⁾ - y⁽¹⁾ ) C d = 0 (3.38)

В соответствии с данным выше определением направления d и (y⁽²⁾ - y⁽¹⁾ ) оказываются С -сопряженными, и свойство параллельного подпространства для квадратичных функций доказано.

Пример 3.5. Минимизация на основе свойства параллельного подпространства.

Опять рассмотрим квадратичную функцию q(x) = 4x + 3x - 4x x + x . Пусть заданы две точки х⁽¹⁾ = [0, 0] , х⁽²⁾ = [1, 0] и направление d = [l, 1]^T. Первый поиск проводится вдоль прямой

x = [0, 0] + λ [1, 1]

и приводит к точке y⁽¹⁾ = [- , - ] (λ *= - ). Второй поиск проводится вдоль прямой

x = [1, 0] + λ [1, 1]

и позволяет получить точку y⁽²⁾ = [ , – ] (λ *= – ). Согласно свойству параллельного подпространства, направление

y⁽²⁾ – y⁽¹⁾ = [ , – ] – [– , – ] = [ , – ]

сопряжено с d = [l, 1]^T

[l, 1] C [ , – ] .

Выше отмечалось, что в случае двух переменных оптимум q(x) можно найти путем проведения поиска вдоль прямой, заданной направлением (y⁽²⁾ – y⁽¹⁾ ). Этот факт нетрудно проверить, поскольку минимум q(x) вдоль прямой

x = [– , – ] + λ [ , – ]

достигается в точке х* = [– , – ]^T(λ * = – ), которая сов­падает с полученным ранее решением.

В рассмотренных выше построениях для того, чтобы определить сопряженное направление, требовалось задать две точки и некоторое направление. Это не слишком удобно при проведении расчетов, поэтому предпочтительнее строить систему сопряженных направлений, исходя из одной начальной точки, что легко осуществить при помощи единичных координатных векторов е⁽¹⁾, е⁽²⁾, е⁽³⁾,..., е^(N). (Здесь рассматривается процедура построения сопряженных на­правлений в случае двух переменных, которая допускает очевидное обобщение для N-мерного пространства.) Пусть е⁽¹⁾ = [l, 0] и е⁽²⁾ = [0, 1] . При заданной начальной точке х⁽⁰⁾ вычислим значение λ ⁽⁰⁾, которому соответствует минимум f (х⁽⁰⁾ + λ ⁽⁰⁾ е⁽¹⁾).

 

Положим

x⁽¹⁾ = х⁽⁰⁾ + λ ⁽⁰⁾ е⁽¹⁾.

и вычислим значение λ ⁽¹⁾, которому соответствует минимум f (х⁽¹⁾ + λ ⁽¹⁾ е⁽²⁾). Положим

x⁽²⁾ = х⁽¹⁾ + λ ⁽¹⁾ е⁽²⁾.

Далее вычислим значение λ ⁽²⁾, минимизирующее f (х⁽²⁾ + λ ⁽²⁾ е⁽¹⁾), и положим

x⁽³⁾ = х⁽²⁾ + λ ⁽²⁾ е⁽¹⁾.

При этом направления (х⁽³⁾ – х⁽¹⁾) и е⁽¹⁾ оказываются сопряженными. Для того чтобы убедиться в этом, рассмотрим рис. 3.11. Заметим, что точка х⁽¹⁾ найдена в результате поиска из точки х⁽⁰⁾ в направление е⁽¹⁾, а точка х⁽³⁾ получена при поиске из точки х⁽²⁾ в направлении е⁽¹⁾. Следовательно, направление е⁽¹⁾ и (х⁽³⁾ – х⁽¹⁾) являются сопряжёнными согласно свойству параллельного подпространства. Далее если на следующей итерации провести поиск в направлении (x⁽³⁾ – x⁽¹⁾), то процедура поиска будет охватывать два сопряженных направления, и поскольку f(x) предполагается квадратичной функцией двух переменных, в результате будет найдено решение х*.

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

В частности, нетрудно показать, что если точка y⁽¹⁾ найдена в результате поиска из точки х⁽¹⁾ вдоль каждого из М (< N) сопряженных направлений, а точка y⁽²⁾ получена в результате поиска из точки х⁽²⁾ вдоль каждого из тех же М сопряженных направлений s⁽¹⁾, s⁽²⁾, s⁽³⁾,..., s^(M) то вектор (y⁽²⁾ – y⁽¹⁾) задает направление, сопряженное со всеми выбранными М направлениями. Это утверждение известно как обобщенное свойство параллельного подпространства. Используя указанное свойство, можно обобщить метод построения сопряженных направлений, последовательные шаги реализации которого отражены на рис. 3.11 на случай пространства управляемых переменных более высокой размерности. Рис. 3.12 иллюстрирует построение сопряженных направлений в трехмерном пространстве.

Как показано на рис. 3.12, сначала поиск осуществляется вдоль трех координатных направлений е⁽¹⁾, е⁽²⁾ и е⁽³⁾ затем эти направления последовательно заменяются вновь построенными сопряженными направлениями. Серия одномерных поисков из точки x⁽⁰⁾ проводится в направлении е⁽³⁾, затем е⁽¹⁾, е⁽²⁾ и снова е⁽³⁾; в результате построены сопряженные направления е⁽³⁾ и (x⁽⁴⁾ – x⁽¹⁾). Направление е⁽¹⁾ заменяется новым направлением поиска, которое на рис. 3.12 обозначено цифрой 4. Следующая серия поисков проводится в направлении 4, затем е⁽²⁾, е⁽³⁾ и снова 4. Согласно обобщенному свойству параллельного подпространства, новое направление (x⁽⁸⁾ – x⁽⁵⁾), обозначенное на рисунке цифрой 5, сопряжено не только с 4, но и с е⁽³⁾. Следовательно, направления е⁽³⁾, (x⁽⁴⁾ – x⁽¹⁾) и (x⁽⁸⁾ – x⁽⁵⁾) образуют систему взаимно сопряженных направлений.

 

Рис. 3.11. Построение сопряженных направлений из одной точки.

Поэтому если провести дополнительный поиск из точки x⁽⁵⁾ в направлении (x⁽⁸⁾ – x⁽⁵⁾) (т. е. в направлении 5 на рисунке), то будет найдена точка x⁽⁹⁾, в которой должен достигаться оптимум квадратичной функции трех переменных f(x), поскольку поиск последовательно осуществляется в трех взаимно сопряженных направлениях. Таким образом, в трехмерном случае для нахождения точного (если, разумеется, оперировать недесятичными дробями) оптимума квадратичной функции требуется провести девять поисков вдоль прямой с использованием только значений функции. Алгоритм легко обобщается и в случае N-мерного пространства требует проведения последовательности N одномерных поисков, которая приводит к получению точки оптимума квадратичной функции. Ниже представлены шаги обобщенного алгоритма.

Рис. 3.12. Построение сопряженных направлений в трехмерном пространстве.

⇐ Предыдущая1234567Следующая ⇒

Поделиться:

Популярное:

1. антропоцентризм как фундаментальное свойство языка. Объективный и субъективный.
2. Общие сведения о двигателях постоянного тока параллельного возбуждения.
3. Свойство направленного ответвления
4. Свойство основных ингредиентов Экстра-Каль
5. Торможение двигателей параллельного возбуждения.
6. Эквивалентная схема параллельного колебательного контура. Основные расчетные соотношения для резонанса токов.