2.2. Метод приведенного градиента
Зададимся вопросом: что, если забыть, что базис не ортонормальный, и при вычислении проекции антиградиента -g вместо р =-C(CTC)-1CTg брать просто p* = -CCTg? К чему приведет такая ошибка? Понятно, что р* вычислить просто. Не нужно даже вычислять произведение матриц ССТ, а просто сначала вычислить CTg, а потом умножить С на результат. Достаточно хранить только базисные векторы.
Но имеет ли смысл такое упрощение сложной формулы Для вычисления проекции р? При неортонормальном базисе это упрощение не будет давать проекцию. Это очевидно. Тем не менее рассмотрим какой вектор р мы получили бы.
Во-первых, это допустимое направление, так как вектор представлен в виде Су*, где у* =-CTg это вектор коэффициентов разложения р* по базисным векторам.
Во-вторых, и это самое интересное, р это подходящее направление, т.е. направление уменьшения целевой функции, так как скалярное произведение р на антиградиент положительно. Действительно,
Вектор CCTg, где g градиент, называется приведенный градиент, а р* можно было бы назвать приведенный антиградиент.
Важно отметить, что при таком построении дополнительных базисных векторов имеется возможность исключать не одно, а сразу несколько ограничений из активного набора. Если принять меры по предотвращению «зигзагов», это открывает возможность быстрее выйти на нужную грань, т.е. сформировать нужный набор активных ограничений, ускорить сходимость и сократить время счета.
Достарыңызбен бөлісу: |
