Численное решение задач метода наименьших квадратов - Лоуcон Ч.
Скачать (прямая ссылка):
Теорема 23.4. (условия Куна-Таккера для задачи НКН). Вектор х размерности п тогда и только тогда будет решением задачи НКН (23.1), когда найдутся m-вектор у и такое разбиение множества (1, 2,... ,т)на непересекающиеся подмножества & и S, что
GT у = Ет (Ех — /), (23.5)
/7 = 0, «€?, r,>0, ieS, ,*.^^oai.< (23-6)
у,>0, /€?, у, = 0, tes, *. (23.7)
где j , < , п i. у;
г = Gx-h. ¦ - " (23.8)
Эта теорема поддается следующей интерпретации. Пусть gf — i-я строка матрицы G. Ограничение gfx > л, определяет допустимое полупространство {х: gjx > я,} . Вектор gt ортогонален (нормален) к граничной гиперплоскости этого полупространства; он направлен в сторону допустимого полупространства. Точка х является внутренней для полупространств, индексированных множеством S (S от слова "slack" - нежесткий), и лежит на границе полупространств, индексированных множеством 8 ( & от слова "equality" - равенство).
Вектор p = ET(Ex—f) является градиентом для функционала <р(х) = = \\Ex-f И2/2 в точке х = х. Поскольку у{ = 0 для i ? &, то условие (23.5) можно переписать в виде
? УЛ-gd'-P- (23.9)
Смысл этого равенства такой: антиградиент <р в точке х можно представить неотрицательной (у, > 0) линейной комбинацией внешних нормалей (-?,) к тем граничным полуплоскостям, которые содержат х, i € 6. Геометрически зто означает, что антиградиент (-р) принадлежит выпуклому конусу с вершиной в точке х, порождаемому внешними нормалями (—jj,).
Всякое возмущение и вектора х, для которого вектор х + и остается допустимым, должно удовлетворять условиям uTgt >0 для всех /6 8. Умножая обе части (23.9) на такой вектор иги используя то, что .у, > 0, заключаем, что и удовлетворяет также и неравенству игр> 0. Из тождества ip(x + u) =ч)(х) +итр+ II Ей II2/2 следует, что никакое допустимое возмущение х не может уменьшить значение <р.
га
__________ —Г * ' '
ВеТЯСрТТили прогивоположный вектор — у), участвующий в формулировке теоремы Куна-Таккера, иногда называют двойственным вектором задачи. Обсуждение этой теоремы и ее доказательство можно найтн в литературе по условной оптимизации (см., например, книгу [Ю]).
i
§ 3. Задача NNLS
Задача NNLS определена в (23.2). Мы опишем сейчас алгоритм NNLS для ее решения. Будет доказана сходимость этого алгоритма в конечное число шагов.
Поначалу заданы m2 X «-матрица Е, целые числа т2 и и и ш2-вектор /. Векторы w и z длины п являются рабочими. В ходе выполнения алгоритма определяются индексные множества и 36 Переменные, индексированные множеством 26,имеют значение нуль. Переменные, индексированные множеством 9s, могут принимать ненулевые значения. Если значение такой переменной неположительно, то алгоритм либо изменит его на положительное, либо, установив нулевое значение, переместит индекс переменной из множества & в множество 36
По окончании работы алгоритма в массиве х будет решение, а в массиве w - двойственный вектор.
Алгоритм 23.10. NNLS (E,m2,n,f,x,w,z, ff>, %):
1. Положить Ф : = 0, 26:= {1,2.....п),х: = 0.
2. Вычислить и-вектор w. = ET(f — Ex).
3. Если множество 36 пусто или w,- <0длявсех/ ? S5, перейти К шагу 12.'
4. Найти индекс / € 26 такой, что wt = max {w(: / € 26 }. t
5. Переместить индекс t из множества 26 в множество 9* .
6. Пусть Е g) — m2 X л-матрица, определяемая таким образом:
(столбец/ матрицыЕ,если/ G ff> , <,
столбец / матрицы Е ¦= '
3> I 0, если/€ 26.
Вычислить и-вектор z как решение задачи наименьших квадратов ЕpZ as эе/. Заметим, что эта задача определяет только компоненты z/,/ ? 5*. Положить z,: = 0 для / € 26 .
7. Если zj >0 для всех / G 3* , положить х: =z и перейти к шагу 2.
8. Найти индекс q&S' такой, что
xql(x4 - z,) = min { Xjl(Xj - Zj): Zj<0, j&& }.
9. Положить a: = xq\(xq - z,).
10. Положитьx: = x + a(z - x).
11. Переместить из множества 3* в множество 26 все ШЦ0КСЫ / € & ,
для которых X/ = 0. Перейти к шагу 6. *
12. Комментарий. Вычисления закончены. • >. ¦• Полученный алгоритмом вектор х удовлетворяет оодщвлимям
х,>0, /6 &, (23.11)
*/ = 0, /6 26, н ' (23.12)
и является решением задай нааменышхквадратов ,(
E&x^f- . .. . (23.13)!
124
Двойственный вектор и> удовлетворяет соотношениям "7 = 0, (23.14)
w;<0, /636, 4 (23.15)
w=ET(f-Ex). (23.16)
Соотношения (23.11), (23.12), (23.14) - (23.16) - это условияКуна-
Таккера (см. теорему 23.4), характеризующие решение х задачи NNLS.
Соотношение (23.13) является следствием (23.12), (23.14) и (23.16). Обсуждению сходимости алгоритма NNLS предпошлем следующую
лемму.
Лемма 23.17. Пусть А - m X п-матрица ранга л, а Ь — m-вектор, для которого I
" О
АТЬ =
О со
п- 1
(23.18)
J > 1
5
со>0. ....... (23.19)
Если х - решение задачи Ах^Ъ, то его п-я компонент
х„ > 0. (23.20)
Доказательство. Пусть Q - ортогональная KrXwl HHtpima, аннулирующая поддиагональные элементы в первых л — 1 (ЛОяОвжхА, т.е.
1А:Ь \-\R 5 " ]>"-1 , _ 1.0 t v J } m - л + 1
(23.2Ц(
и 1 ¦--¦ — — 1- ,г .
л - 1 1 1 1 / Г ¦ . ?
