27
1. Минимум функции одного переменного
ЗАКЛЮЧЕНИЕ
Перечислим наиболее важные примеры множеств, на которых приходится решать задачу нахождения минимума. Если множество является числовой осью, то (1) и (2) есть задача на минимум функции одного вещественного переменного. Если есть -мерное векторное пространство, то мы имеем дело с задачей на минимум функции переменных. Если есть пространство функций , то (1) называют задачей на минимум функционала.
Для нахождения абсолютного минимума есть только один способ: найти все локальные минимумы, сравнить их и выбрать наименьшее значение. Поэтому задача (2) сводится к задаче (1), и мы будем в основном заниматься задачей поиска локальных минимумов.
Известно, что решение задачи (1) удовлетворяет уравнению
. (3)
Если множество есть числовая ось, то написанная здесь производная является обычной производной, и тогда уравнение (3) есть просто одно (нелинейное) уравнение с одним неизвестным. Для -мерного векторного пространства соотношение (3) оказывается системой нелинейных уравнений . Для пространства функций уравнение (3) является дифференциальным или интегро-дифференциальным. В принципе такие уравнения можно решать итерационными методами. Однако эти уравнения нередко имеют сложный вид, так что итерационные методы их решения могут очень плохо сходиться или вообще не сходиться. Поэтому в данной главе мы рассмотрим численные методы, применимые непосредственно к задаче (1), без приведения ее к форме (3).
Пусть является некоторым множеством, принадлежащим какому-то пространству. Тогда (1) называют задачей на минимум в ограниченной области. В частности, если множество выделено из пространства с помощью ограничивающих условий типа равенств, то задачу (1) называют задачей на условный экстремум; такие задачи методом неопределенных множителей Лагранжа часто можно свести к задачам на безусловный экстремум. Однако при численном решении обычно удобнее иметь дело непосредственно с исходной задачей (1), хотя при ее решении в ограниченной области возникают свои трудности.
Функция может иметь на множестве более одного локального минимума. В конкретных прикладных задачах далеко не всегда удается заранее исследовать свойства функции. Поэтому желательно, чтобы численный алгоритм позволял определить число минимумов и их расположение и аккуратно найти абсолютный минимум.
Задачу называют детерминированной, если погрешностью вычисления (или экспериментального определения) функции можно пренебречь. В противном случае задачу называют стохастической. Мы будем рассматривать в основном детерминированные задачи. Для решения стохастических задач есть специальные методы, но они очень медленные, и применять их к детерминированным задачам невыгодно.
1.2 Золотое сечение
В этом параграфе мы рассмотрим задачу нахождения минимума функции одной действительной переменной. Эта одномерная задача нередко возникает в практических приложениях. Кроме того, большинство методов решения многомерных задач сводится к поиску одномерного минимума.
Сейчас мы рассмотрим метод золотого сечения, применимый к недифференцируемым функциям. Будем считать, что задана и кусочно-непрерывна на отрезке , и имеет на этом отрезке (включая его концы) только один локальный минимум. Построим итерационный процесс, сходящийся к этому минимуму.
Вычислим функцию на концах отрезка, а также в двух внутренних точках , сравним все четыре значения функции между собой и выберем среди них наименьшее. Пусть наименьшим оказалось . Очевидно, минимум расположен в одном из прилегающих к нему отрезков (см. рис. 1). Поэтому отрезок можно отбросить и оставить отрезок . Первый шаг процесса сделан.
a x1 x3 x2 b
Рис. 1
На отрезке снова надо выбрать две внутренние точки, вычислить в них и на концах отрезка значения функции, и сделать следующий шаг процесса. Но на предыдущем шаге вычислений мы уже нашли на концах нового отрезка и в одной его внутренней точке . Поэтому достаточно выбрать внутри еще одну точку , определить в ней значение функции и провести необходимые сравнения. Это вчетверо уменьшает объем вычислений на одном шаге процесса.
Как выгодно размещать точки? Всякий раз мы делим оставшийся отрезок на три части (причем одна из точек деления уже определена предыдущими вычислениями) и затем отбрасываем один из крайних отрезков. Очевидно, надо, чтобы следующий отрезок был поделен подобно предыдущему. Для этого должны выполняться соотношения
.
Решение этих уравнений дает
. (4)
После проведения очередного вычисления отрезок сокращается в раза; после вычислений функции он составляет долю первоначальной величины (три первых вычисления в точках еще не сокращают отрезок). Следовательно, при длина оставшегося отрезка стремится к нулю как геометрическая прогрессия со знаменателем , т. е. метод золотого сечения всегда сходится, причем линейно.
Запишем алгоритм вычисления. Для единообразия записи обозначим
,
а поочередно вводимые внутренние точки будут На первом шаге полагаем согласно (4)
. (5)
После сравнения может быть отброшена точка с любым номером, так что на следующих шагах оставшиеся точки будут перенумерованы беспорядочно. Пусть на данном отрезке есть четыре точки из которых какие-то две являются концами отрезка. Выберем ту точку, в которой функция принимает наименьшее значение; пусть это оказалась :
. (6)
Затем отбрасываем ту точку, которая более всего удалена Это верно не при всяких делениях отрезка, но для деления в соответствии (4) это справедливо. от ; пусть этой точкой оказалась :
. (7)
Определим порядок расположения оставшихся трех точек на числовой оси; пусть, для определенности,
. (8)
Тогда новую внутреннюю точку введем таким соотношением См. предыдущую сноску.:
, (9)
и присвоим ей очередной номер. Минимум находится где-то внутри последнего отрезка, . Поэтому итерации прекращаем, когда длина этого отрезка станет меньше заданной погрешности :
. (10)
Метод золотого сечения является наиболее экономичным аналогом метода дихотомии применительно к задачам на минимум. Он применим даже к недифференцируемым функциям и всегда сходится; сходимость его линейна. Если на отрезке функция имеет несколько локальных минимумов, то процесс сойдется к одному из них (но не обязательно к наименьшему).
Этот метод нередко применяют в технических или экономических задачах оптимизации, когда минимизируемая функция недифференцируема, а каждое вычисление функции - это дорогой эксперимент.
Метод золотого сечения рассчитан на детерминированные задачи. В стохастических задачах из-за ошибок эксперимента можно неправильно определить соотношение между значениями функций в точках; тогда дальнейшие итерации пойдут по ложному пути. Поэтому если различия функций в выбранных точках стали того же порядка, что и ошибки эксперимента, то итерации надо прекращать. Поскольку вблизи минимума чаще всего , то небольшая погрешность функции приводит к появлению довольно большой области неопределенности .
2. Минимум функции многих переменных
2.1 Рельеф функции
Основные трудности многомерного случая удобно рассмотреть на примере функции двух переменных . Она описывает некоторую поверхность в трехмерном пространстве с координатами . Задача означает поиск низшей точки этой поверхности.
Изобразим рельеф этой поверхности линиями уровня. Проведем равноотстоящие плоскости и найдем линии их пересечения с поверхностью ; проекции этих линий на плоскость называют линиями уровня. Направление убывания функции будем указывать штрихами, рисуемыми около линий уровня. Полученная картина напоминает топографическое изображение рельефа горизонталями. По виду линий уровня условно выделим три типа рельефа: котловинный, овражный и неупорядоченный.
а) б)
в)
Рис. 2 г)
При котловинном рельефе линии уровня похожи на эллипсы (рис. 1, а). В малой окрестности невырожденного минимума рельеф функции котловинный. В самом деле, точка минимума гладкой функции определяется необходимыми условиями
, (11)
и разложение функции по формуле Тейлора вблизи минимума имеет вид
, (12)
причем квадратичная форма (12) - положительно определенная Квадратичная форма называется положительно определенной, если при любых (за исключением обращающихся одновременно в нуль) она положительна., иначе эта точка не была бы невырожденным минимумом. А линии уровня знакоопределенной квадратичной формы - это эллипсы.
Случай, когда все вторые производные равны в этой точке нулю и минимум определяется более высокими производными, по существу ничего нового не дает, и мы не будем его специально рассматривать (линии уровня вместо эллипсов будут похожими на них кривыми четвертого порядка).
Отметим, что условию (11) удовлетворяют также точки максимумов и седловые точки. Но в точках максимумов квадратичная форма (12) отрицательно определенная, а в седловинах она знакопеременна.
Вблизи минимума функция мало меняется при заметных изменениях переменных. Поэтому даже если мы не очень точно определим те значения переменных, которые должны минимизировать функцию, то само значение функции при этом обычно будет мало отличаться от минимального.
Рассмотрим овражный тип рельефа. Если линии уровня кусочно-гладкие, то выделим на каждой из них точку излома. Геометрическое место точек излома назовем истинным оврагом, если угол направлен в сторону возрастания функции, и гребнем - если в сторону убывания (рис. 2, б). Чаще линии уровня всюду гладкие, но на них имеются участки с большой кривизной; геометрические места точек с наибольшей кривизной назовем разрешимыми оврагами или гребнями (рис. 2, в). Например, рельеф функции
, (13)
изображенный на этом рисунке, имеет ярко выраженный извилистый разрешимый овраг, «дно» которого - синусоида, а низшая точка - начало координат.
В физических задачах овражный рельеф указывает на то, что вычислитель не учел какую-то закономерность, имеющую вид связи между переменными. Обнаружение и явный учет этой закономерности облегчает решение математической задачи. Так, если в примере (13) ввести новые переменные , то рельеф становится котловинным.
Неупорядоченный тип рельефа (рис. 2, г) характеризуется наличием многих максимумов, минимумов и седловин. Примером может служить функция
, (14)
рельеф которой изображен на этом рисунке; она имеет минимумы в точках с координатами и максимумы в точках, сдвинутых относительно минимумов на по каждой координате.
Все эффективные методы поиска минимума сводятся к построению траекторий, вдоль которых функция убывает; разные методы отличаются способами построения таких траекторий. Метод, приспособленный к одному типу рельефа, может оказаться плохим на рельефе другого типа.
2.2 Спуск по координатам
Казалось бы, для нахождения минимума достаточно решить систему уравнений типа (11) методом линеаризации или простых итераций и отбросить те решения, которые являются седловинами или максимумами. Однако в реальных задачах минимизации эти методы обычно сходятся в настолько малой окрестности минимума, что выбрать подходящее нулевое приближение далеко не всегда удается. Проще и эффективнее провести спуск по координатам. Изложим этот метод на примере функции трех переменных .
Выберем нулевое приближение . Фиксируем значения двух координат . Тогда функция будет зависеть только от одной переменной ; обозначим ее через . Найдем минимум функции одной переменной и обозначим его через . Мы сделали шаг из точки в точку по направлению, параллельному оси ; на этом шаге значение функции уменьшилось.
Затем из новой точки сделаем спуск по направлению, параллельному оси , т. е. рассмотрим , найдем ее минимум и обозначим его через . Второй шаг приводит нас в точку . Из этой точки делаем третий шаг - спуск параллельно оси и находим минимум функции . Приход в точку завершает цикл спусков.
Будем повторять циклы. На каждом спуске функция не возрастает, и при этом значения функции ограничены снизу ее значением в минимуме . Следовательно, итерации сходятся к некоторому пределу . Будет ли здесь иметь место равенство, т. е. сойдутся ли спуски к минимуму и как быстро?
Это зависит от функции и выбора нулевого приближения. На примере функции двух переменных легко убедиться, что существуют случаи сходимости спуска по координатам к искомому минимуму и случаи, когда этот спуск к минимуму не сходится.
Будем двигаться по выбранному направлению, т. е. по некоторой прямой в плоскости . В тех участках, где прямая пересекает линии уровня, мы при движении переходим от одной линии уровня к другой, так что при этом движении функция меняется (возрастает или убывает, в зависимости от направления движения). Только в той точке, где данная прямая касается линии уровня (рис. 3, а), функция имеет экстремум вдоль этого направления. Найдя такую точку, мы завершаем в ней спуск по первому направлению, и должны начать спуск по второму направлению (поскольку направления мы сейчас выбираем параллельно координатным осям, то второе направление перпендикулярно первому).
Пусть линии уровня образуют истинный овраг. Тогда возможен случай (рис. 3, б), когда спуск по одной координате приводит нас на «дно» оврага, а любое движение по следующей координате (пунктирная линия) ведет нас на подъем. Никакой дальнейший спуск по координатам невозможен, хотя минимум еще не достигнут; процесс спуска по координатам в данном случае не сходится к минимуму.
Наоборот, если функция достаточно гладкая, то в некоторой окрестности минимума процесс спуска по координатам сходится к этому минимуму. Пусть функция имеет непрерывные вторые производные, а ее минимум не вырожден. Для простоты опять рассмотрим функцию двух переменных . Выберем некоторое нулевое приближение и проведем линию уровня через эту точку. Пусть в области , ограниченной этой линией уровня, выполняются неравенства, означающие положительную определенность квадратичной формы (12):
. (15)
Докажем, что тогда спуск по координатам из данного нулевого приближения сходится к минимуму, причем линейно.
Значения функции вдоль траектории спуска не возрастают; поэтому траектория не может выйти из области , и неравенства (15) будут выполняться на всех шагах. Рассмотрим один из циклов, начинающийся в точке (рис. 3, а). Предыдущий цикл окончился поиском минимума по направлению , следовательно, и . Первый шаг нового цикла спускает нас по направлению в точку , в которой и . Поскольку вторые производные непрерывны, можно применить теорему о среднем; получим
где через обозначены расстояния между точками. Отсюда получаем . Выполним второй шаг цикла - спуск по направлению в точку , после которого и . Аналогичные рассуждения дают соотношение с . Объединяя эти неравенства, найдем
.
Следовательно, за один цикл уменьшается в раз; то же справедливо для , если рассмотреть цикл, сдвинутый на один шаг, т. е. начинающийся в точке и кончающийся в точке .
Значит, когда число циклов , то все первые производные линейно стремятся к нулю:
и .
Первые производные одновременно обращаются в нуль в точке минимума и вблизи него являются линейными однородными функциями приращений координат. Поэтому координаты точек спуска линейно стремятся к координатам точки минимума, т. е. в данном случае спуск по координатам сходится, причем линейно.
Случай (15) заведомо реализуется в достаточно малой окрестности невырожденного минимума, ибо эти условия эквивалентны требованию положительной определенности квадратичной формы (12). Такими образом, вблизи невырожденного минимума достаточно гладкой функции спуск по координатам линейно сходится к минимуму. В частности, для квадратичной функции этот метод сходится при любом нулевом приближении.
Фактическая скорость сходимости будет неплохой при малых , когда линии уровня близки к эллипсам, оси которых параллельны осям координат. Для эллипсов, сильно вытянутых под значительным углом к осям координат, величина и сходимость очень медленная.
Если сходимость медленная, но траектория уже попала в близкую окрестность минимума, то итерации можно уточнять процессом Эйткена; разумеется, при этом надо брать в качестве исходных значения не на трех последних спусках, а на трех циклах спусков (т. е. не точки , а точки и третья точка, которой нет на рис. 3, а).
Разрешимый овраг напоминает сильно вытянутую котловину (см. рис. 3, б). При попадании траектории спуска в такой овраг сходимость становится настолько медленной, что расчет практически невозможно вести. Отметим, что в стохастических задачах наличие ошибок эквивалентно превращению истинных оврагов и гребней в разрешимые; расчет при этом можно продолжать, хотя практическая ценность такого расчета невелика: сходимость очень медленная.
Метод спуска по координатам несложен и легко программируется на ЭВМ. Но сходится он медленно, а при наличии оврагов - очень плохо. Поэтому его используют в качестве первой попытки при нахождении минимума.
Пример. Рассмотрим квадратичную функцию и выберем нулевое приближение . Выполняя вычисления, получим
.
Уточнение по Эйткену дает , т. е. точное положение минимума (заметим, что делать уточнение с использованием нулевого приближения нельзя).
2.3 Наискорейший спуск
Спускаться можно не только параллельно осям координат. Вдоль любой прямой функция зависит только от одной переменной, , и минимум на этой прямой можно найти.
Наиболее известным является метод наискорейшего спуска, когда выбирается , т. е. направление, в котором функция быстрее всего убывает при бесконечно малом движении из данной точки. Спуск по этому направлению до минимума определяет новое приближение . В этой точке снова определяется градиент и делается следующий спуск.
Однако этот метод значительно сложнее спуска по координатам, ибо требуется вычислять производные и градиент и переходить к другим переменным. К тому же, по сходимости наискорейший спуск не лучше спуска по координатам. При попадании траектории в истинный овраг спуск прекращается, а в разрешимом овраге сильно замедляется.
Если функция является положительно определенной квадратичной функцией
, (16)
то формулы наискорейшего спуска приобретают несложный вид. Вдоль прямой функция (16) квадратично зависит от параметра :
. (17)
Из уравнения легко находим ее минимум
, (18)
дающий нам следующую точку спуска:
(19)
направление наискорейшего спуска определяется градиентом квадратичной функции (16):
. (20)
Подставляя это значение в формулы (18) - (19), получим окончательные выражения для вычисления последовательных спусков.
Если воспользоваться разложением всех движений по базису, состоящему из собственных векторов матрицы , то можно доказать, что для квадратичной функции метод наискорейшего спуска линейно сходится, причем
, где ; (21)
здесь - собственные значения положительно определенной матрицы (они вещественны и положительны). Если , что соответствует сильно вытянутым эллипсам - линиям уровня, то и сходимость может быть очень медленной.
Есть такие начальные приближения (рис. 4), когда точно реализуется наихудшая возможная оценка, т. е. в (21) имеет место равенство.
Причины нетрудно понять. Во-первых, в данной точке любую прямую, в том числе невыгодную для спуска, можно сделать направлением градиента, если специально подобрать изменение масштабов по осям. Во-вторых, каждый спуск кончается в точке, где его направление касается линии (поверхности) уровня. Градиент перпендикулярен поверхности уровня. Следовательно, в методе наискорейшего спуска каждый спуск перпендикулярен предыдущему. В двумерном случае это означает, что мы совершаем спуск по координатам, повернутым так, что одна ось параллельна градиенту начальной точки.
Для улучшения метода наискорейшего спуска предлагают «кухонные» поправки к алгоритму - например, совершают по каждому направлению спуск не точно до минимума. Наиболее любопытным представляется такое видоизменение алгоритма. Будем делать по направлению, противоположному градиенту, только бесконечно малый шаг и после него вновь уточнять направление спуска. Это приводит к движению по кривой , являющейся решением системы обыкновенных дифференциальных уравнений:
. (22)
Вдоль этой кривой , т. е. функция убывает, и мы движемся к минимуму при . Уравнение (22) моделирует безынерционное движение материальной точки вниз по линии градиента. Можно построить и другие уравнения - например, дифференциальное уравнение второго порядка, моделирующее движение точки при наличии вязкого трения.
Однако от идеи метода еще далеко до надежного алгоритма. Фактически систему дифференциальных уравнений (22) надо численно интегрировать. Если интегрировать с большим шагом, то численное решение будет заметно отклоняться от линии градиента. А при интегрировании малым шагом сильно возрастает объем расчетов. Кроме того, если рельеф имеет извилистые овраги, то трудно ожидать хорошей сходимости этого метода.
Алгоритмы наискорейшего спуска и всех его видоизменений сейчас недостаточно отработаны. Поэтому метод наискорейшего спуска для сложных нелинейных задач с большим числом переменных () редко применяется, но в частных случаях он может оказаться полезным.
2.4 Случайный поиск
Методы спуска неполноценны на неупорядоченном рельефе. Если локальных экстремумов много, то спуск из одного нулевого приближения может сойтись только к одному из локальных минимумов, не обязательно абсолютному. Тогда для исследования задачи применяют случайный поиск.
Предполагают, что интересующий нас минимум (или все минимумы) лежит в некоторой замкнутой области; линейным преобразованием координат помещают ее внутрь единичного -мерного куба. Выбирают в этом кубе случайных точек.
Даже при миллионе пробных точек вероятность того, что хотя бы одна точка попадет в небольшую окрестность локального минимума, ничтожно мала. В самом деле, пусть диаметр котловины около минимума составляет от пределов изменения каждой координаты. Тогда объем этой котловины составляет часть объема -мерного куба. Уже при ни одна точка в котловину не попадет.
Поэтому берут небольшое число точек и каждую точку рассматривают как нулевое приближение. Из каждой точки совершают спуск, быстро попадая в ближайший овраг или котловину; когда шаги спуска сильно укорачиваются, его прекращают, не добиваясь высокой точности. Этого уже достаточно, чтобы судить о величине функции в ближайшем локальном минимуме с удовлетворительной точностью.
Сравнивая (визуально или при помощи программы) окончательные значения функции на всех спусках между собой, можно изучить расположение локальных минимумов функции и сопоставить их величины. После этого можно отобрать нужные по смыслу задачи минимумы и провести в них дополнительные спуски для получения координат точек минимума с высокой точностью.
Обычно в прикладных задачах нужно в первую очередь добиться того, чтобы исследуемая функция приняла минимальное или почти минимальное значение. Но вблизи минимума значение функции слабо зависит от изменения координат. Зачем тогда нужно находить координаты точки минимума с высокой точностью? Оказывается, что это имеет не только теоретический, но и практический смысл.
Пусть, например, координаты - это размеры деталей механической конструкции, а минимизируемая функция есть мера качества конструкции. Если мы нашли минимум точно, то мы находимся в самом центре котловины около минимума. В этом случае вариации координат влияют на функцию слабее, чем в точках, расположенных ближе к краям котловины. А безопасные вариации координат имеют в данном примере смысл допусков на точность обработки деталей. Значит, при аккуратном вычислении координат минимума мы можем разрешить большие допуски, т. е. удешевить обработку деталей.
Метод случайного поиска зачастую позволяет найти все локальные минимумы функции от 10-20 переменных со сложным рельефом. Он полезен и при исследовании функции с единственным минимумом; в этом случае можно обойтись заметно меньшим числом случайных точек. Недостаток метода в том, что надо заранее задать область, в которой выбираются случайные точки. Если мы зададим слишком широкую область, то ее труднее детально исследовать, а если выберем слишком узкую область, то многие локальные минимумы могут оказаться вне ее. Правда, положение несколько облегчается тем, что при спусках траектории могут выйти за пределы заданной области и сойтись к лежащим вне этой области минимумам.
| ! | Как писать курсовую работу Практические советы по написанию семестровых и курсовых работ. |
| ! | Схема написания курсовой Из каких частей состоит курсовик. С чего начать и как правильно закончить работу. |
| ! | Формулировка проблемы Описываем цель курсовой, что анализируем, разрабатываем, какого результата хотим добиться. |
| ! | План курсовой работы Нумерованным списком описывается порядок и структура будующей работы. |
| ! | Введение курсовой работы Что пишется в введении, какой объем вводной части? |
| ! | Задачи курсовой работы Правильно начинать любую работу с постановки задач, описания того что необходимо сделать. |
| ! | Источники информации Какими источниками следует пользоваться. Почему не стоит доверять бесплатно скачанным работа. |
| ! | Заключение курсовой работы Подведение итогов проведенных мероприятий, достигнута ли цель, решена ли проблема. |
| ! | Оригинальность текстов Каким образом можно повысить оригинальность текстов чтобы пройти проверку антиплагиатом. |
| ! | Оформление курсовика Требования и методические рекомендации по оформлению работы по ГОСТ. |
| → | Разновидности курсовых Какие курсовые бывают в чем их особенности и принципиальные отличия. |
| → | Отличие курсового проекта от работы Чем принципиально отличается по структуре и подходу разработка курсового проекта. |
| → | Типичные недостатки На что чаще всего обращают внимание преподаватели и какие ошибки допускают студенты. |
| → | Защита курсовой работы Как подготовиться к защите курсовой работы и как ее провести. |
| → | Доклад на защиту Как подготовить доклад чтобы он был не скучным, интересным и информативным для преподавателя. |
| → | Оценка курсовой работы Каким образом преподаватели оценивают качества подготовленного курсовика. |
| Курсовая работа | Деятельность Движения Харе Кришна в свете трансформационных процессов современности |
| Курсовая работа | Маркетинговая деятельность предприятия (на примере ООО СФ "Контакт Плюс") |
| Курсовая работа | Политический маркетинг |
| Курсовая работа | Создание и внедрение мембранного аппарата |
| Курсовая работа | Социальные услуги |
| Курсовая работа | Педагогические условия нравственного воспитания младших школьников |
| Курсовая работа | Деятельность социального педагога по решению проблемы злоупотребления алкоголем среди школьников |
| Курсовая работа | Карибский кризис |
| Курсовая работа | Сахарный диабет |
| Курсовая работа | Разработка оптимизированных систем аспирации процессов переработки и дробления руд в цехе среднего и мелкого дробления Стойленского ГОКа |