Методы оптимизации и исследование операций для бакалавров информатики. Часть 2

9.8. Исторические замечания

Классические методы нахождения экстремумов функций без ограничений были созданы в XVII веке и связаны с именами великих математиков Ферм´а, Лейбница, Нь´ютона.

Первый аналитический способ нахождения

максимумов и минимумов был найден французом Пьером Ферм´а (Fermat, Pierre; 1601–

1665). По профессии он был юристом, слыл знатоком классической литературы и лингвистики. Математика всегда была для Ферма лишь увлечением, и тем не менее он заложил основы многих ее областей. Автор выдающих-

Пьер Ферма ся трудов в области математического анализа, алгебры, геометрии, теории чисел. Вместе со своим великим современником — философом и математиком —

Рене Декартом (Descartes, Ren´e; 1596–1650) разработал метод координат. Над сформулированной им в 1630 г. Великой теоремой математики бились более 350 лет, она была доказана только в 1994 г.

Во времена Ферма еще не было понятия производной, поэтому описанный им в 1636 г. метод нахождения максимумов и ми-

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

Великий немецкий мыслитель Готфрид Вильгельм Лейбниц (Leibniz, Gottfried; 1646–1716) по основной профессии также был юристом. Он состоял на дипломатической службе у различных германских курфюрстов, в связи с этим постоянно разъезжал по Европе и в долгих путешествиях в карете предавался размышлениям на самые различные темы.

Круг его интересов поразителен. Он был выдающимся философом, психологом, историком, биологом, геологом, физиком, математиком, лингвистом. Изобрел арифмометр, выдвинул идею паровой машины и открыл двоичную систему счисления. Познакомившись с Петром I во время его путешествий в Европу в 1696 и 1711 гг., Лейбниц предложил проект научных исследований в России, что привело

к созданию Академии наук в Петербурге. От Готфрид Лейбниц российского императора Лейбниц получил титул тайного советника юстиции и пенсию в 2000 гульденов.

Будучи в 1673 г. в Лондоне, Лейбниц прослышал о работах Ньютона в области исчисления бесконечно малых и стал независимо от него развивать основы математического анализа. Вывел основные правила дифференцирования и интегрирования, предложил современную терминологию и систему обозначений. В 1684 г. вышла пятистраничная статья Лейбница «Новый метод нахождения максимумов и минимумов...», которая стала первой в мире публикацией по дифференциальному исчислению.

Эта статья чрезвычайно заинтересовала молодого швейцар-

ского математика Якоба Бернулли5 (Bernoulli, Jakob; 1654– 1705). Изучив ее, он стал восторженным сторонником нового научного направления, вступил в оживленную переписку с Лейбницем и привлек к работе младшего брата Иоганна (Bernoulli, Johann; 1667–1748). В течение 20 последующих лет Лейбниц и братья Бернулли разработали основные концепции математического анализа.

Гениальный современник Лейбница Исаак Ньютон (Newton, Isaac; 1643–1727) пришел к дифференциальному исчислению (он назвал его методом флюксий) еще раньше, в 1666– 1667 гг., когда город Кембридж, где Ньютон работал в знаменитом университете, поразила чума, и он спасался от эпидемии в своем поместье. Однако подход к проблеме у него был не алгебраический, а физический. Новый матема-

тический аппарат был нужен Ньютону не сам Исаак Ньютон по себе, а для решения главной задачи — опи-

сания фундаментальных законов механики. Основной труд Ньютона «Математические начала натуральной философии» (так в те времена называлась физика) был опубликован в 1687 г., однако в нем он почти не использовал анализ бесконечно малых, а придерживался античных геометрических приемов доказательства. Сочинения по математике увидели свет только в XVIII столетии, но в отличие от ясных рассуждений Лейбница, чисто математические идеи в трудах Ньютона излагались довольно туманно. Ньютон постоянно сомневался, стоит ли публиковать свои достижения. Его работа «Метод флюксий» вышла уже после смерти автора в 1736 г.

Отношения Ньютона с Лейбницем были сложными. Снача-

5Семья Николая Бернулли Старшего (1623–1708), переехавшего из неспокойной Голландии в свободный швейцарский город Базель, дала миру несколько поколений математиков. Наиболее известны его сыновья Якоб и Иоганн, а также внуки — сыновья Иоганна — Даниил и Николай.

ла они обменивались дружескими письмами, однако в начале XVIII века между ними разгорелась приоритетная война, «наиболее постыдная склока во всей истории математики», расколовшая Европу на два враждующих лагеря. Хотя исторический приоритет Ньютона был бесспорным, война не ослабевала до декабря 1716 г., когда Ньютону сообщили: «Лейбниц умер — диспут окончен».

Классические аналитические методы решения условных экстремальных задач с ограничениями в виде равенств были созданы в следующем XVIII веке лучшими математиками своего времени Лагранжем и Эйлером (об Эйлере мы будем говорить в исторических замечаниях к гл. 14).

Жозеф Луи Лагранж (Lagrange, Joseph Louis; 1736–1813) родился в семье банковского чиновника в Турине (Италия). Учился на адвоката, но, случайно увидев математический трактат, почувствовал свое настоящее призвание. В 19 лет был уже профессором артиллерийской школы в Турине. В 1766 г. по приглашению Фридриха II прибыл в Пруссию, заняв пост президента Берлинской Академии наук. В 1787 г. после кончины августейшего покровителя принял предложение французского монарха

