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

X, G [a;6] определяется из условия (х,) = niin Ра(х). Оче- х&\а\Ь\ ^ ^ видно, Х| = а илих, =6 . Далее строится функция р^{х) = =max{g(x,x,),p „(x)}, где g(x,x,) =/ ( х , ) -Z, | x-x , |, и на­ ходится следующая точка Х2е[а;&] из условия = = min D(х) и т. д. Пусть точки Х0,Х|,...,Х„ уже найдены. Тогда строится функция р„ (х) =max { g ( х , х„), р„_, (х)} =max g (х , хЛ, и сле- ^ 0<iSn дующая точка х,,^, е[а;Ь] определяется из условия р„ (х,,^ ) = min р„(х). Если минимум р^, (х) достигается xela ; b] В нескольких точках, то в качестве x^^j можно взять любзто из них. Очевидно, (х) является кусочно-линейной функцией, и ее график представляет собой ломаную, состоящую из от­ резков прямых с угловыми коэффициентами +L и —L. Для любого х е [ а ; й ] справедливы неравенства g-(x,x, ) </ ( х ) , i = 1,п, а значит, и неравенства /?„ (х) </ (х) , и = 0,1,2,... Та- ким образом, на каждом шаге метода ломаных требуется ми­ нимизировать кусочно-линейную функцию (х), что мол<ет быть сделано простым перебором вершин соответствующей ломаной. Доказывается, что последовательность {х^^.], построен­ ная методом ломаных, удовлетворяет условиям Ит/(д;„) = (х„,, ) =Л = min / ( х ) /;—>со ^ п—'хо ^ Л'е[г7 ; Ь] 19'