An interior point algorithm of {Mathematical expression} iterations for C1-convex programming

Jie Sun, Liqun Qi

Research output: Journal article publicationJournal articleAcademic researchpeer-review

3 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 {Mathematical expression} 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
Volume57
Issue number1-3
DOIs
Publication statusPublished - 1 May 1992
Externally publishedYes

Keywords

  • Complexity of algorithms
  • convergence analysis
  • interior point algorithms
  • Newton's methods

ASJC Scopus subject areas

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

Cite this