Ф.П. Васильев - Методы оптимизации (2002), страница 4

Пусть функция у(х) кусочно непрерывна и кусочно гладка на отрезке [ц, 6]. Это значит, что на [а, 6] может существовать лишь'конечное число точек, в которых у(х) либо терпит разрыв первого рода, либо непрерывна, но не имеет производной. Тогда, как известно, точками экстремума функции у(х) на [а, Ь] могут быть лишь те точки, в которых выполняется одно из следующих условий: 1) либо У(х) терпит разрыв; 2) либо 1'(х) непрерывна, но производная )'(х) не существует; 3) либо производная !'(х) существует и равна нулю; 4) либо х = а или х = 6. Такие точки принято называть точками, подозрительными на экстремум, Поиск точек экстремума функции начинают с нахождения всех точек, подозрительных на экстремум, После:того как такие точки найдены, проводят дополнительное исследование и отбирают среди них те,,которые являются точками локального минимума или максимума.

Для этого обычно исследуют знак первой производной [',(х) в окрестности (или соответствующей полу- окрестности точек разрыва и граничных точек х = а,х = 6) подозрительной точки. Для того чтобы подозрительная точка е е [а„Ь] была точкой локального минимума, достаточно, чтобы !!ш,)'(х),> у(е), 1!гп 1'(х) > ]'(е) и при ь — е — О е еье некотором сг > О на множествах [а, 6]П(е, е+ сг) = Ое(е), [а, Ь]П(и — се, е) = = 0 (е) существовала производная у'(х), причем б(х) > О при х Е О.+(е) и у'(х) <О при х Е 0,(е).

Если же 1!ш )(х) < 1(е), 1пп У(х) < у(е) и у'(х) < О при х Е 0„"(е), у '(х) > О при х Е 0 (и), то е — точка локального максимума. В тех случаях, когда удается вычислить в подозрительной точке производные второго и более высокого порядков, то их также можно использовать для исследования поведения функции в окрестности этой точки. А именно, пусть известны производные у'(е),...,!(-1(е), причем !ЧО(е) = О (г = 1,...,и — 1), а у! 1(е) ф О (и > 1), Если и — четное число, то в случае )ч"1(е) > О в точке е реализуется локальнгяй минимум, а в случае !'1"1(е) < Π— локальный максимум, Если п нечетно, то прн а < е < Ь в точке е не может быть локального минимума или максимума; при и = а (е = 6) в случае у'1(е) > О в точке и имеем локальный минимум (максимум),.а в случае ~'1(е) < Π— локальный максимум (минимум). Чтобы найти глобальный минимум (максимум) функции у(х) на [а, 6], нужно перебрать все точки локального минимума (максимума) на [а, Ь] и среди них выбрать точку с наименьшим (наибольшим) значением функции, если таковое существует.

Если вместо отрезка [а, 6] имеем дело со множеством Х = (х: а < х < оо), или Х = (х: — оо < х < Ь), или Х = К, то наряду с вышеописанными исследованиями нужно также изучить поведение функции при х — оо или х — -оо. Классический метод исследования функции на экстремум следует использовать во всех тех случаях, когда достаточно просто удается выявить все подозрительные на экстремум точки и реализовать описанную выше схему отбора экстремальных точек. К великому сожалению, классический метод имеет весьма ограниченное применение.

Дело в том, что вычисление производной у'(х) в практических задачах зачастую является непростым делом. Например, может оказаться, что значения функции у(х) определяются из наблюдений или каких-либо физических экспериментов, и получить информацию о ее производной крайне трудно, Но даже в тех случаях, когда производную все же удается вычислить, решение уравнения у'(х) =О и выявление других точек, подозрительных на экстремум, может быть связано с серьезными трудностями. Поэтому важно иметь также и другие методы поиска экстремума, не требующие вычисления производных, более удобные для реализации на современных ЭВМ.

