Foundations T21 / 27 · Decision & optimization
Optimization: why constraints cannot rely on penalties alone
On a convex function the local optimum is the global optimum — that is not a comfort, it is a theorem. TRPO writes a KL constraint instead of a large penalty; the reason lives in duality theory: a penalty coefficient must be hand-picked, a constraint does not.
One-line takeaway
Convexity guarantees local = global (a 3-line proof); Lagrangian duality turns «with constraints» into a saddle-point problem with no parameter choices, and under strong duality the gap = 0. The justification of every «constrained update» in RL (trust regions, KL penalties, safety layers) starts from these two theorems.
PPO's clip, TRPO's trust region, the Lagrangian method of safe RL — why are some written as hard constraints and others as penalties, and why is the penalty coefficient so hard to tune? The answer is not in the RL literature; it is in chapter one of convex optimization. This article takes only the minimal set RL actually uses: convexity, Lagrangians, duality, KKT.
Why this tool exists
In training you have probably seen both forms: TRPO writes max J(θ) s.t. KL(θ,θ_old) < δ (hard constraint); PPO writes max J(θ) − β·KL(θ,θ_old) (penalty, β must be tuned). Mathematically the penalty approaches the constraint as β→∞, but for finite β the constraint is only «soft» — β too small and the constraint fails, too large and the step size is paralyzed. Is there a rigorous way out of this dilemma?
Lagrangian duality gives a third form: L(θ,λ) = J(θ) − λ(KL−δ), maximized over θ and minimized over λ≥0. λ is no longer a hand-picked hyperparameter but the solution of the dual problem (it rises automatically to the value where the constraint is exactly tight). Safe RL's Lagrangian-PPO does exactly this.
Lay the groundwork first: all of this has a complete theory on «convex problems». For nonconvex ones, duality may be weak (gap>0) and KKT is necessary but not sufficient. So keep straight which parts are theorems and which are heuristics.
Definitions
Definition 9.1 Convex function
f is convex: for all x, y and λ∈[0,1], f(λx+(1−λ)y) ≤ λf(x)+(1−λ)f(y). Geometric reading: the chord lies above the curve. Strictly convex: the inequality is strict when x≠y.
Why define it this wayThe definition looks plain, but it encodes precisely «local information is globally valid» — Theorem 9.1 below proves it in three lines.
Definition 9.2 Lagrangian and dual function
Primal problem min f(x) s.t. g_i(x)≤0. Lagrangian L(x,λ) = f(x) + Σλ_i g_i(x) (λ_i≥0). Dual function g(λ) = min_x L(x,λ). Dual problem: maxλ≥0 g(λ).
Why define it this wayg(λ) takes the min over x pointwise — swapping the order of the min and the constraint. The dual function is always a lower bound of the primal (weak duality), provable in two lines; when equality holds is the question of strong duality.
Theorems and proofs
Theorem 9.1 Convexity ⇒ local optimum is global optimum
If f is convex and x̄ is a local minimizer (there is a neighborhood with f(x̄) ≤ f(x)), then x̄ is a global minimizer.
Proof
Proof by contradiction. Suppose there is y with f(y) < f(x̄). Consider points z_λ = λy + (1−λ)x̄ on the segment, with λ small enough that z_λ lies in the local neighborhood of x̄.
By convexity: f(z_λ) ≤ λf(y) + (1−λ)f(x̄) < λf(x̄) + (1−λ)f(x̄) = f(x̄).
So within the neighborhood there is a z_λ strictly better than x̄, contradicting local optimality. ∎
NoteThe proof uses only the definition of convexity and locality — three lines. For nonconvex f the argument breaks where «the chord dips below the curve» — the 9 starting points falling into 3 basins in the T9 experiment is that break made concrete.
Theorem 9.2 Weak duality and strong duality
Weak duality: g(λ) ≤ p* (for all λ≥0; a two-line proof). Strong duality: max g(λ) = p*. Convex problem + Slater's condition (a strictly feasible point exists) ⇒ strong duality (stated without proof).
Proof
Weak duality: for feasible x (g_i(x)≤0) and λ≥0: L(x,λ) = f(x) + Σλ_i g_i(x) ≤ f(x) (the second term is nonpositive). Take the min over x on both sides: g(λ) ≤ f(x) for every feasible x; take the inf over x: g(λ) ≤ p*. ∎
The proof of strong duality (needs separating hyperplanes/Slater) is beyond the boundary; stated only.
NoteThe weak duality proof is worth reading line by line: its entire content is «λ_i g_i(x) ≤ 0». Strong duality is the central miracle of convex optimization — the primal (possibly hard) and the dual (convex, always well-defined) agree in value under mild conditions. KL-constrained problems satisfy Slater (for δ>0 a strictly feasible point exists), so gap=0.
Theorem 9.3 KKT conditions (sufficient when convex)
For a convex problem under Slater, x* is optimal ⟺ there is λ*≥0 such that: (stationarity) ∇_x L(x*,λ*)=0; (dual feasibility) λ*≥0; (complementary slackness) λ*_i g_i(x*) = 0.
Proof
Necessity (general nonlinear programming theory) is beyond the boundary; stated only. Sufficiency proof (when convex): for any feasible x,
First step: λ*≥0 and g_i(x)≤0. Second: stationarity means x* is the global minimizer of L(·,λ*) (L is convex in x — a convex function plus a linear term). Third: complementary slackness kills the sum. ∎
NoteIntuition for complementary slackness: when a constraint is «pressed tight» (g_i=0) λ may be positive; when the constraint is slack (g_i<0) λ must be zero — the multiplier only charges for active constraints. In TRPO the KL constraint is always pressed tight (λ>0); the penalty version corresponds to «λ fixed»; the safety layer's automatic λ adjustment corresponds to «complementary slackness running».
Work it by hand
min x² s.t. x ≥ 1. Compute the dual function and the dual optimum by hand, verify strong duality gap=0, and read off the KKT conditions.
- Standard form: min f(x)=x², constraint written as g(x) = 1−x ≤ 0.
- Lagrangian: L(x,λ) = x² + λ(1−x). Minimize over x: ∂L/∂x = 2x−λ = 0 → x = λ/2 (a minimum for λ≥0).
- [object Object]
- Dual problem maxλ≥0 λ−λ²/4: d/dλ = 1−λ/2 = 0 → λ* = 2, g(λ*) = 2−1 = 1.
- Primal solution: x*=1 (x² is minimized on x≥1 at the boundary), p* = 1. gap = p* − g(λ*) = 0 ✓ strong duality.
- KKT check: stationarity 2x−λ=0 (x=1,λ=2: 2−2=0 ✓); complementary slackness λ·g = 2×(1−1) = 0 ✓; λ≥0 ✓. The constraint is pressed tight (g=0) and λ*=2>0 — the multiplier is charging.
λ*=2, x*=λ*/2=1, gap=0. Geometric reading: the dual problem is maximizing a one-dimensional concave function, easier than the primal — duals are often «more convex and lower-dimensional», which is why they are worth so much algorithmically.
Run the numbers
Where the numbers come from
One-dimensional experiments, each run once (learning rate 0.05, 200 steps of gradient descent):
- Convex f=(x−1.5)²+0.3: all 9 starting points (−2 to 2) converge to 1.5000
- Nonconvex f=0.3sin(3x)+0.08x²: the 9 starting points land in 3 basins: {−2.467}×1, {−0.494}×5, {1.482}×3
- Dual experiment (min x² s.t. x≥1): a grid search over the dual function gives λ*=2.000, x*=λ*/2=1.000, matching the primal solution, gap=0
Where this shows up
| The object here | The counterpart in RL | Used in |
|---|---|---|
| Convexity: local = global | For linear policies with convex objectives (e.g., LQR), local methods are safe to use | used in → |
| Lagrangian duality | Automatic multiplier tuning of safety-layer constraints (Lagrangian-PPO) | used in → |
| KKT complementary slackness | The KL constraint pressed tight in a trust region → multiplier = adaptive upper bound on the learning rate | used in → |
| Nonconvex multi-basin landscape | The practical reasons for random restarts and large batches in policy optimization | used in → |
Boundaries: where this article stops
Where this article stops: general theory of nonconvex optimization, interior-point methods, and algorithms for saddle-point problems (e.g., convergence rates of dual ascent) are all skipped. Honest disclaimer: policy optimization is almost always nonconvex; the theorems here give the skeleton of the «ideal case», and in practice they work as «directional intuition».
Self-test: 4 questions
All hand-computation and «find the flaw in this proof» questions — nothing to memorize. Stuck? Go back to the section.
01Where does the proof of Theorem 9.1 break on a nonconvex function?
At «f(z_λ) ≤ λf(y)+(1−λ)f(x̄)» — the chord-above-curve step needs convexity. For nonconvex f the chord can dip below the curve, and «no better point in the local neighborhood» does not imply «none globally». The 3 basins found in the experiment are that break made concrete.
02Weak duality takes two lines to prove; why is strong duality hard?
Weak duality is a pointwise inequality (λg≤0), holding unconditionally. Strong duality must show the lower bound is «attained» — that needs geometric tools like separating hyperplanes plus Slater's condition. «A lower bound exists» and «the lower bound is tight» are two different things, matching the intuition of the «value gap».
03What is the essential difference between the penalty method (PPO's β·KL) and the dual method (automatic λ)?
The penalty's β is an exogenous hyperparameter (fixed once, indifferent to whether the constraint is slack or tight); the dual's λ is a dual variable that ascends the dual gradient automatically until the constraint is exactly tight (complementary slackness). The latter turns «tuning β» into «solving a low-dimensional convex problem» — that is why safe RL uses the dual method.
04Write the three KKT conditions for min x² s.t. x≥1 and verify x*=1, λ*=2 one by one.
Stationarity: 2x−λ=0 → 2−2=0 ✓. Dual feasibility: λ=2≥0 ✓. Complementary slackness: λ(1−x)=2×0=0 ✓. All three pass, the problem is convex and Slater holds, so KKT is sufficient — x*=1 is indeed the global optimum.