An interior point algorithm of

The authors present a theoretical result on a path-following algorithm for convex programs. The algorithm employs a nonsmooth Newton subroutine. It starts from a near center of a restricted constraint set, performs a partial nonsmooth Newton step in each iteration, and converges to a point whose cost is within accuracy of the optimal cost in iterations, where m is the number of constraints in the problem. Unlike other interior point methods, the analyzed algorithm only requires a first-order Lipschitzian condition and a generalized Hessian similarity condition on the objective and constraint functions. Therefore, the present result indicates the theoretical feasibility of applying interior point methods to certain -optimization problems instead of -problems. Since the complexity bound is unchanged compared with similar algorithms for -convex programming, the result shows that the smoothness of functions may not be a factor affecting the complexity of interior point methods.