6Ф7 Б 61 УДК 62--50 Батищев Д. И. Б 61 Поисковые методы оптимального проектирова- ния. М., «Сов. радио», 1975 216 с. с ил. В книге задача оптимального проектирования формулируется как детерминированная задача нелинейной оптимизации. Обсуждаются приемы сведения задач векторной оптимизации и стохастического про- граммирования к классу детерминированных экстремальных задач. Приводятся алгоритмы решения задач выпуклого и невыпуклого про- граммирования. Книга рассчитана на инженеров, аспирантов и студентов, специа- лизирующихся в области применения ЦВМ в задачах проектирования. 30501-080 046(01)-75 72-73 6Ф7 Редакция кибернетической литературы ДМИТРИЙ ИВАНОВИЧ БАТИЩЕВ Поисковые методы оптимального проектирования Редактор М. С. Гордон Художественный редактор 3. Е. Вендрова Обложка художника О. В. Камаева Технический редактор Г. А. Мешиова Коррекгор Л. А. Максимова Сдано в Hafcp 28/II-I975 г. Подписано в печать 24/1Х-1Э75 г. Т-12567 Формат 84ХЮ8/за Бумага машиномелованная Объем 11,34 усл.-п. л., 11,013 уч.-изд. л. Тираж 10200 экз. Зак. 242. Цена 74 к. Издательство «Советское радио», Москва, Главпочтамт, а/я 693 Московская типография № 10 Союзполиграфпрома при Государственном комитете Совета Министров СССР по делам издательств, полиграфии и книжной торговли, Москва, М-114, Шлюзовая нэб., 10. Издательство «Советское радио», 1975 г. Предисловие При машинном проектировании радиотехнических устройств приходится сталкиваться с необходимостью выбора оптимального (в том или ином смысле) вариан- та из множества допустимых. Математически эта проб- лема может быть сформулирована как задача нелиней- ной оптимизации. Поэтому настоящая книга посвящена изложению алгоритмов, реализующих численные мето- ды решения данного класса задач с помощью ЭВМ. В связи с тем, что существует большое число чис- ленных методов решения экстремальных задач, а при сравнительно небольшом объеме книги нельзя претендовать на полноту изложения, рассматриваются только те методы, которые, по мнению автора, либо наиболее интересны, либо использовались им при реше- нии прикладных задач. Естественно, что при этом отбор материала в ряде случаев носит субъективный харак- тер, так как он отражает опыт автора и его ззгляды на применение поисковых методов минимизации в задачах оптимального проектирования. С другой стороны многие методы оптимального проектирования (например, ли- нейное программирование, случайный поиск и др.), до- статочно подробно изложенные в многочисленных моно- графиях, также здесь не рассматриваются. Книга рассчитана на широкий круг инженеров и научных работников, занимающихся вопросами машин- ного проектирования радиоэлектронных схем, а также на аспирантов и студентов вузов соответствующих спе- циальностей. Настоящая книга написана по материалам лекций, читавшихся автором в течение ряда лет на радиофизи- ческом факультете Горь ко вского_унидег)_ситета_ В заключение автор выражает искреннюю призна- тельность профессорам Л. А. Растригину и В. П. Сигор- скому, которые прочли рукопись и высказали много по- лезных замечаний и предложений. Д. Батищев Введение Под оптимальным проектированием будем пони- мать процесс принятия наилучших (оптимальных) в не- котором смысле решений с помощью ЭВМ. Эта пробле- ма, связанная с получением оптимального решения из множества допустимых, является общей для всех этапов проектирования и во многом определяет технико-эконо- мическую эффективность и технологичность проектируе- мых устройств. С развитием микроэлектроники значение выбора оптимального решения на стадии проектирова- ния еще более возрастает, так как практически исклю- чается возможность экспериментальной оптимизации готовой схемы. Общим для задач принятия оптимальных решений, которые возникают на разных этапах проектирования, является то, что они математически могут быть сформу- лированы как задача нелинейной оптимизации. При этом предполагается, что имеется математическая мо- дель рассматриваемого объекта оптимизации и требует- ся для заданной модели найти такие параметры, кото- рые обеспечивают экстремальное значение одной из наиболее важных характеристик при условии, что другие удовлетворяют заданной системе ограничений. К такой постановке можно свести широкий класс экстремальных задач, в том числе задачи многокрите- риальной оптимизации, стохастического и параметриче- ского программирования. Применение ЭВМ позволяет задавать условия зада- чи не только в аналитическом, формульном виде, но и с помощью таблиц, программ моделирования, алгорит- мов решения дифференциальных и нелинейных уравне- ний и т. д. В связи с этим функции, описывающие проектируемое устройство, могут иметь сложный нели- нейный характер, что не позволяет получить оптималь- ное решение в аналитической форме с помощью классических методов дифференциального и вариацион- ного исчисления. Поэтому в последние годы стали интенсивно развиваться поисковые методы оптимального проектирования, обеспечивающие численное решение задачи при помощи ЭВМ. К сожалению, даже среди 4 поисковых методов не существует универсального (на' пример, такого как симплекс-метод в линейном програм- мировании), который позволял бы получать оптималь- ное решение для любой задачи нелинейной оптимизации. В настоящее время при решении каждой задачи опти- мального проектирования, сформулированной как зада- ча нелинейной оптимизации, может потребоваться при- менение нескольких методов поиска, но даже в этом случае успех во многом будет определяться знанием физической сущности рассматриваемой проблемы. Поэтому для решения экстремальных задач одного и того же класса разработано большое число методов поиска. В связи с этим возникают вопросы: какие же методы использовать для решения конкретных задач оптимизации, как выбирать при этом наилучшие пара- метры в методах поиска и т. д. В настоящее время су- ществует несколько способов получения ответа на по- ставленные вопросы. Один из способов связан с экспериментальным тес- тированием методов поисковой оптимизации. При этом предполагается, что введены некоторые оценки эффек- тивности процесса поиска, которые характеризуют, как затраты на поиск в целом, так и вероятность локализа- ции оптимального решения. Тогда с помощью тестовых задач, в которых известны оптимальные реше- ния, можно указать те методы, которые являются наи- лучшими для данного класса экстремальных задач. Другой способ эффективного решения задач нелиней- ной оптимизации состоит в разработке автоматизиро- ванных систем принятия оптимальных решений, которые позволяют решать задачи данного класса в интерактив- ном режиме*'. В результате диалога «человек—машина» исследователь может менять как число, так и тип варьи- руемых переменных, выбирать наилучший (в смысле за- трат машинного времени) метод поиска, подстраивать численные параметры метода к конкретным особенно- стям минимизируемой функции и т. д. Такой подход к решению экстремальных задач позволяет осущест- влять адаптацию методов поиска к особенностям и трудностям конкретной задачи. Для того чтобы пол- ностью использовать возможности интерактивного режи- *' Интерактивный режим предполагает возможность оперативно- го взаимодействия исследввателя с ЭВМ на любом этапе решения задачи. 5 Ма при решений задачи нелинейной оптимизации, необ- ходимо выполнение двух условий. Во-первых, библиоте- ка стандартных программ, входящих в систему, должна включать широкий класс алгоритмов поисковой оптими- зации и, во-вторых, необходимо знать особенности и возможности поисковых методов оптимального проекти- рования, хотя бы на основании информации, полученной путем экспериментального тестирования. Таким образом, очевидно, что эффективное решение задачи оптимального проектирования сильно зависит от набора алгоритмов поисковой оптимизации, с кото- рыми знаком исследователь. Поэтому целью настоящей книги является систематизация, обобщение и развитие поисковых методов оптимального проектирования. По содержанию книгу удобно разделить на три ча- сти. Первая часть (гл. 1—2) посвящена вопросам мате- матической формулировки задачи оптимального проек- тирования как задачи нелинейной оптимизации и фор- мализации ряда понятий, связанных с наилучшими алго- ритмами поисковой оптимизации. Здесь показано, как к сформулированной задаче могут быть сведены задачи оптимизации характеристик радиотехнических цепей, зависящих от непрерывно изменяющегося параметра, задачи многокритериальной (векторной) оптимизации и задачи стохастического программирования. При опреде- лении наилучшего алгоритма поиска дается методика экспериментального тестирования и приводятся тесто- вые классы экстремальных задач, на которых целесооб- разно сравнивать и исследовать алгоритмы поисковой оптимизации. Во второй части (гл. 3—7) дается подробное изложе- ние алгоритмов поисковой оптимизации, доведенных либо до блок-схем, либо до процедур, описывающих последо- вательность действий, при оптимизации. Эта часть книги построена таким образом, что алгоритмы излагаются в последовательном возрастании трудности решения задач оптимизации: от одномерных к многопараметри- ческим, от унимодальных к многоэкстремальным, от задач без ограничений к задачам с ограничениями, от выпуклого программирования к задачам невыпуклого программирования. Такое построение кажется автору це- лесообразным с двух точек зрения. Во-первых, это по- зволяет излагать материал, наращивая его сложность. 6 Во-вторых, при таком изложении обеспечивается преем- ственность рассматриваемых алгоритмов. Так, напри- мер, алгоритмы одномерного унимодального поиска используются в методах глобальной минимизации про- извольных кривых, которые являются одной из процедур при поиске локального минимума многопараметрических функций, алгоритмы решения последних, в свою оче- редь, используются в качестве процедуры 'в задачах вы- пуклого программирования и т. д. В третьей части (гл. 8) рассматриваются вопросы приложения методов поисковой оптимизации к расчету оптимальных параметров конкретных классов схем (пассивных электрических цепей, кварцевых фильтров, логических транзисторных элементов и т. д.). В заключение необходимо отметить, что радиотехни- ческая направленность книги связана только с иллюст- ративным материалом, так как излагаемые в книге по- исковые методы оптимального проектирования могут быть использованы для решения широкого круга при- кладных задач. Глава первая МАТЕМАТИЧЕСКАЯ ФОРМУЛИРОВКА ЗАДАЧ ОПТИМАЛЬНОГО ПРОЕКТИРОВАНИЯ 1.1. Математические модели проектируемых устройств Для решения на ЭВМ задач оптимального проек- тирования конкретных радиотехнических устройств и схем необходимо иметь их математические модели [1,2J. Несмотря на всю сложность и разнообразие ра- диотехнических цепей (пассивные и активные фильтры, усилительные каскады, переключающие элементы, импульсные схемы и т. п.) процесс построения матема- тической модели физического устройства содержит сле- дующие общие этапы [3]: — формализация задачи проектирования; — анализ и выделение существенных свойств устрой- ства; — построение математического описания, отражаю- щего взаимосвязь существенных свойств устройства между собой. Исходной информацией при этом являются данные о назначении, условиях применения и режимах работы проектируемого устройства. Эти данные позволяют опре- делить основную цель (задачу) проектирования и фор- мализовать требования, предъявляемые к проектируемо- му устройству. Предположим, что каждое конкретное физическое устройство характеризуется некоторым набором свойств, которые соответствуют целям его применения и могут быть измерены или вычислены. Здесь под свойствами будем понимать величины, отражающие поведение реального устройства и учитывающие как технико-эко- номические показатели, так и условия функционирова- ния. При выделении существенных свойств необходимо пренебрегать теми, которые не влияют на решение по- ставленной задачи проектирования. Например,при рас- чете транзисторных схем по постоянному току стоимость транзистора и его шумовые характеристики являются свойс1вами, которые не имеют существенного значения 8 Для решения поставленной задачи и могут не рассма- триваться. Пусть п свойств являются независимыми друг от друга и могут варьироваться в некоторых пределах. Обозначим их вектором х= (xi, xz, ..., Хп) и назовем управляемыми переменными (или параметрами). Дру- гие m свойств являются зависимыми от параметров и называются характеристиками. Обозначим их вектором <р= ((pi, срз, ..., tpm). Параметры и характеристики опре- деляют объект проектирования (или просто объект). Кроме управляемых переменных характеристики могут зависеть от оставшихся I свойств, которые являются случайными величинами. Назовем их внешними факто- рами и обозначим вектором y==[yi, yi, • •., yi)- Внешние факторы образуют среду, в которой рассматривается объект проектирования. В зависимости от характера решаемой задачи свой- ства реального устройства могут быть отнесены либо к свойствам объекта, либо к свойствам среды, т. е. раз- деление на свойства объекта и свойства среды относи- тельно и определяется целью проектирования. Так, при расчете электронной схемы в дискретном исполнении параметрами х обычно являются электрические компо- ненты схемы (сопротивления, емкости и индуктивности), а характеристиками могут быть временные или частот- ные зависимости. В то же время при проектировании электронной схемы в интегральном исполнении в каче- стве параметров х могут быть выбраны геометрические размеры компонентов и удельное сопротивление мате- риала, из которых они изготовлены. В этом случае ха- рактеристиками объекта, кроме временных и частотных зависимостей, будут и параметры электрических компо- нентов схемы. Управляемые переменные и внешние факторы игра- ют роль независимых переменных, а характеристики являются зависимыми от этих величин. Соотношения, выражающие эти зависимости, будем называть матема- тическим описанием объекта: ?i==?i (^i, л:2,..., Хп; г/i, г/2,..., г/г), ................ (1.1) Уот==?т(^1, Хг,..., Хп; г/i, г/г,..., yi) или в векторной форме Ф=(р(х, у). (1.2) 9 Зависимости q)(x, у) в общем случае представляют со- бой отображение между двумя множествами свойств проектируемого устройства (р и (х, у). Они могут быть заданы различными способами: с помощью формул, гра- фиков, таблиц, алгоритмов вычисления характеристик или решения систем дифференциальных и трансцендент- ных уравнений. Таким образом, под математической моделью реаль- ного устройства будем понимать конечное множество переменных {х, у} вместе с математическими связями (1.2) между ними и характеристиками (р. Если матема- тическое описание объекта не содержит элементов слу- чайности (в этом случае внешние факторы отсутствуют), модель называется детерминированной в том смысле, что характеристики <р однозначно определяются параме- трами х: <р=(р(х). (1.3) Модели, в которых приходится учитывать случайные факторы у, называются вероятностными или стохасти- ческими [4]. В таких моделях характеристики (р явля- ются случайными величинами, распределение которых при постоянных значениях параметров х определяется факторами у. В дальнейшем для описания детерминиро- ванных моделей будем пользоваться соотношениями (1.3), а для описания стохастических моделей—(1.2). Для каждого исследуемого объекта проектирования можно построить несколько математических моделей. В зависимости от постановки задачи разрабатывается та или иная модель, которая отражает локальные свой- ства рассматриваемого устройства и полностью опреде- ляется знаниями и опытом разработчиков—специали- стов в данном вопросе. Однако общее требование к лю- бой модели состоит в том, что она должна быть адекватна реальному устройству, т. е. ее математическое описание должно с заданной точностью отражать суще- ственные свойства, присущие конкретному объекту. Из-за большого числа взаимосвязей свойств объекта как между собой, так и со средой построение полностью адекватной модели практически невозможно. Поэтому при построении математической модели необходимо добиваться компромисса между ожидаемой точностью результатов и сложностью модели. Точность модели полностью определяет достоверность тех результатов, которые получаются в процессе оптимизации. (Примеры 10 построения математических моделей для конкретных за- дач расчета радиотехнических цепей будут приведены в гл. 8.) 1.2. Формулировка ограничений, налагаемых на параметры и характеристики математической модели Любая характеристика у^ , у,4" — <р, (х), если у;(х)<у^ . Очевидно, что к ограничениям (1.6) могут быть све- дены ограничения типа равенств g(x)=0 путем замены их парой неравенств: g(x)^0, -g(x)>0. Одной из особенностей проектирования радиотехни- ческих объектов является то, что в систему ограничений (1.6) могут входить характеристики, которые зависят от некоторого параметра v, заданного на интервале [v~, v+]. Таким параметром может быть время, частота, тем- пература и т. п. В этом случае ограничение на .k-ю ха- рактеристику объекта связано с выполнением условия: gk(\, v)^0, v^[v-, v+]. (1.7 Переход от ограничений типа (1.7) к системе нера- венств (1.6) можно осуществить, используя либо сеточ- ный метод [5], либо принцип гарантированного резуль- тата [б]. Идея сеточного метода основана 'на дискретизации исходного интервала [v~, v+] равномерной е-сетыо и рассмотрении функции gft(x, v) Ha дискретной совокуп- ности точек (vi, V2, ..., Ум). При этом выполнение огра- ничения (1.7) сводится к требованию выполнения систе- мы из М неравенств: ^(х, v,)^0, i==l, 2, ..., М. (1.8) Согласно е-теореме [5] для любой непрерывной функции всегда можно выбрать такое число точек М> >Л1о, что выполнение системы неравенств (1.8) будет обеспечивать выполнение ограничения (1.7) с любой заданной точностью е. Однако на практике вопрос выбо- ра конкретного числа Мц остается неясным и приходится задавать число точек дискретизации М на основании опыта и физической сущности задачи. Другим недостат- ком сеточного метода является то, что вместо одного неравенства (1.7) приходится рассматривать систему из М неравенств. В связи с вышесказанным для проверки ограничения (1.7) целесообразно использовать принцип гарантиро- ванного результата, основная идея которого заключает- 12 ся в том, что ограничение (1.7) проверяется для наибо- лее неблагоприятного (критического в смысле выполне- ния неравенства (1.7)) значения параметра v*^1^",^]: g,(x, v*)>0, (1.9) где gft(x, v*)==mingf,(x, v). M-$::V^V+ Необходимо заметить, что критическое значение па- раметра v зависит от управляемых переменных х и является некоторой неизвестной функцией от них, т. е. v*==v*(x). Для отыскания критического значения v* можно применять методы поисковой оптимизации, рас- смотренные в гл. 4, которые основаны только на вычис- лении значений функции gh(x, v) в фиксированных точ- ках V;, i'=l, 2, ..., N. Получаемое при этом расположе- ние точек V; будет неравномерным. Оно не задается зара- нее, а выбирается автоматически в процессе поиска в зависимости от вида функции gh(^, v). Для резко из- меняющихся функций значение N получается больше, чем для плавных кривых. Причем точки У{ располага- ются наиболее плотно в тех подынтервалах, для которых неравенство (1.7) наиболее критично относительно па- раметра v. В дальнейшем будем считать, что ограничения, за- данные на интервале [v~, v+], с помощью принципа га- рантированного результата сведены к системе нера- венств (1.6). Тогда условия (1.6) будут определять не- которое множество изменения управляемых перемен- D,={xlg(x)S&0}. (1.10) Это выражение означает, что множество Dg состоит из всех тех векторов х= {х\, х^, ..., Хп), для которых вы- полняется система неравенств g,(x)^0, i=\, 2, ..., m. Ограничения (1.4) образуют множество допустимых значений вектора х, удовлетворяющих системе линей- ных неравенств D^={x\x,-^x,-^x,+, /=1, 2, ..., п}. (1.11) Эти неравенства могут быть исключены из дальнейшего рассмотрения при помощи введения новых переменных z, связанных с х, например, соотношениями следующего вида: Xj==xj-+ (Xj+—x,-) sWz,, (1.12) где Zj, /'=1,2,..., n, — любое число. 13 Некоторые типы ограничений на параметры х и пре- образования [7—10], позволяющие исключить из зада- чи оптимального проектирования линейны? неравенства, приведены в табл. 1.1. Таблица 1.1 Параметры параметры Преобразование переменных ременные х/^0 Xj = 22/ х/>0 х/ = ехр (г/) X/ Х]~ < X, < X* х/=х,у-+ [(х/1"— 27 —x~)fv.\ arcctg z/ Xj > Х~/~ Х/-Х^-+2^ x,+i>x/Х1+1>Х, Xj = x/+i sin2 г/ x;=(x/+iarcctgz/)/Tt Х/+1. 2/ X/ = ехр (?•/) cos [9„ + +(9p-9„)sin^/+,] XI, Х/+1 0<я-<Х/+1/Х/< <Р, Х/>0,. 0 х/+,=ехр(г/)8ш[9„+ +(9p-9,)sin2z/+i] 9„ •--= arctg a г/, г/+, 9р = arctg р 0<9„<9g<^2 Множество D, полученное при пересечении множеств Dx и Dg(D=Dx П ^g)» будем называть допустимой областью изменения управляемых переменных х. Лю- бой вектор х, принадлежащий допустимой области D(xs/5), является допустимым вектором. 1.3. Постановка и классификация детерминированных задач оптимизации Под решением задачи оптимального проекти- рования будем понимать процесс выбора управляемых переменных х, принадлежащих допустимой области D и обеспечивающих оптимальное значение некоторой ха- рактеристики объекта Q(x). Эта характеристика, пока- 14 зываюЩая относительное «предпочтение» одного вариан- та по отношению к другим, называегся критерием опти- мальности (функцией цели, критерием эффективности, функцией полезности и т. п.). Экстремальное значение критерия оптимальности Q(x) численным образом ха- рактеризует наиболее важное свойство объекта. В зави- симости от цели проектирования необходимо получить либо максимум, либо минимум этой величины. Напри- мер, для логических элементов в зависимости от цели проектирования необходимо получить максимальное быстродействие или минимальную потребляемую мощ- ность, максимальную нагрузочную способность или мак- симальную помехоустойчивость и т. д. Пусть для опре- деленности требуется, чтобы критерий оптимальности был минимален*) minQ(x). х^° (1.13) Выражение (1.13) является сокращенной записью сле- дующей задачи оптимизации. Найти вектор х== (xi, х-ц, ..., Хп), обеспечивающий минимальное значение кри- терия оптимальности Q=Q(Xi,X2, ...,Хп) (1.14) при выполнении системы неравенств gi(xi, X2, ..., Хп)^0, t=l, 2, ..., m, (1.15) хг^х^х,+, !=\, 2, ..., п. (1.16) Таким образом, решение задачи оптимального проек- тирования сводится к решению задачи оптимизации (1.14)—(1.16), т. е. к определению оптимального реше- ния х*, удовлетворяющего неравенствам (1.15), (1.16) и обеспечивающего минимальное значение критерия оптимальности (1.14). Задача оптимизации (1.14)—(1.16) называется зада- чей линейного программирования, если критерий опти- мальности' и ограничения являются линейными функция- ми параметра х: п mm Y CjXi (1.17) /=i ^ Это не нарушает общности рассмотрения, так как максими- зация функции Q(x) сводится к минимизации функции—Q(x). 15 пря условии п ^ aijXf^bi, i=\, 2,..., m; '"^•^O, /=1, 2,,.., /г. (1.18) Численные методы решения задач линейного програм- мирования хорошо разработаны [11—13] и поэтому рассматриваться в дальнейшем не будут. Если критерий оптимальности Q(x)—квадратичная функция, т. е. Q(x) =xтGx+cтx, а ограничения—линей- ные функции, то задача (1.14)—(1.16) называется за- дачей квадратичного программирования. Для положи- тельно полуопределенной матрицы G, как и для задачи линейного программирования, разработаны методы, обеспечивающие получение оптимального решения за конечное число шагов итерационного процесса, послед- няя итерация которого дает точное решение задачи линейного или квадратичного программирования [14— 16]. В тех случаях, когда критерий оптимальности или ограничения являются нелинейными функциями, задача (1.14)—(1.16) называется задачей нелинейной оптими- зации. В зависимости от числа варьируемых параметров х, вида допустимой области D и критерия оптимальности Q(x) задачи нелинейной оптимизации можно классифи- цировать следующим образом. При отсутствии нелинейных ограничений (1.15) <) за- дача оптимизации упрощается и сводится к поиску ми- нимума функции Q(x), определенной в га-мерном евкли- довом пространстве R": minQ(x). (1.19) x^S" Задача (1.19) называется задачей нелинейной оптими- зации без ограничений (или задачей поиска безусловного минимума). При наличии ограничений, связывающих переменные х, задача нелинейной оптимизации называется задачей нелинейного программирования (или задачей поиска экстремума при наличии ограничений). Общим для обоих типов задач оптимизации является то,"то в зависимости от числа варьируемых переменных *' Будем считать, что линейные ограничения (1.16) в этом слу- чае исключены из рассмотрения при помощи преобразований, приве- денных в § 1.2 (см. табл. 1.1). 16 они могут быть одномерными (п==1), когда осуществля- ется поиск минимума произвольной кривой Q(x), или многопараметрическими (и^2), связанными с миними- зацией некоторой re-мерной гиперповерхности Q(x). При этом оптимальное решение х* в зависимости от вида функции Q(x) может быть либо точкой локального, либо точкой глобального минимума. Вектор х* называется точкой локального (или отно- сительного) минимума, если для всех точек х, принад- лежащих е-окрестности а(\*, е) этой точки, значение Q(x) не принимает меньшего значения: Q(x*)• Q/(х). Из определения эффективной точки следует, что она не единственна. Множество всех эффективных точек называется областью компромиссов или областью реше- ний, оптимальных по Парето [19]. Оптимальность по Парето векторного критерия Q(x) означает, что нельзя дальше уменьшать значение одного из частных крите- риев, не увеличивая значения хотя бы одного из осталь- ных. Для определения минимума по Парето необходимо перейти от задачи векторной оптимизации к задаче не- линейной оптимизации (1.13) со специально сконструи- рованной скалярной функцией цели: Q(x)=n?>*-.; D*.,={x|Q,(x)=Q*/, /=1, 2,..., k-\}. На практике для того чтобы получить хорошее реше- ние по менее важным критериям, приходится делать уступки AQ по другим наиболее важным критериям. Этот подход реализуется в методе последовательных уступок. [27], который сводится к решению последова- тельности задач нелинейной оптимизации: mmQ*(x), k =2, 3,..., s, (1.29) "eo/e где ^==ДП^_,; Dft.,={x|Q/(x)0, г=1, 2,..., т}. При решении задачи (1.35) возможны две ситуации: — оптимальное решение х* требуется определить до реализации факторов у, т. е. независимо от их конкрет- ных значений; 27 ь- оптимальное решение х* требуется определить после того, как стали' известны факторы у. В первом случае учет случайных значений вектора у в условиях задачи оптимизации (1.35) сводится, по су- ществу, к введению нового критерия оптимальности и ограничений, которые позволяют избавиться от случай- ности или неопределенности. В зависимости от степени информированности о законе распределения случайных величин у можно рассматривать три случая: — о фактах у ничего не известно, кроме того, что они принадлежат некоторой области Dy : y<^Dy; — для факторов у задана произвольная, но извест- ная функция распределения f(y); — для факторов у тип закона распределения изве- стен с точностью до вектора параметров а, т. е. задана функция /(у, а), для которой неизвестны параметры к, принадлежащие области D ^. В зависимости от степени информированности о за- коне распределения случайных факторов выбор нового критерия оптимальности и ограничений приходится осу- ществлять либо рассчитывая на наихудший случай относительно значений вектора у, либо ориентируясь на некоторые средние значения критерия и ограничений. В тех случаях, когда только известно, что y^Dy, критерий оптимальности назначается из условия обес- печения наилучшего результата в наихудшем по неопре- деленности у случае [17]: Q(x)=maxQ(x, у). (1.36) . уг°г/ Аналогично для ограничений можно записать gi(x)==mmgi(\, у). (1.37) у(=Ду Подставляя (1.36), (1.37) в (1.14), (1.15), при отсутствии информации о факторах у (случай неопределенности) приходим к детерминированной задаче оптимизации: min maxQ(x, у), (1.38) xs=o уе°у где D = {х | [min g, (х, у)] > 0, г= 1,..., т}. У^и Появление информации о том, что у—случайные ве- личины, позволяет выбрать критерии оптимальности бо- лее предпочтительные, чем (1.36). Это связано с тем, что знание законов распределения в критерии (1.36) ничего 28 нового не дает по сравнению со случаем неопределен- ности. Поэтому критерий оптимальности и ограничения необходимо изменить таким образом, чтобы полученный по ним результат был наилучшим «в среднем» для сово- купности ситуаций, задаваемых законом распределения /(у). В этом случае мы отходим в сторону от «осторож- ности», свойственной функциям (1.36), (1.37), и идем на некоторый риск, связанный с тем, что полученное при этом решение может и не быть оптимальным в каждой конкретной ситуации. При известных законах распределения в качестве критерия оптимальности можно использовать матема- тическое ожидание (среднее значение) случайной функ- ции Q(x, у): Q(x)==AI,{Q (х, у)}= ^ Q(x,[y)^(y) (1.39) ys°Q-} (1.41) и т. д. Используя выражения типа (1.39)—(1.41) в качестве критерия оптимальности и ограничений, для случая из- вестных законов распределения приходим к одной из следующих задач стохастического программирования [31—35]. Усредненная задача стохастического программирова- ния. Найти вектор управляемых переменных х, обеспе- чивающий (1.42) т. (1.43) min [ Q(x, y)df(y') ТС •' _ при условии ^ g.(x, y)rf/'(y)->0, г=1, 2,..., уе°у Задача стохастического программирования с вероят- 29 вектор управляемых (1.44) (1.45) нйстными ограничениями. Найти переменных х, обеспечивающий min f Q(x, y)rff(y) x yek при условии P{gi('a, У)^0, 1=1, 2,..., от}>р, где 0p. (1.47) При наличии информации о законах распределения случайных факторов, заданных с точностью до вектора параметров а, выражения (1.39)—(1-41) становятся функциями от этих переменных. При этом о векторе « ничего не известно, кроме того, что он принадлежит области Д„ В этом случае необходимо использовать комбинированый критерий, сочетающий в себе выраже- ние (1.36) и одно из выражений (1.39)—(1.41). Это по- зволяет перейти от задачи (1.35) к одной из задач стьхастического программирования. Например, усред- ненная задача стохастического программирования в этом случае формулируется так. Найти вектор управляемых переменных х, обеспечивающий: min max f Q(x, у) df(y, a) (1.48) х ае=о„ J„ при условии Г min f , | min f g,(x, y)df(y, 0)1530, i==l, 2,..., т. (1.49) l^yek J Таким образом определение оптимального решения х*, не зависящего от конкретной реализации у, сводит- ся к решению задачи нелинейной оптимизации (1.13), в которой статистическая природа исходной задачи (1.35) проявляется только на этапе вычисления крите- рия оптимальности и ограничений. 30 При определении оптимального решения после того, как становятся известными значения у, задача (1.35) аналогична обычной детерминированной задаче оптими- зации (1.13). При этом разным реализациям случайных факторов у, вообще говоря, соответствуют различные оптимальные решения х*=х*(у), т. е. при изменении условий в задаче оптимизации мы можем перестраи- вать оптимальное решение [36, 37]. Таким образом, процесс поиска оптимального ре- шения в задачах проектирования как при многокрите- риальной оптимизации, так и при учете случайных фак- торов практически сводится к численному решению де- терминированной задачи нелинейной оптимизации, сформулированной в § 1.3, Таблица 8.14 Вероятность выполнения условий работоспо- соэности при следующих значениях 6д, % Вариант 5 10 15 20 25 30 ИСХОДНЫЙ 1 0,956 0,729 0,627 0,505 0,399 опти 1 1 1 1 0,961 0,843 мальный изменения управляемых переменных (R.2, R4) и (Rl, R4) для исходного и оптимального вариантов. Заштрихован- ными прямоугольниками показаны области изменения сопротивлений схемы относительно номинальных значе- ний в 'поле допуска 6ft==20%. Список литературы 1. Сложные системы и решение экстремальных задач — «Ки- ^бГв: Яо^З^ михалеви4 в- с- EP•мoльeвю• м- 2. П о л л я к Ю. Г. Общие принципы и эвристические приемы построения моделей для исследования проектируемых систем.— В кн.: Вопросы кибернетики и вычислительной математики Вып 28 Проблемы статистической оптимизации, Ташкент, «ФАН», 1969. 3. 3 а д е Л., Д е з о е р Ч. Теория линейных систем Метод пространства состояний. Пер. с англ. М., «Наука», 1970. 4. П о л л я к Ю. Г. Вероятностное моделирование на электрон- ных вычислительных машинах. М., «Сов. радио», 1971. 5. Р е м е з Е. Я. Основы численных методов чебышевского приближения. Киев, «Наукова думка», 1969. 6. Оптимизация радиотехнических цепей с характеристиками, зависящими от непрерывно изменяющегося параметра. — «Известия вузов. Радиоэлектроника», 1973, № 6. Авт.: Батищев Д И Смыс- лов Г. М., Басалин П. Д., Игуменцева Г. В. 7.КалаханД. Методы машинного расчета электронных схем Пер. с англ. М., «Мир», 1970. 8.Темеш Г.,Калахан Д. Машинная оптимизация электри- i/ ческих цепей. ТИИЭР, 1967, т. 55, № 11. V 9. Box M. J. A comparison of several current optimization me- thods and the use transformations in constrained problem —«Corn- put. J.», 1966, v. 9, № 1. 10. В a n d 1 е г J, W. Optimization methods for computer—Aided design.—«IEEE Trans.», 1969, v. MTT-17, № 8. 11. Юдин Д. Б., Гольштейн Е. Г. Задачи и методы ли- неиного программирования. М., «Сов. радио», 1961. 12. Гольштейн Е. Г., Юдин Д. Б. Новые направления R линейном программировании. М„ «Сов. радио», 1966. 13. Зуховицкий С. И., Авдеева А. И. Линейное и выпук- лое программирование. М., «Наука», 1964. Н.Кюнцн Т., Крелле В. Нелинейное программирование. Пер. с нем., М., «Сов. радио», 1965. 15. Зойтенденк Г. Метод возможных направлений. Пер. с англ., М., ИЛ, 1961. 16. Денни с Дж. Б. Математическое программирование и элек- трические цепи. Пер. с англ. М., ИЛ, 1961. 17. Гермейер Ю. Б. Введение в теорию исследования опе- рации. М., «Наука», 1971. 18. Карлин С. Математические методы в теории игр, програм- мировании и экономике. Пер. с англ., М., «Мир», 1964. 19. Ланге О. Оптимальные решения. Пер. с польск М «Про- \Г гресс», 1967. ' ' у 20. Г е р м е и е р Ю. Б. Игровые концепции в исследовании систем. — «Изв. АН СССР. Техн. кибернетика», 1970, № 2. 21. Вилка с Э. И., Майминас Е. 3. К проблеме сложных решении (постановка и подходы). — «Кибернетика», 1968, № 5 н* 203 . 22. М е л е ш к о В. И. Теория полезности и методы введения глобальных критериев оптимальности.—В кн.: Адаптивные систе- мы. Под ред. Л. А. Растригша. Вып. 3, Рига, «Зинатне», 1972. 23. В о л к о в и ч В. Л. Многокритериальные задачи и методы их решения. — В кн.: Кибернетика и вычислительная техника. Под ред. В. М. Глушкова. Вып. I, Киев, «Наукова думка», 1969. 24. Волкович В. Л. Методы принятия решения по множе- ству критериев оптимальности (обзор).—В кн.: Сложные системы управления. Вып. 1, Киев, ИК АН УССР, 1968. 25. Ю т т л е р X. Линейная модель с несколькими целевыми функциями. — «Экономика и мат. методы», 1967, т. 3, № 3. 26. Д р е ш е р М. Стратегические игры. Теория и приложения. Пер. с англ. М., «Сов. радио», 1964. 27.Венцель Е. С. Исследование операций. М., «Сов. ра- дио», 1971. 28. Л а р и ч е в О. И. Человеко-машинные процедуры принятия решений (обзор).—«Автоматика и телемеханика», 1971, № 12. 29. Линейное программирование с многими критериями. Метод ограничений.—«Автоматика и телемеханика», 1971, № 8. Авт.: Бе- найюн Р., Ларичеи О. И., Монгольфье Ж. Д., Терни Ж. 30. Батищев Д. И. САППОР-система автоматизации процес- са принятия оптимальных решений. — В кн.: Кибернетические систе- мы автоматизации проектирования (материалы семинара, январь 1973). Моск. дом научно-технической пропаганды, 1973. 31. Цыпки н Я. 3. Адаптация и обучение в автоматических системах. М., «Наука», 1968. 32. Ю л и н Д. Б. Новые подходы к стохастическому программи- рованию. — «Экономика и мат. методы», 1968, т. 4, вып. 6. 33. Ю д и н Д. Б. Выбор решений в сложных ситуациях. — «Изв. АН СССР. Техн. кибернетика», 1970, № 2. 34. Е р м о л ь е в Ю. М. О некоторых проблемах стохастического программирования.—«Кибернетика», 1970, № 1. 35. К а п л и н с к и и А. И., Пропой А. И. О стохастическом подходе к задачам нелинейного программирования. — «Автоматика и телемеханика», 1970, № 3. 36. Ю д и н Д. Б. Решающее правило в экстремальных зада- чах.—«Изв. вузов. Радиофизика», 1972, т. 15, № 7. 37. Ю д и н Д. Б. Новые подходы к формализации выбора ре- шений в сложных ситуациях. — «Автоматика и телемеханика», 1972, № 5. 38. Г урин Л. С., Дым а реки и Я. С., М е р к у л о в А. Д. Задачи и методы оптимального распределения ресурсов. М., «Сов. радио», 1968. 39. У а и л д Д. Методы поиска экстремума. Пер. с англ. М., «Наука», 1967. 40. Островский Г. М., Волин В. М. Методы оптимизации химических реакторов. М., «Химия», 1967. 41.Kiefer J. Sequential minimax search for a maximum.— «Proc. Amer. Math. Soc.», 1953, v. 4, p. 502—506. 42. К i e f е г J. Optimum sequential search and appraximation methods under minimum regularity assumptions.—«J. Soc Industr. Appl. Math.», 1957, v. 5, № 3. 43. Сухарев А. Г. Об оптимальных стратегиях поиска экстре- мума.—«Ж. вычисл. мат. и мат. физ.», 1971, т. 11, Xs 4. 204 44. С у х а р е в А. Г. Наилучшие стратегии последовательного поиска экстремума. — «Ж. вычисл. мат. и мат. физ.», 1972, т. 12, № 1. 45. Ч е р н о у с ь к о Ф. Л. Оптимальный алгоритм поиска корня функции, вычисляемой приближенно. — «Ж. вычисл. мат. и мат. физ.», 1968, т. 8, № 4. 46. Ч е р н о у с ь к о Ф. Л. Об оптимальном поиске экстремума унимодальных функций.—«Ж. вычисл. мат. и мат. физ.», 1970, т. 10, № 4. 47. Че р н о у с ьк о Ф. Л. Об оптимальном поиске минимума выпуклых функций.—«Ж. вычисл. мат. и мат. физ.», 1970, т. 10, № 6. 48. И в а н о в В. В. Вопросы точности и эффективности вычис- лительных алгоритмов (обзор достижений в области кибернетики и вычислительной техники). Вып. 2, Киев, ИК АН УССР, 1969. 49. В г о о k s S. Н. A comparison of maximum-seeking methods.— «Oper. Res.», 1959, v. 7, p. 430—457. 50. Шкварцов В. В., Орленко Н. Н. Опыт эксперимен- тального сравнения алгоритмов случайного поиска. — В кн.: Проб- лемы статистической оптимизации. Под ред. Л. А. Растригина. Ри- га, «Зинатне», 1968. 51. Захаров В. В. О сравнении методов решения много- экстремальных задач.—В кн.: Поиск экстремума (математические методы и автоматические системы). Под ред. В. П. Тарасенко. Том- ский ун-т, 1969. 52. Б а т и щ е в Д. И. Об экспериментальном сравнении неко- торых методов поиска экстремума функций многих переменных. — В кн.: Поиск экстремума (математические методы и автоматические системы), Томский ун-т, 1969. 53. Р о з е н б р о к X., С т о р и С. Вычислительные методы для инженеров-химиков. Пер. с англ. М., «Мир», 1968. 54. X и л л Дж., Г и б с о н Дж. Способ автоматической опти- мизации многоэкстремальных функций.—В кн.: Теория самонастраи- вающихся систем управления. Труды II международного симпозиума ИФАК по самонастраивающимся системам. М., «Наука», 1969. 55. А л ь п е р о в и ч Э. Е., Б а т и щ е в Д. И., С т р о н г и н Р. Г. Теоретические и прикладные аспекты тестирования алгоритмов по- иска.—В кн.: Вопросы кибернетики (проблемы случайного поиска). М., Научный совет по комплексной проблеме «Кибернетика» АН СССР, 1973. 56. Г у р и н Л. С. К вопоосу о сравнительной оценке различ- ных методов оптимизации.—В кн.: Автоматика и вычисл. техн. Вып. 10, Рига, «Зинатне», 1965. 57. П о л л я к Ю. Г. К вопросу об экспериментальном иссле- довании алгооитмов поиска экстремума. — «Автоматика и вычисл. техн.», 1968, № 2. 58. Батищев Д. И., Бедная Р. И., Стронгин Р. Г. О выборе параметров алгоритмов поисковой оптимизации. — «Авто- матика и вычисл. техн », 1972, № 4. 59. С т р о н г и н Р. Г. Информационный метод многоэкстремаль- ной минимизации при измерениях с помехами. — «Изв. АН СССР. Техн. кибернетика», 1969, № 6. 205 60. С т р о н г и и Р. Г. Алгоритмы для поиска абсолютного ми- нимума.—В кн.: Задачи статистической оптимизации. Под ред. Растригина Л. А. Рига, «Зинатне», 1971. 61.Батищев Д. И., Литвер А. В. Тестирование метода кусочно-линейной аппроксимации на одном классе многоэкстремаль- ных функций.—«Изв. вузов. Радиофизика», 1971, 1№ 3. 62. Б а т и щ е в Д. И. Тестовые функции для сравнения ме- тодов поиска экстремума функций многих переменных. — «Автомати- ка и вычпсл. техн.», 1968, № 1. 63.Хемминг Р. В. Численные методы для научных работ- ников и инженеров. Пер. с англ. М., «Наука», 1968. 64. Р а с т р и г и н Л. А. Стохастический синтез тестовых задач поисковой оптимизации. — «Автоматика и вычисл. техн.», 1968, № 2. 65. Р а с т р и г и н Л. А. Стохастическая модель объекта много- параметрической оптимизаци i. — В кн.: Методы статистической оптимизации. Под ред. Л. А. Растригина. Рига, «Зинатне», 1968. 66. С т р о н г и н Р. Г. Простой алгоритм поиска глобального экстремума функции нескольких переменных и его использование в задаче аппроксимации функций. — «Изв. вузов. Радиофизика», 1972, т. 15, № 7. 67. R о s e n J., Suzuki S. Constraction of nonlinear programming test problem. — «Communs. ACM», 1965, v. 8, № 2. 68. В о a s А. Н. Optimization techniques. — «AACE Bulletin», 1966, v. 8, №. 2. 69. Воробьев Н. Н. Числа Фибоначчи. М., «Наука», 1969. 70. Беллман Р., Дрейфус С. Прикладные задачи динами- ческого программирования. Пер. с англ. М., «Наука», 1965. 71. Пе р в оз в а иски и А. А. Поиск. М., «Наука», 1970. 72. Heymann M. Optimal simultaneous search for maximum by the principle of statictical information.—«Oper. Res.», 1968, v. 16, № 6. 73. Gal S. Sequential minimax search for maximum when prior information is available. — «SIAM J. Appl. Math.», 1971, v. 21, № 4. 74. Е м е л ь я н о в а Н. М. Оптимизация процессов поиска экстремума функций с использованием априорных данных. — «Авто- матика и телемеханика», 1967, № 5. 75. Ш е н н о н К. Работы -по теории информации и кибернети- ке. Пер. с англ. М., ИЛ, 1963. 76. Overholt К. An instability in the'Fibonacci and Golden section search methods.—«Scientific notes», 1970, v. 12, № 1. 77. Резникова Т. Л. Об одном алгоритме машинного поиска экстремума функции.—«Ж. вычисл. мат. и мат. физ.», 1965, т. 5, № 4. 78-Avriel М., W i 1 d е D. J. Optimal search for maximum with sequences of simultaneous function evaluations. — «Manag. Sci.», 1966, v. 12, № 9. 79. В earn е.г J. Н., W i 1 d е D. J. Minimax optimization of unimodal functions by variable block search.—«Manag. Sci.», 1970, 16, № 9. SO.Kacprzynski В. Sekwencyjna metoda poszukiwania eks- tremum.—«Arch. autom. i telemech.», 1966, v. 11, № 2. 81. Б е резин И. С., Жидков Н. П. Методы вычислений. ч. 1, М., Физматгиз, 1959. 82. А х и е з е р Н. И., Лекции по теории аппроксимации. М., «Наука», 1965. 206 83-Ланцош К. Практические методы прикладного анализ;!. М., Физматгиз, 1961. 84. Б а т и щ е в Д. И. Об одном методе поиска экстремума функций без вычисления производных.—В кн.: Прикладная матема- тика и кибернетика (избранные труды межвузовского симпозиума по прикладной математике и кибернетике), М., «Наука», 1973. 85. К у ш н е р X. Новый метод нахождения точки абсолютного максимума произвольной кривой с большим числом максимумов в присутствии помех. — «Техническая механика, сер. Д», 1964 т. 86 № 2. 86. К u s h n е г H. A versatile stochastic model of a function of unknown and time-varying form. — «J. Math. Anal. and AppL», 1962, v. 5, p. 150—167. 87. С т р о н г и н Р. Г. Информационно-статистическая теория поиска экстремума функций. — «Изв. вузов. Радиофизика», 1972, т. 15, № 7. 88. Н е и м а р к Ю. И., С т р о н г и н Р. Г. Информационный подход к задаче поиска экстремума функции.—«Изв. АН СССР. Техн. кибернетика», 1966, № I. 89. С т р о н г и н Р. Г. Выбор испытаний и условие остановки в одномерном глобальном поиске.—«Изв. вузов. Радиофизика», 1971, т. 14, № 3. 90. В а р ш а в с к и и В. И., В о р о н ц о в а И. П. О поведении стохастических автоматов с переменной структурой. — «Автоматика и телемеханика», 1963, т. 24, № 3. 91. Цетлин М. Л. Исследование по теории автоматов и мо- делированию биологических систем. М., «Наука», 1969. 92. S h а р i г о I., Narendra К. Use of stochastic automata for parameter selfoptimization with multimodal performance criteria.— «IEEE Trans.», 1969, v. SSC-5, № 4. 93. Me M u r t г у g G., F u K. A variable strukture automaton used as a multimodel searching technique.—«IEEE Trans.», 1966, у.АС-11,№3. 94-Jarvis R. Adaptive global search in a time-variant envi- ronmant using a probabilitic automaton.—«iproc. inst. radio and electr. engin. Australia», 1969, v. 30, № 7. 95. S p a n g H. A. A review of minimization technigues for non- linear functions. — «SIAM Rev.», 1962, v. 4, № 4. 96. Fl etcher R. Function minimization without evaluating de- rivatives—a review.—«Comput. J.», 1965, v. 8, IN» 1. 97. W о о d С. F. Review of design optimization techniques. — «IEEE Trans.», 1965, v. SSC-1, № 1. 98. Z о n t e n d i j k G. Nonlinear programming — a numerical survey. — «SIAM J. Contr.», 1966, v. 4, p. 194—210. 99. П о л я к Б. Т. Методы минимизации функции многих пе- ременных.—«Экономика и мат. методы», 1967, т. 3, № 6. 100. Beltrami E. J. A comparison of some recent iterative methods for the numerical solustion of nonlinear programs.—«Lect. Nobes. Oper. Res. and Math. Econ.», 1969, № 14, p. 20—29. 101. Powell M. J. A survey of numerical methods for uncon- strained optimization. — «SIAM Rev.», 1970, v. 12, IN» 1. 102. F 1 et с he г R\ P owel 1 M. J. A rapidly convergent des- cent method for minimization.—«Comput. J.», 1963, v. 7, № 2. 103. Моисеев Н. Н. Методы оптимизации. Задача отыскания экстремума функции многих переменных. ВЦ АН СССР, 1968. 207 104. Демидович Б. П, Марон И. А. Основы вычисли- тельной математики. М., Физматгиз, 1960. 105. Shanno D. E. Parameter selection for modified Newton methods for functions minimization.—«SIAM J. Numer. Anal.», 1970, v. 7, № 3. 106. M i e 1 е А., С a u t г е 11 J. W. Study on a memory gradient for minimization of functions.—«J. Opt. theory and appl.», 1969, v. 3, № 6. 107. С r a g g Е. Е., Levy A. V. Study on a supermemory gra- dient method for the minimization of functions. — «J. O'pt. theory and appl.», 1969, v. 4, № 3. lOS.Fletcher R., Reves С. Н. Function minimization by conjugate gradients.—«Comput. J.», 1964, v. 7, p. 149—154. 109. Поляк Б. Т. Метод сопряженных градиентов.—В кн.: Труды Второй зимней школы по математическому программирова- нию и смежным вопросам (24 января—6 февраля 1969 г., г. Дро- гобыч), вып. 1, М., ЦЭМИ АН СССР, 1969. 110. Sorenson Н. W. Comparison of some conjugate direction procedures for function minimization,—«J. Franklin Inst.», 1969, v. 288, № 6. 111. Поляк Б. Т. Метод сопряженных градиентов в задачах на экстремум. — «Ж. вычисл. мат. и мат. физ.», 1969, т. 9, № 4. 112. Данилин Ю. М., Пшеничный Б.Н.О методах ми- нимизации с ускоренной сходимостью. — «Ж. вычисл. мат. и мат. физ.», 1970, т. 10, № 6. 113. Broyden С. G. Quasi-Newton methods and their applica- tion to function minimization.—«Math. Comput.», 1967, v. 21, № 99. 114. P e a rso n J. D. Variable metric methods of minimization.-..- «Comput. J.», 1969, v. 12, № 2. 115. П ш ен ичн ы и Б. Н. Об одном алгоритме спуска.—«Ж. вычисл. мат. и мат. физ.», 1968, т. 8, № 3. 116. Qreenstade J. Variations of veriable—metric methods.— «Math. comput.», 1970, v. 24, № 109. 117.Myers G. E. Properties of the conjugate—gradient and Davidin methods.—«J. Opt. theory and appl.», 1968, v. 2, № 4. 118. Г о рви ц Г. Г., Ларичев О. И. О сравнении поисковых методов решения нелинейных задач идентификации. — «Автоматика и телемеханика», 1971, № 2. 119. С а n t г е 11 J. W. Relation between the memory gradient method and the Fletcher-Reeves methods. — «J. Opt. theory and appl.», 1969, v. 4, № 1. 120. P о w e 11 M. J. D. An efficient method for finiding the maxi- mum of a function of several variables without calculating derivati- ves. — «Comput. J.», 1964, v. 7, Ns 12. 121. Zangwill W. I. Minimizing a function without calcula- ting derivatives.—«Comput. J.», 1967, v. 10, № 3. 122. Данилин Ю. М., Пшеничный Б.Н. Метод миними- зации без вычисления производных. — «Ж. вычисл. мат. и мат. физ.», 1971, т. 11,№ 1. 123. Hooke R.,Jeever T. Direct searsh solution of numeri- cal and statistical problems.—«J. Ass. Comput. Math.», 1961, v. 8, № 1. 208 124. Rosenbrock Н. Н. Automatic method for finding the greatest or least value of a funcion. — «Comput. J.», 1960, v. 3. 125. Л ю с т е р н и к Л. А., Соболев В. И. Элементы функ- ционального анализа. М., «Наука», 1965. 126. Palmer J. R. An improwed procedure for orthogonalising the search vectors in Rosenbrock's and Swann's direct search opti- mization methods.—«Comput. J.», 1969, v. 12, IN'S 1. 127. Stewart G. W. A modification of Davidon's minimiza- tion methods to accept difference approcimations of derivatives. — «J. Assoc. Comput. Mach.», 1967, v. 14, № 1. 128. Shah В. V., В u e h 1 e r P. J., К e mp t h о r п е 0. Same algorithms for minimization a function of several variables. — «J. Soc. Indust. Appl. Math.», 1964, v. 12, № 1. 129. N е 1 d e r J. A., M e a d R. A simplex method for function minimization.—«Comput. J.», 1965, v. 7. 130. Ермуратский П. В. Модификации симплексного мето- да оптимизации. — В кн.: Труды Московского энергетического ин- ститута, вып. 68, 1970. 131. Метод оврагов в задачах рентгеноструктурного анализа. М., «Наука», 1966. Авт.: Гельфанд И. М., Вул Е. Б., Гинзбург С. А., Федоров Ю. Г. 132. Растригин Л. А. Статистические методы оценки гра- диента.—«Автоматика и вычисл. техника», 1970, № 4. 133. Ермольев Ю. М. О методе обобщенных стохастических градиентов и стохастических квазифейровских последовательно- стях.—«Кибернетика», 1969, № 2. 134. Николаев Е. Г. Метод случайного тп-градиента.— «Автоматика и вычисл. техника», 1969, 1№ 1. 135.Мытыаш И. Случайная оптимизация.—«Автоматика и телемеханика», 1965, т. 26, № 2. 136. Растригин Л. А. Случайный поиск в задачах оптими- зации многопараметрических систем. Рига, «Зинатне», 1965. 137. Растригин Л. А. Статистические методы поиска. М., «Наука», 1968. 138-Неймарк Ю. И., Григоренко В. П., Рапо- порт А. Н. Об оптимизации независимыми детерминированными и стохастическими автоматами.—В кн.: Ученые записки. Прикладная математика и кибернетика (материалы к Всесоюзному межвузовско- му симпозиуму по прикладной математике и кибернетике). Горький, ГГУ, 1967. 139. Григоренко В. П., Неймарк Ю. И., Рапо- порт А. Н. Оптимизация коллективом независимых автоматов и игры автоматов.—«Изв. вузов. Радиофизика», 1967, № 7. 140. Оптимизация коллективом независимых автоматов с адап- тацией.—В кн.: Задачи статистической оптимизации. Под ред. Л. А. Растригина. Рига, «Зинатне», 1971. Авт.: Григоренко В. П., Неймарк Ю. И., Рапопорт А. Н., Ронии Е. И. 141. Оптимизация коллективом независимых автоматов с адап- тацией.—В кн.: Адаптивные автоматические системы. Под ред. Г. А. Медведева. М., «Сов. радио», 1972. Авт.: Григоренко В. П., Неймарк Ю. И., Рапопорт А. Н., Ронин Е. И. 142. Случайный поиск (Теория и применение). Систематический указатель литературы. Под ред. Л. А. Растригина, Рига, «Зинатне», 1972, 209 143. Алгоритмы и программы случайного поиска. Под ред. Л. А. Растригина. Рига, «Зинатне», 1969. 144. Метод статистических испытаний. М., ФМ, 1962. Авт.: Бус- ленко Н. П., Голенко Д. П., Соболь И. М, Стра-ювич В. Г., Шрей- дер Ю. А. 145. Р а с т р и г и н Л. А. Некоторые статистические алгоритмы глобального поиска.—В кн.: Автоматика и вычислительная техника, № 10, Рига, «Зинатне», 1965. 146. Коротаева Л. Н., Панишев А. В. Программа на- хождения глобального экстремума функций многих переменных. — В кн.: Алгоритмы и программы случайного поиска. Под ред. Л. А. Растригина, Рига, «Зинатне», 1969. 147. Калинников Ю. С., Л и в ш и ц А. Л. О некоторых мо- дификациях алгоритма глобального статистического поиска по на- правляющей сфере.—В кн.: Задачи статистической оптимизации. Под ред. Растригина Л. А. Рига, «Зинатне», 1971. 148. Каган Б. М., Тер-Микаэлян Т. М. Решение инже- нерных задач на цифровых вычислительных машинах. М., «Энергия», 1964. 149. Моцкус И. Б. О некоторых асимптотических свойствах функций многих переменных.—В кн.: Автоматика и вычислительная техника. № 13, Рига, «Зинатне», 1966. 150. Моцкус И. Б. Об одной последовательной процедуре статистического решения задач.—В кн.: Автоматика и вычисли- тельная техника, № 10, Рига, «Зинатне», 1965. 151. Моцкус И. Б. Многоэкстремальные задачи в проектиро- вании. М., «Наука», 1967. 152. Юдин Д. Б. Методы количественного анализа сложных систем. — «Изв. АН СССР. Техн. кибернетика», 1965, № 1. 153. Антоне в Г. Е., Катковник В. Я. Фильтрация и сглаживание функций многих переменных для целей поиска глобаль- ного экстремума.—«Автоматика и вычисл. техника», 1970, № 4. 154. Захаров В. В. Метод интегрального сглаживания в мно- гоэкстремальных и стохастических задачах. — «Изв. АН СССР. Техн. кибернетика», 1970, № 4. 155. Чичинадзе В. К. Об одном способе использования случайного поиска для определения экстремума функций нескольких переменных.—«Изв. АН СССР. Техн. кибернетика», 1967, № 1. 156. Джибладзе Н.И.О нахождении координат экстремума функций многих переменных при использовании ^-преобразования.— «Сообщения Академии наук Грузинской ССР», 1970, т. 59, № 3. 157. Бочаров И. Н., Фельдбаум А. А. Автоматический оптимизатор для поиска наименьшего из нескольких минимумов. — «Автоматика и телемеханика», 1962, т. 22, № 3. 158. Г урин Л. С., Л оба ч В. П. Комбинация метода Монге- Карло с методом скорейшего спуска при решении некоторых экстре- мальных задач. — «Ж. вычисл. мат. и мат. физ.», 1962, т. 2, № 3. 159. Никитин А. И. Один алгоритм решения задач нелиней- ного программирования.—В кн.: Семинар Автоматизация производ- ственных процессов. Киев, ДНТП, 1963. 160. Хасьминский Р. 3. Применение случайного шума в за- дачах оптимизации и опознавания. — «Пробл. передачи информ.», 1965. т. 1, вып. 3. 161. Юдин Д. Б., Х а з е н Э. М. Некоторые математические т аспекты статистических методов поиски — В кн.: Автоматика и вы- числительная техника. Вып. 13, Рига, «Зинатне», 1966. 162. Пшеничный Б. Н., Марченко Д. И. Об одном под- ходе к нахождению глобального минимума.—В кн.: Семинар тео- рия оптимальных решений. Вып. 2, Киев, ИК АН УССР, 1967. 163. Данилин Ю. М., Пиявский С. А. Об одном алго- ритме отыскания абсолютного минимума.'—В кн.: Семинар теория оптимальных решений. Вып. 2, Киев, ИК АН УССР, 1967. 164. С 1 о u g h D. J. An asymptotic extreme-value sampling theo- ry for estimation of a global maximum.—«Can. Operat.», 1969, v. 7, № 2. 165. Леонов В. В. Метод покрытий для отыскания глобаль- ного 'минимума многих переменных.—В кн.: Иследования по кибер- нетике. Под ред. Ляпунова, М., «Сов. радио», 1970. 166. Половинкин А. И. Алгоритмы поиска глобального экстремума при проектировании инженерных конструкций. — «Авто- матика и вычисл. техника», 1970, № 2. 167. Евтушенко Ю. Г. Численный метод поиска глобаль- ного экстремума функций (перебор на неравномерной сетке).—«Ж. вычисл. мат. и мат. физ.», 1971, т. 11, № 6. 168. Мелешко В. И. Поиск глобального экстремума перерас- пределением плотности вероятности. — «Автоматика и телемеханика», 1971, № 5. 169. Методы оптимизации с приложением к механике космиче- ского полета. Под ред. Д. Лейтмана. Пер. с англ. М., «Наука», 1965. 170. Luenberger D. Convergence rate of a penalty-function scheme.—«J. Opt. Theory and Appl.», 1971, v. 7, № 1. 171. Ф и а к к о А., Мак-Кормик Г. Нелинейное програм- мирование. Методы последовательной безусловной оптимизации. Пер. с англ. М., «Мир», 1972. "172. К, о w a I i k J., 0 s b о r n e M., R у а п В. A new method for constrained Optimization problems.—«Oper. Res.», 1969, v. 17, № 6. 173. Не дли Д ж. Нелинейное и динамическое программиро- вание. Пер. с англ., М., «Мир», 1967. 174. Brown R. A generalised computer procedure for the design of optimum systems.—«Comm. and Electron.», 19R9, № 43. 175. Rosen J. В. The gradient projection method for nonlinear programming.—«J. Soc. Industr. Appl. Math.», 1960, v. 8, № 1. 176. Rosen J. В. The gradient projection method for nonlinear programming: Pt. II—Nonlinear constraints.—«J. Soc. Industr. Appl. Math.», 1961, v. 9, № 4. 177. Мозговая Э. А. Об одном методе поиска минимума при наличии ограничений.—«Автоматика и телемеханика», 1962, т. 23, № 12. 178-Miele A., Huang М. J., Н e i d e m a n J. Sequential gradient restoration algorithm for the minimization of constrained functions—ordinary and conjugate gradient versions. — «J. Opt. Theo- ry and Appl.», 1969, v. 4, № 4. 179. К ell у Н. J., Speyer J. L. Accelerated gradient pro- jection. — «Lect. Notes. Math.», 1970, v. 132, p. 151—158. ISO.Kelley J. The cutting-plane method for solving convex programms.—«J. Soc. Indust. Appl. Math.», 1960, v. 8, № 4. 211 181. Вольф Ф. Новые методы нелинейного программирова- ния.—3 кн.: Применение математики с экономических исследова- ниях. Т. 3, М., «Наука», 1935. 182. Ермольев Ю. М. Методы решения нелинейных экстре- мальных задач.—«Кибернетика», 1966, № 4. 183-Батищев Д. И. Математические методы оптимального расчета электронных схем. — «Изв. вузов. Радиоэлектроника», 1970, т. 13, № 6. 184.Veinott A. F. The supporting hyperplane method for unimodal programming.—«Oper. Res.», 1967, v. 15, p. 147—152. 185. Von P. Pfranger, Ein heurististisches Verfahren zur globalen Optimierung.—«Unternehmsforschung», 1967, v. 11, № 1. 186. К 1 e i b о h m K. Bemerkungen zum Problem der nichtkonve- xen programming.—«Unternehmsforschung», 1967, v. 11, № 1. 187. Оптимизация режимов обработки на металлорежущих стан- ках. М., «Машиностроение», 1972. Авт.: Гильман А. М., Брах- ман Л. А., Б а т и щ е в Д. И., Матяева Л. К. 188. Батищев Д. И., Белякова Л. Б., Найденко В. В. Определение оптимальных технологических параметров гидроцикло- нов на ЭЦВМ.—«Водоснабжение и санитарная техника», 1970, № 1. 189. Батищев Д. И., Б ел я к о в а Л. Б., Г ур ы ле в а И. Е. Поиск глобального решения в задачах раскроя.—В кн.: Математи- ческие методы исследования и оптимизации систем. Вып. 2, Киев, ИК АН УССР, 1970. 190. Батищев Д. И., Полозов В. С. Оптимизация раз- мерной сети при автоматическом нанесении размеров на чертежах с помощью ЭЦВМ.—В кн.: Вычислительная техника в машино- строении. Науч.-техн. сборник, Минск, ин-т техн. кибернетики АН БССР, 1970. 191. Система автоматической трассировки устройств радиотех- нического назначения. — В кн.: Автоматизация проектирования в электронике. Под ред. В. П. Сигорского. Вып. 7, Киев, «Техшка», 1973. Авт.: Батищев Д. И., Морозов В. Ф., Полозов В. С., Щер- баков В. В., Хохлов Ю. А. 192. Батищев Д. И. Применение методов нелинейного про- граммирования для определения оптимальных параметров электро- магнитных реле.—«Автоматика и телемеханика», 1965, т. 26, № 1. 193. Батищев Д. И. К вопросу о расчете электромагнитов оптимальных размеров. — «Электротехника», 1968, № 3. 104. Батищев Д. И. Оптимальное проектирование радиотех- нических цепей.—«Изв. вузов. Радиофизика», 1972, № 7. 195. Батищев Д. П., Терзян А. А. Синтез электротехни- ческих и электронных устройств методами поисковой оптимизации.— В кн.: Вопросы кибернетики (проблемы случайного поиска), М., Научный Совет по комплексной проблеме «Кибернетика» АН СССР, 1973. 196. Батищев Д.И.,Басалин П. Д. Автоматизированный расчет частотных характеристик пассивных четырехполюсников. — В кн.: Автоматизация проектирования в электронике. Под ред. В. П. Сигорского. Вып. 2, Киев, «Техшка», 1970. 197. Батищев Д. И., Басалин П. Д. САПФ—система автоматического проектирования фильтров-—В кн.: Сборник трудов Московского института электронного машиностроения (Автоматиза- 212 ция проектирования и производства ЭВМ). Под ред. П. П. Сыпчука. Вып. 16, ч. III, М., 1971. 198. Батищев Д. И„ Басалин П. Д. Проектирование ли- нейных RLC-и.еаеи на основе взаимодействия человек — машина. — «Изв. высш. учебных заведений. Радиоэлектроника», 1972, № 2. 199-Волгов В. Л. Детали и узлы радиоэлектронной аппа- ратуры. М., «Энергия», 1967. 200. Кала нта р о в П. Л., Цейтлин Л. А. Расчет индук- тивностей, М., «Энергия», 1970. 201. Басков Е. И., Лебедев А. Т. Оптимизация характе- ристик электрических фильтров на элементах с потерями — «Радио- техника», 1969, № 10. 202. Lasdon L.,Waren A. Optimal design of filters with bounded lossy elements. — «IEEE Trans.», 1966, v. CT-13, № 2. 203. Букреев И. H. Вопросы создания гибридно-пленочных интегральных узлов и блоков. — В кн.: Микроэлектроника. Под ред. Ф. В. Лукина. Вып. 1, М., «Сов. радио», 1967. 204. Шварц H. 3. Выравнивающие диссипативные цепи уси- лителей СВЧ.—«Радиотехника и электроника», 1971, т. 16, № 11. 205. Смагин А. Г., Ярославский М. И. Пьезоэлектриче- ство кварца и кварцевые резонаторы. М., «Энергия», 1970. 206. Великий Я. И., Г е л ь м о н т 3. Д., 3 е л я х Э. В. Пьезоэлектрические фильтры. М., «Связь», 1966. 207. Черне X. И. Индуктивные связи и трансформации в элек- трических фильтрах. М., «Связь», 1962. 208. Батищев Д.И.,Шевякова Т. К. Расчет оптимальных параметров реостатно-транзисторных логических схем. — «Изв. вузов. Радиофизика», 1968, № 3. 209. Степаненко И. П. Основы теории транзисторов и тран- зисторных схем. М., ГЭИ, 1963. 210. Батищев Д. И. Оценка работоспособности электронных схем в процессе проектирования. — «Изв. вузов. Радиоэлектроника», 1970, № 3. 211. Проектирование электронных схем с применением ЭВМ. М., Всесоюзный науч.-исслед. ин-т, стандартизации, 1971. Предметный указатель Автоматы 82, 125 Автоматная оптимизация: коллективом независимых стохастических автоматов 125, 131 с помощью автоматов Бу- ша — Мостеллера 84 с помощью автоматов, ис- пользующих информацию о средних значениях функции 86, 123 Аддитивная функция полезно- сти 21, 23, 25 Алгоритмы поисковой оптими- зации 34, 37, 49 квадратичная скорость схо- димости 92, 97, 101, 157 критерий эффективности 36, 49, 61 надежносгь 40, 74, 141 параметры 36, 73, 116 потери на поиск 38, 74, 116 Глобальная минимизация 118 Градиентный метод: наискорейшего спуска 90, 92 с памятью 93 213 С Неременной метрикой 97 Задача выпуклого программи- рования 19. 142. 172 — квадратичного программиро- — вания 16 — линейного программирова- ния 16, 162, 175 — многокритериальной оптими- зацией 19 — невыпуклого программиро- вания 19, 165 решение методом отсекаю- щей плоскости 165 путем построения выпуклой оболочки 170 — нелинейной оптимизации 15 — стохастического программи- рования 27 вероятностная 39, 199 с вероятностными ограниче- ниями 29, 194 усредненная 38 Класс тестовых задач: выпуклого программирова- ния 46, 142 многопараметричсских функ- ций «овражного» типа 43, 103, 115 многоэкстремальных кривых 41 многоэкстремальных функ- ций нескольких переменных 45, 119, 124 одномерных унимодальных функций 40 — — векторный 19, 40, 74 Метод Брауна 149 — вращающихся координат 104 — Гаусса — Зейделя 102 — Давидона — Флетчера — Па- уэлла 99 — модифицированный 108 — деления пополам 50 — золотого сечения 54 — интерполирующих полино- мов 67 — информационного поиска 79, 119, 123 — квадратичной интерполяции 66, 115 — комбинированный 112 — конфигураций 102 — кусочно-кубической аппро- ксимации 70 — кусочно-линейной аппрокси- мации 72 214 — Кушнера 75 — Ньютона 92 — — модифицированный 93 — отсекающей плоскости 161 — — модифицированный 167 — перераспределения случай- ных испытаний 134 — проектирования градиента 153, 155, 157 — равномерного дихотомиче- ского поиска 49 — сопряженных градиентов 97 — статистических испытаний 133 — случайного поиска с на- правляющим конусом 140 — — —, учитывающий кон- станту Липшица 56 — — —, учитывающий стати- стическую информацию о расположении минимума 60 — Фибоначчи 51, 74 — штрафных функций 142 ^-преобразований 136 Методы поиска: детерминированные 33 итерационные 34 квазиньютоновские 98 локальные 34 многошаговые 34 многопараметрические 33 нелокальные 34 одномерные 34, 48 одношаговые 34 пассивные 33 последовательные 33 Модель: детерминированная 10, 180, 184, 186, 190, 193 вероятностная 10, 20, 195 Непрерывное отображение многомерного параллелепи- педа на единичный отрезок 119 Неустойчивость методов одно- мерного поиска 63 Объединение векторных крите- риев 20, 23, 25, 73 соизмеримых 20 Область допустимых решений 14 Область решений, оптимальных по Парето 20 Преобразование линейных не- равенств 14 ОГЛАВЛЕНИЕ Предисловие ........•••• " Введение ............. 4 Глава 1 Математическая формулировка задач оптимального про- ектирования ............ 8 1.1. Математические модели проектируемых устройств ... 8 1.2. Формулировка ограничений, налагаемых на параметры и характеристики математической модели ..... 11 1.3. Постановка и классификация детерминированных задач оптимизации ............. 14 1.4. Векторные критерии оптимальности и методы их объеди- нения ............... I3 1.5. Учет случайных факторов в задачах оптимизации ... 27 Глава 2 Классификация поисковых методов оптимального проек- тирования и методология их сравнения ..... 32 2.1. Классификация методов решения детерминированных за- дач нелинейной оптимизации ........ 32 2.2. Наилучшие алгоритмы поисковой оптимизации и критерии их эффективности ........... 35 2.3. Об экспериментальном тестировании и сравнении алго- ритмов поисковой оптимизации ........ 37 Глава 3 Одномерная минимизация унимодальных функций . . 48 3.1. Поиск минимума унимодальных функций путем сокраще- ния интервала неопределенности ....... 48 3.2. Повышение эффективности поиска посредством учета дополнительной информации о свойствах унимодальных функций .............. 56 3.3. Совмещение методов сокращения интервала неопределен- ности с методами интерполяции ........ 63 Глава 4 Поиск глобального минимума произвольной кривой . 67 4.1. Методы поиска, основанные на построении аппрокси- мирующих моделей минимизируемой функции .... 67 4.2. Информационно-статистические алгоритмы поисковой опти- мизации .............. 75 4.3. Поиск глобального минимума кривой с помощью стоха- стических автоматов ........... 82 Глава 5 Поиск локального минимума многопараметрических функций .............. 90 5.1. Градиентные методы наискорейшего спуска .... 90 5.2. Минимизация функций без вычисления производных . . 101 5.3. Алгоритмы поисковой оптимизации, комбинирующие ло- кальные и нелокальные стратегии поиска . . . . 111 215 Глава 6 Многомерная минимизация многоэкстремальных функций 118 6.1. Сведение многомерных задач минимизации к задаче одно- мерного поиска ............ 118 6.2. Автоматная оптимизация .......... 123 6.3. Случайный поиск и его модификации ...... 133 \ Глава 7 I Минимизация многопараметрических функций при нали- чии нелинейных ограничений на параметры . . . . 142 7.1. Преобразование исходной задачи в последовательность за- дач оптимизации без ограничений ....... 142 7.2. Поиск условного минимума в экстремальных задачах с ограничениями типа равенств ........ 149 7.3. Сведение исходной задачи к совокупности задач линей- ного программирования .......... 161 ! 7.4. Некоторые подходы к решению задач невыпуклого про- • граммирования ............ 165 | Глава 8 Определение оптимальных^параметров радиотехнических цепей при помощи методов поисковой оптимизации 176 8.1. Проектирование пассивных RLC-u.eneu с оптимальными характеристиками ............ 176 8.2. Оптимизация параметров электрических фильтров с уче- том неоднородных потерь в элементах ...... 185 8.3. Расчет оптимальных параметров кварцевых фильтров по заданным частотным характеристикам ...... 188 8.4. Оптимальный расчет переключающих транзисторных мо- дулей ............... 194 8.5. Обеспечение максимальной работоспособности электрон- ных схем в процессе проектирования ..... 199 Список литературы ............ 203 Предметный указатель . . . . . . . . . . . . 213 Д.И.Батищев ПОИСКОВЫЕ МЕТОДЫ ОПТИМАЛЬНОГО ПРОЕКТИРОВАНИЯ Москва «Советское радио» 1975