TITLE:               Interior-Point L_2-Penalty Methods for Nonlinear Programming
                         (Joint with D. Goldfarb)
 
SPEAKER:         Lifeng Chen, Ph.D candidate in Operations Research at
                          Columbia University
 
DATE / TIME:    Friday, February 16, 2007 / 2:30-3:45 p.m.
 
LOCATION:      Room 451 Mohler Lab, 200 W. Packer Avenue
 
ABSTRACT:  Recent investigation has indicated that direct extension of interior-point methods (IPMs) for LP to nonlinear programming (NLP) is intrinsically unsafe.  Specifically, to guarantee proper convergence, most existing IPMs for NLP assumed that the gradients of critical constraints are linearly independent either on the feasible region or on the entire space of variables.  This assumption was observed to result in failures of IPMs for many well-posed problems even with only a few variables.
 
To address this problem, we propose an interior-point l_2-penalty method for nonlinear programming. We show that the constraint violation measured in the Euclidean norm provides a perfect regularization to the Newton system solved at each IPM iteration.  In particular, we prove that the regularized Newton step is a descent direction for the l_2-merit function.  This enables us to establish strong global convergence results for the proposed method.  We prove that the method either converges to a Karush-Kuhn-Tucker (KKT) point of the NLP problem or a Fritz-John point at which the Mangasarian-Fromovitz constraint qualification (MFCQ) fails to hold, or identifies a stationary point for the infeasibility measure which implies the problem is locally infeasible.  We also prove that the method converges locally quadratically for a fixed barrier parameter and superlinearly (arbitrarily close to quadratically) for a decreasing sequence of barrier parameters.  Comprehensive numerical results show that the proposed method is very competitive with state-of-the-art IPM codes.
 
NLP algorithms find global solutions for convex problems, while may yield only local solutions for non-convex problems. If there is still time, I will briefly discuss work on some chance constrained non-matroid problems for which local solutions are used to recover global solutions.  We show that these problems are not NP-hard by proving the quasi-polynomial complexity of the local solution precedure.  Instances include shortest path, matching, max-cut on planar graphs, etc.
 
BIOGRAPHY:  Lifeng Chen is a forth-year Ph.D student in Operations Research at Columbia University.  Before he earned a M.S in Operations Research and a B.S in Computational Mathematics from Shandong University. of Sci. & Tech.  His research interests center on nonlinear programming, complementarity and equilibrium systems, robust optimization, combinatorial optimization and mixed integer programming.
 
ALL FULL-TIME ISE DEPT. GRADUATE STUDENTS ARE REQUIRED TO ATTEND
REFRESHMENTS WILL BE SERVED FOLLOWING THE SEMINAR