Введение в методы оптимизации

Таблица 1.1 к Ik У* Л л ) fi^k) 1 0 2 0,762 -1,629 1,238 -0,938 2 0 1,238 0,476 -1,267 0,762 -1.629 3 0,476 1,238 0,762 -1,629 0,952 -1,581 4 0,476 0,952 0,667 -1,559 0,762 -1,629 5 0,667 0,952 0,762 -1,629 0,857 -1,638 б 0,762 0,952 0,857 -1,638 0,857 -1,638 Во втором случае наименьшее значение найдено точнее, так как получено меньшее значение / ( х ) , однако это потре­ бовало большего числа шагов вычислений. Заметим, что при­ ближенное значение минимума, найденное во втором случае, с точностью до трех знаков после запятой совпало со значе­ нием, полученньш ранее методом равномерного перебора. 1.4. Метод ломаных Рассматривается задача / ( x ) ^m i n , х е [ а ; 6 ] , где а и 6 конечны. Предполагается, что / ( х ) является липшицевой на {а\Ь\ и известна константа L (или ее верхняя оценка). Данный метод позволяет находить глобальные минимумы многоэкстре­ мальных функций без предположения об унимодальности. Пусть X - произвольная точка [о;й]. Введем вспомога­ тельную функцию g{^x,x) = / ( x ) - Z , | x - x | . Эта функция явля­ ется кyco^шo-линeйнoй, и ее график состоит из участков двух прямых с угловыми коэффициентами +1 и -L . Поскольку L - константа Липшица (или ее верхняя оценка) / ( х ) на [а\Ь], то для любого х е [ а ; 6 ] имеет место неравенство ^ ( х , х ) < / ( х ) . Пусть Хц - произвольная точка [а;6]. Пусть g{x,x^) = = L \X-Х^\ и /?о(х) = g(x,x „ ) , тогда следующая точка 18