Cтраница 2
Имеющийся опыт применения метода покоординатного спуска показывает, что по условию сходимости он при малом числе переменных может дать лучшие результаты, чем градиентный метод. Однако при решении задач с большим числом переменных и сложной системой ограничений метод покоординатного спуска существенно уступает градиентному методу. [16]
В направлении каждой оси определяется локальный оптимум, координаты которого являются исходными для следующего цикла поиска. Число необходимых циклов зависит, в частности, от удачного выбора первого направления спуска. Этот метод наиболее эффективен при поиске экстремума по дискретным переменным. При большом числе переменных метод покоординатного спуска может привести к очеиь большому времени счета. В этом отношении более эффективными являются методы градиентного и наискорейшего спуска. [17]
Выберем каким-либо способом начальную точку, вычислим в ней градиент рассматриваемой функции и сделаем небольшой шаг в обратном, антиградиентном направлении. В новой точке повторим процедуру: снова вычислим градиент функции и сделаем шаг в обратном направлении. Специальный выбор направления движения на каждом шаге позволяет надеяться на то, что в данном случае приближение к наименьшему значению функции будет более быстрым, чем в методе покоординатного спуска. [18]
Поясним смысл такого управления. Временное исключение переменных имеет следующую цель: пусть переменная sn вышла на s; можно предположить, что и в дальнейшем в целях минимизации x e эту переменную следует увеличить, но это уже неосуществимо. Но этот вывод нестрог, так как после выхода sn на s точка х за счет изменения других sn изменилась и, может быть, нужно менять sn в другую сторону. Поэтому различаются два случая ( с и d) при % 20: если в цикле 2 не было случаев выхода на границу, но часть переменных была исключена ( Sxl), то следует снова включить все sn в работу. Если же 0 при 0, то это означает, что в решении задачи ( 10) ограничения s -, s перестали играть роль ( тоже, может быть, лишь временно) и задача ( 10) стала задачей минимизации без ограничений. В этой ситуации метод покоординатного спуска становится неэффективным, и целесообразно перейти к методу сопряженных градиентов. Если анализ показывает необходимость более точного решения задачи ( 10), это делается следующим образом. [19]
На вопрос, какому из способов выбора направления спуска следует отдать предпочтение при решении конкретной задачи, однозначного ответа нет, если только она не является хорошо известной тестовой задачей. Предположим, что мы обладаем определенной информацией о виде минимизируемой функции; скажем, нам известно, что эта функция выпуклая и достаточно гладкая. Но и в этом случае ответ на поставленный вопрос весьма затруднителен. Дело в том, что у многих методов спуска априорные оценки скорости сходимости имеют вид р ( хш) - р х О ( 1 / т), вследствие чего эти оценки не позволяют отдать предпочтение тому или иному методу. Именно на этом этапе приобретает важное значение накопленный опыт. Так, на начальной стадии минимизации отдают предпочтение методам, связанным с незначительными затратами усилий на вычисления направлений спуска, например методам покоординатного спуска. Когда процесс минимизации р ( х) существенно замедляется, переходят к методам, связанным с вычислениями градиента, - к так называемым методам градиентного спуска. [20]