Способы постановки задач параметрической оптимизации

Классификация критериев оптимальности.

Основная проблема по­становки экстремальных задач — формулировка целевой функции. Казалось бы, здесь не следует ожидать трудностей, так как коли­чественное выражение качества проектируемого объекта уже имеет­ся — это вектор выходных параметров Y. Однако все выходные пара­метры являются функциями вектора внутренних параметров X и, следовательно, не могут изменяться независимо друг от друга. Среди выходных параметров всегда можно найти пары таких параметров, что улучшение одного из них приводит к ухудшению другого. Такие параметры называют конфликтными параметрам и.

Поэтому при оптимизации невозможно улучшение всех выходных
параметров одновременно.

Целевая функция должна быть одна и необходим переход от век
тора Y(X) к скалярной функции качества F(X). Такой переход называют свертыванием векторного критерия.

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

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

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

При формулировке комплексных критериев возникает задача пре-, образования выходных параметров в некоторые безразмерные вели­чины, сравнимые между собой. Такое преобразование, иначе нормирование, означает, что устанавливаются отношения важности вы­ходных параметров. Количественно важность выходного параметра у_j может оцениваться коэффициентом влияния у_j на целевую функцию F(X). Для установления относительной важности выходных параметров в комплексных критериях инженер, должен располагать какими-либо ориентирами. В задачах проектирования наилучшим, а, часто и единственно корректным, является выбор относительной важности параметров с точки зрения степени выполнения ТЗ. Ориентация на ТЗ при формулировке комплексного критерия — один из важных принципов оптимизации в задачах проектирования. Иногда используют иные принципы, такие, как ориентация на мнение экс­пертов. Применение этого принципа может быть оправдано только в условиях отсутствия достаточно четко сформулированного и полного ТЗ, т. е. в случаях, когда собственно задача оптимизации объ­екта и задача формулировки ТЗ почему-либо решаются совместно. Если оптимизация ведется без учета статистического разброса параметров, то соответствующий критерий оптимальности называют детерминиpованным критерием, если разброс пара метров учитывается, то имеем критерий статистический.

Статистические критерии оптимальности более полно отражают пред­ставления о качестве объектов проектирования, однако их использо­вание, как правило, ведет к заметному увеличению затрат машинно­го времени. Поэтому чаще используют детерминированные критерии. Рассмотрим наиболее часто встречающиеся на практике способы постановки задач оптимизации. Частные критерии. В большинстве частных критериев в качестве целевой функции принимают один из выходных параметров y_k(X), все остальные выходные параметры в виде соответствующих условий работоспособности относят к ограничениям. Тогда задача становится типичной задачей нелинейного программирования: max y_k (X), где ХР — область, задаваемая прямыми ограничениями на управляе­мые параметры и условиями работоспособности, которые могут иметь вид неравенств у_j< ТТ_j и равенств у _j — ТТ _j.

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

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

(14)

(15)

где у_i и у_ТТi — i -e ординаты соответственно реальной и заданной характеристик; р — количество узловых точек.

Параметр y_i можно рассматривать как i-й выходной параметр. И хотя в целевой функции F(X) учитывается несколько выходных параметров у_i критерии (14) и (15) максимальной близости ре­зальной и заданной характеристик остаются частными, так как усло­вия работоспособности всех остальных выходных параметров должны быть отнесены к ограничениям задачи. Учет других параметров в F(X) не может быть сделан столь же просто, как ординат характеристики, из-за Неодинаковой природы этих параметров.

Мультипликативные критерии. Разделим выходные параметры объекта на три группы по типу соответствующих им условий работо­способности. К первой группе отнесем параметры у _j⁺, имеющие условия работо­способности вида (16) у _j⁺>TT_j, т. е. параметры, для которых желательно максимальное увеличение. Вторую группу составят параметры у_j^- с условиями работоспособности вида

у_j^-<ТТ_i (17)

для них желательна минимизация.

