跳至内容
CVBB ACM Team
用户工具
注册
登录
站点工具
搜索
工具
显示页面
修订记录
Copy this page
导出 PDF
反向链接
最近更改
媒体管理器
网站地图
注册
登录
>
最近更改
媒体管理器
网站地图
您在这里:
front_page
»
2020-2021
»
teams
»
farmer_john
»
2sozx
»
牛客多校第一天d
2020-2021:teams:farmer_john:2sozx:牛客多校第一天d
本页面只读。您可以查看源文件,但不能更改它。如果您觉得这是系统错误,请联系管理员。
=====题意===== 给定一个 $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$ =====证明===== 这道题即为 $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.txt
· 最后更改: 2020/07/17 16:26 由
2sozx
页面工具
显示页面
修订记录
反向链接
Copy this page
导出 PDF
回到顶部