2

Let

$$g(c) = \min_{Ax=c} f(x),$$

where $x$, $c$ are vector-valued, $A$ is a matrix and $f$ is a smooth convex function. Under what conditions can we say $g(c)$ is continuous in $c$?

Hedonist
  • 1,401

1 Answers1

1

If $A$ is a bijection, then this is trivial, because you only changed coordinates with an affine transformation.

Otherwise, the map $Ax=c$ defines a continuous sequence of "slices" (a linear foliation of space) parameterized by $c$: $X=\{x,Ax=c\}$ is the preimage of $A$ (returns a vector subspace of the dimensionality of the kernel of $A$, with the requirement that $c$ is in the image of $A$, which restricts the domain of $g(c)$).

If $c$ is a scalar ($A$ is of rank $1$, $X$ is a hyperplane of dimension $n-1$), you proceed as such:

When the path of the minimum $\vec{x}(c)$ (where $g(c)=f(\vec{x}(c))$) itself is continuous, there is no problem, because the value of a continuous function on a continuous subdomain is also continuous.

Another possibility would be that two local minima exchange in which is the global minimum. In this case, consider two "trajectories" of local minima: $$g(c)=\min(f(\vec{x}_1(c)),f(\vec{x}_2(c)))$$ Because on both trajectories, the function is continuous, and they interchange, they must have an intersection (there is $c$ where the values are equal). So, $g(c)$ is also continuous in this case.

Moreover, this cannot happen if $f$ is convex: on a hyperplane $X$, which slices the entire space, $f$ is also convex. Therefore, it can only have one extremum, and there is always only one trajectory $\vec{x}(c)$ which is both local and global minimum for a given $c$. Moreover, convexity ensures that the function is bounded from below, so the minimum always exists.

In conclusion, $g(c)$ is continuous if $c$ is a scalar and f is a smooth convex function.

For ranks $r>1$, continuity can be checked line-wise: for every subdomain $\vec{c}=\vec{c}_0+\vec{s}t$ for $t\in \mathbb{R}$, $g(\vec{c}_0+\vec{s}t)$ is continuous for the reasons above. Therefore, it is continuous as a whole (if no "cut" has a jump, the entire thing has no jumps).

orion
  • 15,781