Processing math: 100%

Monday, December 21, 2015

Exact minimization of the linearly perturbed distance of a point to a closed convex set

Let a, b \in \mathbb R^n, and C be a nonempty closed convex subset of \mathbb{R}^n with a \not \in C. Consider the problem \text{minimize }\|x-a\| + b^Tx\text{ subject to } x \in C. The case b = 0 corresponds to the well-known problem of projecting the point a onto C. This problem can be easy or difficult, depending on the geometry of C (for example, the latter problem is rather easy if C is a diamond-shaped polyhedron, or an oval). However the perturbative case b \ne 0 is completely non-trivial and must be treated rather carefully. That notwithstanding, we show here that the case \|b\| < 1 is essentially equivalennt to the non-perturbative case b = 0.

No comments:

Post a Comment