An interior point algorithm for semi-infinite linear programming (Q1123804): Difference between revisions

A linear programming problem posed over Hilbert space is considered. To solve this problem the authors construct a generalization of the well- known projective interior point method developed by \textit{I. I. Dikin} [Upr. Sist. 17, 60-66 (1978; Zbl 0475.90093)] and \textit{N. Karmarkar} [Combinatorica 4, 373-395 (1984; Zbl 0557.90065)]. Then the proposed method is concretized for semi-infinite linear programming problems. The major work per iteration in the method developed for this case is in the calculation of \(L_ 2\)-inner products required for the Gram-Schmidt procedure. The generalized algorithm is then applied in particular to the Chebyshev and \(L_ 1\)-approximation problems. The finite discretization of the continual set of constraints using various schemes for integrals computation enables to obtain computationally implementable algorithms for the considered problems. The finite-dimensional linear programming problems obtained after discretization are solved by the generalized variant of Dikin-Karmarkar's method. It differs from the original method by using an additional linear transformation with the diagonal positive definite matrix reflecting different integration schemes. Convergence of the finite-dimensional generalization of Dikin-Karmarkar's method is established. Some results of computational experiments over the Chebyshev and \(L_ 1\)-approximation problems using the proposed algorithms are also given.