Results 1 to 1 of 1

Thread: Maximality with respect to inclusion

  1. #1
    Member
    Joined
    Feb 2009
    Posts
    98

    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.
    Last edited by math8; Nov 26th 2012 at 09:58 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Inclusion/Exclusion
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 3rd 2009, 08:46 AM
  2. Inclusion map
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: Oct 22nd 2009, 09:48 AM
  3. inclusion/exclusion
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Nov 18th 2008, 10:31 PM
  4. 2 rectangles inclusion
    Posted in the Geometry Forum
    Replies: 0
    Last Post: Oct 8th 2008, 01:02 AM
  5. Set Inclusion
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Dec 9th 2006, 02:32 PM

Search Tags


/mathhelpforum @mathhelpforum