# Maximality with respect to inclusion

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

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

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

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

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

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

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