Analysis of a Path Following Method for Nonsmooth Convex Programs

Sanjay Mehrotra (mehrotraiems.nwu.edu)
Muhittin Ozevin (ozeviniems.nwu.edu)

Abstract: Recently Gilbert, Gonzaga and Karas [2001] constructed examples of ill-behaved central paths for convex programs. In this paper we show that under mild conditions the central path has sufficient smoothness to allow construction of a path-following interior point algorithm for non-differentiable convex programs. We show that starting from a point near the center of the first set an $\epsilon$-optimal solution can be obtained in a finite number of iterations converging linearly.

Keywords: Convex Programming Nonsmooth Optimzation Interior Point Methods

Category 1: Convex and Nonsmooth Optimization

Citation:

Download: [Postscript][PDF]

Entry Submitted: 07/16/2002
Entry Accepted: 07/16/2002
Entry Last Modified: 07/16/2002

Modify/Update this entry