Квадратичное программирование и лассо

11

Я пытаюсь выполнить регрессию лассо, которая имеет следующую форму:

Минимизируйте вw(YXw)(YXw)+λ|w|1

Учитывая , мне посоветовали найти оптимальное с помощью квадратичного программирования, которое принимает следующую форму:λw

Минимизируйте в , в зависимости отx12xQx+cxAxb.

Теперь я понимаю, что термин должен быть преобразован в термин ограничения , что довольно просто. Однако я почему-то просто не понимаю, как я мог бы перевести первый член первого уравнения в первый член второго. Я не мог найти много об этом в сети, поэтому я решил спросить здесь.λAxb

spurra
источник

Ответы:

10

Помня, что мы работаем с переменной в качестве переменной в стандартной форме, разверните и соберите термины в и в и , и константы.x ( Y - X w ) ( Y - X w ) w wx(YXw)(YXw)w ww[something]www

Объясните, почему вы можете игнорировать константы.

Объясните, почему вы можете объединить термины и . www


Поскольку BananaCode к настоящему моменту определился с некоторым опережением по пути, вы можете написать и или, проще, вы можете просто написать и (поскольку и имеют одинаковый аргумент argmin для любого ).c = - 2 X Y Q = X X c = - X Y f ( x ) k f ( x ) k > 0Q=2XXc=2XY Q=XXc=XYf(x)kf(x)k>0

Glen_b - Восстановить Монику
источник
Константы можно игнорировать, потому что если x_ является минимумом f (x), то x_ + c является минимумом f (x) + c, поэтому мы можем игнорировать константу c. Я отредактирую свой вопрос, чтобы показать, где я застрял.
Спурра
BananaCode у вашего объяснения есть несколько недостатков. Если под «это минимум для » вы подразумеваете «аргумент, при котором минимизируется», вы говорите что-то вроде « - это of ». Но ваш вывод там неверный. Если вы добавите к , вы не добавите к argmin. f ( x ) x аргмин f c f cf(x)f(x)xargminfcfc
Glen_b
Видите, где я написал в моем ответе? Что - то теперь у вас есть между а в нижней части вашего вопроса ?? w ww[something]www
Glen_b
Да, я имел в виду является из . Не могли бы вы привести пример, где мой вывод неверен? является матрицы Я пытаюсь сформировать. Если я расширяю я получаю . Первая часть будет представлять форму матрицы , однако я не могу избавиться от второго члена . г г м I п F [ s O м е т ч я н г ] В ш ' ( Х ' Х ш - Х ' У ) ш ' X ' X ш - ш ' X ' Y Q - ш ' X Yxargminf[something]Qw(XXwXY)wXXwwXYQwXY
Спурра
1
@ AD.Net Ограничения в основном рассматриваются в другом ответе.
Glen_b
11

Я хотел добавить, как решить преобразование ограничений очень удобная форма для квадратичного программирования, поскольку она не так проста, как я думал. Невозможно найти вещественную матрицу такую, что .A A w s | ш я | с|wi|sAAws|wi|s

Подход, который я использовал, состоял в том, чтобы разделить элементы вектора на и , так что . Если , у вас есть и , иначе у вас естьи . Или, в более математических терминах, иИ и - неотрицательные числа. Идея разделения чисел состоит в том, что теперь у вас есть w w + i w - i w i = w + i - w - i w i0 w + i = w i w - i = 0 w - i = | ш я | w + i = 0 w + i = | ш я | + ш яwiwwi+wiwi=wi+wiwi0wi+=wiwi=0wi=|wi|wi+=0 ш - я =| шя| -шIwi+=|wi|+wi2w - i w + i | шя| =w + i +w - iwi=|wi|wi2.wiwi+|wi|=wi++wi, эффективно избавляясь от абсолютных значений.

Функция для оптимизации превращается в: , субъект к 12(w+w)TQ(w+w)+cT(w+w)wi++wis,wi+,wi0

Где и даны как указано выше Glen_bQc

Это должно быть преобразовано в удобную форму, то есть нам нужен один вектор. Это делается следующим образом:

12[w+w]T[QQQQ][w+w]+[cTcT][w+w]

при условии

[IDIDI2D][w+w][sD02D]

Где - мерная единичная матрица, - мерный вектор, состоящий только из значения а - -мерный нулевой вектор. Первая половина обеспечивает , второй Теперь можно использовать квадратичное программирование для поиска и , заданных . Как только это будет сделано, вашим оптимальным параметром по отношению к будет . D s D D s 0 D 2 D | ш я | = w + i + w - is w + i , w - i0 w + w - s s w = w + - w -IDDsDDs0D2D|wi|=wi++wiswi+,wi0w+wssw=w+w

Источник и дальнейшее чтение: Решение квадратичного программирования с линейными ограничениями , содержащие абсолютные значения

spurra
источник
Предположим, что мы нашли оптимальный вектор . Что гарантирует , что и на самом деле положительные части и отрицательные части некоторого вектора , т.е. их позиции входа совпадают? ( w + , w - ) w + w - w 02D(w+,w)w+ww0
Миаф
Матрица и вектор в конечном выражении могут быть более простыми и более правильными. Вместо [Id Id] [w + w−] '≤ Sd вы можете просто указать [1 1 .... 1] [w + w-]' ≤ s. Это буквально эквивалентно ∑ | wi | = ∑ (wi + + wi−) ≤ s.
Марко