Optimization Online


Linear superiorization for infeasible linear programming

Yair Censor(yair***at***math.haifa.ac.il)
Yehuda Zur(yehuda.zur.89***at***gmail.com)

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.

Download: [PDF]

Entry Submitted: 10/06/2016
Entry Accepted: 10/07/2016
Entry Last Modified: 10/06/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society