0
$\begingroup$

From Convex Optimization:

Let $E_i = \{x \mid f_i(x) \le 0\}$ where $f_i(x) = x^TA_ix + 2b_i^Tx + c_i$ for $ i = 1, 2, \dots, m$ and $A_i \in S^n_{++}$ where $S^n_{++}$ is the set of all positive definite matrices. We then ask when the intersection of these ellipsoids has nonempty interior. This is equivalent to feasibility of the set of strict quadratic inequalities $$f_i(x) = x^TA_ix + 2b_i^Tx + c_i \lt 0 \text{ for } i =1, 2, \dots, m$$

I can see why the inequalities imply the interior because if $f_i(x) \lt 0$, then $f_i(x) \le 0$, but I'm having trouble showing the interior implies the inequalities.

If I start with assuming $\text{int}(\cap E_i) \neq \emptyset$. Then there's an $x$ such that $f_i(x) \le 0$ for all $i$. Assume that the set of inequalities is infeasible, therefore there's $i$ such that $f_i(x) \ge 0$. If $f_i(x) \gt 0$ then I see the contradiction but if $f_i(x) =0$ I'm not sure how to proceed.

Does anyone have any ideas?

$\endgroup$
  • $\begingroup$ There is only one system. The question is asking why showing the intersection is nonempty is the same as showing feasibility of the system. $\endgroup$ – Oliver G Feb 20 at 21:04
0
$\begingroup$

The essence of the result is the following:

Suppose $x^*$ is an interior point of the set $E= \{x | f(x) \le 0 \}$ where $f$ is convex and differentiable. Then either $f(x) = 0$ for all $x \in E$ or $f(x^*) <0$.

In the above case, since the $A_i$ are positive definite, the $f_i$ can never be constant on an open set.

$\endgroup$

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.