Penalty Methods

The penalty method is a technique for solving constrained optimization problems by converting them into unconstrained problems. It works by adding penalty terms to the objective function that impose a high cost for violating the constraints.

Mathematical Formulation

Consider a constrained optimization problem:

\begin{align} \min_{\theta} \quad & L(\theta) \ \text{subject to} \quad & h_j(\theta) = 0, \quad j = 1,2,\ldots,m \ & I_k(\theta) \geq 0, \quad k = 1,2,\ldots,n \end{align}

where:

• $\theta \in {\mathbb{R}}^D$ is the design vector
• $L(\theta )$ is the objective function to be minimized
• $h_j(\theta )$ are the equality constraint functions
• $I_k(\theta )$ are the inequality constraint functions

The penalty method transforms this into an unconstrained problem:

$P(\theta ,\mu )=L(\theta )+\mu \left[{\sum }_{j=1}^m{h}_j(\theta {)}^2+{\sum }_{k=1}^n\max (0,-I_k(\theta ){)}^2\right]$

where:

• $\mu >0$ is the penalty parameter
• The term $h_j(\theta {)}^2$ penalizes violations of equality constraints
• The term $\max (0,-I_k(\theta ){)}^2$ penalizes violations of inequality constraints

Solution Approach

1. Initialization:

   • Select an initial design point ${\theta }^{(0)}$ (not necessarily feasible)
   • Choose an initial penalty parameter ${\mu }^{(0)}>0$
   • Set a parameter $\gamma >1$ for increasing the penalty parameter
   • Set iteration counter $i=0$

2. Iteration:

   • Solve the unconstrained optimization problem: ${\theta }^{(i+1)}=\arg {\min }_{\theta }P(\theta ,{\mu }^{(i)})$
   • Evaluate constraint violations
   • If constraints are satisfied to desired tolerance, terminate
   • Otherwise, update penalty parameter: ${\mu }^{(i+1)}=\gamma {\mu }^{(i)}$
   • Increment $i$ and repeat

3. Convergence:

   • As $\mu \to \infty$, the solution ${\theta }^{(i)}$ approaches the constrained optimum

Key Properties

Advantages

1. Simplicity: Transforms constrained problems into unconstrained problems
2. Generality: Handles both equality and inequality constraints
3. Initial Point: Can start from infeasible points
4. Implementation: Reuses unconstrained optimization algorithms

Disadvantages

1. Ill-Conditioning: As $\mu$ increases, the problem becomes increasingly ill-conditioned
2. Inexact Constraint Satisfaction: Constraints are only approximately satisfied
3. Slow Convergence: Requires solving multiple unconstrained problems with increasing penalty parameters
4. Parameter Selection: Choosing good values for ${\mu }^{(0)}$ and $\gamma$ can be challenging

Variants of Penalty Methods

Exterior Penalty Method

The standard formulation described above is known as the exterior penalty method because it allows iterates to be outside the feasible region. The solution approaches the feasible region from the exterior as $\mu$ increases.

Interior Penalty Method (Barrier Method)

The interior penalty method adds a barrier term that prevents solutions from leaving the feasible region:

$P(\theta ,\mu )=L(\theta )-\mu {\sum }_{k=1}^n\ln (I_k(\theta ))$

This method requires a strictly feasible initial point. As $\mu \to 0$, the solution approaches the constrained optimum.

Exact Penalty Method

The exact penalty method uses non-differentiable penalty functions such as L1-norm:

$P(\theta ,\mu )=L(\theta )+\mu \left[{\sum }_{j=1}^m|h_j(\theta )|+{\sum }_{k=1}^n\max (0,-I_k(\theta ))\right]$

For sufficiently large but finite $\mu$, this method can yield the exact solution to the constrained problem.

Implementation Considerations

Penalty Parameter Update

The rate at which $\mu$ is increased affects both convergence speed and numerical stability:

• Small $\gamma$ (e.g., $\gamma =2$): Slower convergence but better numerical stability
• Large $\gamma$ (e.g., $\gamma =10$): Faster convergence but potential numerical issues

Unconstrained Optimization Algorithm

The choice of algorithm for solving the unconstrained subproblems depends on problem characteristics:

• Gradient-Based Methods: BFGS, conjugate gradient, or steepest descent
• Derivative-Free Methods: Nelder-Mead simplex or pattern search for non-smooth penalties

Stopping Criteria

Common termination conditions include:

• Maximum constraint violation below tolerance
• Change in objective function or solution vector below tolerance
• Maximum number of iterations or function evaluations reached

Example: Penalty Method Application

Consider the problem:

\begin{align} \min_{\theta_1, \theta_2} \quad & \theta_1^2 + \theta_2^2 \ \text{subject to} \quad & \theta_1 + \theta_2 = 1 \end{align}

Using the penalty method, we form:

$P(\theta ,\mu )={\theta }_1^2+{\theta }_2^2+\mu ({\theta }_1+{\theta }_2-1{)}^2$

For any finite $\mu$, the optimum of $P(\theta ,\mu )$ will be close to but not exactly on the constraint ${\theta }_1+{\theta }_2=1$. As $\mu$ increases, the solution approaches the constrained optimum ${\theta }^{\ast }=(0.5,0.5)$.

Numerical Issues and Remedies

Scaling

Poor scaling of constraints can lead to numerical difficulties. Normalizing constraints to similar magnitudes helps balance their contributions to the penalty term.

Gradual Penalty Increase

Starting with a moderate penalty parameter and gradually increasing it allows the algorithm to adapt to the constrained landscape.

Constraint Prioritization

For problems with multiple constraints, applying different penalty weights to different constraints can improve solution quality.

Theoretical Connections

The penalty method is related to several other optimization concepts:

• Lagrange Multipliers: As $\mu \to \infty$, the ratio of penalty term gradients to $\mu$ approaches the optimal Lagrange multipliers
• Duality Theory: The penalty function provides an upper bound on the optimal dual function value
• Merit Functions: Penalty functions serve as merit functions in line search methods for constrained optimization

Engineering Applications

The penalty method is widely used in engineering for:

• Structural Optimization: Minimizing weight subject to stress and displacement constraints
• Parameter Estimation: Fitting models to data with physical constraints
• Path Planning: Finding optimal trajectories subject to kinematic constraints
• Machine Learning: Regularizing models with equality and inequality constraints

Related Pages

• Constrained Optimization
• Barrier Methods
• Augmented Lagrangian Method
• Inequality Constraints
• Equality Constraints
• KKT Conditions