10.1 Exterior penalty methods

Penalty methods are a powerful tool for solving constrained optimization problems. They work by adding penalty terms to the objective function, transforming constrained problems into unconstrained ones that are easier to solve.

This section focuses on exterior penalty methods, which allow solutions to violate constraints but penalize them for doing so. We'll learn how these methods work, their advantages and limitations, and how to implement them effectively in practice.

Penalty Methods

Understanding Penalty Functions and Parameters

• Penalty functions transform constrained optimization problems into unconstrained ones
• Add penalty terms to objective function for constraint violations
• Penalty parameter controls magnitude of penalty terms
• Large penalty parameters force solutions closer to feasible region
• Quadratic penalty function uses squared violations of constraints
  • Expressed as $P(x) = f(x) + \mu \sum_{i=1}^m \max(0, g_i(x))^2$
  • $f(x)$ represents original objective function
  • $g_i(x)$ represents constraint functions
  • $\mu$ denotes penalty parameter

Unconstrained Optimization Techniques

• Convert constrained problems into series of unconstrained subproblems
• Apply standard unconstrained optimization methods to solve subproblems
• Gradient-based methods (steepest descent, Newton's method) commonly used
• Iteratively increase penalty parameter to improve solution accuracy
• Solve sequence of unconstrained problems with increasing penalty values

Advantages and Limitations of Penalty Methods

• Simple implementation for handling complex constraints
• Applicable to wide range of optimization problems
• Gradual transition from unconstrained to constrained solution
• May suffer from ill-conditioning for large penalty parameters
• Requires careful selection of initial penalty value and update strategy

Barrier Methods

Principles of Barrier Functions

• Barrier functions prevent solutions from violating inequality constraints
• Add terms to objective function that approach infinity near constraint boundaries
• Logarithmic barrier function commonly used
  • Expressed as $B(x) = f(x) - \mu \sum_{i=1}^m \log(-g_i(x))$
  • $f(x)$ represents original objective function
  • $g_i(x)$ represents inequality constraint functions
  • $\mu$ denotes barrier parameter
• Interior point methods utilize barrier functions to maintain feasibility

Challenges and Considerations in Barrier Methods

• Ill-conditioning occurs as barrier parameter approaches zero
• Solutions may become trapped near constraint boundaries
• Requires feasible initial point within constraint region
• Careful selection of barrier parameter update strategy needed
• Trade-off between solution accuracy and numerical stability

Convergence Analysis

Theoretical Convergence Properties

• Convergence of penalty and barrier methods depends on problem structure
• For convex problems, convergence to global optimum often guaranteed
• Rate of convergence influenced by penalty/barrier parameter update strategy
• Asymptotic convergence properties established for various problem classes
• Primal and dual convergence rates may differ

Practical Convergence Considerations

• Finite precision arithmetic affects convergence in practice
• Stopping criteria based on constraint violation and optimality conditions
• Trade-off between solution accuracy and computational efficiency
• Sensitivity analysis helps assess robustness of obtained solutions
• Hybrid methods combine penalty/barrier approaches for improved convergence