Методы поиска минимума для функции многих переменных

Методы поиска минимума для функции одной переменной

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

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

Тогда точка будет лежать внутри интервала , меньшего по размеру, чем интервал .

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

Рис. 1. График унимодальной функции

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

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

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

Положим и , причем , как показано на рис. 1., и эти значения будут фиксированы, если известны , и . Если находится в интервале , то:

1. если , то новым интервалом неопределенности будет длиной ;

2. если , то новым интервалом неопределенности будет длиной .

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

Помещаем симметрично относительно точки .

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

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

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

Интервал неопределенности будет иметь длину , следовательно,

(рис. 2., нижняя часть).

На предыдущем этапе точки и должны быть помещены симметрично внутри интервала на расстоянии от концов этого интервала. Следовательно,

(рис. 2., средняя часть).

Рис. 2. Схема организации эксперимента на последней, предыдущей и пре предыдущей итерациях

Из рисунка видно, что на предпоследнем этапе остается в качестве внутренней точки.

Аналогично

(рис. 2. верхняя часть)

В общем случае

при (1.)

Таким образом,

,

и т.д.

Если определить последовательность чисел Фибоначчи следующим образом: и для , то

Если начальный интервал имеет длину , то

то есть

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

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

(2.)

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

Таким образом, поиск методом Фибоначчи, названный так ввиду появления при поиске чисел Фибоначчи, является итерационной процедурой. В процессе поиска интервала с точкой , уже лежащей в этом интервале, следующая точка всегда выбирается такой, что или

Обозначим и , тогда можно рассмотреть четыре случая организации вычислительного процесса:

1. : новый интервал , содержащий точку (рис. 3.а)

2. : новый интервал , содержащий точку (рис. 3.б)

3. : новый интервал , содержащий точку (рис. 3.в)

4. : новый интервал , содержащий точку (рис. 3.г)

Рис. 3. Схема организации вычислений по методу Фибоначчи

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

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

Метод золотого сечения почти столь же эффективен, как и метод Фибоначчи, однако при этом не требует знать – количество вычислений функции, определяемое вначале. После того как выполнено вычислений, исходя из тех же соображений, что и ранее (см. выражение (1.)), записываем

Однако, если неизвестно, то мы не можем использовать условие . Если отношение последующих интервалов будет постоянным, т.е.

(3.)

то

то есть

Таким образом, , откуда . Тогда

и так далее.

Следовательно, то есть

В результате анализа двух рассмотренных значений функции будет определен интервал, который должен исследоваться в дальнейшем. Это интервал будет содержать одну из предыдущих точек и следующую точку, помещаемую симметрично ей. Первая точка находится на расстоянии от одного конца интервала, вторая – на таком же расстоянии от другого. Поскольку , то из уравнения (2) видно, что поиск методом золотого сечения является предельной формой поиска методом Фибоначчи. Название «золотое сечение» произошло от названия отношения в уравнении (3.). Видно, что делится на две части так, что отношение целого к большей части равно отношению большей части к меньшей, т.е. равно так называемому золотому отношению.

Таким образом, если определяется интервал и имеется два значения функции и в точках и , то имеет место два случая (рис. 4.):

1. . Новый интервал неопределенности (рис. 4. а).

2. . Новый интервал неопределенности (рис. 4. б).

Рис. 4. Схема принятия решения в интервале золотого сечения

Оканчивать вычислительный процесс можно также как и в методе Фибоначчи.

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

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

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

,

где A, B и C определяются из уравнений

После преобразований этих уравнений получаем

где . Ясно, что будет иметь минимум в точке , если . Следовательно, можно аппроксимировать точку минимума функции значением

. (4)

Алгоритм поиска минимума в данном случае может быть следующим.

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

1. Вычислить и .

2. Если , то взять в качестве третьей точки и вычислить . В противном случае, в качестве третьей точки взять и найти (рис. 5.)

3. Используя эти точки, найти из уравнения (4.) и вычислить .

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

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

	А-Н А А+Н А А+Н А+2Н

Рис.5. Схема принятия решения при квадратичной аппроксимации минимизации функции

Методы поиска минимума для функции многих переменных

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

Не нашли, что искали? Воспользуйтесь поиском по сайту: