How are these three subjects related? Inconsistency in linear programming occurs in practice due to a variety of causes. Some problems, as for instance, Radiation Treatment Planning, Protein Folding and Digital Video Broadcasting tend to develop formulations that are usually, at a first phase, infeasible. If the model is infeasible, understanding the source of conflicts between constraints is very important. The construction of a definitive feasible model is only possible after a deep and careful infeasibility analysis. One way to repair the model is by finding minimal perturbations of the system coefficients. If the minimization is performed according to the Frobenius norm of the perturbation matrix this leads to a fractional quadratic optimization problem. Globally solving this difficult optimization problem, using for instance a branch and bound approach, requires the construction of good lower bounds. First we show how a fractional quadratic problem with linear constraints can be reformulated as a conic optimization problem using the cone of copositive matrices. Then, replacing the copositive condition by a semidefinite condition a relaxation is obtained, which is easier to solve, and provides a good lower bound. If time permits some new advances for the analysis of inconsistent linear systems will also be presented.
Homepage of Paula A. Amaral