On an Interior Point Algorithm for Non Convex Quadratic Programming

Professor Paul Tseng

ABSTRACT

The simplest and earliest example of an interior point algorithm for linear programming is the affine scaling algorithm of Dikin.This algorithm has been much studied and readily extends to (non convex) quadratic programs (QP).  However, little is known about its behavior on (non convex) QP, even in the case of box constraints. We will present new results on the convergence behavior of the generated iterates and optimality properties of the limit points.  We will also discuss a branch-and-bound strategy for finding local/global minimum in the case of box constraints.The second part of the talk is based on a joint work with Yinyu Ye at Stanford.