Третья группа будет образована параметрами y_k⁼ с условиями ра­ботоспособности типа равенств

y_k⁼= TT_k±Δy_k, (18)

где Δy_k — максимально допустимое по ТЗ отклонение y_k⁼ от ТТ_k. Мультипликативные критерии могут применяться в случаях, ког­да в ТЗ отсутствуют условия работоспособности типа равенства и вы­ходные параметры не могут принимать нулевые значения. Тогда целевая функция, подлежащая максимизации, имеет вид

(19)

где в числителе перемножаются все выходные параметры с условиями работоспособности типа (16), а в знаменателе фигурируют все пара­метры с условиями работоспособности типа (17).

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

Аддитивные критерии. В аддитивных критериях целевая функция образуется путем сложения преобразованных выходных параметров. Преобразование параметров — переход к безразмерным слагаемым — необходимо и чаще всего осуществляется с помощью введения норми­рующих множителей — весовых коэффициентов. Минимизируемая це­левая функция может быть представлена в виде

(20)

При этом по-прежнему предполагается отсутствие выходных пара­метров с условиями работоспособности типа равенств. Для большей краткости записи. Преобразуем условия работоспособности типа (16) в условиях работоспособности типа (17), что потребует умножения у _j⁺ и соответствующих им технических требований ТТ_j на —1. Тог­да получим единую группу выходных параметров и (20) можно за­писать в виде

(21)

Целевая функция (21) имеет тот же существенный недостаток, что и целевая функция (19) в мультипликативном критерии, — неучет конкретных требований ТЗ в коэффициентах влияния у_j(Х) на F(X). Здесь абсолютные коэффициенты влияния

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

Аддитивные критерии успешно применяют в ситуациях, когда все или основные условия работоспособности имеют вид равенств (18). Тогда целевая функция формируется как сумма квадратов уклонений у _j от ТТ _j с весовыми коэффициентами w_j

(22)

и оптимизация сводится к ее минимизации.

Областью техники, где широко применяют целевые функции вида (22), является проектирование оптических систем.

Минимаксные (максиминные) критерии. Пусть условия работо­способности всех выходных параметров приведены к виду (17). Такое преобразование в отношении условий (6.16) было пояснено выше, а условия (18) преобразуются в (17) путем записи следую­щих неравенств:

Если обозначить y_k1 = —y_k, то вместо условия работоспособности
типа равенства одного параметра получаем два эквивалентных ему:
условия работоспособности типа неравенства для параметров y_k и
y_k1. Далее введем количественную оценку степени выполнения j-го
условия работоспособности и обозначим ee s_j. Цели расчета совпадают,
с целями увеличения s_j (причем в первую очередь тех из s_j которые
являются наименьшими).

Отсюда приходим к целевой функции вида (23)

S_j(X)=(TT_j - y_j)/ TT_j

где m — количество условий работоспособности после их приведения к виду (17). Функцию (23) называют функцией мини­мума, и поскольку требуется ее максимизация, т. е.

то критерий с целевой функцией (23) называется максиминным критерием. Если бы требовалось минимизировать функ­цию максимума, то получился бы минимаксный крите­рий.

В максиминном критерии нет того главного недостатка, который

был присущ мультипликативному и аддитивному критериям. Здесь влияние на целевую функцию оказывает только тот выходной пара­метр, который в данной точке X является наихудшим с позиций вы­полнения требований ТЗ. Это существенное преимущество максиминного критерия приводит в последнее время к его все более широкому распространению.

Функция минимума не является гладкой, и условия непрерывной дифференцируемости для нее не выполняются. В связи с этим для опти­мизации объектов по максиминному критерию применяют особые алгоритмы.

Рассмотрим используемые на практике представления оценок s_j(X)

Иногда предлагается

(24)

где учтено, что все условия работоспособности имеют вид (17).

Однако (24) неприемлемо, если какое-либо из ТТ _j равно нулю. Более объективно цели проектирования будут отражены, если принять

