凸优化与 KKT

凸优化研究目标函数与可行域均为凸的问题($f(\theta x_1 + (1-\theta)x_2) \le \theta f(x_1) + (1-\theta)f(x_2)$ 对任意 $\theta \in [0,1]$ 成立,局部最优 = 全局最优)。带约束问题 $\min_x f(x)$ s.t. $h_i(x) = 0,\ g_j(x) \le 0$ 通过拉格朗日乘子转化为无约束形式: $L(x, \lambda, \mu) = f(x) + \sum_i \lambda_i h_i(x) + \sum_j \mu_j g_j(x)$,其中不等式约束乘子要求 $\mu_j \ge 0$(对偶可行性)——只有这样才能保证对可行域外的方向“惩罚”而非“奖励”。KKT 条件给出最优解的必要条件(凸问题 + Slater 条件时为充要条件)四条: ① 平稳性 $\nabla_x L = \nabla f + \sum_i \lambda_i\nabla h_i + \sum_j \mu_j\nabla g_j = 0$;② 原始可行性 $h_i(x) = 0,\ g_j(x) \le 0$;③ 对偶可行性 $\mu_j \ge 0$;④ 互补松弛 $\mu_j g_j(x) = 0$。互补松弛的几何含义: 若约束不起作用($g_j < 0$,解在可行域内部),则 $\mu_j$ 必须为 0;若 $\mu_j > 0$,则约束必须取等($g_j = 0$,解被约束“钉”在边界上)。

SVM 对偶推导、带约束正则(如 L1 的带球约束形式)、策略优化中的约束强化学习,以及“带约束优化怎么解”的面试追问。经典例子: $\min \frac{1}{2}(x-2)^2$ s.t. $x \le 1$。KKT 方程组: $x - 2 + \mu = 0$(平稳性)、$x \le 1$(原始)、$\mu \ge 0$(对偶)、$\mu(x-1) = 0$(互补松弛)。若 $\mu = 0$ 则 $x = 2$ 违反约束,故只能 $x = 1,\ \mu = 1$——无约束最优点 2 在可行域外,解被推到边界。

把约束最优化转化为代数方程组求解,无需显式遍历可行域边界;对偶理论给出弱对偶 $\min_x \max_{\mu\ge0} L \ge \max_{\mu\ge0} \min_x L$(后者的解 $d^*$ 恒 $\le f^*$),在 Slater 条件(存在严格可行点)下强对偶成立 $f^* = d^*$,使得 SVM 等模型可以转向对偶问题求解,并让 KKT 条件同时成为最优性的充要判据。

检验攻克程度：针对「凸优化与 KKT」专属刷题排雷

做单选排雷题、推导选项机制，答错自动收录进专属错题本。