Липшицевы функции

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

Определение 2.8. Функция удовлетворяет на отрезке условию Липшица, если существует такое число (константа Липшица), что

(2.5)

для всех и , принадлежащих .

Липшицевы функции, т.е. функции удовлетворяющие условию (2.5) обладают рядом свойств.

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

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

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

3. Условие (2.5) означает, что модуль углового коэффициента любой хорды графика не превосходит .

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

Так, функция на отрезке условию Липшица не удовлетворяет, потому что при угловой коэффициент касательной к ее графику неограниченно возрастает (рис. 2.5).

Рис. 2.5. График функции , не удовлетворяющий условию

Липшица.

4. Если функция имеет на отрезке непрерывную производную, то она удовлетворяет на этом отрезке условию Липшица с константой .

По формуле конечных приращений для произвольных точек имеем: , где - некоторая точка, лежащая между и . Отсюда с учетом условия получаем неравенство (2.5) для .

5. Если , а функция непрерывна на и удовлетворяет условию (2.5) на каждом из отрезков , , с константой , то она удовлетворяет условию Липшица и на всем отрезке с константой .

Классический метод решения задачи одномерной оптимизации

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

Пусть функция кусочно-непрерывна и кусочно-гладка на отрезке . Это значит, что на отрезке может существовать лишь конечное число точек, в которых либо терпит разрыв первого рода, либо непрерывна, но не имеет производную. Тогда как известно точками экстремума функции на могут быть лишь те точки, в которых выполняется одно из следующих условий: 1) либо терпит разрыв: 2) либо непрерывна, но производная не существует; 3) либо производная существует и равна нулю; 4) либо граничные точки отрезка . Все такие точки принято называть точками, подозрительными на экстремум.

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

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

В тех случаях, когда удается вычислить в подозрительной точке производные второго и более высокого порядков, то применяют достаточное условие более общего вида. А именно, пусть известны производные , ,…, , причем при , а , . Если - четное число, то в случае в точке реализуется локальный минимум, а в случае - локальный максимум. Если же нечетно, то при в точке не может быть локального экстремума, при (или ) в случае в точке имеем локальный минимум (максимум), а в случае - локальный максимум (минимум).

Чтобы найти глобальный минимум (максимум) функции на , нужно перебрать все точки локального минимума (максимума) на и среди них выбрать точку с наименьшим (наибольшим) значением функции, если таковое существует.

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

Шаг 1. Найти все точки, подозрительные на экстремум, в том числе и стационарные точки, т.е. корни уравнения

. (2.6)

Пусть это будут точки . Положить , .

Шаг 2. Вычислить значения функции в точках , .

Шаг 3. Найти . Положить .

Пример 2. 5. Решить задачу классическим методом.

Шаг 1. Находим корни уравнения из интервала : , . Полагаем , .

Шаг 2. Вычисляем значения в точках , : , , , .

Шаг 3. Находим =-17=. Поэтому , .

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

Контрольные вопросы

1. Дайте математическую постановку задачи одномерной оптимизации.

2. Дайте определения точки локального минимума и точки глобального минимума функции одной переменной.

3. Опишите понятие точной нижней грани функции

4. Дайте определение минимизирующей последовательности.

5. Приведите определение унимодальной на отрезке функции и её основные свойства.

6. Приведите определение выпуклой на отрезке функции и её основные свойства.

7. Какие функции называют липшицевыми и в чём смысл условия Липшица?

8. Как находится константа Липшица для непрерывно дифференцируемых функций?

9. В чем заключается классический метод минимизации?

10. Чем объясняется ограниченное применение классического метода?

Дата добавления: 2014-01-06