Optimality Conditions: Supplement L: Quick Reference Tables

Supplement L: Quick Reference Tables

Situation	Method	Key Condition
No constraints	First/Second order	$\nabla f = 0$ , check $H$
Equality constraints only	Lagrange multipliers	$\nabla f + \lambda^\top \nabla g = 0$
Inequality constraints	KKT	4 conditions including $\mu \geq 0$ , CS
Mixed equality + inequality	KKT	Full 4-condition system
Convex problem	KKT (global)	KKT $\Leftrightarrow$ global min (Slater holds)
Non-convex problem	KKT (local)	KKT $\Rightarrow$ local min only
LP/QP	Interior point or simplex	KKT system solved directly
Non-smooth $f$	Subdifferential	$0 \in \partial f + \partial h$

Context	Multiplier meaning
Budget constraint $\mathbf{1}^\top\mathbf{w} \leq B$	$\lambda^*$ = value of one more unit of budget
Norm constraint $\\|\mathbf{w}\\|^2 \leq c$	$\lambda^*$ = decrease in loss per unit norm increase
SVM margin $y(\mathbf{w}^\top\mathbf{x}+b) \geq 1$	$\alpha_i^*$ = importance of sample $i$ to the decision boundary
KL constraint $D_{\text{KL}} \leq \delta$ in RLHF	$\beta^*$ = reward per unit KL allowed (the "temperature")
Power budget $\sum p_i = P$ (water-filling)	$\lambda^*$ = value of one more unit of transmit power
Expected return $\mu^\top\mathbf{w} = r$ (portfolio)	$\lambda^*$ = variance cost per unit extra expected return

Check	Method	Outcome
$f: \mathbb{R} \to \mathbb{R}$	$f''(x) \geq 0$ everywhere	Convex iff true
$f: \mathbb{R}^n \to \mathbb{R}$ , $C^2$	$\nabla^2 f(\mathbf{x}) \succeq 0$ everywhere	Convex iff true
$f$ is a sum	Each term convex?	Sum is convex
$f = g \circ A$ (affine precompose)	$g$ convex?	$f$ convex
$f(\mathbf{x}) = \max_i g_i(\mathbf{x})$	Each $g_i$ convex?	$f$ convex
$f(\mathbf{x}) = \log \sum_i e^{g_i(\mathbf{x})}$	Each $g_i$ affine?	$f$ convex (log-sum-exp)
$f(\mathbf{x}) = \\|A\mathbf{x}-\mathbf{b}\\|^2$	Always	Convex (quadratic, $H = 2A^\top A \succeq 0$ )