✦ LIBER ✦

Complexity analysis of logarithmic barrier decomposition methods for semi-infinite linear programming

✍ Scribed by Zhi-Quan Luo; C. Roos; T. Terlaky

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 816 KB
Volume: 29
Category: Article
ISSN: 0168-9274
DOI: 10.1016/s0168-9274(98)00103-2

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper, we analyze a logarithmic barrier decomposition method for solving a semi-infinite linear programming problem. This method is in some respects similar to the column generation methods using analytic centers. Although the method was found to be very efficient in the recent computational studies, its theoretical convergence or complexity is still unknown except in the (finite) case of linear programming. In this paper we present a complexity analysis of this method in the general semi-infinite case. Our complexity estimate is given in terms of the problem dimension, the radius of the largest Euclidean ball contained in the feasible set, and the desired accuracy of the approximate solution.

📜 SIMILAR VOLUMES

Complex Chebyshev approximation for FIR

Complex Chebyshev approximation for FIR filters using linear semi-infinite programming method

✍ Kenji Suyama; Ken'ichi Takada; Ryuichi Hirabayashi; Hiroshi Iwakura 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 922 KB

## Abstract In the optimum design of an FIR filter by the complex Chebyshev method, it is difficult to limit the increase of computational effort and to guarantee convergence to an optimum solution due to the nonlinearity of the problem and the instability of the frequency points for the optima. In