# Maximality with respect to inclusion

• Nov 26th 2012, 09:31 AM
math8
Maximality with respect to inclusion
Let $\displaystyle g(x)=max_{i=1,...,m} f_{i}(x)$ where $\displaystyle f_{i}$ are continuous concave functions and
let $\displaystyle X = \{x: a_{j}^T x \geq b_{j} \}$ ; $\displaystyle M(x) = \{i: f_{i}(x) = g (x) \}$ and $\displaystyle J(x) = \{j: a_{j}^T x = b_{j} \}$.

We define a "special" point to be a point $\displaystyle \hat{x}$ for which the set $\displaystyle M(\hat{x}) \cup J(\hat{x})$ is maximal, i.e., there is no point $\displaystyle y \in X$ for which $\displaystyle M(\hat{x})$ is properly contained in $\displaystyle M(y)$ and $\displaystyle J(\hat{x})$ is properly contained in $\displaystyle J(y)$.

Assume $\displaystyle x^*$ is the minimizer of $\displaystyle g$ (i.e. $\displaystyle g(x^*) \leq g(x)$ for any $\displaystyle x \in X$ ).

We show there exists a "special point" $\displaystyle \hat{x}$ such that

$\displaystyle M(x^*) \subseteq M(\hat{x})$ and $\displaystyle J(x^*) \subseteq J(\hat{x})$.

I am trying to prove by contradiction. So assume there is no "special" point $\displaystyle \hat{x}$ for which $\displaystyle M(x^*) \subseteq M(\hat{x})$. Let $\displaystyle \hat{x}$ be a "special point". Hence, there exist an $\displaystyle i \in M(x^*)$ such that $\displaystyle i \notin M(\hat{x})$.
So we have $\displaystyle f_{i}(x^*) = g(x^*) \leq g(\hat{x}) \neq f_{i}(\hat{x})$

I think the contradiction comes from the maximality of $\displaystyle M(\hat{x})$. But I am not sure how to prove this.
I also think that the part with $\displaystyle J(x^*) \subseteq J(\hat{x})$ can be proven in a similar way, but I am not sure how.