# Necessary conditions for a linear program

1. Mar 19, 2012

### sdevoe

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. Mar 19, 2012

### Ray Vickson

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 > 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

3. Mar 19, 2012

### sdevoe

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

4. Mar 19, 2012

### Ray Vickson

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

5. Mar 20, 2012

### sdevoe

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

6. Mar 20, 2012

### Ray Vickson

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

7. Mar 21, 2012

### sdevoe

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