The duality gap in semi-infinite linear programming and the quality analysis of geometrical objects' constraints

The paper focuses on the universal problem of linear programming (LP) with an infinite number of linear constraints and a finite number of variables. The authors demonstrate how the LP problem, which limits use a convex closed cone, is reduced to the above-mentioned one. The geometric interpretation using the conical K shell of the system constraints coefficients is proposed for a pair of the dual LP problems. The other two cones (i.e. the K cone epigraph and hypograph) are additionally constructed to analyze the dual problems. The one-dimensional interval using three cones and the target vector of the original problem is also constructed. The characteristics of the interval allow us to determine the main characteristics of the original problem: the optimal values and the solvability of both problems. The interval lies on the boundary of the multidimensional K cone. With regard to the results achieved, we suggest a qualitative analysis of the geometric method of the semi-infinite LP problem without using either the Gauss method being commonly used or the simplex method. It is shown that the basic information of a pair of the dual problems is contained in the characteristics of the surface of an unclosed convex K cone. A new type of dual problem is put forward for the LP problem. It is different from the classic one based on the Lagrange multipliers. It is sufficient to replace the criterion and the inequalities of constraints signs with the opposite ones. The similarity between the two is in the fact that their characteristics are determined by the epigraph and the hypograph of the K cone. Thus, they equally provide information on the surface of an unclosed K cone. The paper shows that the duality gap is not an unwanted extraordinary case. The existence of a gap indicates the places where the feasible set starts to expand abnormally at infinitesimal relaxation of constraints. Thus, gap analysis allows to determine the "weak" places by setting constraints of a feasible set. Similar problems arise in politics, economy and any other sphere in which various constraints are imposed on a set of objects. We construct numerical example of a semi-infinite LP problem with three variables. The characteristics of the surface of an unclosed four-dimensional K cone are analyzed. It is shown that the target vectors with duality gap do not form an isolated ray and fill the two-dimensional region in. The example of the code allowing to carry out the numerical analysis of duality relations by the use of MATLAB are given. The program is based on such standard optimization functions as fsem'nf and l'nprog designed to find approximate solutions of finite-dimensional linear and non-linear semi-infinite optimization problems respectively. A distinguished feature of the MATLAB program is replacing of а semi-infinite linear programming original problem by a LP problem with a finite number of constraints. It is noted that this substitution may change the optimum value of both problems It is worth mentioning that the authors are planning to develop a new MATLAB-program with the ability for users to specify an infinite sequence of constraints.

Keywords

Authors

References