 # Inverse problem

Given a point in the decision space, find parameter values that render it optimal. For example, suppose we have the LP: $LaTeX: \min \{c^T x : Ax = b, \,x \ge 0\}$. Let $LaTeX: B$ be a basis from $LaTeX: A$, and we ask for $LaTeX: (b, c)$ for which this basis is optimal. This has a simple solution. Let $LaTeX: A = [B \, N]$ and partition $LaTeX: c$ and $LaTeX: x$ conformally, so $LaTeX: Ax = Bx_B + Nx_N$ and $LaTeX: c^Tx = c^T_Bx_B + c^T_Nx_N$ Then, the set of $LaTeX: (b, c)$ for which the associated basic solution is optimal is the following cone: $LaTeX: K_B = \{ (b, c) : B^{-1}b \ge 0, \, c_B B^{-1}N \le c_N\}.$

A more difficult inverse problem is when there is some target value for the parameters. We might, for example, fix $LaTeX: b$ and seek to minimize $LaTeX: \|c - c^*\|^2$ subject to $LaTeX: (b, c) \in K_B$, where $LaTeX: c^*$ is a target value for $LaTeX: c$.

The problem can be combinatorial. We might want to minimize $LaTeX: \|c - c^*\|$ for some norm where $LaTeX: c$'s are costs on the arcs or edges of a network. The solution at hand might be a spanning tree or a TSP tour. We might also impose constraints on $LaTeX: c$ directly, such as simple bounds.

The general inverse problem may thus be stated: $LaTeX: \min \{ \|p - p^* \| : p \in P, \, p \in \arg\min \{ f(x; p): x \in F(p)\},$

where $LaTeX: p^*$ is the target, $LaTeX: ||\cdot||$ is some norm, $LaTeX: P$ is a non-empty, closed set, which generally does not contain $LaTeX: p^*$, and $LaTeX: F(p)$ is the feasible region for $LaTeX: x$, given $LaTeX: p$.

There are variations, such as when only a partial solution is given. An example is a partial TSP tour or some partial scheduling of jobs, and we ask for cost values for which there is an optimal

solution that contains these subsets.