计算科学 - 具有形式约束的线性规划Cx ≮ dCx≮d其中C∈R米× ñC∈Rm×n - 吾爱随笔录

我有一个具有线性目标函数的优化问题。约束的形式为：。换句话说，我有： $(Ax \leq b) \wedge (Cx \nless d)$

\begin{aligned} min & f^{T} x \\ s.t. & A x \leq b \\ C x ≮ d \end{aligned}

$\begin{align} \min &f^T x \notag \\ \text{s.t.} &Ax \leq b \\ &Cx \nless d\\ \end{align}$

解决问题的一种方法是将约束 $Cx \nless d$ 分解为 $m$ 个约束（假设 $C\in R^{m\times n}$ ）：

\begin{aligned} c_{1}^{T} x & \geq & d_{1} \\ \lor & c_{2}^{T} x & \geq & d_{2} \\ ⋮ \\ \lor & c_{m}^{T} x & \geq & d_{m} \end{aligned}

$\begin{align} & c_1^T x &\geq &d_1 \\ \vee & c_2^T x &\geq &d_2 \\ & & \vdots & \\ \vee & c_m^T x &\geq &d_m \\ \end{align}$ 我们最终解决了

m

$m$ 个线性规划，它们正好是相同，除了一个约束从一个 LP 更改为另一个。全局最优值只是获得的

m

$m$ 个最优值中的最优值。

谁能想到一种更快的方法来执行这种优化？那么凸松弛呢？我如何将我的问题放松为单个线性程序？凸松弛解决方案有多好？