Interior-point algorithms for semi-infinite programming
type: Item
instance of: scholarly article
title: Interior-point algorithms for semi-infinite programming
zbMATH Open document ID: 0831.90114
DOI: 10.1007/BF01581697
author: Michael J. Todd
published in: Mathematical Programming. Series A. Series B
publication date: 1994-09-26T00:00:00Z
review text: This paper is concerned with linear semi-infinite programming problems of the following kind: Given \(a: T\to \mathbb{R}^m\), \(\gamma: T\to \mathbb{R}\), \(b\in \mathbb{R}^m\), where \(T\) is a compact measurable subset of some \(\mathbb{R}^p\) with measure 1, the linear functional \(b^T y\), \(y\in \mathbb{R}^m\), has to be maximized subject to \(a(t)^T y\leq \gamma(t)\) for all \(t\in T\). As corresponding dual problem the following is considered: Let \(a\in C(T, \mathbb{R}^m)\) and \(\gamma\in C(T)\). Then the linear functional \(\int_T \gamma(t) \xi(t)dt\), \(\xi\in C(T)\), has to be minimized subject to \[ \int_T \xi(t) a(t)dt= b,\;\xi(t)\geq 0\qquad\text{for all}\quad t\in T. \] These problems are discretized by partitioning \(T\) into \(n\) subregions \(T_j\), \(j=1,\dots, n\), of measure \({1\over n}\). In each \(T_j\) some \(t_j\in T_j\) is chosen and for \(f\in C(T)\) the integral \(\int_T f(t)dt\) is replaced by \({1\over n}\sum^n_{j= 1} f(t_j)\). Then the discretized problem consists of maximizing \(b^T y\), \(y\in \mathbb{R}^m\), subject to \(A^T y\leq c\), where \(A= (a(t_1),\dots, a(t_n))\) and \(c= (\gamma(t_1),\dots, \gamma(t_n))^T\). The discretized dual problem consists of minimizing \(c^T x\), \(x\in \mathbb{R}^n\) subject to \(Ax= b\) and \(x\geq \theta_n\) and is the dual of the discretized problem. The vectors \(x\in \mathbb{R}^n\) then correspond to \({1\over n} (\xi(t_1),\dots, \xi(t_n))^T\) with \(\xi\in C(t)\). If \(n\) is replaced by \(2n\), the discretized problem is close to the problem of maximizing \(b^T y\), \(y\in \mathbb{R}^m\) subject to \(A^T y\leq c\), \(A^Ty\leq c\). The discretized dual problem is close to the problem of minimizing \(c^T x'+ c^T x''\), \(x'\), \(x''\in \mathbb{R}^n\), subject to \(Ax'+ Ax''= b\), \(x',x''\geq \theta_n\). If \(x\) is a feasible solution of the discretized dual problem with respect to \(n\), then \((x', x'')\) with \(x_j'= x_j''= {1\over 2} x_j\) is taken as feasible solution of the discretized…
Mathematics Subject Classification ID: 90C34
Mathematics Subject Classification ID: 65K05
zbMATH DE Number: 644756
zbMATH Keywords: linear semi-infinite programming
zbMATH Keywords: discretized dual problem
zbMATH Keywords: interior point algorithm
zbMATH Keywords: large-step path-following
zbMATH Keywords: potential-reduction
reviewed by: Werner Krabs
MaRDI profile type: Publication
cites work: An implementation of Karmarkar's algorithm for linear programming
cites work: A Mesh-Independence Principle for Operator Equations and Their Discretizations
cites work: Q3770273
cites work: A monotonic projective algorithm for fractional linear programming
cites work: A variation on Karmarkar’s algorithm for solving linear programming problems
cites work: Very Large-Scale Linear Programming: A Case Study in Combining Interior Point and Simplex Methods
cites work: Computing material collapse displacement fields on a Cray X-MP/48 by the LP primal affine scaling algorithm
cites work: Q5583564
cites work: An interior point algorithm for semi-infinite linear programming
cites work: On affine scaling and semi-infinite programming
cites work: An analog of Karmarkar's algorithm for inequality constrained liner programs, with a `new' class of projective transformations for centering a polytope
cites work: Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function
cites work: A variant of Karmarkar's linear programming algorithm for problems in standard form
cites work: A polynomial Newton method for linear programming
cites work: Linear optimization and approximation. An introduction to the theoretical analysis and numerical treatment of semi-infinite programs. Transl. from the German
cites work: Conical projection algorithms for linear programming
cites work: Search directions for interior linear-programming methods
cites work: Interior point algorithms for linear programming with inequality constraints
cites work: Polynomial affine algorithms for linear programming
cites work: Large Step Path-Following Methods for Linear Programming, Part II: Potential Reduction Method
cites work: A survey of search directions in interior point methods for linear programming
cites work: Semi-Infinite Programming: Theory, Methods, and Applications
cites work: A new polynomial-time algorithm for linear programming
cites work: Q3491304
cites work: A polynomial-time algorithm for a class of linear complementarity problems
cites work: An \(O(\sqrt n L)\) iteration potential reduction algorithm for linear complementarity problems
cites work: Convergence results and numerical experiments on a linear programming hybrid algorithm
cites work: Q3348699
cites work: On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming
cites work: Computational experience with a dual affine variant of Karmarkar's method for linear programming
cites work: Interior path following primal-dual algorithms. I: Linear programming
cites work: Interior path following primal-dual algorithms. II: Convex quadratic programming
cites work: Q3496152
cites work: Q4288947
cites work: On the number of iterations of Karmarkar's algorithm for linear programming
cites work: A polynomial-time algorithm, based on Newton's method, for linear programming
cites work: A polynomial method of approximate centers for linear programming
cites work: On the complexity of following the central path of linear programs by linear extrapolation. II
cites work: Q3804467
cites work: Q4733658
cites work: An extension of Karmarkar's algorithm for linear programming using dual variables
cites work: A Centered Projective Algorithm for Linear Programming
cites work: An algorithm for linear programming which requires \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\) arithmetic operations
cites work: A modification of Karmarkar's linear programming algorithm
cites work: An \(O(n^ 3L)\) potential reduction algorithm for linear programming
cites work: Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming
full work available at URL: https://doi.org/10.1007/bf01581697
OpenAlex ID: W2007911602
description: scientific article; zbMATH DE number 644756