我应该在 Drake 中使用哪个求解器来求解具有非线性约束的混合整数程序？
Which solver should I use in Drake to solve a mixed-integer program with non-linear constraints?
我正在尝试使用 Snopt 求解器用 Drake 求解混合整数非线性程序，但遇到以下错误：
ValueError: The capabilities of drake::solvers::SnoptSolver do not meet the requirements of the MathematicalProgram ({ProgramAttributes: GenericConstraint, QuadraticCost, LinearConstraint, LinearEqualityConstraint, BinaryVariable})
在我的案例中，推荐的 solver/alternative 方法是什么？
混合整数非线性优化是非常困难的问题，只有少数优化求解器存在，例如：Couenne, Baron。 Drake 不支持任何这些求解器。
Drake 支持大多数常见混合整数凸程序（例如 MILP、MIQP、MISOC）的求解器。但是要使用这些，您的优化问题必须只有凸约束（例如线性等式和不等式）。
使用非线性求解器（如 SNOPT）来解决优化问题的一种方法是强制执行二元约束，如下所示。假设您希望 x 是二进制的，那么您可以添加平滑约束 x * (x - 1) = 0。（请注意，后者已验证 iff x = 0 或 x = 1。）然而，这是一个非常 "tough" 约束，并可能导致数字问题。另请注意，如果存在可行的解决方案（保证您在混合整数凸规划中确实有），那么这样做您在找到可行解决方案方面没有任何保证，并且求解器可能会收敛到局部最小值。
正如您提到的，您的约束是
x[k+1] = A * ((1-b[k]) * x1[k] + b[k] * x2[k])
其中b[k]是二进制变量，x1[k], x2[k], x[k+1]是连续变量。
此约束可以重新表述为混合整数线性约束。你要的是
b[k] = 1, then x[k+1] = A * x2[k]
b[k] = 0, then x[k+1] = A * x1[k]
通常，如果通过将二进制变量固定为 0 或 1，其余约束是线性的，则可以将约束重新表述为混合整数线性约束。有两种方法可以将您的约束转换为混合整数线性约束，即大 M 方法和凸包方法，如本 tutorial 中所述。
作为凸包方法的快速演示，假设您的变量是有界的
x1[k] ∈ ConvexHull(v₁, v₂, ..., vₘ)
x2[k] ∈ ConvexHull(w₁, w₂, ..., wₙ)
其中v₁, v₂, ..., vₘ, w₁, w₂, ..., wₙ都是给分。
我们引入了两个松弛变量s1, s2。我们打算施加以下约束
b[k] = 1, then s1 = 0, s2 = A * x2[k]
b[k] = 0, then s2 = 0, s1 = A * x1[k]
x[k+1] = s1 + s2
上面的约束意味着点(b[k], s2, x2[k])的凸包是有顶点
的多面体
(1, A * w₁, w₁)
(1, A * w₂, w₂)
...
(1, A * wₙ, wₙ)
(0, 0, w₁)
(0, 0, w₂)
...
(0, 0, wₙ)
有了这些顶点，多胞形就写成了V-表示。您可以将此 V 表示转换为 H 表示。此 H 表示表示为
H * [b[k], s2, x2[k]] <= h
其中每一行H是多面体的一个面法线。该 H 表示是对变量 b[k], s2, x2[k] 的（混合整数）线性约束。另一种约束 b[k], s2, x2[k] 位于多面体内的公式是将 (b[k], s2, x2[k]) 写为多面体顶点的凸组合（您还需要引入凸组合权重作为决策变量，所有权重是非负的，并且权重之和等于 1)。使用这种凸组合方法，您不需要将 V 表示转换为 H 表示。这是使用凸组合方法对 b[k], s2, x2[k] 的混合整数线性约束。
b[k] = λ₁ + λ₂ + ... + λₙ
s2 = A*(λ₁w₁ + λ₂w₂ + ... + λₙwₙ)
x2[k] = λ₁w₁ + λ₂w₂ + ... + λₙwₙ + λₙ₊₁w₁ + λₙ₊₂w₂ + ... + λ₂ₙwₙ
1 = λ₁ + λ₂ + ... + λₙ + λₙ₊₁ + λₙ₊₂ + ... + λ₂ₙ
λᵢ ≥ 0 ∀ i = 1, ..., 2n
b[k] is binary
其中权重 λᵢ, i = 1, ..., 2n 是表示凸组合权重的新松弛变量。您可以验证这些约束是否强制执行
if b[k] = 0, then s2 = 0.
if b[k] = 1, then s2 = A*x2[k]
同样我们知道点(b[k], s1, x1[k])的凸包是一个多面体，其顶点如下
(1, 0, v₁)
(1, 0, v₂)
...
(1, 0, vₘ)
(0, A*v₁, v₁)
(0, A*v₂, v₂)
...
(0, A*vₘ, vₘ)
我们可以从多胞形的 H 表示中写出线性约束。我们将从多面体派生的两组线性约束结合起来，再加上线性约束x[k+1] = s1 + s2，我们就得到了你问题的混合整数线性约束。关于这种凸包方法的详细解释，可以参考上面的链接教程。
我正在尝试使用 Snopt 求解器用 Drake 求解混合整数非线性程序，但遇到以下错误：
ValueError: The capabilities of drake::solvers::SnoptSolver do not meet the requirements of the MathematicalProgram ({ProgramAttributes: GenericConstraint, QuadraticCost, LinearConstraint, LinearEqualityConstraint, BinaryVariable})
在我的案例中，推荐的 solver/alternative 方法是什么？
混合整数非线性优化是非常困难的问题，只有少数优化求解器存在，例如：Couenne, Baron。 Drake 不支持任何这些求解器。
Drake 支持大多数常见混合整数凸程序（例如 MILP、MIQP、MISOC）的求解器。但是要使用这些，您的优化问题必须只有凸约束（例如线性等式和不等式）。
使用非线性求解器（如 SNOPT）来解决优化问题的一种方法是强制执行二元约束，如下所示。假设您希望 x 是二进制的，那么您可以添加平滑约束 x * (x - 1) = 0。（请注意，后者已验证 iff x = 0 或 x = 1。）然而，这是一个非常 "tough" 约束，并可能导致数字问题。另请注意，如果存在可行的解决方案（保证您在混合整数凸规划中确实有），那么这样做您在找到可行解决方案方面没有任何保证，并且求解器可能会收敛到局部最小值。
正如您提到的，您的约束是
x[k+1] = A * ((1-b[k]) * x1[k] + b[k] * x2[k])
其中b[k]是二进制变量，x1[k], x2[k], x[k+1]是连续变量。
此约束可以重新表述为混合整数线性约束。你要的是
b[k] = 1, then x[k+1] = A * x2[k]
b[k] = 0, then x[k+1] = A * x1[k]
通常，如果通过将二进制变量固定为 0 或 1，其余约束是线性的，则可以将约束重新表述为混合整数线性约束。有两种方法可以将您的约束转换为混合整数线性约束，即大 M 方法和凸包方法，如本 tutorial 中所述。
作为凸包方法的快速演示，假设您的变量是有界的
x1[k] ∈ ConvexHull(v₁, v₂, ..., vₘ)
x2[k] ∈ ConvexHull(w₁, w₂, ..., wₙ)
其中v₁, v₂, ..., vₘ, w₁, w₂, ..., wₙ都是给分。
我们引入了两个松弛变量s1, s2。我们打算施加以下约束
b[k] = 1, then s1 = 0, s2 = A * x2[k]
b[k] = 0, then s2 = 0, s1 = A * x1[k]
x[k+1] = s1 + s2
上面的约束意味着点(b[k], s2, x2[k])的凸包是有顶点
(1, A * w₁, w₁)
(1, A * w₂, w₂)
...
(1, A * wₙ, wₙ)
(0, 0, w₁)
(0, 0, w₂)
...
(0, 0, wₙ)
有了这些顶点，多胞形就写成了V-表示。您可以将此 V 表示转换为 H 表示。此 H 表示表示为
H * [b[k], s2, x2[k]] <= h
其中每一行H是多面体的一个面法线。该 H 表示是对变量 b[k], s2, x2[k] 的（混合整数）线性约束。另一种约束 b[k], s2, x2[k] 位于多面体内的公式是将 (b[k], s2, x2[k]) 写为多面体顶点的凸组合（您还需要引入凸组合权重作为决策变量，所有权重是非负的，并且权重之和等于 1)。使用这种凸组合方法，您不需要将 V 表示转换为 H 表示。这是使用凸组合方法对 b[k], s2, x2[k] 的混合整数线性约束。
b[k] = λ₁ + λ₂ + ... + λₙ
s2 = A*(λ₁w₁ + λ₂w₂ + ... + λₙwₙ)
x2[k] = λ₁w₁ + λ₂w₂ + ... + λₙwₙ + λₙ₊₁w₁ + λₙ₊₂w₂ + ... + λ₂ₙwₙ
1 = λ₁ + λ₂ + ... + λₙ + λₙ₊₁ + λₙ₊₂ + ... + λ₂ₙ
λᵢ ≥ 0 ∀ i = 1, ..., 2n
b[k] is binary
其中权重 λᵢ, i = 1, ..., 2n 是表示凸组合权重的新松弛变量。您可以验证这些约束是否强制执行
if b[k] = 0, then s2 = 0.
if b[k] = 1, then s2 = A*x2[k]
同样我们知道点(b[k], s1, x1[k])的凸包是一个多面体，其顶点如下
(1, 0, v₁)
(1, 0, v₂)
...
(1, 0, vₘ)
(0, A*v₁, v₁)
(0, A*v₂, v₂)
...
(0, A*vₘ, vₘ)
我们可以从多胞形的 H 表示中写出线性约束。我们将从多面体派生的两组线性约束结合起来，再加上线性约束x[k+1] = s1 + s2，我们就得到了你问题的混合整数线性约束。关于这种凸包方法的详细解释，可以参考上面的链接教程。