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 -