如何用单纯形法求解最小绝对偏差？

机器算法验证回归优化分位数回归线性规划最小绝对偏差

2022-03-04 07:30:21

以下是所关注的最小绝对偏差问题： $\underset{\textbf{w}}{\arg\min} L(w)=\sum_{i=1}^{n}|y_{i}-\textbf{w}^T\textbf{x}|$ . 我知道它可以通过以下方式重新排列为 LP 问题：

$\min \sum_{i=1}^{n}u_{i}$

$u_i \geq \textbf{x}^T\textbf{w}- y_{i} \; i = 1,\ldots,n$

$u_i \geq -\left(\textbf{x}^T\textbf{w}-y_{i}\right) \; i = 1,\ldots,n$

但我不知道一步一步解决它，因为我是 LP 的新手。你有什么主意吗？提前致谢！

编辑：

这是我在这个问题上达到的最新阶段。我正在尝试解决此注释之后的问题：

第 1 步：将其制定为标准形式

$\min Z=\sum_{i=1}^{n}u_{i}$

$\textbf{x}^T\textbf{w} -u_i+s_1=y_{i} \; i = 1,\ldots,n$

$\textbf{x}^T\textbf{w} +u_i+s_2=-y_{i} \; i = 1,\ldots,n$

受制于 $s_1 \ge 0; s_2\ge 0; u_i \ge 0 \ i=1,...,n$

第 2 步：构建初始画面

           |      |    0      |    1   |  0  |   0   |   0    
 basic var | coef |  $p_0$    |  $u_i$ |  W  | $s_1$ | $s_2$ 
      $s_1$| 0    |  $y_i$    |   -1   |  x  |   1   |   0
      $s_2 | 0    |  $-y_i$   |    1   |  x  |   0   |   1
      z    |      |    0      |    -1  |  0  |   0   |   0

第 3 步：选择基本变量

$u_i$ 被选为输入基变量。问题来了。选择输出基变量时，很明显 $y_i/-1=-y_i/1=-y_i$ . 根据注释，如果 $y_i\ge0$ ，问题有无界解。

我完全迷失在这里。我想知道是否有什么问题以及我应该如何继续以下步骤。

2个回答

您需要一个通过线性规划求解最小绝对偏差的示例。我将向您展示 R 中的一个简单实现。分位数回归是最小绝对偏差的概括，这是分位数 0.5 的情况，因此我将展示分位数回归的解决方案。然后您可以使用 Rquantreg包检查结果：

    rq_LP  <-  function(x, Y, r=0.5, intercept=TRUE) {
        require("lpSolve")
        if (intercept) X  <-  cbind(1, x) else X <-  cbind(x)
        N   <-  length(Y)
        n  <-  nrow(X)
        stopifnot(n == N)
        p  <-  ncol(X)
        c  <-  c(rep(r, n), rep(1-r, n), rep(0, 2*p))  
                 # cost coefficient vector
        A  <- cbind(diag(n), -diag(n), X, -X)
        res  <-  lp("min", c, A, "=", Y, compute.sens=1)
            ### Desempaquetar los coefs:
        sol <- res$solution
        coef1  <-  sol[(2*n+1):(2*n+2*p)]
        coef <- numeric(length=p)
        for (i in seq(along=coef)) {
             coef[i] <- (if(coef1[i]<=0)-1 else +1) *  
                  max(coef1[i], coef1[i+p])
        }
        return(coef)
        }

然后我们在一个简单的例子中使用它：

    library(robustbase)
    data(starsCYG)
    Y  <- starsCYG[, 2]
    x  <- starsCYG[, 1]
    rq_LP(x, Y)
    [1]  8.1492045 -0.6931818

然后你自己可以用quantreg.

线性规划可以用凸优化来推广，除了单纯形之外，还有许多更可靠的算法可用。

我建议您查看 The Convex Optimization Book 和他们提供的 CVX 工具箱。您可以通过正则化轻松制定最小绝对偏差。

https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf

http://cvxr.com/cvx/

其它你可能感兴趣的问题

上一篇检测过拟合的技术下一篇手动计算线性混合模型的随机效应预测