- #1
math8
- 160
- 0
Let [itex]g(x)=max_{i=1,...,m} f_{i}(x)[/itex] where [itex]f_{i}[/itex] are continuous concave functions and
let [itex]X = \{x: a_{j}^T x \geq b_{j} [/itex] for [itex] j=1,\cdots, k \}[/itex] be a polytope; [itex]M(x) = \{i: f_{i}(x) = g (x) \}[/itex] and [itex]J(x) = \{j: a_{j}^T x = b_{j} \}[/itex].
We define a "special" point to be a point [itex]\hat{x}[/itex] for which the set [itex]M(\hat{x}) \cup J(\hat{x}) [/itex] is maximal, i.e., there is no point [itex]y \in X[/itex] for which [itex]M(\hat{x})[/itex] is properly contained in [itex]M(y)[/itex] and [itex]J(\hat{x})[/itex] is properly contained in [itex]J(y)[/itex].
Assume [itex]x^*[/itex] is the minimizer of [itex]g[/itex] (i.e. [itex] g(x^*) \leq g(x) [/itex] for any [itex]x \in X[/itex] ).
We show there exists a "special point" [itex]\hat{x}[/itex] such that
[itex] M(x^*) \subseteq M(\hat{x})[/itex] and [itex] J(x^*) \subseteq J(\hat{x})[/itex].
I am trying to prove by contradiction. So assume there is no "special" point [itex]\hat{x}[/itex] for which [itex] M(x^*) \subseteq M(\hat{x})[/itex]. Let [itex] \hat{x}[/itex] be a "special point". Hence, there exist an [itex] i \in M(x^*)[/itex] such that [itex] i \notin M(\hat{x})[/itex].
So we have [itex] f_{i}(x^*) = g(x^*) \leq g(\hat{x}) \neq f_{i}(\hat{x})[/itex]
I think the contradiction comes from the maximality of [itex]M(\hat{x})[/itex]. But I am not sure how to prove this.
I also think that the part with [itex] J(x^*) \subseteq J(\hat{x})[/itex] can be proven in a similar way, but I am not sure how.
let [itex]X = \{x: a_{j}^T x \geq b_{j} [/itex] for [itex] j=1,\cdots, k \}[/itex] be a polytope; [itex]M(x) = \{i: f_{i}(x) = g (x) \}[/itex] and [itex]J(x) = \{j: a_{j}^T x = b_{j} \}[/itex].
We define a "special" point to be a point [itex]\hat{x}[/itex] for which the set [itex]M(\hat{x}) \cup J(\hat{x}) [/itex] is maximal, i.e., there is no point [itex]y \in X[/itex] for which [itex]M(\hat{x})[/itex] is properly contained in [itex]M(y)[/itex] and [itex]J(\hat{x})[/itex] is properly contained in [itex]J(y)[/itex].
Assume [itex]x^*[/itex] is the minimizer of [itex]g[/itex] (i.e. [itex] g(x^*) \leq g(x) [/itex] for any [itex]x \in X[/itex] ).
We show there exists a "special point" [itex]\hat{x}[/itex] such that
[itex] M(x^*) \subseteq M(\hat{x})[/itex] and [itex] J(x^*) \subseteq J(\hat{x})[/itex].
I am trying to prove by contradiction. So assume there is no "special" point [itex]\hat{x}[/itex] for which [itex] M(x^*) \subseteq M(\hat{x})[/itex]. Let [itex] \hat{x}[/itex] be a "special point". Hence, there exist an [itex] i \in M(x^*)[/itex] such that [itex] i \notin M(\hat{x})[/itex].
So we have [itex] f_{i}(x^*) = g(x^*) \leq g(\hat{x}) \neq f_{i}(\hat{x})[/itex]
I think the contradiction comes from the maximality of [itex]M(\hat{x})[/itex]. But I am not sure how to prove this.
I also think that the part with [itex] J(x^*) \subseteq J(\hat{x})[/itex] can be proven in a similar way, but I am not sure how.
Last edited by a moderator: