Квази-ньютоновский метод

4.11. Симплекс-метод

Этот алгоритм не использует производные функции потерь. Вместо этого, при каждой итерации функция оценивается в m+1 точках m -мерного пространства. Например, на плоскости (т.е., при оценивании двух параметров) программа будет вычислять значение функции потерь в трех точках в окрестности текущего минимума. Эти три точки определяют треугольник; в многомерном пространстве. Получаемая фигура называется симплекс. Интуитивно понятно, что в двумерном пространстве три точки позволяют выбрать “в каком направлении двигаться”, т.е., в каком направлении на плоскости менять параметры для минимизации функции. Похожие принципы применимы в многомерном параметрическом пространстве; т.е., симплекс будет постепенно “смещаться вниз по склону”, в сторону минимизации функции потерь; если же текущий шаг окажется слишком большим для определения точного направления спуска, (т.е., симплекс слишком большой), процедура произведет уменьшение симплекса и продолжит вычисления.

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

4.12.Метод Хука-Дживиса

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