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

[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]

Гл. I. Введение

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

NCP найти min F (х)

«ей"

при ограничениях с,(л;) = 0, i = l, 2, .... т;

с, (х)>0, < = т + 1.....т.

Здесь целевая функция F и функция ограничений (с;) суть всщест-веннозначные скалярные функции. Говоря в дальнейшем о функциях задачи, мы будем иметь в виду F и {с,} одновременно.

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

Следующий пример представляет собой упрощенный вариант задачи выбора профиля носовой части летательного аппарата с минимальным сопротивлением в потоке газа. Здесь критерием качества является лобовое сопротивление тела при заданной скорости, а переменные, значения которых надо подобрать,- эго конструктивные параметры. Чтобы формали.човать задачу, надо прежде всего выделить эти параметры, определив структуру математической модели носовой части. Мы будем считать, что последнюю можно описать как набор нескольких конических секций и одной сферической, причем радиус основания R полагается заданным. Эта модель и:чображена на рис. 1а, где перечислены и параметры, значения которых предстоит выбрать. Хотя реальный профиль должен имель более сложную форму, огрубления, допущенные в модели, будут приемлемыми, если число секций взять достаточно большим.

После того как структура модели носовой части зафиксирована, надо найти зависимость лобового сопротивления от восьми перемен-

Постановка задачи оптимизации

....."а. 1.....j- Для ЭТОГО потребуется соответствующая

математическая модель обтекания. Мы ее строить не собираемся и отмегим тмько, что, какова бы она ни была, результатом ее

применения будет функция D (oj.....и„ ги ..., г.), оценивающая

лобовое сопротивление по значениям переменных. Она и станет целевой функцией нашей задачи.


Рис. 1а. Модель профн.1я носоаой части.

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

г,>0. 1=1.....4.

Происхождение задачи требует также, чтобы значения углов {а,) лежали в диапазоне [О, л/21 и чтобы каждый следующий угол не превосходил предыдущего. Значит, в задачу следует включить ограничения вида

i=l, .,

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

объем (ttj, длина (а„

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



Гл. I. Ведение

1.2. Классификация оптимизационных задач

Итак, МЫ свели проблему оптимизации профиля к математической задаче вида

иайти min D (к,.....г,)

«1.....г,

при ограничениях 0<r,.!£R, i = l.....4;

0<к,.<л/2, 1 = 1.....4;

О < объем (о,, Kj, .....r)-V,

OsgL-длина (а„ а,, л,.....г,).

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

1.2. КЛАССИФИКАЦИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ

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

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

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

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

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

Типы F(*)

Типы fCj IK))

Функция ОДНОЙ переменной ЛинеГкая функцня Сумма квадратов линейных функций Квадратичная форма Сумма квадратов нелинейных функций

Гладкая нелинейная функции Нелинейная функция с разреженной матрнпей Гессе

Негладкая нелинейная функция

Ограничения отсутствуют Простые ограничении на переменные

Линейные функции Линейные функции с разреженной матрицей коэффициентов Гладкие нелинейные функции Гладкие нелинейные функции с разреженной матрицей Якобн Негладкие нелинейные функции

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

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



Гл. 1. Введение

и та же задача для мини-ЭВМ может оказаться большой, а для обычной машины - маленькой.

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

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

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

1.3. КРАТКИЙ ОБЗОР СОДЕРЖАНИЯ

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

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

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

1.3. Краткий обзор содержания

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

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

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

В гл. 2 приведен обзор избранных результатов численного анализа. Знакомый с этим предметом читатель может ее пропустить. Особое внимание в ней уделено ошибкам машинной арифметики и некоторым из разделов вычислительной линейной алгебры. Этот материал образует основу для понимания дальнейшего изложения.

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



[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.0011