KK空间

超平面
法矢： $P_C(x_0)-x_0$
平面过中点 $x_0/2+P_C(x_0)/2$
因此超平面方程为

(P_C(x_0)-x_0)^T(x-(1/2)(x_0+P_C(x_0)))

寻找两个凸集的距离

\begin{align} minimize\ \ \ \ \ &||\omega ||\\ subject\ to \ \ \ &f_i(x)\le 0,\\ &g_i(y) \le 0,\\ &x-y=\omega \end{align}

求对偶问题
对偶函数为

g(\lambda,z,\mu) = \inf_{x,y,\omega} (||\omega||+\Sigma_{i=1}^m \lambda_if_i(x)+\Sigma_{i=1}^p\mu_ig_i(y)+z^T(x-y-\omega))

这个式子可以变形为

\inf_{\omega} (||\omega||+z^T\omega) + \inf_{x}(\Sigma_{i=1}^m \lambda_if_i(x) + z^Tx) + \inf_{y}(\Sigma_{i=1}^p\mu_ig_i(y) - z^Ty)

三个变量的影响相互独立，对于 $\omega$ 而言，如果 $||z||<1$ ，第一项一定能找到一个合适的 $\omega$ 使其最小，否则的话可以达到负无穷。
因此

g(\lambda,z,\mu) = \inf_{x}(\Sigma_{i=1}^m \lambda_if_i(x) + z^Tx) + \inf_{y}(\Sigma_{i=1}^p\mu_ig_i(y) - z^Ty)

可以得到对偶问题为

\begin{align} maximum \ \ \ \ \ \ \ \ & \inf_{x}(\Sigma_{i=1}^m \lambda_if_i(x) + z^Tx) + \inf_{y}(\Sigma_{i=1}^p\mu_ig_i(y) - z^Ty)\\ subject \ to\ \ \ \ \ \ \ \ & ||z||<1\\ &\lambda_i\ge 0,\mu_i\ge0 \end{align}

超平面
法矢： $P_C(x_0)-x_0$
平面过中点 $x_0/2+P_C(x_0)/2$
因此超平面方程为

(P_C(x_0)-x_0)^T(x-(1/2)(x_0+P_C(x_0)))

\begin{align} minimize\ \ \ \ \ &||\omega ||\\ subject\ to \ \ \ &f_i(x)\le 0,\\ &g_i(y) \le 0,\\ &x-y=\omega \end{align}

求对偶问题
对偶函数为

g(\lambda,z,\mu) = \inf_{x,y,\omega} (||\omega||+\Sigma_{i=1}^m \lambda_if_i(x)+\Sigma_{i=1}^p\mu_ig_i(y)+z^T(x-y-\omega))

这个式子可以变形为

\inf_{\omega} (||\omega||+z^T\omega) + \inf_{x}(\Sigma_{i=1}^m \lambda_if_i(x) + z^Tx) + \inf_{y}(\Sigma_{i=1}^p\mu_ig_i(y) - z^Ty)

三个变量的影响相互独立，对于 $\omega$ 而言，如果 $||z||<1$ ，第一项一定能找到一个合适的 $\omega$ 使其最小，否则的话可以达到负无穷。
因此

g(\lambda,z,\mu) = \inf_{x}(\Sigma_{i=1}^m \lambda_if_i(x) + z^Tx) + \inf_{y}(\Sigma_{i=1}^p\mu_ig_i(y) - z^Ty)

可以得到对偶问题为

\begin{align} maximum \ \ \ \ \ \ \ \ & \inf_{x}(\Sigma_{i=1}^m \lambda_if_i(x) + z^Tx) + \inf_{y}(\Sigma_{i=1}^p\mu_ig_i(y) - z^Ty)\\ subject \ to\ \ \ \ \ \ \ \ & ||z||<1\\ &\lambda_i\ge 0,\mu_i\ge0 \end{align}