Метод - штраф
Cтраница 3
Задача ( 2) является канонической задачей линейного программирования с неизвестными Хц. Если воспользоваться методом штрафа ( см. § 2.3), то с каждой искусственной переменной должна быть связана достаточно большая положительная оценка. В нашем случае поступим иначе. [31]
Для решения указанной системы можно использовать методы, описанные в главе III. В отличие от методов штрафов и метода уровней, где приходилось подбирать только один параметр, в данном случае подбирают п - р параметров по числу закрепленных на правом конце фазовых переменных. Вероятно такой подход целесообразно применять, когда число закрепленных переменных на правом конце мало. [32]
 |
Регулярное исправление ограничений задачи выпуклого программирования. [33] |
Теоремы о сходимости метода штрафов и оценках скорости сходимости наводят на мысль, что для получения приближенного решения исходной задачи (5.1) нужно лишь определить минимум на множестве Р функции Ф ( х, С), где С - достаточно большое число. [34]
Так как штрафная добавка обычно разрушает сепарабельность целевой функции, задача 1а не распадается в сумму блочных задач. Следовательно, для достижения декомиозиционности в схеме метода штрафов нужно организовать выполнение процедуры нижнего уровня, чтобы решение задачи 1а получалось в результате оптимизации отдельных блоков. [35]
Наряду с рассмотренными выше дискретными ( конечно-разностными) алгоритмами метода штрафов представляют интерес непрерывные алгоритмы, которые описываются системами дифференциальных уравнений. [36]
Предложен ряд методов решения поставленной задачи. Здесь изложены три часто употребляемых метода: метод Фельдбаума 20, метод штрафов 87 и метод проектирования вектора-градиента. [37]
Важным и полезным для исследования задач условной оптимизации является понятие о расширении экстремальной задачи. Оно позволяет подчеркнуть взаимосвязь таких различных подходов, как метод Лагранжа, метод штрафов, переход к оеред-ненной постановке и др. Основное внимание будет уделено изложению и пояснению методики перехода от условий задачи ( критерия оптимальности, связей и ограничений) к условиям, выделяющим оптимальные решения. Конструкции, которые будут приведены, позволяют провести такой переход по определенным правилам для произвольной задачи из очень широкого класса задач оптимизации. Важно и то обстоятельство, что изменения в постановке задачи легко учесть при составлении условий оптимальности решения. [38]
При втором подходе ( блок DII) задачу оптимизации с ограничениями посредством того или иного приема ( метод штрафов, метод неопределенных множителей Лагранжа) сводят к задачам безусловной оптимизации. [39]
Рассмотрим теперь метод решения оптимальной задачи с постоянной длиной интервала. Это решение осложнялось наличием фазового ограничения ( IV, 174), для учета которого использован описанный выше метод штрафов ( см. стр. [40]
Знак перед вторым слагаемым выбирается в зависимости от условий решаемой задачи: , если определяется минимум Q, и - при поиске максимума Q. Однако, как только изображающая точка оказывается за пределами области D, накладывается штраф ( отсюда и название - метод внешнего штрафа), который значительно ухудшает значение F ( х), что способствует возвращению изображающей точки в область допустимых значений параметров. [41]
Подход, использованный в задаче 4, является компромиссом между подходами, примененными в задачах 1 и 3, в нем сочетаются положительные стороны этих двух подходов, причем в некоторых случаях он может оказаться более эффективным. Действительно, пусть ограничения ( I, 10) присутствуют и задача оптимизации ХТС сводится к задаче 1, для решения которой используется метод штрафов. Тогда, если суммарная размерность этих векторов мала по сравнению с г, подход, использованный в задаче 4, может оказаться предпочтительным по сравнению с примененным в задаче 1, поскольку незначительно увеличивая размерность задачи, он делает расчет критерия безытерационным. Однако мы исходим из предположения, что выполняется следующее свойство: если минимизируется штрафная функция, то добавление в нее небольшого числа новых штрафных членов, связанных с ограничениями типа ( I, 56), ненамного ухудшает характеристики поиска. [42]
Метод штрафа обладает следующим недостатком. Оказывается, что при больших А структура линий уровня ФА, как правило, такова, что сходимость методов минимизации существенно замедляется. Искусство применения метода штрафа при решении конкретных задач состоит в удачном выборе функции ФА такой, что при заданной близости значений нижней грани А - А е замедление скорости сходимости применяемого итерационного метода будет минимальным. [43]
Функция штрафа добавляется к целевой функции, после чего решается параметрическое семейство получившихся задач без функциональных ограничений. В рамках соответствующих предположений последовательность решений этих задач при неограниченном возрастании штрафного параметра сходится к решению исходной задачи. В этом и состоит основная идея метода штрафов. [44]
С наблюдается эффект неустойчивости, связанный с плохой обусловленностью матриц, аппроксимирующих Ф хх. Таким образом, если минимизацию функции Ф ( ж, С) при большом С начать из точки х, которая не является достаточно близкой к точке минимума функции Ф на Р, то могут потребоваться слишком большие затраты времени ЭВМ и увеличиться вероятность прерывания процесса ввиду потери точности при вычислениях. По этой причине в практических алгоритмах метода штрафов используется идея постепенного увеличения параметра С вместе с постепенным увеличением точности решения вспомогательных задач. Ниже приводится простейший алгоритм, основанный на этой идее. [45]
Страницы: 1 2 3 4