A Smoothing Method For An Inverse Linear Programming Problem

Inverse optimization problems are widely used in many fields, and it has drawn in-creasing attentions from scholars in recent years.There are many important results about inverse linear programming problems, however we do not see much deep study on effective methods for l∞-norm inverse problems for linear programming.Therefore, this disserta-tion focuses on the study of numerical methods for a class of l∞-norm inverse linear programming problems in which the parameters in the objective function of a given linear programming problem are adjusted as little as possible so that a known feasible solution becomes the optimal one.In this paper,we formulate this inverse problem into an opti-mization problem with only equality constraints,and solve this problem with a Newton method.The main results obtained in this dissertation can be summarized as follows:1,In chapter 1, we first introduce the background and current research of inverse optimization.Then we describe the l∞-norm inverse problem of the linear programming considered in this thesis.2,Chapter 2 is devoted to give some basic results of optimization problems which are needed in inverse problem's formulating and the convergence analysis.3,In chapter 3, we first introduce the maximum entropy method and Fischer-Burmeister function to smooth the inverse linear programming problem, and demonstrate that the optimal solution of the perturbation problem converges to that of the original problem.As the perturbation problem is a nonlinear programming with only equality con-straints, its KKT condition can be reformulated as a system of smooth equations.So we present the KKT condition of the perturbation problem, and prove the non-singularity of Jacobi matrix. 4,In chapter 4, a Newton method is constructed to solve the perturbation prob-lem,which is proved to have both global and local quadratic convergences.5,In chapter 5, numerical experiments are reported to verify the effectiveness of the proposed method.