Как найти нормаль к прямой в пространстве. Как найти уравнения касательной плоскости и нормалик поверхности в заданной точке? Вид уравнения плоскости согласно координатам двух точек и вектора, коллинеарного плоскости

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

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

1. Метод наискорейшего спуска.

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

Этот метод, предложенный в 1845 г. О. Коши, принято теперь называть методом наискорейшего спуска.

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

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

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

с симметричной положительно определенной матрицей А.

Согласно формуле (10.8), в этом случае Поэтому формула (10.22) выглядит здесь так:

Заметим, что

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

Таким образом, применительно к минимизации квадратичной

функции (10.24) метод наискорейшего спуска эквивалентен расчету по формуле (10.25), где

Замечание 1. Поскольку точка минимума функции (10.24) совпадает с решением системы метод наискорейшего спуска (10.25), (10.26) может применяться и как итерационный метод решения систем линейных алгебраических уравнений с симметричными положительно определенными матрицами.

Замечание 2. Отметим, что где отношение Рэлея (см. § 8.1).

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

Заметим, что Поэтому точное значение точки минимума нам заранее известно. Запишем данную функцию в виде (10.24), где матрица и вектор Как нетрудно видеть,

Возьмем начальное приближение и будем вести вычисления по формулам (10.25), (10.26).

I итерация.

II итерация.

Можно показать, что для всех на итерации будут получены значения

Заметим, что при Таким образом,

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

На рис. 10.5 изображена именно та траектория спуска, которая была получена в данном примере.

Для случая минимизации квадратичной функции справедлив следующий общий результат .

Теорема 10.1. Пусть А - симметричная положительно определенная матрица и минимизируется квадратичная функция (10.24). Тогда при любом выборе начальною приближения метод наискорейшею спуска (10.25), (10.26) сходится и верна следующая оценка погрешности:

Здесь и Ладо - минимальное и максимальное собственные значения матрицы А.

Отметим, что этот метод сходится со скоростью геометрической прогрессии, знаменатель которой причем если их близки, то мало и метод сходится достаточно быстро. Например, в примере 10.1 имеем и поэтому Если же Ащах, то и 1 и следует ожидать медленной сходимости метода наискорейшего спуска.

Пример 10.2. Применение метода наискорейшего спуска для минимизации квадратичной функции при начальном приближении дает последовательность приближений где Траектория спуска изображена на рис. 10.6.

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

чем в предыдущем примерю. Так как здесь и полученный результат вполне согласуется с оценкой (10.27).

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

Замечание 2. Для квадратичной целевой функции (10.24) решение задачи одномерной минимизации (10.23) удается найти в виде простой явной формулы (10.26). Однако для большинства других нелинейных функций этого сделать нельзя и для вычисления методом наискорейшего спуска приходится применять численные методы одномерной минимизации типа тех, которые были рассмотрены в предыдущей главе.

2. Проблема "оврагов".

Из проведенного выше обсуждения следует, что градиентный метод сходится достаточно быстро, если для минимизируемой функции поверхности уровня близки к сферам (при линии уровня близки к окружностям). Для таких функций и 1. Теорема 10.1, замечание 1, а также результат примера 10.2 указывают на то, что скорость сходимости резко падает при увеличении величины Действительно, известно, что градиентный метод сходится очень медленно, если поверхности уровня минимизируемой функции сильно вытянуты в некоторых направлениях. В двумерном случае рельеф соответствующей поверхности напоминает рельеф местности с оврагом (рис. 10.7). Поэтому такие функции принято называть овражными. Вдоль направлений, характеризующих "дно оврага", овражная функция меняется незначительно, а в других направлениях, характеризующих "склон оврага", происходит резкое изменение функции.

Если начальная точка попадает на "склон оврага", то направление градиентного спуска оказывается почти перпендикулярным "дну оврага" и очередное приближение попадает на противоположный "склон оврага". Следующий шаг в направлении ко "дну оврага" возвращает приближение на первоначальный "склон оврага". В результате вместо того чтобы двигаться вдоль "дна оврага" в направлении к точке минимума, траектория спуска совершает зигзагообразные скачки поперек "оврага", почти не приближаясь к цели (рис. 10.7).

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

Более подробную информацию о проблеме "оврагов" и "овражных" методах можно найти, например, в , .

3. Другие подходы к определению шага спуска.

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

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

1. Градиент функции – это вектор, который в каждой точке области определения функции
направлен по нормали к поверхности уровня, проведенной через эту точку.

Проекции градиента
на оси координат равны частным производным функции
по соответствующим переменным, т.е.

. (2.4)

К градиентным методам относятся: метод релаксации, градиента, наискорейшего спуска и ряд других .

Рассмотрим некоторые из градиентных методов.

Метод градиента

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

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

При выполнении шага одновременно изменяются значения всех независимых переменных. Каждая из них получает приращение пропорциональное соответствующей составляющей градиента по данной оси.

Формульная запись алгоритма может иметь вид:

,
. (2.5)

В этом случае величина шага
при постоянном значении параметраhизменяется автоматически с изменением величины градиента и при приближении к оптимуму уменьшается.

Другая формульная запись алгоритма имеет вид:

,
. (2.6)

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

В стратегии изменения шага
в этом случае используется то, что градиенты
и
отличаются по направлению. Изменение шага поиска производится в соответствии с правилом:

(2.7)

где
– угол поворота градиента наk-ом шаге, определяемый выражением

,

,
– допустимые пределы угла поворота градиента.

Характер поиска оптимума в методе градиента показан на рис. 2.1.

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

