3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you. Good point. I am guessing there are some non-degeneracy assumptions that make sure you can avoid this situation? $\endgroup$ – Barrett May 6 '14 at 6:28
  • $\begingroup$ 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." $\endgroup$ – Brian Borchers May 6 '14 at 13:12
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Barrett May 6 '14 at 18:35
  • $\begingroup$ 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. $\endgroup$ – littleO May 6 '14 at 19:55
  • $\begingroup$ 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. $\endgroup$ – littleO May 6 '14 at 20:01
  • $\begingroup$ I see. Thanks. I will look into it. $\endgroup$ – Barrett May 7 '14 at 16:53
1
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Alex M. Aug 10 '17 at 16:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.