Maximality continuous concave functions

[math8]

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} for j=1,\cdots, k \} be a polytope; 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.

 

[gopher_p]

Let g(x)=max_{i=1,...,m} f_{i}(x) where f_{i} are continuous concave functions

What are the domain and codomains of the f_i?

let X = \{x: a_{j}^T x \geq b_{j} \}

What are the a_j and b_j? Do the js run over a finite index set?


Not that it really matters though. It looks to me like the bulk of the set up for this problem is smoke and mirrors. It's basically there to define a partial ordering on whatever the domain space of the f_i is using the partial ordering on I\times J (where I is the index set for the f_i and J is the index set for the a_j and b_j) induced by set inclusion.


I would advise you to ask yourself what must be true if a point x is not maximal; i.e. what if x is not "the biggest"?

Edit: Note that, for partial orderings, there is not necessarily a single largest element (there may be many). Also for an arbitrary ordering, we may not have a largest element; though it appears that we do have at least one largest element here (why?).

Edit: I should have said "partial ordering on the power set of I\times J." Sorry about that.

 

[math8]

The f_i are defined on the polytope X and f_i(x) is a real number.

j is an index in a finite index set. The a_j; b_j 's are just vectors with the same dimension as x.

Your question makes me think about Zorn's Lemma which says that "Suppose a partially ordered set P has the property that every chain (i.e. totally ordered subset) has an upper bound in P. Then the set P contains at least one maximal element."

So I am thinking about defining the set:

R=\{ M(x): M(x^*) \subseteq M(x) where x is a special point \} .

I am tempted to say that every totally ordered subset of R has an upper bound in R. (which I don't know how to prove here, I am not even sure why R is would not be empty) If that's the case, then by Zorn's Lemma, there is a maximal point M(\hat{x}) of R and so \hat{x} exists with M(x^*) \subseteq M(\hat{x}).

 

[math8]

I am also thinking about saying that the polytope X is compact, so if the set of "special points " is closed, then it is compact too. And then consider a sequence x_1, x_2, \cdots of special points such that M(x^*) \subseteq M(x_1)\subseteq M(x_2)\subseteq \cdots

Then there exists a subsequence x_{k_i} which converges to a "special point" x'.

Hence M(x_k) \subseteq M(x') for each k, i.e. every totally ordered subset of R has an upperbound in R.


my question is, why is the set of "special points " closed? And also, why would there exist a sequence x_1, x_2, \cdots of special points such that M(x^*) \subseteq M(x_1)\subseteq M(x_2)\subseteq \cdots?

 

[gopher_p]

I think you should run with your Zorn's lemma idea, though you really don't need to use it. Use the finiteness of the index sets to get maximal elements.

As for your issues with showing that certain sets are nonempty, I'll remind you of the reflexive property of "less than or equal to". Hopefully that's enough to get you through.

Also, I should have said "the power set of the disjoint union of I and J" instead of "the power set of I\times J". I'm not sure what's wrong with me today.

 

[math8]

I am trying to think about how I can use the finiteness of the index set I to show that there must be a special point \hat{x} such that M(\hat{x}) \supseteq M(x^*). But I am not sure how to go about it. Can you give another hint?

 

[math8]

hmm let see

Let C = \{M(x) \cup J(x): M(x^*) \cup J(x^*) \subseteq M(x) \cup J(x) , x \in X \}. M(x^*)\cup J(x^*) \in C by the reflexive property of " is contained in or is equal to", so C is not empty.

C is a set of subsets of a (disjoint union) of finite sets. So C contains a maximal element. Call it M(x')\cup J(x'). Assume M(x')\cup J(x') is not maximal with respect to all M(x)\cup J(x) with x \in X (not just the ones in C). Then \exists y \in X s.t. M(x')\cup J(x') is contained properly in M(y)\cup J(y). But then M(x^*) \cup J(x^*)\subseteq M(x')\cup J(x') \subset M(y)\cup J(y), thus M(y)\cup J(y) \in C. Contadiction.
Hence M(x') \cup J(x' ) is maximal, and hence x' is a "special point" such that M(x^*) \cup J(x^*)\subseteq M(x')\cup J(x'). Let x'=\hat{x}

Does this work?

 

[gopher_p]

That's pretty much how I see it. Good job.

 

[math8]

Thanks a lot.