Методы безусловной оптимизации

 

Рис.6

 

 

 

В этом методе направление  из касается линии в

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

Все градиентные методы плохо работают в овражных функциях.

Условия окончания итерационного поиска в градиентных методах связывают обычно с величиной градиента (критерий с номером 3).

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

 

 

Рис.7

 

 

 

 

 

Метод сопряженных градиентов является попыткой объединить достоинства методов первого и второго порядков с исключением их недостатков.

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

 

 

 

Метод тяжелого шарика

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

X_i+1 = X_i - a(X_i –X_i-1) – h gradF(X_i)

При a = 0 – метод превращается в обычный градиентный. При 0 < a < 1 можно получать различную эффективность метода, которая будет зависеть и от h. Вдали от оптимума поиск будет ускоряться, а вблизи возможны колебания около минимума.

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

 

 

Рис.8

 

 

 

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

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

 

Метод случайного поиска 

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

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

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

Метод особенно эффективен для овражных функций, т.к. свойства функции не оказывают существенного влияния на характер поиска.

 

Рис.9

 

 

Оценка алгоритма по точности поиска производится путем вычисления уже известных локальных характеристик e, d, g после выполнения заданного числа итераций N. Они отражают степень приближения к оптимуму, как по координатам, так и по критерию оптимальности. Характеристика g используется лишь в специальных случаях: учет ограничений в неявной форме, поиск с помощью градиентных методов, методов переменной метрики и т.д.

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

Оценка алгоритма по скорости сходимости в некотором  смысле обратна оценке их точности. При ее вычислении фиксируется точность e или d и производится сравнение алгоритмов по числу пробных шагов N, необходимых для точности. Эта характеристика не зависит от быстродействия ЭВМ (а лишь от длины разрядной сетки), сложности модели проектируемого объекта и поэтому является показателем эффективности алгоритма. Она зависит от точности на каждой из двух стадий поиска. Задание высокой точности может увеличить существенно общее число обращений к модели (пробных вычислений) даже в сл. совершенного способа выбора направления. Необоснованное же снижение точности может нарушать теоретическое предположения, положенные в  основу выбора направления (например, условие ортогональности в методе сопряженных градиентов). В качестве компромиссных вариантов м.б. использован критерий с заданным числом проб в одномерном поиске.

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

 

- относительное время.