Метод обобщенного градиента для решения негладких задач оптимизации. Одной из мощных тенденций в разработке методов решения задач оптимизации является стремление к возможно более простой (внешне) формулировке вычислительной задачи. В частности, все многообразие задач может быть приведено к простейшей форме [c.412]
Сначала приведем результаты решения этой задачи методом спуска по обобщенному градиенту. Следующая ниже таблица 1 [c.415]
Ш о р Н. 3., Ш а б а пг о в а1 Л. П. Отрешении минимаксных задач методом обобщенного градиента с растяжением пространства. — Кибернетика, 1972, 11, № 1. f [c.482]
Обобщенный градиент 413 Обратная задача 358 Общие краевые условия 65J Овраг 111, 406 Ограничения общего типа 28, 78, 112 [c.485]
В 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]
Метод сопряженных градиентов является итерационным методом нахождения минимума квадратичной формы. Характерная его особенность — конечность минимум достигается не более, чем за п шагов (тг-размерность пространства). Вычислительная схема метода сопряженных градиентов была обобщена на задачи нахождения минимума общих функций, не являющихся квадратичными. Опыт вычислений показал высокую эффективность метода, особенно в ситуациях, когда метод простого спуска по градиенту оказывался практически неработоспособным в силу крайне меД ленной сходимости. Ниже излагается вычислительная схема ме -тода в случае квадратичной функции, затем будет приведено его формальное обоснование. В заключение будет приведено обобщение вычислительной схемы в случае неквадратичной функции. [c.469]
Кроме того, различные формы алгоритма приводят к различным обобщениям его на задачи с произвольными, не квадратичными функциями. Эти обобщения, разумеется, уже не эквивалентны друг другу и с формальной точки зрения. Ниже мы приведем некоторые формы метода сопряженных градиентов и соответствующие их обобщения на задачи min / (x) с произвольной [c.474]
Другие формы метода сопряженных градиентов и их обобщения. ([62]). Алгоритм II. Рассмотрим задачу с квадратичной формой [c.475]
Отметим, что, в отличие от алгоритма I, в формулы алгоритма II явно входит и квадратичная форма G (в алгоритме I форма G использовалась лишь при вычислении градиента). Это обстоятельство сказывается при обобщении алгоритма на произвольную функцию / (х) при этом возникает необходимость заменить форму G другим подходящим объектом. Естественным аналогом G является матрица вторых производных / (х). [c.475]
Обобщение на случай k факторов делается механически — все эффекты независимы друг от друга. Важно, что существенно только соотношение произведений коэффициентов на соответствующие интервалы. Их абсолютные величины могут все одновременно умножаться или делиться на любое положительное число. При этом снова получаются точки, лежащие на градиенте, только с другим шагом. Шаги получаются, если к нулевому уровню последовательно алгебраически прибавлять строки из величин, пропорциональных составляющим градиента. Так как выбор длины шага произволен, то возникает вопрос, как его следует осуществлять. Здесь руководствуются следующим. Первый шаг, т. е. результат первого сложения полученной строки составляющих градиента с нулевым уровнем, должен давать точку, лежащую за экспериментальной областью хотя бы по одному их факторов. Однако этот шаг не должен быть столь большим, чтобы выйти за пределы области определения хотя бы одного из факторов. Если при выборе в этом диапазоне окажется, что для каких-либо факторов шаги различаются меньше, чем ошибки в установлении значений, то приходится изменять их через 2 — 3 шага. Для облегчения работы обычно шаги округляют. [c.235]
Выражение (4.24) - это не классический показатель Шарпа, потому что в числителе вычитается осредненная доходность по всему классу облигаций, а не доходность одних гособлигаций. Но смысл этого показателя очень значим он выражает экономическую эффективность инвестиций в обобщенный инвестиционный портфель из всех акций и всех облигаций в пределах данного экономического региона. Мы говорим, что по мере снижения экономической эффективности портфеля (преимущественно за счет падения доходности акций) доля акций в портфеле должна снижаться опережающими темпами. То есть условие сохранения оптимальности при движении справа налево по границе - это условие положительного градиента (при движении слева направо градиент может быть любым) [c.125]
Здесь я<°> — произвольный n-мерный вектор, принадлежащий множеству К — начальная точка процесса ps — величина шага на s-й итерации YS — нормирующий множитель gw — случайный вектор, условное математическое ожидание которого относительно х<-° х . . . , x(s> зависит линейно от обобщенного градиента срж (субградиента или опорного функционала) функции
Случайный вектор уп, удовлетворяющий условию (4.5), называется стохастическим квазиградиентом функции f(x) в точке хп. Если а 1, bn=szQ, то уп называется стохастическим обобщенным градиентом, а если f(x) непрерывно дифференцируема — стохастическим градиентом. [c.359]
Внутренность этого конуса К есть совокупность направлений убывания F. Для метода движения по О. Г. наиболее трудны ситуации, в которых конус К становится очень узким. Это происходит при малых значениях / в ситуации, близкой к оптимальной, а при больших значениях / и вдалеке от минимума. Кстати, необходимым признаком оптимальности является вырождение конуса К — его внутренность пуста. Нетрудно понять, что при этом совокупность векторов f x, i M] оказывается линейно зависимой. Как правило, это наступает в ситуации, когда число входящих в М индексов / сравнивается с разменростыо пространства х, хотя, в принципе, не исключена линейная зависимость векторов (Txi i iM и при 7, меньшем размерности х. Объяснение медленной сходимости метода О. Г. узостью конуса К послужило основой для одного из методов ускорения его сходимости. Этот метод, предложенный и разработанный Шором [83], основан на подходящем [преобразовании пространства х с тем, чтобы в новых переменных конус К стал шире. Это достигается операциями последовательного растяжения пространства х по направлениям последовательных О. Г. Суть дела поясняет рис. 75, на котором изображен (для 1=2) конус К до и после растяжения пространства в направлении g. Операция растяжения не вполне детерминирована — остается произвол в выборе коэффициента растяжения. Так или иначе, этот прием был отработан, усложнен растяжением в направлении разности двух последовательных градиентов, что в совокупности с некоторой техникой подбора шагов движения по О. Г. существенно повысило эффективность и надежность метода О. Г. Читатель может познакомиться с подробностями по работам [83], [84]. Здесь мы этих деталей не излагаем, поскольку автор не является сторонником подобных методов, полагая, что вычислительные методы, явно использующие достаточно полный анализ конуса К, должны быть более эффективными. Метод Ньютона как раз и основан на анализе конуса К. Для подтверждения этой точки зрения мы сейчас проведем сравнение решения некоторой модельной задачи методом обобщенного градиента с растяжением пространства и методом Ньютона. [c.414]
Как уже отмечалось, метод обобщенных стохастических градиентов не требует дифференцируемости целевой функции эквивалентной детерминированной задачи. Здесь мы рассмотрим возможный вариант применения метода возможных направлений к решению двух-этапной задачи линейного стохастического программирования. Использование и обоснование этого метода требует существования и непрерывности градиента целевой функции эквивалентной детерминированной задачи. В 4 гл. 6 указывалось, что для этого достаточно, чтобы вероятностная мера была абсолютно непрерывна относительно меры Лебега. Как и при изложении других методов, будем предполагать возможность вычисления всех математических ожиданий, значения которых используются в излагаемом ниже алгоритме. [c.189]
Искомыми переменными являются х, х, и /г, Tn /t. В [77] JV=12, и решение вариационной задачи свелось к дискретной задаче с 48 перемерными, с 24 условиями-равенствами (28) и 36-ю условиями-неравенствами (29). Это — изученная задача, для ее решения разработано большое число алгоритмов, включенных в систему математического обеспечения современных ЭВМ. Остается воспользоваться такой программой. Именно так и решается задача в [77], причем используется программа безусловной минимизации с помощью штрафных функций задача сводится к минимизации одной функции от 48 переменных. Минимум ищется каким-то вариантом спуска по градиенту (в других местах [77] упоминается обобщенный метод Ньютона, в котором используется матрица вторых производных минимизируемой функции). За 8 минут работы IBM-7094 было получено решение, представленное заимствованной из [77] (стр. 150) табл. 3. [c.310]
Опираясь на опыт работы разработанных в ЭНИНе программ, в качестве метода решения поставленной задачи был выбран обобщенный метод приведенного градиента (ОПТ). Метод ОПТ основан на процедуре неявного исключения переменных. Для того чтобы неравенства (1.5.3) привести к виду равенств, применяется подход, использующий дополнительные переменные С/ . Тогда ограничения (1.5.3) примут вид [c.49]