Задачи высокой информационной сложности и численные методы их решения

2
ОГЛАВЛЕНИЕ
Введение .............................................................6
Список обозначений ..................................................19
Глава 1. Оптимизационное задачи высокой информационной
сложности н минимаксный подход к их исследованию ...........21
§ 1. Об исследуемых постановках задач оптимизации ...................21
1. Многокритериальные задачи в теории принятия решений ..............21
2. О выборе модели критерия эффективности ...........................27
3. Особенности постановок исследуемых задач .........................35
§ 2. Оптимизационные задачи проектирования —
примеры задач высокой информационной сложности ..................37
1. Задачи формирования облика в автоматизированном
проектировании сложных технических объектов ......................37
2. О формировании облика летательных аппаратов ......................43
3. Характерные черты задач проектирования
и развиваемые численные методы ...................................54
§ 3. Основные понятия и некоторые результаты теории
оптимальных алгоритмов и информационной сложности ...............57
1. Модели вычислительных алгоритмов .................................57
2. Понятия оптимальных алгоритмов
и информационной сложности задач .................................62
3. Некоторые известные результаты теории
оптимальных алгоритмов и информационной сложности ................67
4. Об информационной и комбинаторной сложности
алгоритмов и задач ...............................................82
Глава 2. Информационная сложность задач оптимизации .................88
§ 1. 11онятия аппроксимации множества парето-оптимальных точек. Информационная сложность аппроксимации множества парето-оптимальных точек по функционалу .........................88
3
1. Основные определения ..............................................88
2. Информационная сложность построения ^аппроксимации
множества парето-оптимальных точек по функционалу .................95
§ 2. Информационная сложность аппроксимации множества
парето-оптимальных точек в пространстве стратегий ...............101
1. Трехпараметрическос семейство сеток ..............................101
2. Информационная сложность построения (б,Р)-аппроксимации множества парето-оптимальных точек в классе
пассивных алгоритмов .............................................108
3. Асимптотическое оценивание информационной сложности построения (8,р) -аппроксимации множества
парето-оптимальных точек в классе последовательных алгоритмов ....115
4. Обсуждение результатов. Сравнение информационной сложности разных постановок задачи аппроксимации множества
парето-оптимальных точек .........................................132
§ 3. Об информационной сложности глобальной оптимизации
и глобального решения уравнений .................................138
1. Постановка вопросов ..............................................138
2. Оценивание и сравнение информационной сложности
глобальной оптимизации и глобального решения уравнений ...........144
Глава 3. Алгоритмы многокритериальной оптимизации ...................150
§ 1. Обзор методов многокритериальной оптимизации ...................150
1. Предварительные сведения .........................................150
2. Методы решения многокритериальных задач, основанные на скаляризации векторного критерия .................................153
3. Методы решения многокритериальных задач, не использующие скаляризацию векторного критерия .................................165
§ 2. Алгоритмы покрытий в многокритериальной оптимизации ............170
1. Постановки задач и предварительные рассуждения ...................170
2. Алгоритмы построения (е,а)-аппроксимации множества парето-оптимальных точек по функционалу ..........................179
4
3. Алгоритмы построения (6, Р, а) -аппроксимации множества
парето-оптимальных точек в пространстве стратегий ................206
§ 3. Вопросы устойчивости и регуляризации
в многокритериальных задачах ...................................227
1. Некоторые общие сведения о проблемах устойчивости и регуляризации. Различные трактовки устойчивости
в многокритериальных задачах .....................................227
2. У тверждения об устойчивости и регуляризации многокритериальных задач .........................................236
Глава 4. Декомпозиционные методы оптимизации ........................244
§ 1. Общие аспекты развиваемого декомпозиционного подхода ...........244
1. О терминах "декомпозиция", "декомпозиционные методы" .............244
2. Предпосылки и принципы создания
декомпозиционных численных методов ...............................246
§ 2. Двухуровневые схемы
глобальной и многокритериальной оптимизации ....................256
1. Двухуровневая схема поиска глобального максимума
скалярной функции ................................................256
2. Двухуровневая схема построения множества парето-оптимальных точек в многокритериальных задачах
с ограничениями ..................................................284
§ 3. Многоуровневые декомпозиционные методы оптимизации .............298
1. Модельная декомпозиция в многокритериальной оптимизации ..........298
2. О применении декомпозиционных методов оптимизации ................307
Глава 5. Квадратурные формулы интегрирования с двумя моделями вычисления
подынтегральпой функции ....................................312
§ 1. Двухмодельные квадратурные формулы .............................312
1. Построение двухмодельных квадратурных формул .....................312
2. Погрешность двухмодельных квадратур на классах функций
с ограниченной г-ок производной ..................................317
5
3. О применении двухмодельных квадратурных формул ...................322
§ 2. Задачи об оптимальных двухмоделышх квадратурных формулах
на классе лигппицевых функций ..................................326
1. Постановка задач об оптимальных двухмодельных квадратурах ........326
2. Вспомогательные рассуждения ......................................329
3. Оптамальные коэффициенты
двухмодельных квадратурных формул ................................339
4. Оптимальные двухмодельные квадратурные формулы
с единственным основным узлом ....................................342
5. Оптимальный выбор вспомогательных узлов
в двухмодельной квадратуре с двумя основными узлами,
совпадающими с концами отрезка интегрирования ....................355
6. Оптимальные двухмодельные квадратуры
с произвольным количеством основных и вспомогательных узлов ......365
Заключение ..........................................................377
Литература ..........................................................379
6
ВВЕДЕНИЕ
Анализ сложности многообразных задач вычислительной математики и создание рациональных, эффективных численных методов является важной и актуальной проблематикой. В современной литературе имеются различные трактовки сложности — информационная сложность и комбинаторная (вычислительная) сложность. Поясним эти термины, не давая пока формализо-ванных определений. С позиций минимаксной концепции [136, 214, 227] информационная сложность задачи — это минимальное количество информационных вычислений, обеспечивающее гарантированное решение данной задачи с требуемой точностью. Например, для экстремальных задач информационными обычно считаются вычисления значений целевой функции, се производных, каких-нибудь других ее характеристик. Комбинаторной сложностью задачи называют минимальное число элементарных операций, необходимое для отыскания ее решения по располагаемой и добываемой информации о данной задаче. Понятия информационной и комбинаторной сложности отражают разные стороны общей проблемы сложности задач — проблемы, называемой авторами [227] одной из центральных в вычислительной математике (см. [227|, стр. 10).
Нередко встречаются задачи, при решении которых на ЭВМ подавляющая доля машинного времени затрачивается на информационные вычисления. Трудоемкость решения подобных задач характеризуют их информационной сложностью, и именно такие задачи изучаются в этой диссертации. Говоря конкретнее, диссертация посвящена задачам и численным методам оптимизации и интегрирования со сложными информационными вычислениями. Яркими примерами прикладных задач указанного типа служат задачи из области проектирования технических объектов. Далее во введении, говоря о сложности задач, всюду будем иметь ввиду их информационную сложность.
7
Как правило, сложность задач оценивают по отношению к тем или иным классам алгоритмов их решения. Существует неразрывная связь между понятиями сложности задач и оптимальности алгоритмов. Выражаясь здесь не вполне строго, сложность задачи можно определить как трудоемкость "оптимального по сложности" алгоритма из некоторого фиксированного класса методов, решающих эту задачу с требуемой точноегью. (Строгие формулировки понятий сложности задач и оптимальности алгоритмов, основанные на минимаксной концепции 1136, 214, 227], даются во вводно-обзорной главе 1.) К настоящему времени теория информационной сложности и оптимальных алгоритмов сформировалась как перспективное, интенсивно развивающееся направление в проблематике оптимизации вычислительных процессов. Ряд основных результатов диссертации примыкает непосредственно к этой теории.
Важная особенность исследований, описываемых в диссертации, заключается в том, что они были инициированы и проводились в русле работ по созданию системы автоматизированного проектирования (САПР) сложных технических объектов. Таким образом, материал диссертации довольно тесно связан с тематикой САПР, хотя и существенно выходит за ее рамки. Развиваемые в данной работе численные методы оптимизации и интегрирования ориентированы, в первую очередь, на прикладные задачи проектирования технических объектов. Более того, в сфере проектирования лежат истоки и предпосылки возникновения некоторых из предлагаемых методов. Дело в том, что применение традиционных вычислительных процедур и алгоритмов в проектировании зачастую сталкивается с определенными трудностями и не всегда оказывается эффективным. Поэтому, возникла интересная идея построения таких численных методов, которые, обладая математической строгостью, учитывали бы в той или иной степени технологию проведения расчетов характеристик создаваемых технических объектов, используемую конструкторами в своей деятель-
8
ности. Разработка и изучение подобных "нетрадиционных" численных методов является одной из главных целей данной диссертации.
Бо'льшая часть диссертации отведена задачам и численным методам оптимизации. Обычно при построении методов оптимизации делаются те или иные априорные предположения о критерии эффективности (целевой функции) и области его задания. Желательно, чтобы такие предположения были по возможности адекватны реальным задачам, для решения которых предназначаются конструируемые методы. Часто критерий эффективности относят к какому-либо функциональному классу, и этот класс служит идеализированной моделью реальных целевых функций. Характерными аспектами интересующих нас задач оптимизации являются многокритериальность, невыпукл ость, многоэкстре-мальность, отсутствие явного аналитического вида критерия эффективности, высокая трудоемкость расчета значений критерия и невозможность вычисления его производных с приемлемой точностью. Отмеченные черты свойственны, в частности, оптимизационным задачам проектирования сложных технических объектов. В качестве модели целевых функций, достаточно адекватной указанным задачам и, вместе с тем, удобной для теоретических исследований и рационального построения алгоритмов, в диссертации принимается класс функций, удовлетворяющих условию Липшица на компактном множестве. Подробнее вопрос о выборе модели критерия эффективности обсуждается в главе I.
В настоящей работе оптимизационные задачи чаще рассматриваются в многокритериальной постановке. Под точным решением в них понимается множество оптимальных по Парето (иногда — оптимальных по Слейтеру) стратегий. При этом все результаты, полученные для многокритериальных задач, как частные случаи автоматически распространяются на скалярные задачи глобальной оптимизации. Углубленное внимание обращается на разные трактовки аппроксимации множества парето-опггимальных стратегий — аппроксимации "по функционалу" (но значениям векторного критерия) и аппроксимации "по
9
аргументу" (в метрике пространства стратегий). Второе из названных понятий сильнее первого в том смысле, что при стандартных предположениях (компактность множества стратегий, непрерывность критерия) аппроксимация множества паретовских стратегий "по аргументу" обеспечивает аппроксимацию того же множества и "по функционалу", но не верно обратное утверждение. Для скалярных оптимизационных задач указанные два вида аппроксимации решений означают соответственно отыскание произвольной допустимой точки, в которой значение целевой функции близко к глобальному экстремальному, и приближенное нахождение всего множества точек глобального экаремума. Известные до сих пор результаты но оцениванию сложности задач оптимизации (и скалярных, и многокритериальных) были получены, главным образом, в ситуациях, когда искомое решение аппроксимировалось "по функционалу". Вопросы же аппроксимации "по аргументу" всего множества точных решений в оптимизационных задачах долгое время оставались недостаточно исследованными. В диссертации с точки зрения сложности анализируются оба упомянутых типа ашгроксимации множества парето-оптимальных стратегий, причем гораздо бо'лыние усилия сосредоточены на трактовке аппроксимации "по аргументу" ввиду ее меньшей изученности. Оказывается (см. главу 2), что при естественных допущениях и корректных условиях сравнения сложность аппроксимации множества паретовских стратегий "по аргументу" существенно превышает сложность аппроксимации этого множества "по функционалу". Получена соответствующая количественная оценка. По сложности сравниваются также задачи скалярной глобальной оптимизации и глобального поиска корней нелинейных уравнений.
Трактовки аппроксимации решений "по функционагу" и "по аргументу" находятся в центре внимания и при построении в главе 3 алгоритмов многокритериальной оптимизации, относящихся к классу методов покрытий. В большинстве ранее известных методов такого рода точность решений оценива-
10
лась "по функционалу". Однако, технику методов покрытий удается приспособить и для аппроксимации множества паретовских стратегий "по аргументу", и в частности, для приближенного отыскания множества точек глобального экстремума скалярной целевой функции.
Разработка численных методов многокритериальной и глобальной оптимизации ведется в диссертации но двум направлениям. Во-первых, — это конструирование алгоритмов путем изыскания каких-либо новых или не полностью исчерпанных возможностей в русле традиционных идей и подходов, таких как минимаксная концепция оптимальности, техника методов покрытий для решения многоэкстремальных задач с лишпицевыми функциями. Алгоритмы подобного рода предлагаются в главе 3. Второе направление заключается в развитии так называемого декомпозиционного подхода к решению оптимизационных задач, основанного на предположении о наличии двух или более вычислительных моделей критерия эффективности. Данное направление освещается в главе 4. Скажем здесь немного об истоках его возникновения, лежащих в области проектирования сложных технических объектов.
Отправными посылками для разработки декомпозиционных численных методов послужили следующие соображения. Как известно, па роль критерия эффективности в оптимизационных задачах проектирования технических объектов чаще всего выбираются характеристики реального функционирования этих объектов, отражающие цели их создания. Для расчета каждой такой характеристики в распоряжении конструктора обычно имеется не один, а целый ряд способов (и соответствующих вычислигельных процедур), называемых в данной диссертации вычислительными (расчетными) моделями. На практике использование той или другой модели бывает продиктовано многообразными факторами. Иногда одну и ту же характеристику проектируемого объекта конструктор специально определяет с помощью разных моделей, сопоставляя получаемые результаты. Такое координированное применение вычислительных
II
моделей является неотъемлемой частью конструкторской технологии, и данное обстоятельство должно учитываться разработчиками САПР технических объектов. Модели расчета одной и той же характеристики могут сильно различаться по точности и сложности, причем, как правило, чем точнее модель, тем выше оказывается ее сложность.
Итак, гипотеза о наличии нескольких вычислительных моделей критерия эффекгивности предст авляется вполне естественной, по крайней мере, для задач в сфере проектирования. Нередко встречается следующая ситуагщя. Исходное множество альтернативных вариантов нового технического объекта выбрано настолько обширным, что за отведенное время не удается решить задачу "оптимального проектирования", используя только точную, но сложную вычислительную модель критерия из-за ограниченного быстродействия ЭВМ. С другой стороны, решение той же задачи, относительно легко находимое с привлечением лишь какой-нибудь простой, но грубой модели критерия, имеет неприемлемую погрешность. В подобной ситуации желательно комбинировать разные расчетные модели гак, чтобы получить удовлетворительный по точности результат, затрачивая как можно меньше времени.
Принцип сочетания и координированного приме!гения нескольких различающихся по точности и сложности вычислительных моделей критерия эффективности воилонгается в декомпозиционных методах глобальной и многокритериальной оптимизации, построенных в главе 4. При этом требуется определенная согласованность точной и грубых моделей критерия. В идейном плане развиваемым декомпозиционным методам оптимизации предшествует теория иерархических схем проектирования [29 — 32, 99 — 101, 103]. Отметим также, что предлагаемые в главе 4 методы являются нетрадиционными по типу выполняемых в них информационных вычислений.
С позиций объявленного декомпозшдюнного подхода, при его соответствующей корректировке, можно разрабатывать и методы численного решения
12
задач совершенно других типов (а не только задач оптимизации). Эта идея реализуется в заключительной главе 5, где рассматривается задача численного интегрирования, и вводится класс квадратурных формул, базирующихся на двух различающихся по точности и сложности расчетных моделях подьнггегральной функции. Такие квадратурные формулы названы двухмодельными или декомпозиционными. Они ориентированы, в первую очередь, на вычисление инте-гралов в задачах проектирования технических объектов.
Подчеркнем, что в современной литературе понятия "декомпозиционный подход", "декомпозиционный метод" допускают очень широкое толкование. В настоящей работе за ними закрепляется вполне конкретный смысл, и их не следует отождествлять с аналогичными терминами, употребляемыми во многих статьях и монографиях.
С точки зрения создания САПР как системы, основанной на знаниях и технологических принципах работы конструкторов, построенные в главах 4, 5 декомпозиционные методы представляют интерес не только как собственно численные методы, но и потому, что в них отражены некоторые элементы конструкторской технологии, а именно — сочетание и координированное использование разных моделей расчета функциональных характеристик проектируемых объектов.
Охарактеризовав в самых общих чертах направления исследований, проводимых в диссертации, коротко опишем ее содержание по главам. Каждая из пяти г лав диссертации разбита на параграфы, которые, в свою очередь, состоят из болсс мелких разделов — пунктов.
Главу 1 в целом следует рассматривать как развернутое введение к остальным главам. Ее параграфы весьма разноплановы по излагаемому в них материалу. В § 1 обсуждаются основные черты и специфика (высокая информационная сложность, многокритсриатьность и т.д.) задач оптимизации, изучаемых в настоящей работе. Приводятся необходимые в дальнейшем сведения о много-
13
критериальных задачах. Дается аргументация в пользу условия Липшица как достаточно адекватного и, вместе с тем, "удобного" (хотя и не лишенного недостатков) ограничения на целевые функции во многих реальных задачах. Упоминается ряд известных подходов к решению экстремальных задач с лип-шицевыми функциями. Следующий §2 посвящен одному из классов прикладных задач высокой информационной сложности — оптимизационным задачам проектирования сложных технических объектов и, конкретно, летательных аппаратов. Показывается многокритериальная сущность таких задач. Наибольшее внимание концентрируется на тех их аспектах, которые послужили предпосылками для разработки новых, в том числе декомпозиционных численных методов. Наглядно продемонстрировано, что для расчета летных и других характеристик летательных аппаратов в практике проектирования широко используются различающиеся по точности и сложности вычислительные модели. Заключительный §3 главы 1 как бы предваряет главу 2. В нем вводятся терминолог ия и понятия из теории оптимальных (минимаксных) алгоритмов и информационной сложности, а затем предлагается обзор известных результатов этой теории. В обзоре, во-первых, прослеживаются общие (с точки зрения данной теории) закономерности, свойственные сразу нескольким типам задач вычислительной математики, таким как оптимизация, интегрирование, приближение функций. А во-вторых, в том же обзоре отражены исследования широкого спектра оптимизационных задач: от традиционных скалярных — унимодальных, выпуклых, липшицсвых, гладких — до сравнительно новых — многокритериальных задач с различными принципами оптимальности решений, задач оптимизации по бинарным отношениям и функциям выбора. Все собранные в указанном обзоре результаты образуют общую картину, на фоне которой излагается материал главы 2.
В главе 2 изучается сложность (информационная) липшицсвых задач приближенного построения множест ва парето-оптимальных точек (стратегий).
14
Показано, как существенно она зависит от постановки задач, от того, каким образом в них определяется понятие аппроксимирующег о решения. В §1 вводятся трактовки аппроксимации множества паретовских стратегий "по функционалу" и "по аргументу". Каждая из данных трактовок предписывает свой способ измерения погрешности приближенного решения в многокритериальных задачах. Кроме того в § 1 легко усганавливается сложность задачи аппроксимации "по функционал}'" множества паретовских стратегий. Найден оптимальный (по сложности) пассивный алгоритм такой аппроксимации, являющийся оптимальным и в более широком классе последовательных алгоритмов. Отметим, что этот факт близок к ранее полученному результату в [2131, представленному также в [214]. Значительно бо'льших усилий потребовал анализ сложности задачи аппроксимации множества парето-оптимальных стратегий "по аргументу", проводимый в §2. Сначала построен оптимальный пассивный алгоритм решения этой задачи. Затем доказываегся асимптотическая оптимальность семейства таких алгоритмов при стремлении к нулю параметров аппроксимации. Тем самым, .для сложности задачи аппроксимации множества паретовских стратегий "по аргументу" обосновывается асимптотическая оценка. Конструктивно реализовать указанные оптимальные алгоритмы и явно подсчитать информационную сложность рассматриваемых задач легко удается, когда множество допустимых стратегий — координатный параллелепипед в пространстве с кубической (чебышевской) метрикой. В этом случае при коррекгных условиях сравнения сложность аппроксимации "по аргументу" множества паретовских стратегий выше сложности аппроксимации "но функционалу" того же множества "примерно" в 2Д раз, где N — размерность пространства стратегий. Наконец, в §3 по сложности сравниваются липшицевы задачи приближенного отыскания множества точек глобазьного экстремума скалярной функции и множества корней нелинейного уравнения. Если решения обеих этих задач ищутся на А'-мерном параллелепипеде в пространстве с кубической метрикой,
15
то (опять-таки при некоторых корректных условиях) первая из них "сложнее" второй "примерно" в 2Л раз. Основные результагы главы 2 могут рассматриваться в русле выдвигаемой в [227] общей проблемы построения иерархии сложности разнообразных задач вычислительной математики.
Глава 3 посвящена алгоритмам многокритериальной оптимизации. В §1 делается обзор известных численных методов приближенного нахождения множеств парстовских и слейтеровских стратегий. Коротко упоминаются некоторые подходы, развиваемые в линейной многокритериальной оптимизации. Обсуждаемые более подробно методы решения нелинейных задач разделены на две группы. Первая из них объединяет методы, в которых осуществляется какая-либо скаляризация векторного критерия, и таким образом, многокритери-альная задача сводится к совокупности скалярных экстремальных задач. Вторая группа включает методы, оперирующие с векторным критерием непосредственно, без его скаляризации. В §2 предлагаются и обосновываются последовательные алгоритмы приближенного решения липшицевых многокритериальных задач с функциональными ограничениями, относящиеся к классу методов покрытий. Причем сконструированы как алгоритмы, позволяющие аппроксимировать множество парето-оптимальных стратегий "по функционалу", так и алгоритмы, обеспечивающие аппроксимацию того же множества "по аргументу". Последние заслуживают повышенного внимания в связи с тем, что в ранее известных методах покрытий (и скалярных, и многокритериальных) погрешность решений всегда (или почти всегда) оценивалась "по функционалу". На классе задач без функциональных ограничений указанные алгоритмы (точнее говоря, упрощенные модификации указанных алгоритмов) обладают свойствами оптимальности. Специальные методы построены для решения овражных многокритериальных задач. Обсуждаются некоторые аспекты программной реализации и практического использования предлагаемых алгоритмов. Рассматриваются соответствующие примеры. Однокритериальные версии всех алгоритмов из §2
16
представлякп самостоятельный интерес как методы скалярной глобальной оптимизации. В §3 освещаются вопросы устойчивости многокритериальных задач относительно погрешностей вычислений. Обосновываются схемы регуляризации для решения неустойчивых многокритериальных задач.
В главе 4 разрабатываются декомпозиционные методы глобальной и многокритериальной оптимизации. В § 1 излагаются (более развер1гуто, чем в настоящем введении) предпосылки возникновения и принципиальные особенности развиваемого декомпозиционного подхода. Исходным предположением служит гипотеза о наличии двух или нескольких вычислительных моделей критерия эффективности в оптимизационной задаче. Считается, что наиболее сложная модель является точной, а остальные — приближенные (грубые) модели согласованы с ней. Описанию и обоснованию декомпозиционных методов оптимизации посвящены §§ 2, 3. Условия согласования вычислительных моделей критерия задаются в форме неравенств Липшица для погрешностей (расхождений) грубых моделей относительно точной сложной модели. (Указанные погрешности рассматриваются как функции на множестве допустимых точек.) В содержательном плане такая согласованность расчетных моделей означает, что расхождение между ними от точки к точке не может изменяться "слишком резко". За счет координированного использования согласованных моделей критерия эффективности в декомпозиционных методах удается рационально организовать процесс решения трудоемких оптимизационных задач. Предлагаемые методы позволяют весги отбраковку неоптимальных точек с помощью простых грубых моделей критерия и, по возможности, реже прибегать к вычислениям на его точной сложной модели. Обсуждаются вопросы практического применения декомпозиционных методов оптимизации, и их работа иллюстрируется на примерах. Эффективность этих методов существенно зависит от того, насколько "хорошо" согласованы используемые в них расчетные модели.
17
В завершающей главе 5 общие идеи декомпозиционного подхода к задачам оптимизации переносятся на другую область — численное итерирование. В §1 описывается класс так называемых двухмодельных квадратурных формул для приближенного нахождения определенных интегралов от функций одной переменной. Особенность указанных формул (объясняющая их название) состоит в том, что они базируются на двух согласованных вычислительных моделях подынтегральной функции, одна из которых — точная, но сложная, а другая — простая, но грубая. Целью построения двухмодельных квадратур является повышение точности интегрирования мри ограниченном количестве вычислений значений подынтегральной функции на ее сложной модели. Такое повышение точности достигается благодаря координированному использованию обеих моделей подынтегральной функции. Получена оценка погрешности двухмодельных квадратурных формул на классах функций с ограниченной г-ой производной. Рассматривается одна из конкретных формул такого рода — двухмоделъная квадратура Симпсона, и обсуждается возможная область их приложения. Как известно, в теории численного интегрирования много внимания уделяется задачам об оптимальных (наилучших) квадратурах на различных функциональных классах. В §2 подобные задачи формулируются применительно к двухмодельным квадратурным формулам. Исследование этих задач, довольно большое по обьему, проводится для класса липшицевых подынтегральных функций. Оно позволяет глубже проанализировать эффективность развиваемого подхода к вычислению интегралов, полнее продемонстрировать важную роль согласованност и расчетных моделей подынтегральной функции, а также оценить потенциатьный выигрыш в точности итерирования, который двухмодельные квадратурные формулы могут обеспечить по сравнению с традиционными (одномодельными) квадратурами. В ряде ситуаций оптимальные узлы и коэффициенты двухмодельиых формул удается найти в явном виде. Построение оптимальной двухмодельной квадратуры в наиболее общем случае
18
сводится к целочисленной оптимизационной задаче специального вида, для решения которой указывается подходящий алгоритм.
По-видимому, результаты глав 4, 5, полученные в рамках декомпозиционного подхода к задачам оптимизации и интегрирования, могут служить косвенным теоретическим подтверждением правомерности и эффективности таких технологических приемов работы конструкторов, как сочетание и координированное применение разных моделей и способов расчет а характеристик проектируемых сложных технических объектов.
Скажем несколько слов о нумерации утверждений и формул в диссертации. Теоремы, леммы, а также озаглавленные определения и примеры нумеруются в пределах каждой главы. При ссылках на них в той же главе, где они находятся, указываются их номера. В ссылках же на теоремы, леммы, определения из других глав кроме соответствующих номеров обязательно называются разделы (пункты, параграфы, главы), в которых эти теоремы, леммы, определения содержатся. Формулы, ввиду их большого количества, нумеруются заново в пределах каждого параірафа. При ссылках на формулы в том же параграфе, где они введены, используются только их номера. Для упоминания формул из других параграфов в той же главе применяется двойная нумерация: первое число означает номер параграфа, а второе — номер формулы в этом параграфе. В ссылках на формулы других глав к названным двум номерам добавляется номер главы. Так, формула (10) внутри §1 главы 2 именуется просто формулой (10), в других параграфах главы 2 — формулой (1.10), а вне главы 2 — формулой (1.10) гл. 2.
Результаты диссертации опубликованы в [168— 170, 172 — 191, 280], а также в [39, 53 — 59].
19
СПИСОК ОБОЗНАЧЕНИЙ
Здесь перечисляются лишь некоторые из обозначений, употребляемых в данной работе. Не приводятся стандартные общепринятые символы. Все прочие обозначения в тексте используются только после того, как они введены, и в необходимых местах сопровождаются пояснениями.
df
= — равно по определению ;
R” — л-мерное координатное пространство ;
/„ = {/, 2 , ... , л} — множество индексов ;
R>={a = (a,....а„) \ а,>0,
R" = {a = (a,..а„)\а^0,
г — метрика в координатном пространстве ;
Л(Х, Y) = sup inf г(х, у) — отклонение множества X от множества Y;
х<=Х у<=¥
h(X, Y)- тах{Л(X, Y), A(Y, X)} — расстояние по Хаусдорфу между множествами X и У (метрика Хаусдорфа);
>- — бинарное отношение Парето ;
>• — бинарное отношение Слейтера ;
| М\ — число элементов конечного множества Л/;
f (X) — множество значений функции (всктор-фуикции, отображения) /, заданной на множестве X;
Argmaxf(x) — множество точек максимума скалярной функции / на
хеХ
множестве X ;
df
P-Pj(X) — множество оптимальных но Парето точек (стратегий) по векторному критерию f - (fна множестве X ;
df
S = S f( X) — множество оптимальных но Слейтеру точек (стратегий) по векторному критерию f-(на множестве X;
20
/ (Р) — множество оптимальных по Парето точек (оценок) на множестве ]'(Х) в пространстве значений векторного критерия / = ;
/(Б) — множество оптимальных по Слейтеру точек (оценок) на множестве /(X) в пространстве значений векторного критерия / = (//,— ,/„) ;
Р(Ь) — класс функций (вектор-функций), удовлетворяющих условию Липшица с константой ;
■ — символ окончаний доказательств, озаглавленных определений, примеров. замечаний, описаний алгоритмов и численных методов.
21
ГЛАВА 1. ОПТИМИЗАЦИОННЫЕ ЗАДАЧИ ВЫСОКОЙ ИНФОРМАЦИОННОЙ СЛОЖНОСТИ И МИНИМАКСНЫЙ ПОДХОД К ИХ ИССЛЕДОВАНИЮ
Эта глава является вводной по отношению к последующим главам. В ней обсуждаются характерные черты и особенности задач оптимизации, изучаемых в данной работе. Рассматривается один из классов прикладных задач высокой информационной сложности — оптимизационные задачи проектирования технических объектов. Наибольшее внимание уделяется тем аспектам задач проектирования, которые послужили предпосылками для создания новых численных методов. Формулируются необходимые понятия, и делается обзор известных результатов теории оптимальных алгоритмов и информационной сложности.
§ 1. Об исследуемых постановках задач оптимизации.
1. Многокритериальные задачи в теории принятия решений.
В современной математической теории принятия решений изучается широкий круг проблем: задачи системного анализа [125], исследования операций и теории игр [35, 36], программно-целевого планирования и управления [192], проектирования сложных систем [102, 103, 121]. Термин "принятие решений" означает выбор того или иного способа действий, направленных на достижение поставленных целей. При этом содержательная интерпретация целей и способов их осуществления зависит от предметной области, к которой относится конкретная рассматриваемая задача.
Постановка задач принятия решений предусматривает создание адекватных математических моделей, в которых цели и пути их достижения должны быть представлены в формализованном виде. В относительно простых случаях удается сформулировать единственную цель и описать ее скалярным критерием
22
эффективности (целевой функцией). Построение и исследование таких моделей приводит к традиционным однокритериальным экстремальным задачам. В более сложных ситуациях принятия решений цель (концепцию) рационального или оптимального выбора невозможно выразить скалярным критерием, поскольку она должна удовлетворять различным, зачастую противоречивым, а порой и не полностью формализуемым требованиям. Если в той или иной модели качество конкурирующих решений оценивается набором показателей, то может быть поставлена многокритериальная задача — задача оптимизации по векторному критерию эффективности. Такого рода задачи возникают в ситуациях, в которых выбором решения нужно обеспечить достижение нескольких целей. Многокритериальные задачи появляются также при анализе игровых моделей с участием нескольких лиц, когда интересы участников не совпадают и описываются собственными скалярными критериями, образующими в совокупности векторный критерий. В многокритериальной трактовке изучаются различные вопросы математической экономики, моделирования военных операций, теории автоматического регулирования и управления, проектирования сложных объектов.
Пусть X — непустое множество в //-мерном координатном пространстве /?Л и /,(х), / = 1, 2,..., п—заданные на X скалярные функции, называемые частными критериями. Вместе они составляют векторный критерий 1(х) = (/](х),...,/п(х)), на основе которого среди элементов х^Х производится рациональный (оптимальный) выбор. В литературе по теории и методам приня тия решений в зависимости от сложившихся традиций и содержательной интерпретации элементы множества X называют альтернативами, стратегиями, вариантами, планами. Каждая альтернатива х е X характеризуется вектором (критериальной оценкой) /(х). Обозначим через
ИХ)*{у = /(х) \ хеХ} а Я"
23
множество значений векторного критерия / на X, т.е. / (X ) — это множество критериатьных оценок всех альтернатив из X. Пространства и
/?" именуют соответственно пространством альтернатив (стратегий) и критериальным пространством. Нередко альтернативы х є X и их оценки /(х) є /(X) называют просто точками соответствующих пространств.
При постановке многокритериальных задач, в отличие от обычных экстремальных задач, возникает вопрос о выборе концепции (принципа) оптимальности. Иначе говоря, необходимо определить само понятие решения задачи оптимизации с векторным критерием эффективности. В настоящее время выработан целый ряд пршщипов оптимальности в многокритериальных задачах (см., например, [35, 36, 92, 107, 123, 160, 161, 208]). Вопрос о выборе приемлемой концепции оптимальности относится к разряду методологических проблем и часто рассматривается применительно к конкретным прикладным задачам с учетом их содержательного смысла и различных неформальных соображений.
Напомним необходимые определения, касающиеся бинарных отношений [161, 249]. Как известно, бинарным отношением р на множестве X называется совокупность упорядоченных пар альтернатив из X, т.е. р с X х X.
Тот факг, что пара (х\ х") содержится в р обозначают записью: х'рх". При этом говорят, что альтернатива х' доминирует' альтернативу х" по отношению р. Если же не выполнено ни х’рх" ни х"рх’, то альтернативы х' и хи полагают несравнимыми по отношению р.
Бинарное отношение р на множестве X называется:
— асимметричным, если для всех х', х" є X из х'рх" следует, что не справедливо х"р х' ;
— транзитивным, если для всех х', х", хт е! из х'рх", х"рхш следует х'рх"'.
24
Альтернатива х* є X называется максимальной (недоминируемой) на множестве X по отношению р, если либо не существует х є X такого, что хрх*, либо из условия хрх\ х еХ вытекает х*рх. Множество
максимальных альтернатив на X по отношению р, обозначаемое через МаХрХ, называется внешне устойчивым, если для любого х єХ\ МахрХ
найдется х* є МахрХ такое, что х*рх .
1 Іредположим, что в многокритериальной задаче все частные критерии следует максимизировать, т.е. произвольная альтернатива х еХ тем предпочтительнее, чем больше значения /;(х), / = 7, 2,..п. Введем известные бинарные отношения, играющие важную роль в теории многокритериальной оптимизации
— отношение Парею > :
х' >х" <-> /і(х')>/(х"), /-/, 2,..., п, /(х')Ф/(х")> х\х"ьХ,
— отношение Слейтера V :
х' ух" /,(х')>/(х"), і = 1У 2,..., п, хг, х" є X.
Оба они асимметричны и трагоитивны.
Альтернатива х є X называется оптимальной по І Іарето (эффективной) на множестве X, если она является максимальной на X по отношению ь , т.е. не существуег хєХ такого, что т >:Х*. Максимальная на X альтернатива по отношению >- называется оптимальной по Слейтеру (слабо эффективной, полуэффективной) на X. Критериальные оценки эффективной и полу эффективной аіьтернатив именуются соответственно эффективной и полуэффективной оценками. Примем обозначения:
<ц 4г
Ру(Х) = МаХуХ — множество оптимальных по Парето альтернагив на множестве X по векторному критерию /;
25
<9 <У
8 = Зг(Х)= Мах^Х — множество оптимальных по Слейтеру альтернатив на МНОЖеСТВе X 110 векторному КрИГерИЮ /. ЯСНО, ЧТО Ру(Х)^8у(Х). Множества эффективных и полуэффективных оценок /(Р) и f(S) называются соответственно множеством Парето и множеством Слейтера.
Определения оптимальности по Парето и Слейтеру обобщают понятие максимума скалярной функции. Так, задача нахождения Р/(Х) была названа
в [90] задачей векторной максимизации.
Известно (см., например, [161]), что если множество X конечно, или же X — компакт, и векторный критерий / непрерывен на X , то множества Р/(Х), Зу(Х) оказываются непустыми и внешне устойчивыми. Следовательно, при естественных для оптимизационных задач предположениях отыскание Р/(Х) позволяет сузить исходное множество конкурирующих альтернатив с тем, чтобы окончательный выбор единственной альтернативы производить не из всего X, а из его подмножества Р/(Х). Такой выбор может
осуществляться либо по каким-то дополнительным критериям, не входящим в вектор /, либо путем субъективных предпочтений лица, принимающего решение (ЛПР), например, при помощи экспертных процедур. В силу сказанного, построение (точное или приближенное) множества Р/(Х) является первым
этапом в различных методах принятия решений при многих критериях. Поэтому, одна из наиболее распространенных концепций оптимальности в многокритериальных задачах заключается в выделении множества парето-оптимальных точек Ру(Х). То же самое относится и к множеству 8^(Х).
Поскольку частные критерии обычно бывают противоречивы и достигают максимума в различных точках множества X, единственное решение многокритериальных задач, как правило, не удается определить на основе лишь формальных подходов. По этой причине в многокритериальных задачах часто принимается концепция оптимальности но бинарному отношению, связанному
26
с векторным критерием / и характеризующему систему предпочтений ЛИР. В данной кщщепции предполагается, что бинарное отношение последовательно уточняется в ходе решения задачи по мере выявления предпочтений ЛПР. Для решения многокритериальных задач в такой постановке разрабатываются диалоговые (человеко-машинные, адаптивные) процедуры (см., например, [27, 61, 107, 1211). Аналогичные процедуры применяются для решения задач оптимизации по бинарным отношениям и в тех случаях, когда отношения на множестве альтернатив определяются не на основе критерия эффективности, а путем непосредственного сравнения конкурирующих альтернатив.
Отметим еще, что обобщением классов многокритериальных задач и задач оптимизации по бинарным отношениям является класс задач оптимизации по функциям выбора [3, 115, 245, 249]. Язык функций выбора — это универсальное средство для описания всевозможных концепций выбора в ситуациях принятия решений. Именно в терминах функций выбора в наиболее общем плане ставятся и изучаются вопросы методологического характера: что следует считать решением той или иной задачи рационального выбора; какими свойствами обладает решение, получаемое в рамках принятой концепции выбора; как определить непротиворечивый набор аксиом — требований к рациональному выбору и т.д. Другой круг вопросов, относящийся к функциям выбора, связан с представлением функций выбора в виде реализующих их механизмов — конструктивных алгоритмических процедур.
В настоящей работе исследуются многокритериальные задачи оптимизации, в которых под решением понимается множество паретовских (иногда — слейтеровских) альтернатив. При этом методологические вопросы не возникают, а рассматриваются теоретические и вычислительные аспекты, характерные и для скалярных экстремальных задач, но имеющие в многокритериальном случае определенную специфику.
27
2. О выборе моделей критерия эффективности.
Предмет нашего изучения составляют гак называемые непрерывные задачи многокритериальной оптимизации. Естественным предположением в них (зачастую, однако, усиливаемым другими условиями) является компактность множества X допустимых точек и непрерывность на X векторного критерия /(х) = (/{(х)»>:>/п(х)), который будем именовать также (векторной) целевой функцией. Задачи скалярной глобальной оптимизации (максимизации) в данной работе трактуются как частные случаи многокритериальных задач при п=1. Пространство, содержащее X, всюду считается конечномерным. Не исключается и дискретность (полная или частичная — по отдельным координатам) множества X; важно лишь, чтобы на X была введена метрика.
В ряде прикладных оптимизационных задач критерий эффекгивности (скалярный или векторный) не задается в аналитической форме, и получение информации о нем требует трудоемких численных или физических экспериментов. При этом обычно имеются лишь минимальные априорные сведения о критерии —например, его непрерывность или, возможно, гладкость, и допускается его невыпукл ость, многоэкстремаяьность. Существенное требование к численным методам решения подобных задач заключается в экономном добывании информации о критерии и ее рациональном использовании.
С точки зрения приложений вполне естественным было бы рассмотрение таких широких классов задач оптимизации, как классы всех непрерывных и всех гладких задач. Однако, для конструктивного построения вычислительных алгоритмов, а тем более для оценивания их эффекгивности и сложности оба упомянутых класса оказываются слишком широкими. Это обусловлено следующими обстоятельствами. Легко понять, что существуют две непрерывные функции на бесконечном множестве X, у которых совпадают значения на произвольном фиксированном конечном наборе точек из X, но максимальные значения в X различаются на сколь угодно большую величину. Как указыва-
28
ется в [78], сходимость алгоритма глобальной оптимизации гарантируется для любой непрерывной целевой функции на X, если генерируемая алгоритмом последовательность точек всюду плотна в X. Аналогичное утверждение справедливо для любого класса оптимизируемых функций, скорость изменения которых не является равномерно ограниченной на X, в частности, для класса гладких функций, дифференцируемых на X заданное число раз (см. [78, 79]).
В [78] отмечается также, что в глобальном поиске гладкость критерия эффективности играет не столь существенную роль, как в локальной оптимизации. Дело в том, что производные функции характеризуют ее локальные изменения, тогда как в процессе глобальной оптимизации в первую очередь должны выявляться общие тенденции поведения критерия на всем множестве допустимых точек. В некоторых методах глобального поиска предположение о гладкости целевой функции необходимо постольку, поскольку на их промежуточных этапах используются локальные алгоритмы, требующие вычисления производных. В то же время часто методы глобальной и особенно многокритериальной оптимизации (в том числе предлагаемые в данной работе) базируются на получении информации только о значениях критерия эффективности. Именно такие методы (называемые методами нулевого порядка) применяются для решения задач, в которых целевая функция задается алгоритмически, и вычисление производных с приемлемой точностью затруднено.
При разработке и исследовании численных методов оптимизации обычно исходят из той или иной модели критерия эффективности. Другими словами, полагают, что критерий принадлежит некоторому классу функций, характеризующихся какими-либо общими свойствами. Модель критерия должна быть адекватна реальным задачам, на решение которых ориентирован конкретный создаваемый численный метод. Как уже отмечалось выше, классы непрерывных и гладких функций чрезмерно широки, для того чтобы служить моделями критерия эффективности при построении методов оптимизации. Однако, при-
29
емлемым с этой точки зрения оказывается выделение из класса всех непрерывных функций подкласса функций с ограниченной скоростью изменения. Таким подклассом является, например, Р(Ь) — класс функций, удовлетворяющих условию Липшица на множестве X с константой Ь > 0. Класс 7*71) часто выбирается в качестве модели целевой функции, и именно эта — липши-цева модель критерия эффективности принимается в данной работе. В случае векторного критерия / = условие Липшица предполагается вы-
полняемым покомпонентно — для каждого с константой Ц > 0,
/ = 7,2,..., п, и Ь = (Ь1у...,Ьп).
Достоинство принимаемой здесь модели критерия заключается в том, что она охватывает широкий круг прикладных задач. В него входят, в частности, задачи проектирования сложных технических объектов, рассматривающиеся в §2 этой главы. Сам факт липшицевости целевой функции нередко вытекает из физического смысла конкретной реальной задачи ; в то же время, возникают немалые (обсуждаемые ниже) трудности с определением константы Липшица I.
Допущение о принадлежности целевой функции классу Р( I) позволяет теоретически строго обосновывать разрабатываемые численные методы: доказывать их сходимость, находить гарантированные оценки точности решения, устанавливать скорость сходимости, рационально строить алгоритмы и оценивать их сложность, конструировагь алгоритмы, оптимальные в минимаксном смысле. Данные факторы играют важную роль при создании методов решения задач, в которых получение информации о критерии эффективности сопряжено с трудоемкими затратами.
Класс методов, гарантирующих (по крайней мере в теоретическом плане) решение задач оптимизации на Р(1) с заданной точностью, образуют методы покрытий. Обычно в них не предусматривается вычисление производных целевой функции. Среди методов покрытий различают так называемые пассив-
30
ные и последовательные алгоритмы. (Эти известные понятия формально определяются в §3 главы I.) Здесь речь идет о последовательных алгоритмах. Главная идея методов покрытий состоит в рациональном получении и использовании информации об f gF(L) за счет исключения (из зоны поиска решения) неперспективных областей множества допустимых точек, т.е. областей, про которые в ходе решения задачи выясняется, что они не содержат оптимальных точек. Указанным методам посвящена обширная литература — см., например, [7, 21, 45, 46, 63, 64, 69, 78, 108, 141, 144, 149, 158, 159, 163, 209, 211, 212, 214, 215, 220, 253, 256, 266, 279, 285], где изучаются схемы покрытий глобального поиска и [67, 68, 174, 175, 213, 214], где предлагаются многокритериальные схемы покрытий.
Из всего многообразия методов покрытий выделим алгоритмы, оптимальные на F(L) в минимаксном смысле [211,213, 214]. Разработка многокритериальных алгоритмов такого рода является одной из основных целей глав 2, 3 настоящей работы. Отметим, что стремление к надежности результатов оптимизации и рациональному построению алгоритмов, выражающееся в ориентации на минимаксный подход, особенно оправдано в многокритериальной ситуации, когда из-за противоречивости частных критериев возрастает количество "неблагоприятных" задач по сравнению со скалярным случаем. К разряду "неблагоприятных" задач с векторным критерием / относятся задачи, решение которых — множество оптимальных по Парето точек /у (X) мало
отличается от X или даже Pf (X) - X. Подчеркнем также, что в рамках
минимаксной концепции оптимальности конструируются алгоритмы не только гарантирующие с требуемой точностью решение всех задач с критериями / gF(L), но и позволяющие учесть особенности конкретных функций f eF(L) с целью наиболее эффективного решения задач. 11одробнее о мини-
31
максной концепции оптимальности алгоритмов речь пойдет в §3 данной главы.
Принципиальный недостаток липшицсвой модели критерия эффективности и методов покрытий, разработанных на основе этой модели, связан с трудностью оценивания константы Липшица Ь , которая неизвестна в большинстве прикладных задач. Завышение константы I в алгоритмах покрытий приводит к резкому возрастанию количества информационных вычислений,обеспечивающего решение задачи с нужной точностью. При занижении величины I алгоритмы покрытий становятся некорректными в том смысле, что в результате их применения может быть потеряна область, содержащая оптимальные точки, и неверно найдено решение. Способы приближенного определения константы Липшица обсуждаются во многих работах по глобальной и многокритериальной оптимизации — см., например, [78, 174, 210, 212, 214]. Если критерий эффективности задан алгоритмически, то величина Ь оценивается численно путем отыскания разностных отношений критерия в ряде пар точек и умножения максимального из найденных значений на некоторый коэффициент "осторожности" больший единицы. Такая процедура может предварять оптимизацию либо использоваться непосредственно в самих алгоритмах покрытий на начальном и промежуточных этапах. В последнем случае литницева модель как бы уточняется в процессе решения задач, и способ оценивания константы I называется адаптивным. При этом уже не удается гарантировагь теоретическую строгость (корректность) алгоритмов покрытий, но с практической точки зрения они нередко оказываются достаточно эффективными и позволяют получать приемлемые результаты. К тому же (см. [78]) проблема теоретического обоснования в неменьшей степени стоит и для иных методов глобальной оптимизации, таких как, например, методы многократного применения алгоритмов
1) Информационными называют вычисления, доставляющие информацию о решаемой задаче; п данном случае таковыми являются вычисления значений критерия / еР(Ь).
32
локального поиска (мультистарт) и методы перехода из области притяжения одного локального экстремума в друг ую подобную область.
Иногда недостатком липшицевой модели целевой функции считают высокую трудоемкость алгоритмов глобальной оптимизации, базирующихся на этой модели. Информационная сложность алгоритмов покрытий экспоненциально зависит от размерности решаемых задач. Данный факт является, однако, следствием широты класса липшицевых функций Р(Ь) (подробнее — см. §3 главы 1) и свидетельствует в первую очередь об объективной трудности реальных задач, адекватным описанием критерия в которых служит лишницева модель.
В большинстве рассуждений главы 2 при исследовании информационной сложности задач, как и во многих работах но проблематике минимаксных алгоритмов, вид множества X допустимых точек не конкретизируется. В прикладных задачах (в том числе в задачах проектирования) оно часто задается функциональными ограничениями:
Х={хеХ°\ &(х)>0, / = /,
где X0 — множество простой струкгуры, например, параллелепипед с ребрами, параллельными координатным осям. При этом функции gj, / = /, 2,..., т, наряду с критерием /, нередко определяются алгоритмически; может оказаться, что получение информации об их значениях связано с трудоемкими расчетами, а достаточно точное вычисление производных от g/ (если они существуют) вовсе невозможно. Развиваемые в главах 3, 4 методы оптимизации ориентированы на задачи с ограничениями, в которых функции g/, / = 1, 2,..., т9 как и критерий /, обладают указанными специфическими чертами. По аналогии с критерием эффект ивности для таких функций gi принята липшицева модель.
33
Вообще, методы решения оптимизационных липшицевых задач (задач с липшицевыми функциями) характеризуются разнообразием теоретических подходов. По этому поводу отметим, что класс Р(Ь) содержит негладкие функции, методам отыскания экстремумов которых посвящены многие работы (с*м., например, монографии [50, 93, 122, 2471). Для липшицевых функций предложены обобщения понятий градиента дифференцируемой функции и субградиента выпуклой функции; получены аналоги правила множителей Лагранжа [93, 281]. Алгоритмы негладкой оптимизации, позволяющие находить локальные экстремумы, могут применяться в комбинации со схемами глобального и многокритериального поиска.
Для решения липшицевых задач широко используются также подходы, основанные на случайном поиске. Развитию таких подходов в глобальной оптимизации уделено большое внимание в [77, 78, 134, 196]. В частности, идея случайного поиска разными способами реализована в уже упоминавшихся методах покрытий [108, 256]. Известный вид глобального и многокритериального случайного (точнее говоря, квазислучайного) поиска представляют алгоритмы Л/7г-поиска [207]; как показано в [205, 206], они обладают определенными достоинствами при решении липшицевых задач. Существуют и другие подходы в глобальной оптимизации, применяемые для решения задач с липшицевыми критериями и ограничениями. В связи с этим отметим, например, информационно-статистические алгоритмы [210].
В качестве моделей реальных функций наряду с классом Р(Ь) рассматриваются его различные обобщения: класс гельдеровых функций с заданными параметрами, функциональные классы, определяемые модулями непрерывности и квазиметриками [214]. Сходной с липшицсвой является модель дважды дифференцируемой функции с ограниченными вторыми частными производными [26, 254]. Последняя модель чаще используется при решении
34
одномерных задач из-за трудности оценивания матрицы вторых производных от функции нескольких переменных.
Перечисленные в предыдущем абзаце модели (т.е. по сути априорные предположения) характеризуют функции с ограниченной скоростью изменения. В теории оптимизации широко распространены и другие виды моделей. Так, методы поиска локального экстремума обычно изучаются на классах унимодальных или выпуклых функций [21,91,215]. Методы нахождения глобального экстремума функций специального вида (см., например, [212]) базируются на соответствующих узких моделях целевых функций. Некоторые часто применяемые на практике методы глобальной оптимизации (мультистарт, алгоритмы перехода из одного локального экстремума в другой) недостаточно исследованы теоретически. Для них не описаны четко классы гарантированно решаемых задач, не полностью проанализированы вопросы эффективности. Возможшлй подход к указанным проблемам заключается в изучении моделей, учитывающих количество локальных экстремумов и объемы областей притяжения этих экстремумов.
До сих пор речь шла о детерминированных моделях реальных целевых функций. При разработке численных методов используются также вероятностные (байесовские, статистические) модели глобального поведения функций. В моделях такого рода на выбираемом функциональном классе вводится распределение вероятностей. В конструируемых на их основе алгоритмах оптимизации получение информации о решаемой задаче организуется в соответствии с ожидаемыми (наиболее вероятными) значениями критерия эффективности, определяемыми согласно заданному распределению. Подобные подходы к построению методов поиска глобального экстремума развиваются в [78, 79, 210, 275). С вероятностными моделями функций связана концепция оптимальности алгоритмов "в среднем”.
35
Подытоживая сказанное, отметим еще раз, что в данной работе принима-егся лишпицева модель реальных функций, поскольку она, с одной стороны, достаточно адекватна интересующим нас прикладным задачам, а с другой стороны, весьма удобна для теоретических исследований и рационального построения алгоритмов.
Подчеркнем также, что фразы типа "задача имеет высокую информационную сложность" в настоящей работе допускают толкование в двояком смысле. Во-первых, оно подразумевает большую трудоемкость информационных вычислений. Во-вторых, имеется ввиду резкий рост количества информационных вычислений, необходимых для решения задачи при повышении требований к точности решения и увеличении размерности задачи. Для многих задач характерны оба отмеченных здесь аспекта, и именно задачам такого рода посвящена данная работа. Термин "информационная сложность" формально определяется в §3 главы I.
3. Особенности постановок исследуемых задач.
Напомним, что через Р= Pf(X) в п. 1 было обозначено множество
парето-оптимальных точек на множестве X по векторному критерию / = (7/»—»/лЛ а через /(Р)—множество Парето.
Договоримся различать следующие две постановки многокритериальных задач. В задачах первого типа достаточно отыскать (точно или приближенно)
л л
произвольное подмножество Р € Р9 такое что /(Р) = /(Р) ■ Подобные задачи соответствуют так называемым замкнутым моделям принятия решений, в которых все интересы ЛИР (лица, принимающего решение) описываются частными критериями и альтернативы х, у е X при /(х) = /(у)
счит аются эквивалентными. В задачах второго типа требуется найти все множество Р - Ру( X). Такие задачи возникают, когда модель с критерием
36
/ - (/] > ” • ’ Iп ) перестав быть замкнутой и рассматривается как часть более широкой модели принятия решений, в которой ЛПР руководсгвуется не только критерием /, но и какими-то иными предпочтениями, нс учтенными в /. В этом случае альтернативы х, у при /(х) = /(у) уже неправомерно полагать эквивалентными.
Последняя ситуация является весьма характерной, поскольку, как отмечалось в п.1, во многих процедурах принятия решений нахождение множества Ру(Х) служит промежуточным этапом, после которого производится выбор
из Р/(Х) по некоторым дополнительным критериям, не включенным в вектор /. Такой подход к принятию решений используется, например, в проектировании сложных технических объектов. В начальной стадии процесса проектирования ставится задача формирования облика нового объекта. (Вопросы формирования облика обсуждаются в следующем параграфе.) В математическом плане эта задача нередко сводится к отысканию множества парето-оптималъных вариантов (проектов) объекта по векторному критерию, отражающему эффективность функционирования создаваемого объекта. Найденные на этапе формирования облика варианты прорабатываются и детализируются на последующих стадиях проектирования. При этом два варианта с одинаковыми функциональными характеристиками могут существенно различаться по внутреннему устройству, стоимости и возможностям пракгической реализации.
Указанные две постановки многокритериаэьных задач приводят к разным понятиям аппроксимации множества Р^(Х): аппроксимации по функционалу (по векторному критерию /) и аппроксимации по ар1ументу (в метрике пространства, содержащего множество X ). Соответствующие строгие определения даются в главах 2, 3. Основное внимание в этих главах уделяется задачам и методам приближенного построения множества Р/(Х) при различных трактовках аппроксимации Р/(Х).
37
§ 2. Оптимизационные задачи проектирования — примеры задач высокой информационной сложности.
1. Задачи формирования облика в автоматизированном проектировании сложных технических объектов.
Типичными образцами интересующих нас задач служат оптимизационные задачи автоматизированного проектирования сложных технических объектов [29 — 32, 53, 56, 59, 83, 99 — 103, 190]. Обсудим некоторые аспекты автоматизации проектирования.
Процесс проектирования сложных технических объектов имеет иерархическую структуру. Традиционно он разбивается на два этапа (стадии) — внешнее проектирование и внутреннее проектирование. На первой стадии формулируются цели создания нового технического объекта, и устанавливаются требования к его функциональным характеристикам, от которых зависит достижение поставленных целей. По результатам внешнего проектирования составляется техническое задание на разрабатываемый объект. Стадия внутреннего проектирования в свою очередь разделяется на этапы; первым из них является этап предварительного проектирования, на котором формируется облик создаваемого объекта, т.е. определяются структурная (конструкционная) схема и основные конструктивные параметры объекта, обеспечивающие выполнение требований внешнего проектирования. Формирование облика технического объекта называют также структурно-параметрическим синтезом объекта. Па последующих этапах внутреннего проектирования осуществляется детализация облика до необходимой степени подробности, которая делает возможной практическую реализацию (т.е. производство) технического объекга.
В работах [29, 32, 99, 101] предлагается подход к формализации процесса внутреннего проектирования. Этот подход заключается в построении иерархи-