2.3.3 Метод наискорейшего спуска

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

n – размерность вектораu,Q – алгоритм вычисления целевой функцииQ (u),

L –количество шагов по конкретному направлению градиента функцииQ.

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

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

2.3.4 Метод квантования симплексов

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

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

Рисунок 2.11 –Блок-схема метода наискорейшего спуска

Алгоритм поиска заключается в следующем.

1) Определяются значения целевой функции в трех точкахS10,S20,S30, соответствующих вершинам симплекса. Из найденных значений выбирается наибольшее. В рассматриваемом примере – этоS10 (рис. 2.12).

Рисунок 2.12 –Поиск оптимума симплексным методом

2) Строится новый симплекс, для этого вершинаS10 исходного симплекса заменяется вершинойS11, расположенной симметрично вершинеS10 относительно центра грани, расположенной против вершиныS10. Построение нового симплексаS20 S30 S11 осуществляется определением центраА стороныS20 S30 треугольникаS10 S20 S30, после чего проводится прямаяS10A, на продолжении которой откладывается отрезокАS11 равныйS10А.

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

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

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

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