Interior point algorithm of O(√m| ln ε|) iterations for C1-convex programming

Jie Sun, Liqun Qi

Research output: Journal article publicationJournal articleAcademic researchpeer-review

6 Citations (Scopus)

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 languageEnglish
Pages (from-to)239-257
Number of pages19
JournalMathematical Programming, Series B
Volume57
Issue number2
Publication statusPublished - 2 Nov 1992
Externally publishedYes

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

Cite this