Let there be given a parametric linear programming problem with a corresponding solution set mapping $\Psi: \Bbb R^n\to 2^{\Bbb R^n}$, and some point $x^0\in \Bbb R^n$. Then, the inverse linear programming problem $$\min_{x,y}\{\| x-x^0\|: x\in \Psi(y), y\in Y\}$$ consists in finding a value $y^0$ in some set $Y$ such that the distance of $x^0$ to the solution set $\Psi(y^0)$ is minimal. This problem is a special case of a bilevel programming problem [1]. It is a continuous, but nondifferentiable optimization problem with a implicitly determined feasible set. In the talk, focus is on different (necessary as well as sufficient) optimality conditions for this problem. Necessary optimality conditions can be given as nonexistence of feasible descent directions [2] in primal formulation or in a dual one as Fritz-John respectively Karush-Kuhn-Tucker conditions [3]. Using the special structure of the inverse problem stronger formulations can be given.
References
[1] S. Dempe: Foundations of Bilevel Programming, Kluwer Academie Publishers, Dordrecht, 2002.
[2] J.-S. Pang and M. Fukushima: Complementarity constraint qualifications and simplified B-stationarity conditions for mathematical programs with equilibrium constraints, Comput. Optim. Appl. 13(1999), 111-136.
[3] H. Scheel and S. Scholtes: Mathematical programs with equilibrium constraints: stationarity, optimality, and sensitivity, Mathematics of Operations Research, 25(2000), 1-22.
Last modified: Mon Sep 28 16:09:42 CEST 2004