Численное решение задач метода наименьших квадратов - Лоуcон Ч.
Скачать (прямая ссылка):
Алгоритм 23.27. LDP (G, т, л, л, х,
1. Определим (л + 1) Хт-матрицу?'ил+ 1 -вектор /следующим образом:
Посредством алгоритма NNLS вычислить «i-вектор и, решающий задачу
§ 4. ЗАДАЧА LDP
л
NNLS:
Минимизировать И Ей — / I при условиии> 0.
2. Вычислить л + 1-вектор.*: = Ей-/. t
3. Если Иг И = 0, положить у: = FALSE и перейти к шагу 6.
4. Положить <р: =TRUE.
5. Для/: = 1,..., л вычислитьX/ : = -^//-,|+j.
6. Вычисления закончены.
Обоснование алгоритма LDP. Рассмотрим прежде всего задачу NNLS, решаемую на шаге 1 алгоритма LDP. Для целевой функции U?u -/12/2 значением градиента в точке и будет вектор
р = Етг. (23.28)
Согласно условиям Куна-Таккера (теорема 23.4), для этой задачи NNLS существуют непересекающиеся индексные множества & и S такие, что
SU 5={1,2,...,т), (23.29)
и, = о, /еа, и,>о, /е5, (23.зо)
Pi>o, /е&, р, = о, ies. ' . (23.31)
Используя соотношения (23.28)—(23.31), получаем
irV=rTr = rT[Eu-f) =prS-r„ + 1=-rn+I. (23.32)
Рассмотрим случай, когда на шаге 3 И г И > 0. Согласно (23.32), зто означает, что г„+1 < 0, поэтому деление на г„+1 на шаге 5 возможно. Используя (23.31), (23.32) и соотношения шагов 2 и 5, устанавливаем допустимость вектора V:
0<p = ETr=[G:h) •[_* j(-r(l+1)«(C5-*)lrl». (23.33)
Следовательно,
Gx>h. (23.34)
Из (23.31) и (23.33) вытекает, что строки системы (23.34), индексированные множеством 5. являются в действительности точными равенствами. Градиент для целевой функции llxll2/2 задачи LDP - это попросту вектор х. Условия Куна-Таккера, характеризующие вектор х, который минимизирует l.vB2/2 при условии Gx>h, требуют, чтобы градиент х был представим неотрицательной линейной комбинацией строк С, ассоциированных с равенствами в системе (23.34), т.е. строк G, индексированных множеством 5.
Согласно описанию шагов 2 и 5, используя (23.32), имеем
(-г^.Г1 =tvr/?(-rr, + 1r1 =сг2
Условия (23.30) для знаков компонент и, показывают, что х есть решение задачи LDP.
Очевидно, что это решение будет единственным. Действительно, если •V - другое решение, то Ixl = Ixil и вектор х = (х + х)/2 - допустимый вектор, длина которого строго меньше длины х. Это противоречит тому, что х — допустимый вектор с минимальной длиной.
Теперь рассмотрим случай, когда на шаге 3 II г II =0. Нужно показать, что система неравенств Gx > Л несовместна. Предположим противное.
128
т.е. что существует вектор х, для которого Gx> к.
q=Gx-h= [G:h]^ *J>0-
Тогда , .,. ^ ,
0=Fr:-l]r=[3rr.-l]| I " \u-f\~qTU + l.
(I
Это последнее выражение не может быть равно нулю, так как q > 0 и й>0. Из полученного противоречия заключаем, что условие I г Н = О влечет за собой несовместность системы Gx~>h. Это завершает математическое обоснование алгоритма LDP. к>
-•К' ..
§ 5. Преобразование задачи НКН в задачу LDP
Рассмотрим задачу НКН (23.1) с т2 Хи-матрицей ? ранга и. Различными способами (см. гл. 2—4) можно получить ортогональное разложение матрицы Е
= q\r\kt = [Q1. q, ]\r\kt. (23.35)
L о J г L о J
? =
Здесь Q - ортогональная тг X тг -матрица, К - ортогональная и X и-матри-ца и R - невырожденная л X л-матрица. Кроме того, матрицу R можно выбрать треугольной или диагональной.
Произведем ортогональную замену переменных
х = Ку. (23.36)
Целевую функцию, минимизируемую в задаче НКН, можно тогда записать в виде
И/-?х112 = HI „ |-| IIе 11Л -Ry^ +ИЛ И . (23-37) где
?< = Qff, /= 1,2. •'. " (23.38) После еще одной замены переменных
z=Ry-fi (23.39) мы можем написать ¦ ¦ ^ - -/¦; ' ¦>
*>(*) = II z II2 + ВДВ2. ''iV (23.40)
Таким образом, исходная задача минимизации И/-?хИ при условии
Gx> п эквивалентна, с точностью до аддитивной константы IIЛ В2 в целе-
9.Ч.Лоусон 129
вой функции, следующей задаче LDP: Мшизировать
I z И (23.41)
при условии GKR~lz > л — GKR~lft.
Если вычислить решение z этой задачи LDP, то решение х исходной задачи НКН можно получить с помощью соотношений (23.39) и (23.36). Квадрат нормы невязки для исходной задачи можно вычислить по формуле (23.40).
§ 6. Задача НКН с ограничениями-уравнениями
Рассмотрим задачу НКН (23.1), к которой добавлена система ограничений-уравнений Cm> xnx~d, где rank С=/и, < и и гапк[Сг : Ет] = л. Эти ограничения можно исключить с соответствующим сокращением числа независимых переменных. Для этой цели годятся методы гл. 20, 21.
Если использовать метод гл. 20, то выполняется ортогональная замена переменных
х = К
Уг.
}n-m,
(23.42)
где К - матрица, которая приводит С к треугольному виду:
"С с, 0 "
Е К = ?. Ёг
С. с, G2-
(23.43)
После этого из нижней треугольной системы c\yi = d определяется ylt а затемг как решение следующей задачи НКН: Минимизировать
li?iV2-(/-?iPi)l . (23.44)
при условии G2y2 > я - G,pi.
Как только из (23.44) определен вектор у2, по формуле (23.42) вы-
л
чиспяется решение х исходной задачи.
Если используется метод гл. 21, то по формулам (21.11) — (21.14) нужно вычислить величины G,, С\, C2,d, Elt Е2, f\ кроме того, из нижних треугольных систем определяют матрицу G t:
