Методы поиска безусловного экстремума

Пусть в R" задан вектор Зс°. Требуется построить такую последовательность векторов х°, х',…, х^к е R", чтобы выполнялось условие.

Методы поиска экстремума, обеспечивающие выполнение условия (3.4), разделяются на ряд этапов.

I. Выбор начальной точки х°. Так как ограничений нет, следовательно, значения вектора х° любые, но целесообразнее выбрать х° близкое к минимуму.

II. Выбор направления движения в сторону экстремума.

III. Выбор шага перемещения.

—к

При любом методе спуска (поиска) последовательность {х }, к = 0,1…, подчиняется условию:

где d_k — направление спуска; ||"г_Лс/_Л || - величина шага.

Если d_k нормализовано, т. е. d_k | = 1, то величина шага равна а_к |. Компоненты формулы (3.5) представлены на рис. 3.5.

Рис. 3.5. Направление движения и величина шага

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

—* —.

Разложим в ряд Тейлора /(х +a_kdk), ограничиваясь линейными членами разложения:

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

• 1. Прямые методы поиска, использующие только значения.
• 2. Градиентные методы, использующие значения первых производных целевой функции.
• 3. Методы второго порядка, использующие значения первых и вторых производных целевой функции.