Главная  Методы условной оптимизации 

[ 0 ] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83]

методы условной оптимизации

Читатель знаком с Ф, Гиллом и У. Мюрреем не только по их многочисленным статьям в научных журналах. Они редактировали сборник трудов конференции по методам условной оптимизации, проведенной Национальной физической лабораторией (Великобритания, Тэддингтон) в январе 1974 года. Сборник был переведен на русский язык Это был обзор тогдашнего состояния численных методов отыскания экстремума функции при ограничениях. Он имел четкую прикладную направленность: концентрировал внимание читателя на трудностях, возникающих при практическом решении задач, и способах преодоления этих трудностей.

Предлагаемая монография Ф, Гилла, У, Мюррея и М, Райт «Практическая оптимизация» имеет столь же острую практическую направленность. Как и упомянутый сборник статей, она отражает современное - теперь уже спустя десятилетие - состояние методов и техники решения задач оптимизации. Общая картина предстает перед читателем преломлеииой через призму опыта и, если угодно, научных вкусов авторов - больших знатоков своего дела. Это придает изложению и ясность, и логическую стройность, и оригинальность. Правда, отдельные детали получились не совсем удачными и потребовали от переводчика дополнительных усилий, чтобы точно передать существо дела.

Авторы старались написать книгу так, чтобы даже не слишком подготовленный читатель мог понять ее, не обращаясь к учебникам. Для ее чтения достаточно знать только основы математического анализа и линейной алгебры. Изложение начинается со сведений о способах представления чисел в ЭВМ, о возникающих при этом погрешностях и о погрешностях, сопутствующих вычислениям. Показано, как ошибки могут влиять на результаты работы алгоритмов. Так, с самого начала внимание читателя привлекается к практическим вычислениям. Затем сообщаются нужные сведения из линейной алгебры и выводятся необходимые и достаточные условия минимума функции как для случая, когда на независимые переменные не наложено никаких условий, так и для случая, когда условия наложены-

См, «Численные методы условной оптимизации». Ред. Ф. Гилл н У. Мгор рей. -М.; Мир. 1977.



Предисловие редактора перевода

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

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

Книга «Практическая оптимизация» может служить и учебным пособием по математическому программированию и численным методам, и руководством к применению наиболее надежных из имеющихся сейчас универсальных алгоритмов оптимизации. Ясность изложения основных принципов и практические советы, основанные на богатом опыте авторов, привлекут к книге всех, кто начинает изучать численные методы оптимизации. Общий взгляд авторов на алгоритмы. выска:*1ваемые ими суждения не оставят равнодушными и специалистов в этой области.

А. А. Петров

ПРЕДИСЛОВИЕ

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

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

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

Избранные алгоритмы безусловной оптимизации и оптимизации при линейных и нелинейных ограничениях описаны в трех главах. Приводятся соображения, лежащие в основах алгоритмов, рассматриваются их теоретические и численные свойства. Для пояснения везде, где это уместно, даются примеры и иллюстрации. В основном мы представили алгоритмы, которые не раз успешно применяли на практике; иные обсуждаются лишь постольку, поскольку это способствует пониманию некоторых важных моментов или служит основой для последующих построений. Более подробные сведения, а также не попавшие в наш обзор алгоритмы можно найти по ссылкам, вынесенным в замечания, завершаю1цие каждый большой раздел. Материал книги излагается достаточно подробно, и это позвгаяет рекомендовать ее в качестве учебника по курсу математического программирования.



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

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

Мы очень признательны Дэвиду Мартину за его постоянную поддержку группы оптимизации в Национальной физической лаборатории и Джорджу Данцигу за его усилия по созданию алгорит.ми-ческой группь[ в Лаборатории опти.мизации систем Стэнфордского университета.

Мы благодарим Брайена Хинде, Сузан Ходсои, Инид Лонг и Дэвида Рида за нх участие в создании и испытаниях многих представленных в этой книге алгоритмов.

Разнообразную помощь при подготовке книги оказывали Грег Добсон, Дэвид Фукс, Стефания Гэй, Ричард Стоун и Уэс Винклер. Отдельные места уда.пось изложить яснее благодаря замечаниям Па-уло Беневидес-Соареса, Энди Конна, .Пауреано Эскудеро, Дона Игл-харта, Джеймса Лайпесса, Хорхе Море, Майкла Овертона и Дэиии Соренсеиа.

Мы благодарим Клива Холла за воспроизведение сгенерированных машиной рисунков на лазерном графопостроителе в Национальной физической лаборатории. Прочие рисунки были мастерски исполнены Ненси Симина.

Эта книга была набрана с помощью программной системы ТЕХ, созданной Донам Кнутом \ы благодарим его за то, что он предоставил нам различные макросы этой системы, позволившие улучшить качество окончательного текста. Крис Туччи очень помог в подготовке последнего варианта.

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

Ф. Э. Г.

Стэнфордский университет Май 1981 г.

У. !Л. М- Г. Р.

и D Е. Knuth. ТЕХ and METAFONT. New Directions in Typesettinij. American Malliematical Society and Digital Press. Bedford. Massacliusctls (1979).

ГЛАВА 1 ВВЕДЕНИЕ

Человечество ставит перед собой только те аадачи, которые оно может разрешать. К. Маркс. Из предисловия к «Критике политической экономии» (1859)

1.1. ПОСТАНОВКА ЗАДАЧИ ОПТИМИЗАЦИИ

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

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

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



[ 0 ] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83]

0.0013