计算下列优化问题的对偶问题：(c) min x∈Rn ∥Ax − b∥∞;

考虑原始问题：

$$\min_{x \in \mathbb{R}^n} \|Ax-b\|_{\infty}$$

其中，$A$ 是 $m \times n$ 的矩阵，$b$ 是 $m$ 维向量，$\|\cdot\|_{\infty}$ 表示向量的无穷范数，即向量中绝对值最大的元素。

将 $\|\cdot\|_{\infty}$ 表示为一系列线性不等式的形式，即：

$$\|v\|_{\infty} \leq t \iff -t \leq v_i \leq t, \forall i=1,2,\ldots,n$$

则原始问题可以表示为：

$$\min_{x \in \mathbb{R}^n} t$$

$$\text{s.t.} \quad -t \leq (Ax-b)_i \leq t, \quad \forall i=1,2,\ldots,m$$

将上述问题转化为拉格朗日对偶问题，定义拉格朗日函数：

$$L(x,t,\lambda,\mu) = t + \sum_{i=1}^{m}\lambda_i (Ax-b)_i - \sum_{i=1}^{m}\mu_i(Ax-b)_i - \sum_{i=1}^{n}\nu_i(-t-x_i)+\sum_{i=1}^{n}\omega_i(t-x_i)$$

其中，$\lambda_i$、$\mu_i$、$\nu_i$、$\omega_i$ 都是拉格朗日乘子，并满足 $\lambda_i \geq 0$、$\mu_i \geq 0$、$\nu_i \geq 0$、$\omega_i \geq 0$。

对 $x$ 求导，并令导数为 $0$，得到：

$$\frac{\partial L(x,t,\lambda,\mu,\nu,\omega)}{\partial x_i} = \sum_{j=1}^{m} A_{ji}(\lambda_j - \mu_j) - \nu_i + \omega_i = 0, \quad \forall i=1,2,\ldots,n$$

对 $t$ 求导，并令导数为 $0$，得到：

$$\frac{\partial L(x,t,\lambda,\mu,\nu,\omega)}{\partial t} = 1 - \sum_{i=1}^{n}(\nu_i + \omega_i) = 0$$

将上述式子代入拉格朗日函数，得到对偶函数：

$$g(\lambda,\mu,\nu,\omega) = \inf_{x,t} L(x,t,\lambda,\mu,\nu,\omega) = \sum_{i=1}^{m}b_i\lambda_i - \sum_{i=1}^{m}\lambda_i\left(\sum_{j=1}^{n}A_{ij}\mu_j\right) - \sum_{i=1}^{n}\nu_i t - \sum_{i=1}^{n}\omega_i x_i$$

对偶问题为：

$$\max_{\lambda \geq 0, \mu \geq 0, \nu \geq 0, \omega \geq 0} g(\lambda,\mu,\nu,\omega)$$

$$\text{s.t.} \quad \sum_{i=1}^{m}A_{ij}(\lambda_i - \mu_i) - \nu_j + \omega_j = 0, \quad \forall j=1,2,\ldots,n$$

$$\quad \sum_{i=1}^{n}(\nu_i + \omega_i) = 1$$

对偶问题的目标是最大化 $g(\lambda,\mu,\nu,\omega)$，约束条件包括 $\lambda \geq 0$、$\mu \geq 0$、$\nu \geq 0$、$\omega \geq 0$、以及一组线性等式约束。