4.2.3.7. Методы второго порядка
Методы второго порядка основаны на учете третьего члена в разложении функции n переменных в ряд Тейлора, содержащем вторые производные ЦФ.
К методам второго порядка относятся обычный метод Ньютона и ряд его модификаций.
Обычный метод Ньютона предполагает построение итеративного процесса поиска экстремума по формуле
X k+1 = Xk - G(Xk)-1 grad z(Xk) , k=0,1,2,… , (4.36)
где G(Xk)-1 – обратная матрица Гессе, рассчитанная в точке Xk .
При решении задач минимизации выпуклых функций метод Ньютона обладает более высокой скоростью сходимости, чем градиентные методы, так как позволяет резко уменьшить число шагов, необходимых для достижения точки оптимума.
Условие сходимости данного метода сводится к требованию, чтобы начальное приближение X0 лежало в достаточно малой окрестности точки локального минимума. Вместе с тем на практике условие близости начальной точки к точке оптимума часто бывает трудно выполнить. Поэтому при неудачном начальном приближении X0 использование этого метода может привести к расходящемуся процессу. Рассмотренную особенность следует рассматривать как недостаток метода.
Для преодоления этого недостатка разработан модифицированный метод Ньютона с регулировкой шага [22]. Этот метод сходится к решению независимо от выбора начальной точки X0. Рекуррентная формула этого метода имеет вид
X k+1 = Xk - hk G(Xk)-1 grad z(Xk) , hk > 0, k=0,1,2,… . (4.37)
(При этом в качестве hk может быть использован оптимальный шаг [20]).
Близким к рассмотренному является модифицированный метод Ньютона [49], в котором
X k+1 = Xk - m r G(Xk)-1 grad z(Xk) , k=0,1,2,… . ( 4.38)
где r = ±1 – коэффициент направления; 0< m £ 1 – постоянный множитель. Коэффициент направления r выбирается из условия, чтобы первая вариация ЦФ была отрицательной, а параметр m - из требования обеспечения условия убывания ЦФ.
Общим недостатком методов второго порядка является то, что в процессе поиска необходимо вычислять матрицу вторых производных (матрицу Гессе) и находить для нее обратную матрицу. Объем таких вычислений очень велик (Дополнительные вычислительные трудности возникают также при близости определителя матрицы Гессе к нулю).
В связи с указанными недостатками на практике чаще используются методы поисковой оптимизации, обладающие скоростью сходимости методов второго порядка, но не требующие вычисления обратной матрицы вторых производных. (Такие методы были рассмотрены нами в предыдущем пункте.)
4.3. Задачи и методы условной оптимизации НП
4.3.1. Общие вопросы
Если минимум целевой функции находится внутри допустимой области изменения переменных (в ОДР), то наличие ограничений не влияет на процесс поиска решения. Поиск минимума осуществляется практически так же, как и в случае без ограничений. Если точка минимума находится за пределами допустимой области, то отыскание наименьшего значения целевой функции при ограничениях на переменные становится существенно сложнее.
Методы условной оптимизации могут быть разделены на различные группы. Так, могут быть выделены аналитические и численные методы. Могут быть также выделены методы для решения задач НП с ограничениями типа равенств и типа неравенств. (С учетом таких разновидностей необходимо рассматривать четыре класса методов).
З а м е ч а н и е 4.27. Поскольку в задачах с ограничениями наибольшее или наименьшее может быть достигнуто на границе ОДП, то следует говорить о нахождении точки оптимума.
Методы условной оптимизации существенно различаются по видам функциональных ограничений. В связи с этим далее нами будут рассмотрены отдельно такие задачи с ограничениями типа равенств и ограничениями типа неравенств.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.