您有几个选择，具体取决于您采用的欧几里得范数的重要性。$z$

1. 按原样使用您的公式，稍作调整：

   $max_{r,z}\quad r$
   受以下两个约束
   $r\|x_i\| - x_i^Tz \leq 0 \qquad \forall i=1,\dots, N$
   $z^{T}z \leq 1$
   $r\geq0$

   这个问题是一个二次约束的程序，有许多快速求解器，例如 CPLEX 和 Gurobi。这个特定程序也是二阶锥程序、半定程序和凸非线性程序，因此您也可以使用这些求解器中的任何一个。我用点积替换欧几里得范数约束的原因是这两个约束是等价的，但后者是可微的，而前者不是。不可微函数需要更昂贵的算法，而这个问题不需要那种类型的机器，所以最好避免它。

2. 改变的范数。1-norm 和 infinity-norm 都是元素的线性函数，将公式中的欧几里得范数替换为这些范数中的任何一个都会产生一个线性程序，最好的求解器往往是商业的（Gurobi，CPLEX )，但存在速度较慢的免费求解器（GLPK，COIN-OR 套件中的求解器）。使用 1 范数意味着该公式的任何解决方案也将是您当前公式的可行解决方案（也就是说，使用 1 范数会限制您当前的公式）。使用无穷范数意味着您当前公式的任何解决方案在无穷范数公式中也是可行的（也就是说，使用无穷范数会产生当前公式的松弛）。$z$$z$

虽然线性规划求解器确实非常有效，但我会选择选项 1，因为二次约束规划求解器也非常有效（相对于凸规划求解器和其他类型的非线性规划求解器）并且可以求解大型公式（在至少有几十万个决策变量，上次我看文献）。除非您的公式非常大，否则您应该可以串行使用二次约束规划求解器，并且除非绝对必须更改，否则无需更改公式中的规范。

最后一点：我会在构建公式之前对向量进行缩放，以便它们都具有单位范数，这可能有助于在数值求解时调整公式。这是另一个几乎不会花费您任何费用的技巧，但可以保护您免受数字困难的影响。$x_{i}$

正如我们在 Geoffs 的回答中看到的，这是一个非常简单的二次约束问题，或者更一般地说是一个二阶锥程序。如果您没有极端的性能要求或巨大的尺寸，使用二次形式的标准非线性求解器或使用范数公式的 SOCP 求解器将完美地工作美好的。$z^Tz \leq 1$$\|z\|\leq 1$

如果你必须提高性能，有一些方法可以利用单锥特征。这是一个例子

SIAM J. Optim., 17(2), 459–484。（26 页）单锥二阶锥程序 E. Erdougan 和 G. Iyengar 的主动集方法

我想指出，用 1 范数替换范数可能效果不佳。二次范数起源于这个问题的几何背景（我将其解释为找到一个与给定向量集具有最小角度的向量）。

有趣的是，问题的 QP 近似似乎非常有效。移除二次约束，并改为向目标如果有可能证明这一点，我不会感到惊讶。$\alpha z^Tz$

和使用 QP 启发式计算的平均距离，而从 LP（1-范数）公式到解的距离大约为。$z$$z$$10^{-6}$$10^{-1}$

z = sdpvar(5,1);
r = sdpvar(1);

err1 = [];
err2 = [];
for i = 1:1000
    X = randn(5,10);
    Con = [r*sqrt(sum(X.^2,1)) <= z'*X,norm(z,2) <= 1]
    sol = solvesdp(Con,-r)
    if sol.problem == 0 & double(r)>1e-3
        zSOCP = double(z);
        Con = [r*sqrt(sum(X.^2,1)) <= z'*X];
        sol = solvesdp(Con,-r+0.001*z'*z);
        zQP = double(z/norm(double(z)));
        err1 = [err1 norm(zQP-zSOCP)];
        Con = [r*sqrt(sum(X.^2,1)) <= z'*X, norm(z,1)<=1];
        sol = solvesdp(Con,-r);
        zLP = double(z/norm(double(z)));
        err2 = [err2 norm(zLP-zSOCP)];
    end
end

最后，使用几何洞察力可能会导致更好的方法来解决这个问题。您实际上是在寻找单位球面上一组点的特别定义的中心。