Removing Inequalities in the Dynamic Double Description Methods

One of the fundamental problems of the theory of systems of linear inequalities is the transition from the description of the polyhedron in the form to the description and back. This problem has not only theoretical interest, but it also appears in a number of applications: when finding a set of all solutions to the linear programming problem, in the methods of cutting planes for global optimization problems, in biological kinetics, in the analysis, optimization and verification of computer programs, in the problems of identification of the state of dynamic systems and many others. Often in such problems the initial set of constraints Ax ≥ b in can not be fixed, but can be refined. For example, new inequalities may be added to, and some excluded from, the system. Note that the problem of adding constraints seems to be more deeply studied: any incremental algorithm, for example, the method of double description, can be used to reconstruct the description when adding new inequalities in the description. On the contrary, the problem of elimination of inequalities is not well studied. Problem statement. The topic of the given research paper is the analysis of the following problem: taking into account the vertex and phase representations of a convex polyhedron, calculate the vertex representation of the polyhedron defined by the inequality subsystem of the original polyhedron. The aim is the implementation of the dual description algorithm of a polyhedron with a remark about the removal of edges from the description. The research objectives: - learning the double description method - learning incremental method - developing new modification of double description method - proof of correctness of the new algorithm - numerical experiment, comparison with existing algorithms