Упражнения 1. Найти точки экстремума фуикции г"(х) = з!п я+ созе е иа отрезках [О, Зя/4], [О, 2к]. 2. Пусть т(х) = (1+ еке) 1 при я тО и т(0) = О. Найти точки экстремума этой функции иа отрезках [0> 1], [ — 1, О], [ — 1, 1), [1, 2] и иа и. 3. пусть непрерывная иа отрезке [а, ь] функция г(я) в точке е (а < е < ь) имеет строгий локальный минимум.

Можно ли утверждать, что существует число о > 0 такое, что г(з) монотонно убывает при е — о < я < е и монотонна возрастает при е < е < е+ а? Рассмотреть функцию г(с) = 2х + иг з1п(1/я) (е ~ 0), Г(0) =0 иа [ — 1, 1). Исследовать случай, когда г(х) имеет ив [о, Ь] конечное число точек локального экстремума. 4. Пусть функция Де) определена па [а,ь) и дважды диффереицируема в точке е я [а,ь]. Доказать, что если о < е < Ь и в точке е реализуется локальиыи минимум у(м), то необходимо, чтобы ге(х) ) О. Будет ли верным это утверждение, если е = а или е = Ьу Будет ли оио верным, г если о = а или е = Ь и, кроме того т"'(е) =О? Рассмотреть функции 1(х) ='-я, т(х) =созе иа [ — ~г, к], б.

Пусть функция т" (х) определеиз иа [а, Ь] и в точке е Е [а, Ь] имеет и производных (и ) 2), причем известио, что 110(е) = 0 при з = 1,..., п — 1 и 1(е1(е) ф О. Доказать, что если е— точка аокальиога минимума и а< е < ь, то п — четное число и г (е) > О. что изменится, (е) если о=вили е=Ь) 6. Пусть функция у"(е) аналитична иа [а, Ь], т, е, ряд Тейлора этой функции сходится к т(к) во всех точках [а, Ь]. Может ли эта функция иметь иа [о, Ь) бесконечное число точек локального экстремума? 7. Пусть функция г"(х) определена па [о, Ь]и в точке е имеет производные всех порядков. Можно аи утверждать, что если е †точ локального минимума, то у (е) ф 0 при каком(") либо и ) !? Рассмотреть функцию у(з) = е ~Ы (я ~ 0), г(0) = 0 в точке о = О, Что изменится, если функция г'(х) аналитична па [а, Ь]У 3.

Пусть фуикция г"(и) диффереицируема иа [а,Ь) и в точке е и [а, Ь) достигает своей нижней греки иа [а, Ь]. Доказать, что тогда необходимо, чтобы ~'(е)(х — е) > 0 при всех з Е а [а, Ь]. Будет ли выполнение етого условия достаточно дая того, чтобы в точке е достигалась нижняя грань т"(е) иа [а, Ь)? й 3. Метод деления отрезка пополам Простейшим методом минимизации функции одной переменной, не требующим вычисления производной, является метод деления отрезка пополам, Опишем его, предполагая, что минимизируемая функция у'(х) унимодальна на отрезке [а, 6].

Поиск минимума )'(х) на [а, 6] начинается с выбора двух 17 16 Гл. 1. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ ОДНОЙ ПЕРЕМЕННОЙ 6 3. МЕТОД ДЕЛЕНИЯ ОТРЕЗКА ПОПОЛАМ точек х, = (а+ Ь вЂ” б)/2 и х, =(а+ 6+ б)/2, где б — постоянная, являющаяся параметром метода, 0 < б < 6 — а. Величина б выбирается вычислителем и может определяться целесообразным количеством верных десятичных знаков при задании аргумента х. В частности, ясно, что б не может быть меньше машинного нуля ЭВМ, используемой при решении рассматриваемой задачи. Точки х„х, расположены симметрично на отрезке [а, 6] относительно его середины и при малых б делят его почти пополам — этим и объясняется название метода. После выбора точек х„ х, вычисляются значения /(х(), /(х,) и сравниваются между собой. Если /(х,) < /(х,), то полагают а, = а, 6, = х„ если же /(хг) > /(х,), то полагают а, = х,, 6, = 6.