Людовика XVI и переехал в Париж, где был принят с королевскими почестями и стал членом Парижской Академии наук, профессором Политехнической школы. Великую французскую революцию Лагранж пережил безболезненно. Ему дали пенсию и назначили в комиссию, занимающуюся разработкой метрической системы мер и весов, а также нового календаря. Там ему удалось благополучно заблокировать революционный проект всеобщего перехода на 12-ричную систему счисления. В послереволюционное императорское время Наполеон пожаловал Лагранжу титул графа, должность сенатора и орден Почетного легиона.

Имя Лагранжа внесено в список 72 величайших ученых Фран-

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

Великой заслугой Лагранжа является то, что он не просто разработал метод решения условных экстремальных задач, а возвел принцип экстремальности (принцип наименьшего действия) в ранг фундаментальных законов природы (см. исторические замечания к гл. 14). Вершиной научной деятельности Лагранжа является «Аналитическая механика», опубликованная в 1788 г., которую современники назвали «научной поэмой». Впервые со времен Архимеда монография по механике не содержала ни одного чертежа, чем автор особенно гордился.

Следующий прорыв — учет ограничений в виде неравенств — произошел почти 200 лет спустя, во второй половине XX века. После Второй мировой войны в Принстонском университете (США,

штат Нью-Джерси) под руководством Альберта Таккера (Tucker, Albert William; 1905–

1995), в течение 20 лет возглавлявшего факультет математики и работавшего рядом с легендарным Джоном фон Нейманом, сложилась самая авторитетная научная школа в об-

ласти линейного и выпуклого программирова- Альберт Таккер ния. В 1950 г. Таккер и его ученик Гарольд Кун (Kuhn, Harold W.; р. 1925) опубликова-

ли вызвавшую большой научный резонанс статью «Нелинейное программирование», в которой было приведено доказательство их

теоремы. Однако в дальнейшем выяснилось, что схожие результаты были получены ранее, и даже дважды: в 1939 г. Вильямом

Карушем (Karush, William; 1917–1997) из Чикагского университета в его неопубликованной магистерской диссертации и в 1949 г. Фритцем Джоном (John, Fritz; 1910–1994). По этой причине необходимые условия оптимальности часто называются условиями Каруша — Куна — Таккера (ККТ).

Глава 10

Одномерная оптимизация

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

Как мы увидим в следующей главе, подавляющее число существующих методов нелинейного программирования относятся к числу релаксационных с линейным поиском, когда оптимизация

сколько эффективны алгоритмы одномерной оптимизации, в су-

щественной степени зависит результативность многомерных методов. В связи с этим, а также потому, что одномерные задачи оптимизации представляют самостоятельный интерес, настоящая глава будет посвящена относительно подробному изучению одномерного (линейного) поиска экстремума — one-dimensional search, line search.

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

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

В общем случае задачу приближенного нахождения экстремума (для определенности минимума) функции одной переменной можно поставить следующим образом. Пусть априорно известно, что минимум расположен на отрезке [a0, b0]. Требуется за k шагов локализовать его на отрезке [ak, bk] длиной bk − ak = ε .

10.1. Классификация одномерных методов

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

Самым простым является предположение об унимодальности функции, то есть о наличии у нее единственного экстремума

Рис. 10.1. Целевые функции одной переменной: a — произвольная; б — унимодальная;

в — выпуклая

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

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

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

Наконец, когда целевая функция дважды дифференцируема

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

10.2. Грубая локализация минимума

Для поиска точки x минимума функции одной переменной f (x) обычно требуется указать начальный промежуток [a0, b0], в котором достоверно содержится минимум. К этому вопросу нужно относиться ответственно, непростительную ошибку делают программисты, которые «зашивают» концы промежутка в текст программы, считая, например, что значения a0 = −1000, b0 = 1000 будут приемлемыми во всех случаях.

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

то можно попытаться найти выпуклую (удачную) тройку точек x1 < x2 < x3, для которой f (x1) > f (x2) < f (x3).

Возможны два варианта прохождения оптимизируемой функции через выпуклую тройку точек (рис. 10.2), однако в силу ее унимодальности в любом случае минимум находится на отрезке [a0 = x1, b0 = x3]. Для нахождения выпуклой тройки можно воспользоваться следующим алгоритмом [17, с. 133].

Рис. 10.2. Выпуклая тройка точек

Шаг 1 (нестандартный). Выбирают точку x0 и определяют направление убывания функции f (x).

Для этого выбирают число h и вычисляют f (x0 + h). Если

f (x0 + h) < f (x0), то x1 = x0 + h и переходят к шагу 2 при k = 1. Если f (x0 + h) f (x0), то h := −h и вычисляют

f (x0 + h). Если f (x0 + h) < f (x0), то полагают x1 = x0 + h и переходят к шагу 2 при k = 1. Если f (x0 + h) f (x0), то полагают h = h/2 и повторяют процедуру предварительного шага. В результате шага 1 получают число h и точки x0, x1 = x0 + h, такие, что f (x1) < f (x0) .

Шаг 2. Удваивают h и вычисляют xk+1 = xk + h.

Шаг 3. Вычисляют f (xk+1). Если f (xk+1) < f (xk) то полагают k = k + 1 и переходят к шагу 2. Если f (xk+1) f (xk), то поиск останавливают и в качестве отрезка [a0, b0], содержащего точку минимума, выбирают [xk−1, xk+1].