Методические указания к курсовой работе для студентов специальности «Управление и информатика в технических системах» (стр. 4 из 8)

.

Из этих формул находится

.

Если

, то .

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

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

7. Вычислить значение каждой координаты

новой пробной точки:

.

Переход к п. 3.

8. За точку минимума принимается точка

.

Вследствие конечности шагов поиска градиентные методы также, как и методы покоординатного поиска, могут привести к ложному оптимуму, особенно при наличии «оврагов» и «гребней».

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

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

с помощью ряда Тейлора, ограниченного членами со вторыми производными:

.

где

– градиент второго порядка, представляющий квадратичную матрицу Гессе типа:

Оптимизируя

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

т. е. и направление, и значения шага определяются одновременно.

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

Сходимость метода Ньютона к локальному экстремуму гарантируется только при положительности

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

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

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

,

где

Благодаря суммированию направлений

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

3.8 Методы случайных направлений

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

,

где

– единичные векторы случайных направлений, а – соответствующие приращения целевой функции.

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

Более развитые случайные методы полностью исключают определенность при выборе направлений поиска. Если принять, что

,

где

– первый случайный вектор, определенный в точке , и обеспечивающий улучшение , то можно построить многошаговый процесс поиска, сходящийся к локальному оптимуму. В каждой точке перебираются случайные направления до тех пор, пока не будет найден . В более общем случае можно рассматривать несколько удачных случайных направлений и выбирать то, которое доставляет наибольшее приращение . Для преодоления «оврагов» и «хребтов» можно учитывать предыдущие направления поиска, т. е. принимать:

.

Чтобы избежать нормирования векторов направления, присущего детерминированным методам, можно рассматривать

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

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

.

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

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

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

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