(25)

где δ _j — величина, характеризующая рассеяние j -го выходного пара­метра; у_jном — оценка его математического ожидания.

При определении δ _j с помощью статистического анализа критерий превращается в статистический. Но можно δ_j считать постоянными величинами и задавать как исходные данные на основе априорных представлений о рассеянии выходных параметров. Тогда максиминный критерий остается детерминированным, а δ_j играют роль весовых коэффициентов. Указание для δ_j физического смысла облегчает их правильный выбор по сравнению с выбором весовых коэффициентов w_j для аддитивных критериев.

Статистические критерии. Оптимизация при статистических кри­териях имеет целью получение максимальной вероятности Р выпол­нения условий работоспособности. Эту вероятность и принимают в ка­честве целевой функции. Тогда имеем задачу

(26)

Применение статистических критериев позволяет добиться наи­меньшего процента брака при серийном производстве спроектиро­ванных изделий, т. е. получить максимальную серийнопригодность. Если при расчетах целевой функции Р(Х) учитывать статистические сведения о X, включающие данные по старению параметров, то опти­мизация (26) является оптимизацией по критерию надежности. Эти обстоятельства — бесспорные преимущества статистических крите­риев. Главным недостатком статистических критериев является большая трудоемкость оптимизации, так как велики потери на поиск n₁ в (13).

Кроме целевой функции Р(Х) при статистической оптимизации может использоваться и целевая функция (23), как об этом уже сказано выше. Вдали от границ области работоспособности ХР функ­ция Р(Х) близка к нулю или единице и перестает быть чувствитель­ной к изменениям X. Поэтому при максиминном критерии поиск об­легчается.

Значения внешних параметров при оптимизации выбирают либо номинальными,либо исходя из принципа наихудшего случая. Боль­шую ценность представляют результаты расчета, полученные при оптимизации в тяжелых режимах, однако выполнение такой оптими­зации более сложно: во-первых, инженеру нужно определять значения внешних параметров для тяжелых режимов в исходной точке и быть уверенным в том, что эти значения остаются корректными и в про­цессе поиска; во-вторых, для разных выходных параметров тяжелые режимы обычно оказываются различными. Это требует решения урав­нений математической модели объекта для определения каждого вы­ходного параметра при новых значениях внешних параметров, что увеличивает затраты машинного времени.

ОБЩИЕ СВЕДЕНИЯ О МЕТОДАХ ПОИСКА

ЭКСТРЕМУМА

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

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

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

Подавляющее большинство методов оптимизации ориентировано на поиск локальных экстремумов. Глобальная оптимизация несрав­ненно сложнее. К глобальным методам относят один из самых простых по своему идейному содержанию методов — метод сканиро­вания. В этом методе вся допустимая область ХД пространства управляемых параметров разбивается на элементарные подобласти-ячейки и в центре каждой из ячеек осуществляется подсчет целевойфункции. Если ячейки достаточно малы, то получается общая кар тина поведения целевой функции в ХД с выявлением всех ее экстре­мумов. Однако метод сканирования практически неприменим в сколь­ко-нибудь сложных задачах из-за чрезмерно больших затрат машин­ного времени на решение. Здесь количество ячеек, а следовательно, и количество вариантов расчета целевой функции равно Кⁿ, где К — количество интервалов, на которые разбивается область ХД по каж­дой из координатных осей, a n — размерность пространства управляе­мых параметров.

