Hard → soft constraints (satisfaction becomes cost)
Parent: relaxation
The single most important relaxation for reaching optimization: turn a hard constraint (must hold) into a penalty (better to hold, and measured by how much it's violated). A predicate becomes a quantity.
The move
- SAT → MaxSAT. SAT: "is there an assignment satisfying all clauses?" (a yes/no decision). MaxSAT: "which assignment satisfies the most clauses?" (an optimization). Feasibility → optimality.
- CSP → soft-constraint / weighted optimization. Hard constraints become weighted penalties; find the assignment minimizing total violation. (Exactly the harness's CSP softened.)
- Feasibility → objective. "Find a point in the feasible set" becomes "minimize distance to feasibility" — the same set, now with a gradient pointing in.
The Lagrangian is literally this relaxation
A hard constraint g(x) ≤ 0 becomes a penalty term λ · max(g(x), 0) added to the objective — that is the Lagrangian move, and the multiplier λ is the price of violating the constraint. So constrained optimization is the soft-constraint relaxation of logical feasibility: instead of forbidding g(x) > 0, you charge for it, and let the optimizer trade violation against objective.
Why it's the doorway to optimization
"Satisfy φ" (a predicate you can only check) becomes "minimize violation of φ" (a number you can descend). The moment the constraint has a magnitude, gradient descent, duality, and continuous search all become available — you've stepped from logic into optimization.
Cost: MaxSAT is still NP-hard, and penalty weights/λ must be chosen — the hardness moved into tuning the prices, it didn't vanish (no free lunch).