On this page
article
最优条件
考虑下面这个问题。
$$
\begin{aligned}
\min~ & c^Tx + \mu F(x)\\
\text{s.t. } & Ax = b\\
& x > 0
\end{aligned}
$$
接下来给出它的最优解条件。理论和相关推导来自凸优化中的 KKT 条件，这里不展开。
最优条件
设 $x$ 是上述问题的最优解。当且仅当存在对偶变量 $y, s$ 和 $x$ 一起满足如下条件。
原始可行： $Ax=b$
对偶可行： $A^Ty + s = c$
互补松弛： $XSe = \mu e$
其中
$$
\begin{aligned}
X =
\begin{bmatrix}
x_1 & 0 & \cdots & 0 \\
0 & x_1& \cdots & 0\\
\vdots & \vdots & \ddots & \vdots\\
0 & 0 & \cdots & x_n
\end{bmatrix}
\quad
S =
\begin{bmatrix}
s_1 & 0 & \cdots & 0 \\
0 & s_1& \cdots & 0\\
\vdots & \vdots & \ddots & \vdots\\
0 & 0 & \cdots & s_n
\end{bmatrix}
\quad
e = \begin{bmatrix}
1\\
1\\
\vdots \\
1
\end{bmatrix}
\end{aligned}
$$
上面的互补松弛条件也可以写成
$$ x_i s_i = \mu,\quad i =1, 2, …, n $$
因为 $\mu > 0$，所以 $x_i > 0$ 且 $s_i > 0$。这说明 $x$ 和 $(y, s)$ 都是内点。
$$
\begin{aligned}
& x\in \mathcal{F}^{\circ}_P =\{x \mid Ax=b, ~ x > 0\}\\
& (y,s) \in \mathcal{F}^{\circ}_D = \{(y,s)\mid A^Ty + s =c, ~ s > 0\}
\end{aligned}
$$
方程形式
最优条件也可以写成方程的形式。
$$
F(x,y,s) := \begin{bmatrix}
Ax-b\\
A^Ty + s - c\\
XSe-\mu e
\end{bmatrix}
$$
$x$ 是最优解等价于这个方程有解。
$$ F(x,y,s) = \mathbf{0} $$
解出这个方程，得到 $x$ 就是上面问题的最优解。
注意到 $F(x,y,s)$ 是一个连续函数且可导，可以用牛顿迭代法求解这个方程。
Last updated 04 Jul 2025, 08:25 +0800 .