Skip to content

feat(optim): Implement Augmented Lagrangian for equality-constrained …#63

Merged
noahgift merged 1 commit into
mainfrom
claude/research-optimization-techniques-01LWS5ZwqVEHQ13NbShwH7Ls
Nov 23, 2025
Merged

feat(optim): Implement Augmented Lagrangian for equality-constrained …#63
noahgift merged 1 commit into
mainfrom
claude/research-optimization-techniques-01LWS5ZwqVEHQ13NbShwH7Ls

Conversation

@noahgift

Copy link
Copy Markdown
Contributor

…optimization

Add comprehensive Augmented Lagrangian method for Phase 3: Constrained Optimization.

Implementation (298 lines):

  • Algorithm: L_ρ(x, λ) = f(x) + λᵀh(x) + ½ρ‖h(x)‖²
  • Solves: minimize f(x) subject to h(x) = 0
  • Automatic Lagrange multiplier updates: λ_{k+1} = λ_k + ρh(x_k)
  • Adaptive penalty parameter ρ (increases when convergence is slow)
  • Superlinear convergence under regularity conditions

Key Features:

  • Automatic constraint satisfaction via penalty method
  • Adaptive ρ increase via with_rho_increase(factor)
  • Gradient descent subproblem solver (50 inner iterations)
  • Full convergence tracking with constraint violation metrics
  • Handles multiple equality constraints simultaneously

Algorithm:

  1. Initialize λ = 0, ρ = initial_rho
  2. For each outer iteration:
    • Solve subproblem: min L_ρ(x, λ) via gradient descent
    • Update multipliers: λ += ρ * h(x)
    • Check constraint violation ‖h(x)‖
    • Increase ρ if convergence is slow

Tests (7 comprehensive tests):

  1. test_augmented_lagrangian_linear_equality - Single linear constraint
  2. test_augmented_lagrangian_multiple_constraints - Two constraints
  3. test_augmented_lagrangian_3d - 3D problem space
  4. test_augmented_lagrangian_quadratic_with_constraint - Quadratic objective
  5. test_augmented_lagrangian_convergence_tracking - Status and metrics
  6. test_augmented_lagrangian_rho_adaptation - Custom penalty increase
  7. test_augmented_lagrangian_max_iterations - MaxIterations status

All tests passing: analytical solution verification, constraint satisfaction (‖h(x)‖ < 1e-3), and Lagrange multiplier convergence.

Applications:

  • Equality-constrained least squares
  • Manifold optimization (constraints define manifolds)
  • ADMM (Alternating Direction Method of Multipliers)
  • PDE-constrained optimization
  • Consensus optimization in distributed systems

Performance:

  • Typical convergence: 10-50 outer iterations
  • Subproblem solver: 50 gradient descent steps
  • Constraint violation: < 1e-3 at convergence

Total: 298 lines implementation + 164 lines tests = 462 lines
Phase 3: Constrained Optimization - 2/3 complete

…optimization

Add comprehensive Augmented Lagrangian method for Phase 3:
Constrained Optimization.

**Implementation** (298 lines):
- Algorithm: L_ρ(x, λ) = f(x) + λᵀh(x) + ½ρ‖h(x)‖²
- Solves: minimize f(x) subject to h(x) = 0
- Automatic Lagrange multiplier updates: λ_{k+1} = λ_k + ρh(x_k)
- Adaptive penalty parameter ρ (increases when convergence is slow)
- Superlinear convergence under regularity conditions

**Key Features**:
- Automatic constraint satisfaction via penalty method
- Adaptive ρ increase via `with_rho_increase(factor)`
- Gradient descent subproblem solver (50 inner iterations)
- Full convergence tracking with constraint violation metrics
- Handles multiple equality constraints simultaneously

**Algorithm**:
1. Initialize λ = 0, ρ = initial_rho
2. For each outer iteration:
   - Solve subproblem: min L_ρ(x, λ) via gradient descent
   - Update multipliers: λ += ρ * h(x)
   - Check constraint violation ‖h(x)‖
   - Increase ρ if convergence is slow

**Tests** (7 comprehensive tests):
1. test_augmented_lagrangian_linear_equality - Single linear constraint
2. test_augmented_lagrangian_multiple_constraints - Two constraints
3. test_augmented_lagrangian_3d - 3D problem space
4. test_augmented_lagrangian_quadratic_with_constraint - Quadratic objective
5. test_augmented_lagrangian_convergence_tracking - Status and metrics
6. test_augmented_lagrangian_rho_adaptation - Custom penalty increase
7. test_augmented_lagrangian_max_iterations - MaxIterations status

All tests passing: analytical solution verification, constraint satisfaction
(‖h(x)‖ < 1e-3), and Lagrange multiplier convergence.

**Applications**:
- Equality-constrained least squares
- Manifold optimization (constraints define manifolds)
- ADMM (Alternating Direction Method of Multipliers)
- PDE-constrained optimization
- Consensus optimization in distributed systems

**Performance**:
- Typical convergence: 10-50 outer iterations
- Subproblem solver: 50 gradient descent steps
- Constraint violation: < 1e-3 at convergence

Total: 298 lines implementation + 164 lines tests = 462 lines
Phase 3: Constrained Optimization - 2/3 complete
@noahgift noahgift merged commit d4ccdc6 into main Nov 23, 2025
4 of 11 checks passed
@noahgift noahgift deleted the claude/research-optimization-techniques-01LWS5ZwqVEHQ13NbShwH7Ls branch November 23, 2025 17:25
noahgift added a commit that referenced this pull request Apr 18, 2026
…ublish::execute

dispatch_analysis.rs:1035 invoked commands::publish::execute with 10 args but
the function signature grew to 12 (manifest: Option<&Path>, extra_files: &[PathBuf])
for F-PUBLISH-EXTRA-001. Pass None/&[] defaults at the dispatch call site so the
non-manifest path still type-checks. A follow-up will thread --manifest + extra
files through the ToolCommands::Publish enum variant for full feature parity.

Zero-Tolerance fix per SHIP-TWO-001 spec §3 row #8: the branch must always
compile; no staged hacks or #[ignore] escape valves.

Refs: #96 (broken-branch unblock), #63 (F-PUBLISH-EXTRA-001 parent)

Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants