凸优化与 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 条件同时成为最优性的充要判据。

写出拉格朗日函数 $L = f + \sum_i\lambda_i h_i + \sum_j\mu_j g_j$ 与四条 KKT 条件(平稳性/原始可行/对偶可行/互补松弛),并解释每条的含义。

互补松弛 $\mu_j g_j = 0$ 的几何含义: 为什么约束不起作用时乘子必须为 0?举一个约束在边界上起作用的例子。

用 KKT 求解 $\min \frac{1}{2}(x-2)^2$ s.t. $x \le 1$:写出全部 KKT 方程、讨论 $\mu = 0$ 分支并求解。

KKT 在什么条件下是充要条件?Slater 条件与强对偶 $f^* = d^*$ 的关系是什么?

硬间隔 SVM 的对偶推导中,哪些约束是“起作用”的?支持向量与互补松弛 $\mu_j g_j = 0$ 如何联系?