Sensitivity analysis in conic optimization

Question

I have a conic optimization of the form:

$$\min_x \langle c, x \rangle,\ \text{s.t.}\ Ax = b,\ x \in K.$$

where $x \in \mathbb{R}^{n}$, $A$ is an $m \times n$ matrix, $b \in \mathbb{R}^m$, $K$ is a self dual cone in $\mathbb{R}^n$ and $\langle~,~\rangle$ is the standard Euclidean inner product on $\mathbb{R}^n$.

I am looking for conditions under which the optimal value function is a continuous function of perturbations in the vector $b$. In particular, if we replace $b$ with $b + \Delta b$, so the linear constraint becomes $Ax = b + \Delta b$, and if we let $\phi ( \Delta b)$ denote the optimal value of this perturbed problem, I am interested in when $| \phi(0) - \phi(\Delta b) | \rightarrow 0$ as $\| \Delta b\|_{\infty} \rightarrow 0$.

I have seen results that show $\phi(\Delta b)$ is a linear function in $\Delta b$ for perturbations that preserve the optimal partitions, but I am interested in the case when the optimal partition is not necessarily preserved.

Answer 1

In general, your problem can become infeasible under arbitrarily small perturbations $\Delta b$. For example, consider the problem

$\min X_{11}+X_{22}$

subject to

$X_{11}=0$

$X_{22}=0$

$X \succeq 0$.

The only feasible solution $X=0$, and the problem becomes infeasible if $\Delta b_{1}$ or $\Delta b_{2}$ is negative.

The book "Perturbation Analysis of Optimization Problems" by Bonnans and Shapiro has some relevant theorems, but as I recall, there's nothing really useful.

Answer 2

I'm not sure, but the proof of Proposition 2.3 in Ekeland and Temam might be relevant. I'll summarize / quote from Ekeland and Temam:

Assume that $\Phi$ is a closed, convex, proper function on $V \times Y$, where $V$ and $Y$ are (Hausdorff) topological vector spaces. (Perhaps for simplicity we should just assume $V$ and $Y$ are finite dimensional inner product spaces over $\mathbb R$.) For $p \in Y$ let \begin{equation} h(p) = \inf_{u \in V} \Phi(u,p). \end{equation}

(So $h$ is the optimal value function. The unperturbed primal problem is to minimize $\Phi(u,0)$ with respect to $u$.)

Assume that $\inf_u \Phi(u,0)$ is finite and that \begin{equation} \text{There exists $u_0 \in V$ such that $p \mapsto \Phi(u_0,p)$ is finite and continuous at $0 \in Y$.} \end{equation}

(This assumption can be compared with Slater's condition.)

The proof of Proposition 2.3 argues as follows:

Note that $h$ is convex and $h(0)$ is finite. As the function $p \mapsto \Phi(u_0,p)$ is convex and continuous at $0 \in Y$, there exists a neighborhood $\mathcal V$ of $0$ in $Y$, on which this function is bounded above: \begin{equation} \Phi(u_0,p) \leq M < +\infty, \quad \forall p \in \mathcal V. \end{equation} But \begin{equation} h(p) = \inf_{u \in V} \Phi(u,p) \leq \Phi(u_0,p) \leq M, \quad \forall p \in \mathcal V \end{equation} from which it follows (by proposition I.2.5 in Ekeland and Temam) that $h$ is continuous at $0$.

(Corollary I.2.5 states that every closed convex function on a Banach space is continuous over the interior of its effective domain.)

(Most of what I've written is taken word from word from Ekeland and Temam.)

Answer 3

This bibliography should help:

"Semidefinite and Cone Programming Bibliography/Comments", Henry Wolkowicz, 2011 (http://www.math.uwaterloo.ca/~hwolkowi/henry/software/sdpbibliog.pdf)

...or have you settled the question in the meantime?