(4.4)), выполненных в х*; (ii) решением квадратичной подзадачи из схемы спроектированного лагранжиана (см. разд. 5.6.3) для минимизации F при условии соблюдения выделенных равенств опреда. ляется направление поиска; (iii) делается шаг спуска вдоль иацдеи-ного направления. При этом для выбора длины шага и оценивания множителей Лагранжа. фигурирующих в подзадаче расчета направления поиска, можно предложить специальные процедуры.

Описанный подход фактически есть приложение схемы спроектированного лагранжиана к эквивалентным (4.4) и (6.73) задачам с ограничениями (см. разд. 4.2.3). Он применим ие только к (4.4) и (6.73), но и к другим задачам безусловной минимизации негладких функций особой структуры. Например, его можно использовать для поиска минимума абсолютной штрафной функции (6.8) (см. замечания к разд. 6.2 и 6.5).

6.8.2. СПЕЦИАЛЬНЫЕ ЗАДАЧИ С ОГРАНИЧЕНИЯМИ

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

Задачи типа NCP (см. разд. Г1), в которых F {х) выпукла, функции равенств линейны, а неравенств вогнуты, обладают многими специфическими свойствами. На этом основаннн их группируют а отдельный класс, и.менуя задачами выпуклого программирования или просто выпуклыми задачами. С теоретической точки зрения они прежде всего хороши тем, что в ннх любой локальный минимум с необходимостью оказывается глобальным (см. разд. 3.1), причем положительная определенность С(х*) гарантирует единственность решения.

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

Во-вторых, для выпуклых задач нет проблемы несовместности линеаризованных неравенств, получающихся аппроксимацией исходных по Тейлору (см. разд. 6.5.4.1): если функция Сг(х) вогнута, независимо от х из с,(х)0 следует, что Oi(x)(x-х)>-Cj(x).

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

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

6.8.2.2. Сепарабельное программирование. Функцию Ф называют сепарабельной, если

Ф(Х):

