RobotGuide
Math foundations/Optimization: why constraints cannot rely on penalties alone

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.

About 55 min3 theorems8 proof steps4 self-test questions

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,

f(x) ≥ L(x,λ*) ≥ L(x*,λ*) = f(x*) + Σλ*_i g_i(x*) = f(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.

  1. Standard form: min f(x)=x², constraint written as g(x) = 1−x ≤ 0.
  2. Lagrangian: L(x,λ) = x² + λ(1−x). Minimize over x: ∂L/∂x = 2x−λ = 0 → x = λ/2 (a minimum for λ≥0).
  3. [object Object]
  4. Dual problem maxλ≥0 λ−λ²/4: d/dλ = 1−λ/2 = 0 → λ* = 2, g(λ*) = 2−1 = 1.
  5. Primal solution: x*=1 (x² is minimized on x≥1 at the boundary), p* = 1. gap = p* − g(λ*) = 0 ✓ strong duality.
  6. 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.
Answer

λ*=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 hereThe counterpart in RLUsed in
Convexity: local = globalFor linear policies with convex objectives (e.g., LQR), local methods are safe to useused in →
Lagrangian dualityAutomatic multiplier tuning of safety-layer constraints (Lagrangian-PPO)used in →
KKT complementary slacknessThe KL constraint pressed tight in a trust region → multiplier = adaptive upper bound on the learning rateused in →
Nonconvex multi-basin landscapeThe practical reasons for random restarts and large batches in policy optimizationused 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.

Up next

The full series · 27 articles

T1The Matrix Is a Ledger for Rotation≈ 25 minT2From Slope to Gradient: The First Line of Every Robot Learning Algorithm≈ 25 minT3Vectors and forces: the physical reading of the dot productAbout 20 minT4Two Rulers and a Better Rulerabout 25 minT5The Ledger of One Motor Revolution: Radians, Speed, and Powerabout 20 minT6Complex multiplication is rotation: the one-dimensional version of quaternionsAbout 20 minT7Bases and coordinates: why robots put everything in matrices45 minT8Matrix Multiplication: Chaining Transformations, Not a Table OperationAbout 40 minT9The Jacobian: Rotate a Joint One Degree — How Far Does the End Effector Move?About 45 minT10Eigenvectors: The Directions a Matrix Dare Not Touchabout 45 minT11SVD and the Pseudoinverse: When There Is No Exact Solution, Find the Nearest Oneabout 50 minT12Taylor expansion: putting a straight line to work in place of a curveAbout 40 minT13Probability spaces: why «random» needs axioms50 minT14Expectation: A Rigorous Construction of «Average»About 55 minT15Conditional Expectation: What the Vertical Bar Really Means≈ 60 minT16Four inequalities: the quantitative answer to «how many samples are enough»45 minT17Norms and fixed points: where «it always converges» comes from55 minT18Markov Chains: When the Time Average Equals the Ensemble Averageabout 55 minT19The Mathematical Construction of the MDP: What One Axiom Is Worthabout 50 minT20Dynamic Programming: The Accounting for Two Iterations≈ 50 minT21Optimization: why constraints cannot rely on penalties aloneAbout 55 minT22Stochastic Approximation: Every Term in the Learning-Rate Formulaabout 55 minT23The Mathematics of Contact: Hertz Theoryabout 45 minT24Friction and the Friction Cone: The Geometry of Constraintsabout 40 minT25Force Closure and Grasp Metrics: ε Is a Linear ProgramAbout 50 minT26Contact Kinematics: Why Rolling Is Not «Sliding Along»≈ 45 minT27Slip detection: from «I felt it» to «I computed it»About 50 min