Cтраница 2
Заметим, что в задачах безусловной минимизации любое направление является возможным, вследствие чего отыскание вектора sp сопряжено с меньшей затратой усилий по сравнению с аналогичной задачей в методе возможных направлений ( напр. [16]
Эти два примера показывают, что отображение М3 не обязательно должно быть замкнутым. Поэтому алгоритмическое отображение AM3D метода возможных направлений для задач с ограничениями не обязательно должно быть замкнутым, а это значит, что не могут быть применены теоремы сходимости А и В. [17]
Любопытно отметить, что методы возможных направлений, которые были предложены Зойтендейком [34] в 1959 г. и независимо от него Зуховицким и др. [ 39J в 1962 - 1963 гг., на несколько лет опередили появление модифицированного метода центров (2.27), а также приведенного ниже алгоритма ( предложенного Топкисом и Вейноттом [ Т1 ]), из которых они логически вытекают и в терминах которых они наиболее легко воспринимаются. [18]
Методы непосредственного решения задачи условной оптимизации, основанные на движении из одной допустимой точки, где выполнены все ограничения, к другой допустимой точке с лучшим значением целевой функции. Эти методы часто называются методами возможных направлений. [19]
Учет ограничений производится методами условной оптимизации, которые в отличие от методов безусловной оптимизации, предназначены специально для оптимизации при наличии ограничений. К методам условной оптимизации относятся методы возможных направлений, методы проекции градиентов и другие методы, более подробно рассмотренные в следующей главе. [20]
К сожалению, алгоритмическое отображение, которое вырабатывает xk l по заданному xh, необязательно должно быть замкнутым. Это отсутствие замкнутости вызывает серьезное затруднение в методах возможных направлений и может нарушать их сходимость. Когда происходит заклинивание, алгоритм вырабатывает последовательность точек xh f, которая сходится к точке, не являющейся решением задачи. Таким образом, алгоритм не сходится. После того, как мы обсудим различные способы, с помощью которых можно избежать заклинивания, будет доказана теорема сходимости, специально приспособленная к методам возможных направлений. [21]
В настоящее время для решения задачи (7.54) разработано и исследовано большое количество алгоритмов. К наиболее распространенным относятся различные варианты метода спуска, градиентные методы, методы возможных направлений, метод локальных вариаций и другие методы. [22]
Они позволяют построить методы вычисления апостериорных решающих распределений для стохастических задач достаточно общего вида. При заданном распределении ш решающие распределения могут быть построены с помощью методов, обобщающих методы возможных направлений. В случаях, когда можно наблюдать реализацию со, для построения апостериорных решающих распределений предлагаются итеративные вычислительные схемы, обобщающие методы стохастической аппроксимации. [23]
Таким образом, существенным недостатком классического вариационного исчисления является практическая невозможность учета в сложных задачах ограничений в форме неравенств. В современной математике разработан ряд методов учета таких ограничений - метод штрафных функций, методы возможных направлений ( проекционные методы), метод модифицированных множителей Лагранжа, принцип максимума Понтрягина. Первые два метода, используемые в данной работе, будут рассмотрены ниже более подробно. Авторы отмечают большую перспективность этого метода решения задачи. [24]
Следовательно, при решении вопроса, насколько конкретный алгоритм подходит для решения данной задачи, мы должны принимать во внимание не только скорость сходимости этого алгоритма, но также и степень обусловленности, вытекающую из природы рассматриваемой задачи. Вообще говоря, когда область поиска очень узка и имеет форму банана, алгоритмы, в которых поиск осуществляется вдоль направления градиента целевой функции, или методы возможных направлений первого порядка ( разд. Что же касается квазиньютоновских методов, методов сопряженных градиентов и методов возможных направлений второго порядка ( разд. Таким образом, если область поиска имеет неблагоприятную форму, мы предпочтем один из сверхлинейно сходящихся алгоритмов, если только время, требующееся на одну итерацию, не окажется очень большим. [25]
ППП системы САППОР использует различные методы оптимизации для решения задач нелинейного программирования. При этом физическая сущность объекта проектирования не имеет значения: важно, чтобы задача проектирования была бы сформулирована в терминах математического программирования. ППП системы ДИСО включает методы внешних и внутренних штрафных функций, методы возможных направлений Зойтендейка, методы Ньютона и другие для решения задач программирования. Таким образом, все указанные пакеты относятся к числу объектно-независимых. [26]
Методы, которые мы будем рассматривать, называются методами центров. Смысл этого термина станет ясен несколько-ниже. Эти методы были предложены Хьюардом [ Х4 ], [ Б7 ] 1), и они служат как бы переходным мостом между описанными в предыдущем разделе методами штрафных функций и методами возможных направлений, которые мы изложим в следующих разделах. Возвращаясь мысленно наза д, читатель найдет, что эти методы можно трактовать либо как не содержащие параметров барьерные методы, основанные на внутренних штрафных функциях, либо как не содержащие параметров методы возможных направлений. [27]
Методы, которые мы будем рассматривать, называются методами центров. Смысл этого термина станет ясен несколько-ниже. Эти методы были предложены Хьюардом [ Х4 ], [ Б7 ] 1), и они служат как бы переходным мостом между описанными в предыдущем разделе методами штрафных функций и методами возможных направлений, которые мы изложим в следующих разделах. Возвращаясь мысленно наза д, читатель найдет, что эти методы можно трактовать либо как не содержащие параметров барьерные методы, основанные на внутренних штрафных функциях, либо как не содержащие параметров методы возможных направлений. [28]
К сожалению, алгоритмическое отображение, которое вырабатывает xk l по заданному xh, необязательно должно быть замкнутым. Это отсутствие замкнутости вызывает серьезное затруднение в методах возможных направлений и может нарушать их сходимость. Когда происходит заклинивание, алгоритм вырабатывает последовательность точек xh f, которая сходится к точке, не являющейся решением задачи. Таким образом, алгоритм не сходится. После того, как мы обсудим различные способы, с помощью которых можно избежать заклинивания, будет доказана теорема сходимости, специально приспособленная к методам возможных направлений. [29]