Пакет программ для решения линейной регрессии L-бесконечности

Существует ли какой-либо программный пакет для решения линейной регрессии с целью минимизации нормы L-бесконечности.

Краткий ответ : Ваша проблема может быть сформулирована как линейная программа (LP), позволяя вам выбрать свой любимый решатель LP для этой задачи. Чтобы узнать, как записать проблему в виде LP, читайте дальше.

Эту проблему минимизации часто называют чебышевским приближением .

Пусть , со строкой обозначенной и . Затем мы стремимся минимизировать функцию относительно . Обозначим оптимальное значение через $\newcommand{\y}{\mathbf{y}}\newcommand{\X}{\mathbf{X}}\newcommand{\x}{\mathbf{x}}\newcommand{\b}{\mathbf{\beta}}\newcommand{\reals}{\mathbb{R}}\newcommand{\ones}{\mathbf{1}_n} \y = (y_i) \in \reals^n$$\X \in \reals^{n \times p}$$i$$\x_i$$\b \in \reals^p$$f(\b) = \|\y - \X \b\|_\infty$$\b$

$$f^\star = f(\b^\star) = \inf \{f(\b): \b \in \reals^p \} \>.$$

Ключ к преобразованию этого в LP - переписать проблему в форме эпиграфа . Нетрудно убедить себя, что на самом деле

$$f^\star = \inf\{t: f(\b) \leq t, \;t \in \reals, \;\b \in \reals^p \} \> .$$

Теперь, используя определение функции , мы можем переписать правую часть выше как и мы видим, что минимизация нормы в настройке регрессии эквивалентна LP где выполняется оптимизация через , а обозначает вектор единиц длины . Я оставляю читателю в качестве (простого) упражнения переписать вышеуказанный LP в стандартной форме.f ⋆ = inf { t : - t ≤ y i - x i β ≤ t $f$ℓ ∞ свести к минимуму т подлежащего у - Х & beta ; & le ; т 1

$$f^\star = \inf\{t: -t \leq y_i - \x_i \b \leq t, \;t \in \reals, \;\b \in \reals^p,\; 1 \leq i \leq n \} \>,$$ $\ell_\infty$ (β,t)1n $$\begin{array}{ll} \text{minimize} & t \\ \text{subject to} & \y-\X \b \leq t\ones \\ & \y - \X \b \geq - t \ones \>, \\ \end{array}$$ $(\b, t)$$\ones$$n$

Связь с версией линейной регрессии (полная вариация)$\ell_1$

Интересно отметить, что нечто очень похожее можно сделать с нормы . Пусть . Затем аналогичные аргументы приводят к выводу, что так что соответствующий LP является г ( & beta ; ) = | | у - Х & beta ; | | 1 г ⋆ = инф { т Т 1 п : - т я ≤ у я - х я & beta ; ≤ т я$\ell_1$$g(\b) = \|\y - \X \b \|_1$Свести к минимуму т Т 1 л при условии у - Х & beta ; & le ;

$$\newcommand{\t}{\mathbf{t}} g^\star = \inf\{\t^T \ones : -t_i \leq y_i - \x_i \b \leq t_i, \;\t = (t_i) \in \reals^n, \;\b \in \reals^p,\; 1 \leq i \leq n \} \>,$$ $$\begin{array}{ll} \text{minimize} & \t^T \ones \\ \text{subject to} & \y-\X \b \leq \t \\ & \y - \X \b \geq - \t \>. \\ \end{array}$$

Обратите внимание, что теперь является вектором длины вместо скаляра, как это было в случае . п л $\t$$n$$\ell_\infty$

Сходство в этих двух проблемах и тот факт, что они оба могут быть разыграны как LP, конечно, не случайны. Две нормы связаны в том, что они являются двойственными нормами друг друга.

Малаб может сделать это, используя cvx. получить cvx (бесплатно):

http://cvxr.com/cvx/download/

В cvx вы бы написали это так:

cvx_begin
   variable x(n);
   minimize( norm(A*x-b,Inf) );
cvx_end

(см. пример на странице 12 руководства )

Существует реализация Python для CVX ( здесь ), но команды немного отличаются ...

Ответ @ cardinal хорошо сформулирован и принят, но ради полного закрытия этой темы я предлагаю следующее: Числовые библиотеки IMSL содержат процедуру для выполнения регрессии нормы L-бесконечности. Процедура доступна на Фортране, C, Java, C # и Python. Я использовал версии C и Python, для которых этот метод называется lnorm_regression, который также поддерживает общую регрессию -norm, . p > = $L_p$$p >= 1$

Обратите внимание, что это коммерческие библиотеки, но версии Python бесплатны (как в пиве) для некоммерческого использования.