Convergence Analysis of an Interior-Point Method for Nonconvex Nonlinear Programming

In this paper, we present global and local convergence results for an interior-point method for nonlinear programming. The algorithm uses an $\ell_1$ penalty approach to relax all constraints, to provide regularization, and to bound the Lagrange multipliers. The penalty problems are solved using a simplified version of Chen and Goldfarb’s strictly feasible interior-point method [6]. … Read more

An Optimization Approach to Computing the Implied Volatility of American Options

We present a method to compute the implied volatility of American options as a mathematical program with equilibrium constraints. The formulation we present is new, as are the convergence results we prove. The algorithm holds the promise of being practical to implement, and we demonstrate some preliminary numerical results to this end. Citation Princeton University … Read more

Convergence Analysis of an Interior-Point Method for Mathematical Programs with Equilibrium Constraints

We prove local and global convergence results for an interior-point method applied to mathematical programs with equilibrium constraints. The global result shows the algorithm minimizes infeasibility regardless of starting point, while one result proves local convergence when penalty functions are exact; another local result proves convergence when the solution is not even a KKT point. … Read more

Interior-Point Algorithms, Penalty Methods and Equilibrium Problems

In this paper we consider the question of solving equilibrium problems—formulated as complementarity problems and, more generally, mathematical programs with equilibrium constraints (MPEC’s)—as nonlinear programs, using an interior-point approach. These problems pose theoretical difficulties for nonlinear solvers, including interior-point methods. We examine the use of penalty methods to get around these difficulties, present an example … Read more