На разработку методов глобальной оптимизации направлены уси­лия многих исследователей, однако имеющиеся к настоящему времени предложения как из-за повышенной трудоемкости, так и из-за недо­статочной надежности определения глобального экстремума еще не нашли широкого распространения. Поэтому, отмечая важность ре­шения задачи глобальной оптимизации, все же сосредоточим вни­мание только на методах локального поиска, как достаточно развитых и широко используемых. Дополнительным обо­снованием такой позиции является следующее рассуждение. Назовем областью притяжения экстремума Э геометриче­ское место точек таких, что их выбор в качестве исходных для поиска градиентным методом приводит к нахождению экстремума Э при достаточно малом шаге. Если область притяжения глобального экстремума имеет объем не менее нескольких процентов от объема всей области ХД, то существует большая вероятность определения гло­бального экстремума с помощью локальных методов. Для этого нуж­но несколько раз повторить локальный поиск со случайно выбираемыми исходными точками. Как видно из рис. 4, при поисковой оптимизации движение в пространстве параметров осуществляется шагами. От величины шага зависят многие параметры поиска, например потери на поиск, точность определения экстремума, надежность поиска. Существует большое количество различных способов выбора шага, но среди них особое место занимает способ выбора оптимального по величине шага h. В этом способе при минимизации F(X) после того, как выбрано направление очередного шага, осуществляется минимизация F(X) вдоль избранного направления и перемещение в точку такого минимума. Подобная минимизация выполняется методами одномерного поиска. Поэтому, хотя при проектировании практически не встречаются объекты с единственным управляемым параметром, методы одномерного поиска представляют для САПР интерес.

Методы оптимизации объектов с несколькими управляемыми пара­метрами называют методами многомерного поиска или методами многопараметрической оптимизации.

Способ выбора величины шага обычно не относят к процедурам, определяющим метод поиска. Сущность метода, в первую очередь, выражается в способе выбора направления очередного шага. Если при выборе направления используется информация о первых производных целевой функции по управляемым параметрам, то метод относится к группе методов первого порядка, если ис пользуется информация о вторых производных —к группе мето­дов второго порядка. Имеется также группа методов нулевого порядка — в них вообще производные не используются. С повышением порядка метода наблюдаются две тен­денции: с одной стороны, увеличиваются потери на поиск п2, с другой стороны, уменьшаются потери на поиск n₃, фигурирующие в (13). К сожалению, предсказать заранее для конкретного метода нели­нейного программирования величины потерь на поиск, точность нахождения экстремума, а иногда и сам факт сходимости к экстремуму невозможно, так как характер поиска зависит не только от метода, | но и от особенностей целевых функций. Несмотря на это, знание ме­тодов поиска и характерных особенностей соответствующих им тра­екторий в типовых ситуациях может существенно помочь инженеру в выборе конкретных программ оптимизации для решения задач в САПР.

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

Рассмотрение методов ведется при предположении, что управляе­мые параметры каким-либо образом пронормированы и потому яв­ляются безразмерными величинами, так же как и целевая функция.

Метод покоординатного спуска (метод Гаусса—Зейделя). Пусть решению подлежит задача минимизации функции F(X)

(27)

где ХП — n -мерное пространство.

В методе покоординатного спуска направление очередного шага выбирается вдоль какой-либо одной координатной оси, например оси параметра х₁. Движение в этом направлении производится в сто­рону, в которой наблюдается уменьшение F(X), и выполняется до тех пор, пока F(X) уменьшается. Далее движение начинается вдоль новой координатной оси, например параметра х₂, и т. д. После цикла спусков вдоль всех п осей производится новый цикл, если экстремум еще не найден. Когда ни по одной из осей невозможно перемещение с умень­шением функции F(X) с шагом h> h_min, поиск прекращается, и полу­ченная точка X признается за принадлежащую малой окрестности экстремальной точки X* (здесь h_min —задаваемое ограничение шага снизу).

Пример траектории покоординатного спуска в двумерной задаче показан на рис. 5, где линии равного уровня целевой функции F(X) соответствуют ее значениям, равным а₁ — а₄, причем a₁ < a₂ < C < а₃ < a₄. Из исходной точки Х₀ движение начато вдоль оси х₂. Пусть используется вариант мето­да с одномерной минимизацией F(X) на выбранных направлениях. Тогда после определения опти­мального шага произойдет переме­щение в точку X₁. Далее выпол­няется смена направлений движе­ния. На новом направлении вдоль оси х₁ шаг будет совершен в точ­ку Х₂ и т. д.

