Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: 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?
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook