Cтраница 2
Кидаясь в другую крайность, следовало бы каждый раз перед выбором направления спуска вычислять оценки множителей Лагранжа и тут же выводить из базиса все ограничения, для которых значения Xj окажутся отрицательными. Однако, поскольку в такой схеме равенство gA ( x) 0 соблюдаться не будет, упомянутые оценки могут оказаться слишком неточными ( см. следствия теоремы 2.3); вполне реальна ситуация, когда какое-нибудь ограничение будет то выходить из базиса, то появляться в нем снова, а в результате - крайне медленное продвижение к решению. Короче говоря, нельзя доказать, что такая стратегия позволит найти локальный минимум общей задачи, сменив базис конечное число раз. Здесь возможно зигзагообразное движение, пример которого рассмотрен в гл. [16]
В [43] учет условия нормировки ( 5.46 а) при решении задачи выбора направления спуска приводит к задаче линейного программирования. [17]
Как мы видели, в задачах минимизации с ограничениями-собственно задачах математического программирования - задача выбора направления спуска обладает в общем случае задания множества X большой трудоемкостью, которая зачастую делает изложенные методы минимизации малоэффективными. [18]
Так, в одном из вариантов метода возможных направлений для численного решения задач нелинейного программирования проблему выбора направления спуска на каждой итерации сводят к решению задачи К. [19]
Релаксационные методы решения задач мате магического программирования ( экстремальных задач с ограничениями) отличаются тем, что при выборе направления спуска учитывается, что оно должно быть возможным, в том смысле, что очередная точка хь ь вычисляемая в ходе реализации релаксационного процесса, должна принадлежать допустимой области О. [20]
Далее, коль скоро матрица Т плохо обусловлена, таковой может оказаться и Z, что отрицательно повлияет на выбор направлений спуска. Ньютоновская схема их расчета предполагает модификацию спроектированной матрицы Гессе Од если она плохо обусловлена. [21]
На практике метод случайного покоординатного спуска применяется в совокупности с некоторыми эвристическими приемами с целью ускорения процесса минимизации. Так, при выборе направления спуска исключают из рассмотрения неперспективные направления, например, при выборе номера j ( k) направление - s /, - s /, i себя уже исчерпало на предыдущем шаге. [22]
Метод возможных направлений основан на том, что среди всех возможных направлений в точке х 01 выбирается направление наибольшего убывания функции / ( х) и делается спуск вдоль этого направления в точку х ( 1), затем, исходя Из точки х 11, процесс повторяется. При этом приходится решать задачу выбора направления спуска и задачу выбора шага по этому направлению. [23]
Помимо трудностей реализации метода Ньютона, связанных с неопределенностью матрицы вторых производных, существуют еще и неприятности, возникающие при появлении у минимизируемой функции седловой точки, градиент в которой равен нулю и угодив в которую метод Ньютона ( равно как и любая из перечисленных выше модификаций) не сможет сдвинуться с места. Здесь нужен иной подход к выбору направления спуска. [24]
В заключение отметим, что линейная тактика используется и в методе наискорейшего спуска. Разница между случайным поиском с линейной тактикой и алгоритмом наискорейшего спуска заключается лишь в выборе направления спуска. В первом случае это направление является случайным, а во втором - антиградиентным. [25]
Если такой точности достаточно, можно дальше не считать. Если нет - нужно взять новый параметр точности elt меньший чем е0, и при выборе направления спуска из точки xl xo - - aopo руководствоваться им. [26]
Если для некоторого метода существуют априорные оценки, устанавливающие порядок скорости сходимости, например, сравнивающие величину отклонения m - го приближения от точного решения с величиной О ( 1 / та) ( здесь число а определяет порядок сходимости), то метод назовем устойчивым по отношению к выбору направления спуска и величины шага в том случае, если метод допускает приближенное определение этих параметров, не меняющее порядка сходимости. Если установлен факт сходимости метода, но оценки скорости отсутствуют, устойчивым по отношению к выбору направления спуска и величины шага будем называть метод, допускающий приближенное определение этих параметров, не нарушающее сходимости процесса минимизации. Из дальнейшего будет ясно, что методы скорейшего спуска, проекции градиента, условного градиента, возможных направлений являются устойчивыми. [27]
В задачах с ограничениями при выборе направления спуска приходится учитывать два обстоятельства: направление должно быть возможным и должно гарантировать убывание минимизируемой функции. При этом выбор направления спуска связан с вычислением величины р ( х), а в ряде методов и величин / г ( х), и с решением на каждом шаге некоторой экстремальной задачи. Последнее обстоятельство приводит к тому, что метод условного градиента применяют лишь для множеств, задаваемых линейными ограничениями, поскольку в этих случаях для выбора направления спуска достаточно решить задачу линейного программирования, а метод проекции градиента применяют для множеств X такого вида, что задача отыскания проекции некоторой точки на это множество является достаточно простой с точки зрения ее численной реализации, так как решение этой задачи и определяет направление спуска. [28]
Если для некоторого метода существуют априорные оценки, устанавливающие порядок скорости сходимости, например, сравнивающие величину отклонения m - го приближения от точного решения с величиной О ( 1 / та) ( здесь число а определяет порядок сходимости), то метод назовем устойчивым по отношению к выбору направления спуска и величины шага в том случае, если метод допускает приближенное определение этих параметров, не меняющее порядка сходимости. Если установлен факт сходимости метода, но оценки скорости отсутствуют, устойчивым по отношению к выбору направления спуска и величины шага будем называть метод, допускающий приближенное определение этих параметров, не нарушающее сходимости процесса минимизации. Из дальнейшего будет ясно, что методы скорейшего спуска, проекции градиента, условного градиента, возможных направлений являются устойчивыми. [29]
В задачах с ограничениями при выборе направления спуска приходится учитывать два обстоятельства: направление должно быть возможным и должно гарантировать убывание минимизируемой функции. При этом выбор направления спуска связан с вычислением величины р ( х), а в ряде методов и величин / г ( х), и с решением на каждом шаге некоторой экстремальной задачи. Последнее обстоятельство приводит к тому, что метод условного градиента применяют лишь для множеств, задаваемых линейными ограничениями, поскольку в этих случаях для выбора направления спуска достаточно решить задачу линейного программирования, а метод проекции градиента применяют для множеств X такого вида, что задача отыскания проекции некоторой точки на это множество является достаточно простой с точки зрения ее численной реализации, так как решение этой задачи и определяет направление спуска. [30]