2020-2021:teams:farmer_john:2sozx:牛客多校第一天d
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2sozx:牛客多校第一天d [2020/07/17 15:38] 2sozx |
2020-2021:teams:farmer_john:2sozx:牛客多校第一天d [2020/07/17 16:26] (当前版本) 2sozx [证明] |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| =====题意===== | =====题意===== | ||
| - | 给定一个 $n\times n$ 的正定二次型 $A$ 以及 $1\times n$ 的 $B$，找到 $(x_1,x_2,\cdots,x_n)$ 满足 $X^T A X \le 1$ 并且使得 $X^T B$ 最大，求最大值的平方。$n\le200$ | + | 给定一个 $n\times n$ 的正定二次型 $A$ 以及 $1\times n$ 的 $B$，找到 $(x_1,x_2,\cdots,x_n)$ 满足 $X^T A X \le 1$ 并且使得 $BX^T$ 最大，求最大值的平方。$n\le200$ |
| =====题解===== | =====题解===== | ||
| 答案即为 $BA^{-1}B^T$ | 答案即为 $BA^{-1}B^T$ | ||
| =====证明===== | =====证明===== | ||
| + | 这道题即为 $KKT$ 模板。\\ | ||
| + | 令 $F(x)=BX^T+\lambda(XAX^T-1)$ 则取极值的条件为$$\begin{cases}B_i+2\lambda\sum_{j=1}^{n}A_{i,j}x_j=0 \\ XAX^T-1\le 0 \\ \lambda (XAX^T-1) = 0 \\ \lambda \ge 0\end{cases}$$ | ||
| + | 易知 $X=\frac{-B{(A^{-1})}^T}{2\lambda}$ ,代入 $\lambda (XAX^T-1) = 0 $ 可知 $\frac{BA^{-1}B^T}{4{\lambda}^2}=1$\\ | ||
| + | 最大值的平方则为 $(BX^T)(BX^T)=\frac{BA^{-1}B^TBA^{-1}B^T}{4{\lambda}^2}=BA^{-1}B^T$ | ||
2020-2021/teams/farmer_john/2sozx/牛客多校第一天d.1594971481.txt.gz · 最后更改: 2020/07/17 15:38 由 2sozx
