1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Necessary conditions for a linear program

  1. Mar 19, 2012 #1
    1. The problem statement, all variables and given/known data

    Consider the following optimization problem:

    min f(x)

    s.t. g(x) ≥ 0
    h(x) ≤ 0
    q(x) = 0
    
    Let xbar satisfy g(x) = h(x) = q(x) = 0.
    a)State and prove a set of necessary and sufficient conditions for x to be a local minimum.

    b)How would the conditions change if g(x) = q(x) = 0; h(x) < 0? You do not have to
    present the proof for this case. Just write down the new set of conditions.

    2. Relevant equations

    NONE

    3. The attempt at a solution

    I am completely stumped on this one. Besides the obvious x must lie within the region. Is there something to do with the region only being one point and not an actual region
     
  2. jcsd
  3. Mar 19, 2012 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    In such problems, the standard approach is to look at points near xbar. That is, let [itex] \textbf{x} = \bar{\textbf{x}} + t \textbf{p}, \; t > 0, \; t \text{ small }, [/itex] and to look at conditions of first order in small t (that is, taking first differentials). What are the conditions on [itex] \textbf{p} [/itex] in order that [itex] g(\bar{\textbf{x}} + t \textbf{p}) \geq 0, \text{ that } h(\bar{\textbf{x}} + t \textbf{p}) \leq 0, \text{ and that } q(\bar{\textbf{x}} + t \textbf{p}) = 0 [/itex]? For all such [itex] \textbf{p} [/itex], what are the conditions on f that guarantee [itex] f(\bar{\textbf{x}} + t \textbf{p}) \geq f(\bar{\textbf{x}})[/itex]?

    RGV
     
  4. Mar 19, 2012 #3
    The only thing that I can come up with is maybe the P must be positive definite.
     
  5. Mar 19, 2012 #4

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Absolutely not. The object p is a vector, not a matrix. And, anyway, you still need to answer the questions about g, h and q.

    RGV
     
  6. Mar 20, 2012 #5
    Must g,h and q be differentiable around those points where p(x)=h(x)=q(x)=0?
     
  7. Mar 20, 2012 #6

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    I think that must be assumed. I don't know what the precise statement was of the problem you were given, but normally in such discussions we assume at least once continuously-differentiable functions.

    RGV
     
  8. Mar 21, 2012 #7
    I am obviously lost. What direction should I be looking in?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Necessary conditions for a linear program
  1. Linear programming (Replies: 2)

  2. Linear Programming (Replies: 0)

  3. Linear Programming (Replies: 0)

Loading...