# Necessary conditions for a linear program

• sdevoe
In summary, the problem involves an optimization problem with constraints and the need to find necessary and sufficient conditions for a given point to be a local minimum. This is done by looking at points near the given point and examining conditions of first order in small t. The conditions on the constraints and the objective function must be determined in order for the given point to be a local minimum. Differentiability is assumed for the constraints and objective function.
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.

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

sdevoe said:

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

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

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

sdevoe said:
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

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

sdevoe said:
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

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

## 1. What are the necessary conditions for a linear program?

In order for a linear program to be solvable, there are three necessary conditions that must be met: the objective function must be linear, the constraints must be linear, and the variables must be continuous.

## 2. What does it mean for the objective function to be linear in a linear program?

A linear objective function is one that can be written in the form of c1x1 + c2x2 + ... + cnxn, where ci represents the coefficients and xi represents the variables.

## 3. Can a linear program have nonlinear constraints?

No, a linear program must have linear constraints in order to be solvable. Nonlinear constraints would result in a non-linear program, which requires different methods of optimization.

## 4. What is the significance of the variables being continuous in a linear program?

Continuous variables are those that can take on any value within a given range. In a linear program, this means that the variables can take on fractional values, which allows for a more precise and accurate solution to be found.

## 5. Are there any other conditions that must be met for a linear program to be solvable?

Yes, there are other conditions that must be met for a linear program to be solvable, such as having a finite feasible region and a bounded objective function. However, these conditions are not as frequently asked about as the three main necessary conditions mentioned above.

• Calculus and Beyond Homework Help
Replies
1
Views
546
• Calculus and Beyond Homework Help
Replies
8
Views
3K
• Calculus and Beyond Homework Help
Replies
8
Views
743
• Calculus and Beyond Homework Help
Replies
2
Views
1K
• Calculus and Beyond Homework Help
Replies
8
Views
2K
• Calculus and Beyond Homework Help
Replies
13
Views
2K
• Special and General Relativity
Replies
1
Views
890
• Set Theory, Logic, Probability, Statistics
Replies
1
Views
258
• Calculus and Beyond Homework Help
Replies
3
Views
2K
• Calculus and Beyond Homework Help
Replies
6
Views
2K