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

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

1.  Теоретическая часть

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

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

Рассмотрим функцию ­ двух переменных ­­ и  (рис.1). Проекция линии пересечения функции с плоскостью , где F – некоторое заданное значение функции , на плоскости называется линией постоянного уровня. Задавая различные значения , можно получить другие линии постоянного уровня и представить функцию  совокупностью этих линий (рис.2). Перемещение по поверхности, отображающей функцию , из точки  в точку  (рис.1) эквивалентно перемещению из точки  в точку на плоскости (рис.2). Если это перемещение осуществлять в направлении убывания функции  , то через определённое число шагов(итераций) можно достигнуть окрестности точки локального минимума.

Если и - начальная и конечная точки перемещения на К - ом шаге, то справедливо соотношение

,                                         (1)

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

Учитывая, что ,                                        (2)

Получим следующее выражение для определения координат конечной точки перемещения на К – ом шаге:

     ,                                    (3)

                                      (4)

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

      Если из точки  поиск ведётся в направлении антиградиента - , то в точке , являющейся начальной точкой следующего шага, направление поиска будет определяться антиградиентом - . Векторы и  в точке (рис.3), перпендикулярны, откуда следует, что их скалярное произведение в данной точке равно 0, т.е.

(5)

или

     С учётом (2) выражение (5) примет вид:

           (6)

Решение уравнения (6) совместно с (3),(4) позволяет определить величину на k – ом шаге поиска по методу наискорейшего спуска. Процесс поиска минимума в соответствии с (3) и (4) будет продолжаться до тех пор, пока не будет выполнено условие:

                                                      (7)

где - требуемая точность определения минимума функции . Величина  задаёт размеры окрестности точки минимума, удовлетворяющие заданной точности. С учётом (2) выражение (7) примет вид:

                                 (8)

Таким образом, выражения (3), (4), (6), (8) являются основными рабочими соотношениями решения задач нелинейного программирования методом наискорейшего спуска.

2.  Практическая часть.

1.  Постановка задачи.

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

Необходимо найти условные координаты точки =, при посадке в которой расход горючего был бы минимальным.

Решение типового примера. 

Пусть x⁰ = (6;8), f(x) =  x₁² + 2 x₂² - 2 x₁ - 8 x₂ + 12; e = 0.6.

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

В соответствии с формулами (2),(3) координаты точки на k-ом шаге поиска рассчитываются следующим образом:

x₁^(k) = x₁^(k-1)-g_k(2 x₁^(k-1)-2), (9)
x₂^(k) = x₂^(k-1)- g_k(4 x₂^(k-1)-8), (10)

Для определения величины шага g_k используем уравнение (6), которое в данном случае имеет вид:

(2 x₁^(k-1) - 2)(2 x₁^(k) - 2) + (4 x₂^(k-1) - 8)(4 x₂^(k) - 8) = 0. (11)

Поисковая процедура завершается при выполнении согласно (8) условия

 (12)

Последовательность поиска оптимального решения в соответствии (9)-(12) имеет вид:

Поскольку начальной точкой поиска является = (6;8), то координаты точки в конце 1-го шага (k=1) определяются в соответствии с (9)-(12) следующими образом:

x₁⁽¹⁾ = x₁⁽⁰⁾ - g₁(2 x₁⁽⁰⁾ - 2),
x₂⁽¹⁾ = x₂⁽⁰⁾ - g₁(4 x₂⁽⁰⁾ - 8).

Тогда

x₁⁽¹⁾ = 6 - g₁(2*6 - 2) = 6 - g₁*10,
x₂⁽¹⁾ = 8 - g₁(4*8 - 8) = 8 - g₁*24.