Inverse problem

From Glossary

Jump to: navigation, search

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:

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.

Personal tools