## Abstract

We 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 O(√m| 1n ε|) 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, our result indicates the theoretical feasibility of applying interior point methods to certain C1-optimization problems instead of C2-problems. Since the complexity bound is unchanged compared with similar algorithms for C2-convex programming, the result shows that the smoothness of functions may not be a factor affecting the complexity of interior point methods.

Original language | English |
---|---|

Pages (from-to) | 239-257 |

Number of pages | 19 |

Journal | Mathematical Programming, Series B |

Volume | 57 |

Issue number | 2 |

Publication status | Published - 2 Nov 1992 |

Externally published | Yes |

## ASJC Scopus subject areas

- Computer Graphics and Computer-Aided Design
- Software
- Management Science and Operations Research
- Safety, Risk, Reliability and Quality
- Mathematics(all)
- Applied Mathematics

## Fingerprint

Dive into the research topics of 'Interior point algorithm of O(√m| ln ε|) iterations for C^{1}-convex programming'. Together they form a unique fingerprint.