11.1 Barrier methods

Interior point methods revolutionized optimization by tackling constrained problems from within the feasible region. Barrier methods, a key component, use logarithmic functions to transform constraints into penalties, creating a smooth path to the optimal solution.

This section dives into barrier functions, the central path concept, and algorithms like the primal barrier method and Karmarkar's groundbreaking approach. We'll explore convergence properties and practical considerations for implementing these powerful techniques.

Barrier Functions and Central Path

Logarithmic Barrier Function and Central Path

• Logarithmic barrier function transforms constrained optimization problems into unconstrained ones
• Function takes form $B(x) = -\sum_{i=1}^m \log(g_i(x))$ where $g_i(x)$ represents inequality constraints
• Adds penalty term to objective function, creating new problem $\min f(x) - \mu B(x)$
• Central path consists of optimal solutions to barrier problem for different values of barrier parameter $\mu$
• Path approaches optimal solution of original problem as $\mu$ approaches zero
• Provides smooth trajectory from interior of feasible region to optimal solution

Barrier Parameter and Self-Concordant Functions

• Barrier parameter $\mu$ controls trade-off between original objective and barrier term
• Large $\mu$ emphasizes feasibility, small $\mu$ emphasizes optimality
• Gradually decreasing $\mu$ allows algorithm to approach optimal solution
• Self-concordant functions possess special properties facilitating efficient optimization
• Include logarithmic barrier functions for linear and convex quadratic constraints
• Self-concordance ensures Newton's method converges quickly for barrier problems

Barrier Methods and Algorithms

Primal Barrier Method

• Iterative approach to solving constrained optimization problems
• Starts with strictly feasible point in interior of constraint set
• Solves sequence of barrier problems with decreasing $\mu$
• Each subproblem solved using unconstrained optimization techniques (Newton's method)
• Algorithm steps include:
  1. Choose initial $x_0$ and $\mu_0$
  2. Solve barrier problem for current $\mu$
  3. Update $\mu$ (typically $\mu_{k+1} = \gamma\mu_k$ with $0 < \gamma < 1$)
  4. Repeat until convergence criteria met
• Primal method works directly with original variables

Newton's Method for Barrier Problems

• Applies Newton's method to solve barrier subproblems
• Computes search direction by solving system of linear equations
• Newton step: $\Delta x = -(\nabla^2 f(x) + \mu \nabla^2 B(x))^{-1}(\nabla f(x) - \mu \nabla B(x))$
• Implements line search or trust region methods to ensure sufficient decrease
• Exploits structure of barrier function for efficient computations
• Achieves quadratic convergence rate for each subproblem

Karmarkar's Algorithm

• Groundbreaking polynomial-time algorithm for linear programming
• Utilizes projective transformations and logarithmic barrier function
• Steps of algorithm include:
  1. Transform problem to standard form
  2. Apply projective scaling to current point
  3. Compute search direction using modified Newton step
  4. Update solution and repeat
• Achieves complexity of $O(n^{3.5}L)$ operations, where $n$ is number of variables and $L$ is input size
• Sparked development of interior point methods for various optimization problems

Convergence Analysis

Convergence Properties and Rates

• Barrier methods exhibit polynomial complexity for linear and convex quadratic programming
• Primal barrier method converges to KKT point of original problem as $\mu \to 0$
• Convergence rate depends on problem structure and algorithm parameters
• For self-concordant functions, Newton's method achieves quadratic convergence for each subproblem
• Overall complexity typically $O(\sqrt{n}L)$ iterations for linear programming
• Primal-dual methods often achieve faster practical convergence than pure primal methods

Theoretical and Practical Considerations

• Gap between primal and dual objectives provides natural stopping criterion
• Complementarity measure $\mu m$ (where $m$ is number of constraints) indicates closeness to optimality
• Trade-off between number of outer iterations (barrier parameter updates) and inner iterations (Newton steps)
• Practical implementations often use adaptive strategies for updating $\mu$
• Warm-start techniques can significantly improve performance for sequences of related problems
• Preconditioning and scaling crucial for numerical stability and efficiency in large-scale problems