= .2 Ф((/),

т. е. если Ф - сумма функций одной переменной. Ясно, что матрица Гессе сепарабельной функции диагональна и что задача ее мнии-мизацни без ограничений (или при простых ограничениях на переменные) распадается на п одномерных.

Термин «сепарабельная задача» обычно употребляют в отношении постановок вида

найти min F (х)

прн ограничениях с,(х)0,

где F и {Ci} - сепарабельиые функции. Многие из методов, разработанных для решения сепарабельных задач, предполагают линейность ограничений н опираются на технику линейного программирования.

6.8.2.3. Геометрическое программирование. Термин «геометрическое программирование» возник благодаря известному неравенству между геометрическим и арифметическим средними, играющему важную роль в задачах с позиномиальными функциями. Яози-ном - это функция положительного векторного аргумента х (х g e3J") вида

Ф(х)=2ч().

где V, (х) =а,х°»х°". .. х„", I.....W. и к,. > О, i = 1.....JV.

Задачу позиномиального (геометрического) программирования обычно ставят так:

найти minf(x)

при ограничениях (х) 1, < = 1, ..., т;

12 № 2S84

где F и (с,-)- позиномы. Можно показать, что опа эквивалентна некоторой сепарабельной выпуклой задаче.

К позиномиальным близки так называемые сигномиальные задачи. Отличие состоит в том, что в них не требуется неравенств аг>0. Они могут и не сводиться к выпуклым задачам.

Замечания и избранная библиография к разделу 6.8

По методам реигеиня задач, рассмотренных в разд. 6.8.1, существует обширнейшая литература. Одна нз самых старых публикаций иа эту тему - статья Полна (1913), где описан алгоритм для задачи (6.73) с линейными функциями. Наиболее эффективными для линейного случая являются методы, построенные по схеме Шти-феля (1960).

Нелинейные задачи (6.73) чаще всего решаюг сведением к последовательности линейных, причем обычно решение линеаризованной задачи используется в качестве направления поиска, т. е. предполагается еще н одномерный спуск. Так работают, например, алго-ршмы Зуховицкого, Поляка и Примака (1963), Осборна и Уотсоиа (1969). Иначе устроены методы Зангвилла (1967b), Караламбуса и Конна (1978). В них направление поиска определяется в результате решения нескольких систем линейных уравнений, формируемых в процессе идентификации набора функций, «активных» в текущей точке. Обобщения иа задачи (6.73) алгоритма Левенберга - Маркардта (см. разд. 4.7.3) предлагались Мадсеном (1975), Андерсеном и Осборном (1977). В статье Уотсоиа (1979) описан двухэтап-ный гибридЕШЙ метод. Методы решения задачи (6.73), родственные схеме спроектированного лагранжиана из разд. 6.5.3, читатель найдет у Хана (1978а, Ь), Конна (1979), Мюррея и Овертона (1980а); в них направления поиска интерпретнруе.мы как решения неких квадратичных подзадач.

Линейная задача (4.4) безусловной минимизации суммы модулей тоже имеет довольно долгую историю. На ее связь с линейным про-граммнроватшем впервые указано в статье Чарнеса, Купера н Фер-гюсоиа (1955), Эта связь неоднократно использовалась для разработки алгоритмов; см., например, Бэрродейл и Роберте (1973), Армстронг и Годфри (1979). Нелинейную задачу (4.4) можно сводить к последовательности линейных. Соответствующий алгоритм описан у Осборна и Уотсоиа (1971). Эль-Аттар, Видьясагар и Дутта (1979) предложили для нее метод со штрафной функцией, а Мак-Лин н Уотсон (1979) - метод, основанный на процедуре Левенберга - Маркардта. Способ решения (4.4) с нелиненньши функциями переходом к эквивалентной задаче с ограничениями (см. разд. 4.2.3) и применением к последней специального метода спроетсгированиого лагранжиана с квадратичной подзадачей описай у Мюррея и Овертона (1980b).

Исчерпывающие сведения о всех аспектах выпуклости читатель найдет в книге Рокафсллара (1970), а тому, кого интересуют лишь принципиальные для выпуклого программирования результаты, мы рекомендуем книгу Мангасарьяна (1969).

Основной подход к решению задач сепарабельного программи-роватшя с линейными ограничениявш (см. Хартли (1961) и Миллер (1963)) состоит в том, чтобы нелинейные составляющие целевой функции аппроксимировать кусочно-линейными и применять к полученной подзадаче специальную версию симплекс-метода (разд. 5.3.1) Подобные схемы реализованы во многих коммерческих пакетах линейного программирования.

Полный обзор ранних работ по геометрическому протраммнро-ванню содержится в книге Даффина, Петфсона и Зеиера (1967). Первоначалыю термин «геометрическое программирование» применялся только в отношении позииомнальных задач; теперь его употребляют в значительно более широком смысле (см. статью Петер-соиа (1976)). Две прекрасные обзорные статьи гю практическим и вычислительным аспектам геометрического программирования опубликованы Дембо (1978) и Эккером (1980). В обеих приведены обширные списки литературы.

...кто может сказать,

какое из обличий верно отражает ее суиикть"? Уильям Батлер Йитс, Л Bronze Неа4> (1933)

7.1. ВВЕДЕНИЕ

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

Среди всевозможных численных моделей выделяются открытые, соотношения которых оставляют некую свободу выбора значений переменных. Открьгеая модель, как правило, служит для определе ния таких величин варьируемых параметров объекта исследования которые оптимизируют некую «меру благоио.чучия» (скажем, мак симизируют его устойчивость илн обеспечиваю! его оптимальное функщюнирование при конкретных внешних условиях). Здесь и нужны методы предыдущих глав.

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

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

вершиной допустимого множества, а для нелинейной, как правило, это не так (см. разд. 5.3.1).

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

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

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

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

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

В гл. 1 была введена следующая общая постановка оптимизационной задачи:

NCP найти min F {х)

при ограничениях c,-(x) = 0, « = 1,2.....т;

с,(х)>0, i = m-l.....т.

Ограничения иа переменные могут принимать и другие формы; например, иногда каким-то переменным разрешается пробегать лишь

МОДЕЛИРОВАНИЕ