Рисунок 5. Иллюстрация поиска экстремума методом покоординатного спуска

Методы случайного поиска. Ме­тоды случайного поиска отличает от других рассматриваемых здесь методов та черта, что траектория случайного поиска не предопре­делена заданием всех необходимых исходных данных —вида целе­вой функции F(X), координат исходной точки, величины шага. Повторяя поиск при одинаковых исходных данных, будем получать разные траектории.

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

Случайный выбор направления движения из точки X_k выполня­ется с помощью уже рассмотренных выше алгоритмов выработки слу­чайных чисел. Если выработать n- значений равномерно распределенной в интервале [—1, +1] случайной величины, то можно рассматривать эти значения как элементы n-мерного случайного вектора, задающего направление в n-мерном пространстве. Проверка перспективности направления выполняется путем расчета и сопоставления значений целевой функции F(X) в двух точках, одной из них является точка X_k, другой — точка X_k+1, находящаяся на выбранном направлении и отстоящая от X_k на величину шага. Если F(X)< X_k+1, то новой отображающей точкой будет X_k+1, иначе попытка неудачна и остается отображающая точка X_k. Поиск обычно прекращают, если было выполнено подряд L неудачных попыток продвижения, где L относится к исходным данным.

Метод градиента. Известно, что вектор-градиента в каждой точке совпадает с направлением наибыстрейшего возрастания целевой функ­ции, т. е. локально наилучшим является градиентное направление при максимизации или антиградиентное направление при минимиза­ции. Это свойство градиента и используется в методе градиента. В соответствии с методом в каждой отображающей точке X_k рассчи­тывается градиент целевой функции:

Рисунок 6. Иллюстрация поиска экстремума методом градиента (а) и методом наискорейшего спуска (б).

и при решении задачи (6.27) шаг осуществляется в антиградиентном направлении в новую отображающую точку, имеющую координаты

где h —величина шага поиска.

Если F( X_k+1 )< F( X_k ), то вычисляется градиент grad F (X_k+1) уже в точке X_k+l и делается новый шаг той же величины h. Если F (X_k+1) > F( X_k ), то такая ситуация отождествляется с заметной кривизной линий равного уровня у функции F(X), что требует продолжения по­иска с уменьшенным шагом. Если шаг уменьшен до некоторого за­данного предела h _min, но по-прежнему F( X_k+1 ) ≥ F( X_k ), то считается, что точка X_k находится в h _min -окрестности экстремальной точки и принимается X*≈ Х_k.

На рис. 6 а) показана траектория поиска минимума некоторой функции, представленной своими линиями равного уровня и точкой минимума X*, с помощью градиентного метода. При использовании геометрических представлений полезно помнить, что градиентное направление является, нормальным к линиям (в общем случае к ги­перповерхностям) равного уровня. Именно это свойство градиента и определило вид траектории рис. 6 а).

Метод наискорейшего спуска. Этот метод можно считать разновид­ностью градиентного метода в условиях, когда величина шага h рас­считывается оптимальной с помощью одномерной минимизации це­левой функции вдоль градиентного направления. Иногда из алгоритмов наискорейшего спуска исключают процедуру одномерной минимизации и стратегия изменения величины шага h принимается такой же, как в основном градиентном методе. Тогда различие между методами градиента и наискорейшего спуска будет заключаться в том, что по-разному определяются направления движения. Если для оче­редной точки Х_k+1 выполняется условие F( X_k+1 )<F( X_k ), т. е. имеет место улучшение целевой функции, то наискорейший спуск требует продолжения движения в прежнем направлении без расчета grad F( X_k+1 ). Действия, предписываемые методами градиента и наискорейшего спуска, будут одинаковыми только в тех точках, в которых

