Cтраница 1
Одномерный поиск организуется для определения точки w, называемой оптимальной, которая максимизирует I / на интервале L. Для непрерывной функции общего вида эта задача достаточно трудоемка, и поэтому необходимы специальные методы, приспособленные к различным частным классам максимизируемых функций. Обычно задача требует исчерпывающего исследования всего интервала, но даже и при таком подходе могут встретиться трудности. [1]
Во многих алгоритмах безусловной минимизации одномерный поиск осуществляется на основе квадратичной или кубической аппроксимации целевой функции по выбранному направлению. Надеяться на то, что такая аппроксимация дает хорошую модель поведения барьерной функции с ее особенностью на границе допустимой области, бессмысленно; тут нужны иные модели. [2]
Причем это справедливо независимо от того, проводится одномерный поиск или нет. [3]
В точке ( - 1 825; 1 9) найден локальный минимум функции; одномерный поиск ( с 12 - й итерации) проводился методом золотого сечения. Описанный метод имеет высокую скорость сходимости при минимизации многоэкстремальных функций с крутыми оврагами. При минимизации многоэкстремальных функций желательно предварительно ознакомиться с организацией функций, что позволяет строить вычислительный процесс с глобальными свойствами, который не зацикливается в мелких впадинах и замедляет поиск лишь в глубоких минимумах. [4]
В зависимости от количества управляемых параметров целевой функции различают методы одномерного и многомерного поиска. Одномерный поиск может рассматриваться как самостоятельная задача, если аргументом целевой функции является один параметр. [5]
В соответствии с правилами матричного исчисления числители выражений для А ( А) и В ( представляют собой матрицы размерности NxN, a знаменатели являются скалярами. Определив новое направление поиска, проводят одномерный поиск и продолжают итерационный процесс. При выполнении описываемого алгоритма поиск после первой попытки ведется в тех направлениях, в которых целевая функция в ближайшей окрестности имеет значения, приближающиеся к оптимальному. Лишь в редких случаях эти направления совпадают с направлением градиента. Поэтому данный алгоритм часто называют методом отклоненного градиента. Указанное свойство метода Дэви-дона - Флетчера - Пауэлла позволяет обходить трудности, связанные с разрывами производных в пространстве проектирования. Широко распространено мнение, что этот метод является наиболее эффективным из всех градиентных методов. [6]
Заметим, что вычисление коэффициентов не требует знания матрицы Q в явном виде. Если матрица Гессе Q неизвестна, то одномерный поиск ( шаг 7) надо осуществить численно. Существует несколько других вариантов использования методов сопряженных направлений п сопряженных градиентов. [7]
Полный отказ от одномерного поиска может привести к тому, что итерационный процесс ( 11 262) с произвольным а - будет расходиться. Поэтому в рассмотренных ниже алгоритмах в той или иной форме присутствует одномерный поиск. [8]
Читатель может придумать различные способы улучшения приближений к х, получаемых этими грубыми методами. Во многих приложениях, однако, целесообразно принять подобную грубую оценку для х и затем вернуться к основному алгоритму, для которого одномерный поиск является подпрограммой. [9]
Ведь при всем различии в них явно просматривается одна общая черта: в каждой точке выбирается одно из подходящих направлений, составляющих острый угол с градиентом, а потом проводится одномерный поиск по выбранному направлению. На выбор подходящего направления тратятся значительные средства. [10]
Есть и еще одно разумное подсемейство: как и в градиентном наискорейшем спуске, выбрав направление, можно длину шага, параметр 9, подбирать, двигаясь вплоть до экстремума по выбранному направлению, а сам одномерный поиск экстремума производить разнообразными способами. [11]
В зависимости от количества управляемых параметров различают методы одномерного и многомерного поиска. Если, аргументом целевой функции является один управляемый параметр, поиск будет одномерным. Одномерный поиск используют также в задачах многопараметрической оптимизации для определения оптимального шага в выбранном напряжении. [12]
Как и любой градиентный алгоритм, метод обратного распространения застревает в локальных минимумах функции ошибки, т.к. градиент вблизи локального минимума стремится к нулю. Шаг в алгоритме обратного распространения выбирается неоптимально. Точный одномерный поиск дает более высокую скорость сходимости. [13]
Индекс k указывает на последовательность вычислений в процессе итераций. Новые направления называются сопряженными и соответствуют текущей локальной квадратичной аппроксимации функции. Затем по новому направлению проводят одномерный поиск и, найдя минимум, проверяют, достигнута ли требуемая степень сходимости. Если проверка показывает, что это так, то счет прекращается. В противном случае определяют новые сопряженные направления, k увеличивают на единицу и продолжают процесс до тех пор, пока не будет обеспечена сходимость или пока поиск не будет проведен по всем Ы направлениям. Закончив цикл поиска по N - - направлениям, начинают новый цикл, в котором опять используется направление наискорейшего спуска. Достоинство этого алгоритма состоит в том, что он позволяет использовать преимущества градиентных методов, проявляющиеся при исследовании целевой функции с разрывными производными. Так как N - - направлений поиска второй совокупности отличаются от направлений единичных векторов градиента, то поиск не зависает на изломе, а идет вдоль линии, соединяющей точки изломов линии уровня, которая, как правило, проходит через точку оптимума. Вообще можно утверждать, что методы, основанные на определении новых направлений поиска на основе накопленных данных о локальном поведении функции, по самой своей природе более эффективны, чем методы, в которых направление поиска задается заранее. Именно поэтому метод Флетчера - Ривса обладает большими преимуществами по сравнению с методами наискорейшего спуска или подъема. Его недостаток состоит в том, что, будучи сложнее указанных методов, он требует разработки более сложных программ. [14]
Но, может быть, здесь лучше ведут себя градиентные методы. Ведь в них заложено свойство выбора наилучшего направления. К сожалению, и здесь дело плохо. Во-первых, это направление лучше только локально, в малом. Направление по перпендикуляру к линии уровня, например из точки В на том же рис. 9.6, отнюдь не лучшее в большом. При наискорейшем спуске необходимо очень тщательно вести одномерный поиск по этому направлению, чтобы не прозевать дна оврага. Если же используется обычная градиентная схема с фиксированным коэффициентом пропорциональности, то этот коэффициент придется брать очень малым, иначе проскакивание неминуемо - шаг может вывести на противоположный склон в точку, расположенную еще выше исходной. [15]