Поскольку /(х) унимодальна на [а, 6], то ясно, что отрезок [а„ Ь,] имеет общую точку с множеством Х„ точек минимума /(х) на [а, 6] и его длина равна Ь, — а, = (Ь вЂ” а — б)/2+ б. Пусть отрезок [аь „6„,], имеющий непустое пересечение с Х„, уже известен, и пусть 6„, — а,, =(Ь вЂ” а — б)/2" '+ б > б (6 > 2). Тогда*берем точки х,„, =(а,,+Ь,,— б)/2, х„=(а,,+Ь„,+б)/2, расположенные на отрезке [а „6,,], симметрично относительно его середины, и вычисляем значения /(т,),/(хзь), Если /(х,,) < /(хм), то полагаем а = а„ Ь = х,„; если же /(хз„,) > /(х, ), то полагаем а„= х„„Ь„= 6„,. Длина получившегося отрезка [а,, Ьь] равна ܄— а„=(6 — а — б)/2'+б > б и [а, 6,]п П Х„~ ч'.(.

Если количество вычислений значений минимизируемой функции ничем не ограничено, то описанный процесс деления отрезка пополам можно продолжать до тех пор, пока не получится отрезок [а„Ь„] длины Ь~ -'аь < е, где е — заданная точность, е > б, Отсюда имеем, что й > 1од ((Ь вЂ” а- б)/(е— — б)). Поскольку каждое деление пополам требует двух вычислении значений функции, то для достижения точности ܄— а, < е требуется всего п = 26 > 2 1од,((6 — а — б)/(е — б)) таких вычислений. После определения отрезка [а„, Ьь] в качестве приближения, ко множеству Х можно взять точку х„= хз ( при /(хзь — ~) < /(хзь) и при /(х,,) > /(хзз), а значит /(х„) может служить приближением для (й1 /(х).

При таком выборе приближения для Х„будет допущена ке(а,ь( погрешность р(х, Х„) < шахТ܄— х„; х„— а ) =(6 — а — б)/2"'. Если не требовать того, чтобы значение функцйи, принимаемое за приближение к /„, было вычислено непременно в той же точке, которая служит приближением к Х„, то вместо х„можно взять точку е„= (а + Ь.)/2 с меньшей погрешностью р(х„, Х.) < (Ь, — а„)/2 = (Ь вЂ” а — б)/2 + ' + б/2 (здесь й = о/2 и б достаточно мало). Конечно, и в этом случае можно бы провести еще одно дополнительное вычисление значения функции в точке о„и принять |(о„) ж/,.

Однако заметим, что на практике нередко встречаются функции, нахождение значения которых в каждой точке связано с большим объемом вычислений или 'дорогостоящими экспериментами, наблюдениями, — понятно, что здесь приходится дорожить каждым вычислением значения минимизируемой функции. В таких ситуациях возможно даже, что число и, определяющее количество вычислений значений функции, заранее жестко задано и превышение его недопустимо. Из предыдущего следует, что методом деления отрезка пополам с помощью и = 26 вычислений значений функции можно определить точку ми- нимума унимодальной функции на отрезке [а, 6] в лучшем случае с точностью =(6 — а)2 ' "Н.

Возникает вопрос, не существует ли методов, позволяющих с помощью того же числа вычислений значений функции решить задачу минимизации унимодальной функции поточнее? Оказывается, такие методы есть. Один из них будет описан в З 4. В заключение отметим, что метод деления отрезка пополам без изменений можно применять для минимизации функций, не являющихся унимодальными. Однако в этом случае нельзя гарантировать, что найденное решение будет достаточно хорошим приближением к глобальному минимуму. 9 4.