F( X_k+1 )≥ F( X_k )

Траектория поиска минимума той же целевой функции F(X), что и на рис. 6 а), методом наискорейшего спуска показана на рис. 6 б).

Из сопоставления рис. 6 а) и 6 б) видно, что метод наискорей­шего спуска приводит к выполнению большего количества шагов, чем метод градиента, но в среднем один шаг при методе наискорей­шего спуска требует меньшего объема вычислений — анализ чувст­вительности для определения градиента выполняется реже.

(28)

Метод Ньютона. Метод Ньютона при оптимизации совпадает с одноименным методом решения систем алгебраических и трансцен­дентных уравнений. Это объясняется тем, что задача оптимизации при использовании необходимых условий экстремума

сводится к решению системы уравнений (28). Формула метода Ньютона, применительно к (28) имеет вид

где Ю_k —матрица Гессе целевой функции F (Х), вычисленная в точ­ке X_k.

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

Одномерный поиск. Определение оптимального шага означает по­иск минимума функции F (X) вдоль избранного направления g, т. е.

где Х_k —текущая отображающая точка.

Например, в методе наискорейшего спуска g есть антиградиент­ное направление.

Из методов одномерной оптимизации наиболее часто используют метод полиномиальной аппроксимации и ме­тод Фибоначчи.

В методе полиномиальной аппроксимации сначала отыскивается интервал изменения h, на котором должна находиться оптимальная точка h*. Простейший способ определения такого интервала заклю­чается в последовательном вычислении значений

(29)

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

f (h) = а₀ + a₁h + a₂h² (30)

и задача отыскания h* преобразуется в задачу минимизации поли­нома (30).

В результате получается оценка/г*, равная h* = — а_х/(2а₂). Если
окажется, что f(h*) превышает какое-либо из трех вычисленных на ин­тервале значений функции, то оценка h * неудовлетворительна и следу­ет уменьшить интервал, на котором ищется минимум. Обычно одна из
трех точек отождествляется с исходной точкой (при h= 0), поэтому
минимальное количество вычислений целевой функции при одномерном поиске равно трем. Однако это будет только при удачном выборе
значения h₁ в последовательности (29) и при получении оценки h *
без необходимости ее уточнения. Следовательно, одномерный поиск,
как правило, требует более чем трехкратного вычисления целевой
функции.

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

Идея метода штрафных функций заключается в замене исходной
целевой функции F(X) на функцию Ф (Х), которая должна быть мак­симально близкой к функции F( X ) в области работоспособности ХР
(при выполнении всех ограничений) и быть существенно больше, чем
функция F( X ), вне области ХР. Другими словами, нарушение ограничений можно рассматривать как наложение штрафа в виде ухуд­шения новой целевой функции Ф (Х).

Обычно функция Ф (Х) образуется суммированием исходной це­левой функции F( X ) и функции штрафа θ_k(X):

где в качестве θ_k(X) часто выбирается следующая функция:

где r_k> 0.

Величина штрафа θ_k(X) зависит от коэффициента r_k: чем больше r_k, тем больше штраф, тем ближе должны находиться условный ми­нимум F( X ) и безусловный минимум Ф (Х); при r_k ™¥ эти минимумы становятся неразличимыми. Здесь следует отметить, что если услов­ный минимум функции F(X) лежит внутри области ХР, то он одно­временно является и безусловным, так как для X Î ХР всегда max {0, j_i(Х)} = 0. Тогда минимум функции F(X) мог быть найден и без введения штрафа. Если же условный минимум функции F(X) ле­жит на границе области ХР, то минимумы функций F( X ) и Ф (Х), как правило, не совпадают и для их сближения нужно увеличивать r_k. Однако чем больше r_k, тем ближе должна быть выбрана исходная точка поиска к экстремальной точке, иначе могут возникнуть неприят­ности типа переполнения разрядной сетки ЭВМ.

Дата добавления: 2014-01-07