Linear superiorization for infeasible linear programming
Abstract: Linear superiorization (abbreviated: LinSup) considers linear programming (LP) problems wherein the constraints as well as the objective function are linear. It allows to steer the iterates of a feasibility-seeking iterative process toward feasible points that have lower (not necessarily minimal) values of the objective function than points that would have been reached by the same feasiblity-seeking iterative process without superiorization. Using a feasibility-seeking iterative process that converges even if the linear feasible set is empty, LinSup generates an iterative sequence that converges to a point that minimizes a proximity function which measures the linear constraints violation. In addition, due to LinSup's repeated objective function reduction steps such a point will most probably have a reduced objective function value. We present an exploratory experimental result that illustrates the behavior of LinSup on an infeasible LP problem.
Keywords: Superiorization; perturbation resilience; infeasible linear programming; feasibility-seeking; simultaneous projection algorithm; Cimmino method; proximity function.
Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )
Category 2: Nonlinear Optimization (Constrained Nonlinear Optimization )
Citation: In: Discrete Optimization and Operations Research, Editors: Y. Kochetov, M. Khachay, V. Beresnev, E. Nurminski and P. Pardalos, Lecture Notes in Computer Science (LNCS), Vol. 9869, 2016, Springer International Publishing, pp. 15-24. DOI:10.1007/978-3-319-44914-2_2.
Entry Submitted: 10/06/2016
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|