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$

3 Answers 3

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$
2
  • $\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, 2014 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$ May 6, 2014 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$
4
  • $\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, 2014 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, 2014 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, 2014 at 20:01
  • $\begingroup$ I see. Thanks. I will look into it. $\endgroup$
    – Barrett
    May 7, 2014 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$
1
  • 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, 2017 at 16:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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