Метод обобщенного градиента для решения негладких задач оптимизации. Одной из мощных тенденций в разработке методов решения задач оптимизации является стремление к возможно более простой (внешне) формулировке вычислительной задачи. В частности, все многообразие задач может быть приведено к простейшей форме [c.412]
Ш о р Н. 3., Ш а б а пг о в а1 Л. П. Отрешении минимаксных задач методом обобщенного градиента с растяжением пространства. — Кибернетика, 1972, 11, № 1. f [c.482]
В 1 исследуется метод обобщенных стохастических градиентов — итеративный метод, позволяющий по реализациям наборов случайных 180 [c.180]
Метод обобщенных стохастических градиентов [c.181]
Метод обобщенных стохастических градиентов, предложенный в работах [106 — 109], не предполагает дифференцируемости целевой функции задачи и не требует задания статистических характеристик случайных параметров условий задачи. Метод стохастических градиентов является общим методом стохастической аппроксимации (см. гл. 15). [c.181]
Применение метода обобщенных стохастических градиентов основано на следующих соображениях. [c.181]
Метод проекции градиента и скользящие режимы. Следует особо отметить те задачи, в которых конструкция (45) будет иметь значительное преимущество перед методом проекции градиента в форме (46), (43). Это — задачи, где оптимальная траектория содержит участок так называемого скользящего режима (см. 23). В этом случае могут существовать неоптимальные траектории, на которых конструкция (46) при не слишком больших s дает функцию u(t, s)=u (t) такая траектория оказывается тупиковой для методов (46), (43). В то же время конструкция (45) приводит к ненулевой вариации управления и (t, з)фи (t). Пример, рассмотренный в 23, показывает, что эта возможность действительно реализуется при численном решении подобных задач, причем множество тупиковых для локального варианта проекции градиента (46) траекторий достаточно мощно и содержит траектории, далекие от оптимальной. Тем не менее, в дальнейшем мы будем иметь дело именно с локальным вариантом. Это связано с тем, что среди известных автору прикладных задач, решавшихся приближенными методами, нет задач, содержащих скользящие режимы. Более того, в монографиях [39], 1102], посвященных преимущественно обобщению теории вариационных задач, охватывающему и скользящие режимы (что, разумеется, приводит к серьезному усложнению аналитического аппарата теории), подобных примеров тоже нет Речь, разумеется, идет о примерах задач, естественно возникших в приложениях, а не специально сконструированных с целью иллюстрации тех или иных возможных осложнений. С этой точки зрения те предостережения, которые делает инженерам и физикам автор [102] в связи с наивным использованием результатов классического вариационного исчисления, представляются преувеличенными. Разумеется, практика решения вариационных задач может расшириться, и задачи со скользящими. режимами станут обычным, инженерным явлением. В этом случае изменится и отношение к соответствующему разделу в теории, и в вычислительные методы будут внесены необходимые коррективы. [c.155]
Сначала приведем результаты решения этой задачи методом спуска по обобщенному градиенту. Следующая ниже таблица 1 [c.415]
Метод сопряженных градиентов является итерационным методом нахождения минимума квадратичной формы. Характерная его особенность — конечность минимум достигается не более, чем за п шагов (тг-размерность пространства). Вычислительная схема метода сопряженных градиентов была обобщена на задачи нахождения минимума общих функций, не являющихся квадратичными. Опыт вычислений показал высокую эффективность метода, особенно в ситуациях, когда метод простого спуска по градиенту оказывался практически неработоспособным в силу крайне меД ленной сходимости. Ниже излагается вычислительная схема ме -тода в случае квадратичной функции, затем будет приведено его формальное обоснование. В заключение будет приведено обобщение вычислительной схемы в случае неквадратичной функции. [c.469]
Кроме того, различные формы алгоритма приводят к различным обобщениям его на задачи с произвольными, не квадратичными функциями. Эти обобщения, разумеется, уже не эквивалентны друг другу и с формальной точки зрения. Ниже мы приведем некоторые формы метода сопряженных градиентов и соответствующие их обобщения на задачи min / (x) с произвольной [c.474]
Другие формы метода сопряженных градиентов и их обобщения. ([62]). Алгоритм II. Рассмотрим задачу с квадратичной формой [c.475]
Внутренность этого конуса К есть совокупность направлений убывания F. Для метода движения по О. Г. наиболее трудны ситуации, в которых конус К становится очень узким. Это происходит при малых значениях / в ситуации, близкой к оптимальной, а при больших значениях / и вдалеке от минимума. Кстати, необходимым признаком оптимальности является вырождение конуса К — его внутренность пуста. Нетрудно понять, что при этом совокупность векторов f x, i M] оказывается линейно зависимой. Как правило, это наступает в ситуации, когда число входящих в М индексов / сравнивается с разменростыо пространства х, хотя, в принципе, не исключена линейная зависимость векторов (Txi i iM и при 7, меньшем размерности х. Объяснение медленной сходимости метода О. Г. узостью конуса К послужило основой для одного из методов ускорения его сходимости. Этот метод, предложенный и разработанный Шором [83], основан на подходящем [преобразовании пространства х с тем, чтобы в новых переменных конус К стал шире. Это достигается операциями последовательного растяжения пространства х по направлениям последовательных О. Г. Суть дела поясняет рис. 75, на котором изображен (для 1=2) конус К до и после растяжения пространства в направлении g. Операция растяжения не вполне детерминирована — остается произвол в выборе коэффициента растяжения. Так или иначе, этот прием был отработан, усложнен растяжением в направлении разности двух последовательных градиентов, что в совокупности с некоторой техникой подбора шагов движения по О. Г. существенно повысило эффективность и надежность метода О. Г. Читатель может познакомиться с подробностями по работам [83], [84]. Здесь мы этих деталей не излагаем, поскольку автор не является сторонником подобных методов, полагая, что вычислительные методы, явно использующие достаточно полный анализ конуса К, должны быть более эффективными. Метод Ньютона как раз и основан на анализе конуса К. Для подтверждения этой точки зрения мы сейчас проведем сравнение решения некоторой модельной задачи методом обобщенного градиента с растяжением пространства и методом Ньютона. [c.414]
Как уже отмечалось, метод обобщенных стохастических градиентов не требует дифференцируемости целевой функции эквивалентной детерминированной задачи. Здесь мы рассмотрим возможный вариант применения метода возможных направлений к решению двух-этапной задачи линейного стохастического программирования. Использование и обоснование этого метода требует существования и непрерывности градиента целевой функции эквивалентной детерминированной задачи. В 4 гл. 6 указывалось, что для этого достаточно, чтобы вероятностная мера была абсолютно непрерывна относительно меры Лебега. Как и при изложении других методов, будем предполагать возможность вычисления всех математических ожиданий, значения которых используются в излагаемом ниже алгоритме. [c.189]
Опираясь на опыт работы разработанных в ЭНИНе программ, в качестве метода решения поставленной задачи был выбран обобщенный метод приведенного градиента (ОПТ). Метод ОПТ основан на процедуре неявного исключения переменных. Для того чтобы неравенства (1.5.3) привести к виду равенств, применяется подход, использующий дополнительные переменные С/ . Тогда ограничения (1.5.3) примут вид [c.49]
Искомыми переменными являются х, х, и /г, Tn /t. В [77] JV=12, и решение вариационной задачи свелось к дискретной задаче с 48 перемерными, с 24 условиями-равенствами (28) и 36-ю условиями-неравенствами (29). Это — изученная задача, для ее решения разработано большое число алгоритмов, включенных в систему математического обеспечения современных ЭВМ. Остается воспользоваться такой программой. Именно так и решается задача в [77], причем используется программа безусловной минимизации с помощью штрафных функций задача сводится к минимизации одной функции от 48 переменных. Минимум ищется каким-то вариантом спуска по градиенту (в других местах [77] упоминается обобщенный метод Ньютона, в котором используется матрица вторых производных минимизируемой функции). За 8 минут работы IBM-7094 было получено решение, представленное заимствованной из [77] (стр. 150) табл. 3. [c.310]