Sensitivity analysis in conic optimization

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.

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.

• Thank you. Good point. I am guessing there are some non-degeneracy assumptions that make sure you can avoid this situation? – Barrett May 6 '14 at 6:28
• In the special case of LP, if an optimal BFS is non-degenerate then the result holds. I think this is equivalent to "perturbations preserve the optimal partitions." – Brian Borchers May 6 '14 at 13:12

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.)

• This is the sort of result I am interested in, but I think I don't think I can directly apply this result because the function is being optimized over the whole vector space V, so it avoids the issue of having constraints that must be satisfied. – Barrett May 6 '14 at 18:35
• But, $\Phi$ is allowed to take on the value $+\infty$, to enforce constraints. So I think it will be possible to put your problem into this framework. – littleO May 6 '14 at 19:55
• Let's assume $A$ has full rank and $m < n$, and that the primal optimal value is finite. You could let $\Phi(u,p) = \langle c, u \rangle + I_K(u) + I_0(Au - b - p)$, where $I_K$ is the indicator function of $K$, and $I_0$ is the indicator function of $\{0\}$. I'm not sure about this, but I'm guessing that if you assume there exists $u_0$ in the interior of $K$ such that $A u_0 = b$, then it will follow that $h$ is continuous at $0$. This is similar to Slater's condition. I don't think the argument I posted applies exactly, but perhaps something similar would work. – littleO May 6 '14 at 20:01
• I see. Thanks. I will look into it. – Barrett May 7 '14 at 16:53

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?

• This is a very poor answer: first, it contains an URL, which might disappear over time; second, it is very brief and does not really attempt to give a specific answer to the question, therefore it should rather be a comment; third, it links to a bibliography containing 1082 titles about everything related to semidefinite and cone programming, without telling the OP what title to look for among these. A truly poor answer. – Alex M. Aug 10 '17 at 16:39