A new potential reduction algorithm for smooth convex programming

Research output: Contribution to journalArticle

Abstract

This paper extends and analyzes a new potential reduction algorithm for solving smooth convex programming. Under a kind of strict feasibility assumption, we show that the algorithm under modification requires a total of O((ρ - n)ℓ) number of iterations, and the total arithmetic operations are not more than O(n3ℓ), where n + √2n ≤ ρ ≤ 2n and ℓ is the initial input size. As an application to usual linear or convex quadratic programming, this algorithm solves the pair of primal and dual problems in at most O((ρ - n)L) iterations, and the total arithmetic operations are shown to be of the order of O(n3L), where L is the input size.

Original languageEnglish
Pages (from-to)235-262
Number of pages28
JournalOptimization
Volume44
Issue number3
DOIs
Publication statusPublished - 1998 Jan 1

Keywords

  • Arithmetic operation
  • Potential reduction algorithm
  • Smooth convex programming
  • Strict feasibility

ASJC Scopus subject areas

  • Control and Optimization
  • Management Science and Operations Research
  • Applied Mathematics

Fingerprint Dive into the research topics of 'A new potential reduction algorithm for smooth convex programming'. Together they form a unique fingerprint.

Cite this