Многомерные методы

Многомерные методы можно классифицировать по пяти широким категориям.

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

Второе семейство образуют direction set methods, известные также как line minimization methods или (методы сопряженных направляющих) conjugate direction methods. Наиболее примечательными среди них являются различные методы Пауэла. В смысле скорости они эффективнее симплекс-методов скорейшего подъема (не путайте с симплекс-алгоритмом для линейных функций, упоминавшимся ранее), не требуют вычисления частных производных первого порядка, но требования по памяти по-прежнему имеют порядок п2.

Третье семейство образуют метод сопряженных градиентов conjugate gradient methods. Среди них выделяются методы Флет-чера-Ривза и тесно примыкающие к ним методы Полака-Рибьера. Они тяготеют к группе наиболее эффективных методов в смысле скорости и памяти (порядка п), но требуют вычисления частных производных первого порядка.

Четвертое семейство методов многомерной оптимизации образуют квази-ньтоновы, или методы с переменной метрикой variable metric methods. Туда входят алгоритмы Дэвидсона-Флет-чера-Пауэла (DiP) и Бройдена-Флетчера-Годдфарба-Шанно (B.fGS). Подобно conjugate gradient methods, они требуют вычисления частных производных первого порядка, обычно быстро приводят к экстремуму, однако эти алгоритмы требуют большей памяти (порядка п2). Вместе с тем они уравновешивают достоинства conjugate gradient methods тем, что дольше известны, шире используются и лучше документально обеспечены.

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