Exact penalty functions are game-changers in optimization. They transform tricky constrained problems into unconstrained ones, making them easier to solve. This approach bridges the gap between theory and practical problem-solving.

L1 and L∞ penalty functions are the stars of the show. They work by penalizing constraint violations, pushing solutions towards feasibility. With the right penalty parameter, these functions can find the exact solution to the original problem.

Penalty Functions

L1 and L∞ Penalty Functions

• L1 penalty function sums absolute values of constraint violations
  • Defined as $P_1(x) = f(x) + \rho \sum_{i=1}^m |h_i(x)| + \rho \sum_{j=1}^p \max\{0, g_j(x)\}$
  • Produces piecewise smooth optimization problem
• L∞ penalty function takes maximum of constraint violations
  • Defined as $P_\infty(x) = f(x) + \rho \max\{|h_i(x)|, \max\{0, g_j(x)\}\}$
  • Results in minimax optimization problem
• Both L1 and L∞ penalty functions are exact for sufficiently large penalty parameter ρ
• Penalty functions transform constrained optimization problems into unconstrained ones
• L1 and L∞ penalty functions exhibit non-differentiability at constraint boundaries

Exact Penalty Parameters and Merit Functions

• Exact penalty parameter ρ* exists such that for ρ > ρ*, minimizer of penalty function solves original constrained problem
• Determining exact penalty parameter involves analyzing problem structure and constraint qualifications
• Merit functions measure progress in optimization algorithms
  • Combine objective function and constraint violation into single scalar value
  • Used in line search and trust-region methods to assess step quality
• Penalty functions serve as merit functions in many optimization algorithms
• Exact penalty functions allow solving constrained problems through series of unconstrained minimizations

Optimization Techniques

Nonsmooth Optimization Methods

• Nonsmooth optimization addresses problems with non-differentiable objective functions or constraints
• Subgradient methods generalize gradient descent for nonsmooth functions
  • Use subgradients instead of gradients to determine descent directions
  • Slower convergence compared to smooth optimization methods
• Bundle methods accumulate subgradient information to build model of nonsmooth function
  • Combine ideas from cutting-plane and trust-region methods
  • Effective for convex nonsmooth problems
• Smoothing techniques approximate nonsmooth functions with smooth ones
  • Allow use of standard smooth optimization algorithms
  • Examples include Moreau-Yosida regularization and log-sum-exp approximation
• Nonsmooth optimization crucial for handling exact penalty functions in constrained optimization

Augmented Lagrangian Methods

• Augmented Lagrangian methods combine penalty functions with Lagrange multiplier techniques
• Augmented Lagrangian function defined as $L_A(x, λ, μ; ρ) = f(x) + λ^T h(x) + μ^T g(x) + \frac{ρ}{2}(||h(x)||^2 + ||max\{0, g(x)\}||^2)$
• Method alternates between minimizing Augmented Lagrangian and updating multipliers
• Advantages over pure penalty methods:
  • Avoids ill-conditioning associated with large penalty parameters
  • Can achieve exact solutions with finite penalty parameters
• Augmented Lagrangian methods applicable to both smooth and nonsmooth problems
• Variations include method of multipliers and alternating direction method of multipliers (ADMM)

Constraint Handling

Constraint Violation Measurement and Reduction

• Constraint violation measures deviation from feasible region
  • For equality constraints: $v_h(x) = ||h(x)||$
  • For inequality constraints: $v_g(x) = ||max\{0, g(x)\}||$
• Total constraint violation often defined as $v(x) = v_h(x) + v_g(x)$
• Optimization algorithms aim to reduce constraint violation while improving objective function
• Feasibility restoration phase in some algorithms focuses solely on reducing constraint violation
• Constraint violation used in:
  • Penalty function formulation
  • Merit function definition
  • Feasibility checks in optimization algorithms
• Constraint scaling important for balancing different constraint types and magnitudes
• Active-set methods identify binding constraints to simplify constraint handling
  • Reduces problem dimension by focusing on active constraints
  • Allows application of equality-constrained optimization techniques