,

где – заданная погрешность расчета.

Рис. 2.1. Характер движения к оптимуму в методе градиента с большой величиной шага

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

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

Метод наискорейшего спуска

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

Сокращения объема вычислений можно добиться используя метод наискорейшего спуска.

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

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

Рис. 2.2. Характер движения к оптимуму в методе наискорейшего спуска (–) и методе градиента (∙∙∙∙)

В сравнении с методом градиента метод наискорейшего спуска оказывается более выгодным из-за сокращения объема вычислений.

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

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

Кроме того, можно также принять условие окончания поиска в форме соотношения

,

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

.

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

Рис. 2.3. К определению окончания поиска в методе наискорейшего спуска

В качестве стратегии изменения шага спуска можно использовать методы изложенные выше (2.7).

В основе метода лежит следующая итерационная модификация формулы

x k +1 = x k + a k s(x k),

x k+1 = x k - a k Ñ f(x k), где

a - заданный положительный коэффициент;

Ñ f(x k) - градиент целевой функции первого порядка.

Недостатки:

необходимость выбора подходящего значения ;

медленная сходимость к точке минимума ввиду малости f(x k) в окрестности этой точки.

Метод наискорейшего спуска

Свободен от первого недостатка простейшего градиентного метода, т.к. a k вычисляется путем решения задачи минимизации Ñ f(x k) вдоль направления Ñ f(x k) с помощью одного из методов одномерной оптимизации x k+1 = x k - a k Ñ f(x k).

Данный метод иногда называют методом Коши.

Алгоритм характеризуется низкой скоростью сходимости при решении практических задач. Это объясняется тем, что изменения переменных непосредственно зависит от величины градиента, которая стремится к нулю в окрестности точки минимума и отсутствует механизм ускорения на последних итерациях. Поэтому, учитывая устойчивость алгоритма, метод наискорейшего спуска часто используется как начальная процедура поиска решения (из точек, расположенных на значительных расстояниях от точки минимума).

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

Общая задача нелинейного программирования без ограничений сводится к следующему: минимизировать f(x), x E n , где f(x) является целевой функцией. При решении этой задачи мы используем методы минимизации, которые приводят к стационарной точке f(x), определяемой уравнением f(x *)=0. Метод сопряженных направлений относится к методам минимизации без ограничений, использующим производные. Задача: минимизировать f(x), x E n , где f(x) является целевой функцией n независимых переменных. Важной особенностью является быстрая сходимость за счет того, что при выборе направления используется матрица Гессе, которая описывает область топологии поверхности отклика. В частности, если целевая функция квадратичная, то можно получить точку минимума не более чем за количество шагов, равное размерности задачи.

Для применения метода на практике его необходимо дополнить процедурами проверки сходимости и линейной независимости системы направлений. Методы второго порядка

Метод Ньютона

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

x k +1 = x k - Ñ 2 f(x k -1) Ñ f(x k).

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

x k +1 = x k - a k Ñ 2 f(x k -1) Ñ f(x k), где

a k - параметр, выбираемый таким образом, чтобы f(x k+1) min.

2. Нахождение экстремума функции без ограничения

Дана некоторая функция f(х) на открытом интервале (а, в) изменения аргумента х. Предполагаем, что exst внутри этого интервала существует (нужно сказать, что в общем случае математически заранее это утверждать не могут; однако в технических приложениях очень часто наличие exst внутри некоторого интервала изменения интервала изменения аргумента может быть предсказано из физических соображений).

Определение exst. Функция f(x) заданная на интервале (а, в) имеет в точке x * max(min), если эту точку можно окружить таким интервалом (x * -ε, x * +ε), содержащимся в интервале (а, в), что для всех ее точек х, принадлежащих интервалу (x * -ε, x * +ε), выполняется неравенство:

f(x) ≤ f(x *) → для max

f(x) ≥ f(x *) → для min

Это определение не накладывает никаких ограничений на класс функций f(x), что, конечно, очень ценно.

Если ограничится для функций f(x), достаточно распространенным, но все же более узким классом гладких функций (под гладкими функциями мы будем понимать такие функции, которые непрерывны вместе со своими производными на интервале изменения аргумента), то можно воспользоваться теоремой Ферма, которая дает необходимые условия существования exst.

Теорема Ферма. Пусть функция f(x) определена в некотором интервале (а, в) и в точке "с" этого интервала принимает наибольшее (наименьшее) значение. Если существует в этой точке двухсторонняя конечная производная , то существования необходимоexst .

Примечание. Двухсторонняя производная характеризуется свойством иными словами, речь идет о том, что в точке "с" производная в пределе одна и та же при подходе к точке "с" слева и справа, т.е.f(x) – гладкая функция.

* В случае имеет местоmin, а при →max. Наконец, если при х=х 0 , то использование 2-ой производной не помогает и нужно воспользоваться, например, определением exst.

При решении задачи I необходимые условия exst (т.е. теорема Ферма) используется очень часто.

Если уравнение exst имеет вещественные корни, то точки, соответствующие этим корням, являются подозрительными наexst (но не обязательно самыми экстремумами, ибо имеем дело с необходимыми, а не с необходимыми и достаточными условиями). Так, например, в точке перегиба Х п имеет место , однако, как известно, это не экстремум.

Заметим ещё, что:

из необходимых условий нельзя сказать, какой вид экстремума найден max или min: для определения этого нужны дополнительные исследования;

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

Поэтому, когда находят точки подозрительные на exst, их дополнительно исследуют, например, на основе определения exst или 2-ой производной.