Necessary conditions for a linear program

[sdevoe]

Homework Statement

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.

Homework Equations

NONE

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

 

[Ray Vickson]

Homework Statement

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.

Homework Equations

NONE

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

In such problems, the standard approach is to look at points near xbar. That is, let \textbf{x} = \bar{\textbf{x}} + t \textbf{p}, \; t &gt; 0, \; t \text{ small }, and to look at conditions of first order in small t (that is, taking first differentials). What are the conditions on \textbf{p} in order that 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? For all such \textbf{p}, what are the conditions on f that guarantee f(\bar{\textbf{x}} + t \textbf{p}) \geq f(\bar{\textbf{x}})?

RGV

 

[sdevoe]

The only thing that I can come up with is maybe the P must be positive definite.

 

[Ray Vickson]

The only thing that I can come up with is maybe the P must be positive definite.

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

 

[sdevoe]

Must g,h and q be differentiable around those points where p(x)=h(x)=q(x)=0?

 

[Ray Vickson]

Must g,h and q be differentiable around those points where p(x)=h(x)=q(x)=0?

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

 

[sdevoe]

I am obviously lost. What direction should I be looking in?