о квадратичної апроксимації цільової функції)
(1.4а)
Примножуючи обидві частини цього рівняння на, отримуємо
(1.4б)
При цьому якщо квадратичною, то, тобто постійна матриця. Рівняння (1.4б) можна розглядати як систему n лінійних рівнянь, що містять n невідомих параметрів, які потрібно оцінити для того, щоб апроксимувати або при заданих значеннях, і на більш ранніх етапах пошуку. Для вирішення цих лінійних рівнянь можуть бути використані різні методи, кожен з яких призводить до різних методів змінної метрики. p> У досить великій групі методів апроксимується за допомогою інформації, отриманої на k -му кроці:
, (1.5)
де ? (x) - матриця, апроксимуюча. являє собою обумовлену матрицю, а - масштабний множник, константа, зазвичай рівна одиниці. Вибір по суті визначає метод змінної метрики. Для забезпечення збіжності повинна бути позитивно певної і задовольняти рівнянню (1.4б) в тому випадку, коли вона замінює. p> На (k + 1) -м кроці ми знаємо,, і і хочемо обчислити, так щоб задовольнялося співвідношення
(1.4в)
Нехай. Тоді рівняння
(1.4г)
потрібно дозволити відносно. Прямий підстановкою результату можна показати, що рівняння (1.4г) має наступне рішення:
, (1.6)
де y і z - довільні вектори розмірності nx 1 . Якщо для ? = +1 вибирається лінійна комбінація двох напрямків і, а саме
,
то використовуємо алгоритм Бройдо; якщо ж береться
,,
то матрицю обчислюємо за допомогою алгоритму Девідона - Флетчера - Пауелла.
Якщо кроки визначаються послідовно шляхом мінімізації в напрямку, то всі методи, за допомогою яких обчислюють симметрическую матрицю, що задовольняє (1.4в), дають напрямки, що є взаємно сполученими (у випадку квадратичної цільової функції).
Метод Бройдо ( ?? (k) має ранг 1)
Бройдо, описуючи методи розв'язання систем лінійних рівнянь, показав, що якщо виявляється симетричною матрицею рангу 1 і має задовольнятися співвідношення, то єдиним можливим вибором є
. (1.7)
де
,
.
У найпростішому алгоритмі цього типу мінімізація починається з вибору початкової точки x (0) і деякого ? (0) > 0; потім послідовно застосовуються рівняння (1.3), (1.5), (1.7) до тих пір, поки, наприклад,. Якщо для кожного напрямку пошуку являє собою скаляр, здатний мінімізувати в цьому напрямку, то даний метод дає сполучені напрямки пошуку. Таким чином, за певних обмежуючих умовах описаним алгоритмом забезпечена збіжність. Однією з цікавих особливостей методів рангу 1 є те, що (або) в рівн...
