TY - JOUR

T1 - A new potential reduction algorithm for smooth convex programming

AU - Chu, Liang Ju

PY - 1998

Y1 - 1998

N2 - 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.

AB - 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.

KW - Arithmetic operation

KW - Potential reduction algorithm

KW - Smooth convex programming

KW - Strict feasibility

UR - http://www.scopus.com/inward/record.url?scp=26444471950&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=26444471950&partnerID=8YFLogxK

U2 - 10.1080/02331939808844411

DO - 10.1080/02331939808844411

M3 - Article

AN - SCOPUS:26444471950

VL - 44

SP - 235

EP - 262

JO - Optimization

JF - Optimization

SN - 0233-1934

IS - 3

ER -