Глава 9. МЕТОДЫ ОДНОМЕРНОЙ МИНИМИЗАЦИИ

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

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

§ 9.1. Задача одномерной минимизации

1. Постановка задачи. Определения.

Пусть действительная функция одной переменной, определенная на множестве

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

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

х, выполняется неравенство то называется точкой строгою локальною минимума.

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

Рис. 9.1

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

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

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

2. Отрезок локализации.

Подобно тому, как алгоритмы решения нелинейных уравнений настроены на отыскание одного

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

Пример 9.2. Для функции произведем локализацию точек локального минимума.

Рис. 9.2

Из графика функции, изображенного на рис. 9.2, видно, что функция имеет две точки локального минимума первая из которых является и точкой глобального минмума. Для точки за отрезок локализации можно принять отрезок , а для точки отрезок [0, 1].

Докажем теперь, что на отрезке [0, 1] действительно содержится точка локального минимума. Для этого заметим, что Так как значения имеют разные знаки, то на отрезке [0, 1] содержится точка х, для которой Но для всех . Следовательно, и точка х на отрезке [0, 1] есть единственная точка локального

минимуыа. Аналогично доказывается, что отрезок также является отрезкам локализации.

3. Унимодальные функции.

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

Рис. 9.3

Рис. 9.4

Замечание. Унимодальная функция, вообще говоря, не обязана быть непрерывной. Например, функция, изображенная на рис. 9.4, унимодальна и имеет три точки разрыва.

Приведем достаточное условие унимодельности функций на отрезке

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

Пример 0.3. Функция унимодальна на каждом из отрезков и [0, 1]. Чтобы убедиться в этом, достаточно заметить, что

для всех и воспользоваться предложением 9.1.

Для сужения отрезка локализации точки минимума унимодальной функции полезно использовать следующее утверждение.

Предложение 9.2. Пусть унимодальная на отрезке функция и Тогда:

1°. Предположим противное: Тогда вследствие унимодальности получим , что противоречит условию.

2°. Предположим противное: Тогда вследствие унимодальности получим , что противоречит условию.

3°. В силу имеем а в силу имеем

Следовательно,

Геометрическая иллюстрация пп. 1° и 2° приведена на рис. 9 5.

Рис. 9.5

Рис. 9.6

Многие алгоритмы одномерной минимизации построены в расчете на то, что на отрезке локализации целевая функция унимодальна. В частности, такими являются алгоритмы, рассматриваемые в § 9.3.

4. Об одном подходе к локализации точки минимума.

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

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

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

Описанный метод не является строгим и не гарантирует, что отрезок локализации всегда будет найден. Например, для функции, график которой изображен пунктиром на рис. 9.6, а, при выбранном шаге А справедливы неравенства и поэтому отрезок локализации точки х обнаружен уже не будет Тем не менее этот или близкий к нему методы часто используются на практике.

Пример 9.4 Локализуем указанным выше образом точку локального минимума функции

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

Таблица 9.1 (см. скан)