Курсовая работа: Исследование методов оптимизации

где

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

2.2 Градиентный метод с дроблением шага

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

(2.2)

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

Выберем произвольным образом точку , направление и сконструируем луч

. (2.3)

Рассмотрим вопрос о выборе направления , обеспечивающего (2.2). Для этого изучим поведение вдоль луча . Имеем

Введем

(2.4)

Здесь

В соответствии с (2.3)

Тогда

Вычислим (2.5)

Теперь, чтобы для любого обеспечить отрицательность (2.5), достаточно положить , где произвольная положительно определенная матрица. Тогда

При этом (2.6)

Выбрав каким-либо образом , получим Затем аналогично рассчитаем

Общее рекуррентное соотношение имеет вид :

(2.7)

Различные варианты градиентных процедур отличаются друг от друга способом выбора .

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

(2.8)

(2.9)

где и -некоторые достаточно малые числа .

Понятно, что критерий (2.8) хорош в тех случаях, когда функция в окрестности минимума, используя ранее введенную классификацию, имеет характер «глубокой» впадины. С другой стороны, если функция ведет себя как «пологое плато», то более предпочтительным является критерий (2.9).Аналогом критерия (2.8) является другое часто применяемое правило останова :

, (2.10)