# Optimum exists but not extreme point in Standard Form LP problem?

Standard form problem

$$\min \bar c^T \bar x \text{ so that } A \bar x=\bar b, \bar x\geq \bar 0$$

I am thinking the point II (Finnish) i.e. optimum exists but it is not extreme point, why it cannot be a standard form problem? Basically, can standard-form problem have the matrix $A$ a zero matrix and the vector $\bar b$ a zero vector?

Wikipedia states no non-zero constraints for $A$ or $\bar b$. There may be simpler explanation for the statement "Optimum exists but not extreme point in Standard Form LP problem".

-
Your example isnt a linear programming problem, since $f(x)=-1/x$ cannot be written in the form of $f(x)=c^Tx$... – qmsource Feb 27 '13 at 22:54
Because $x \mapsto \frac{1}{x_1}$ is not linear... The cost must be of the form $\sum_k c_k x_k$. – copper.hat Feb 27 '13 at 23:06
Linear means what I just wrote, the cost must be of the form $\sum_k c_k x_k$. – copper.hat Feb 27 '13 at 23:09
$x \in \mathbb{R}^n$ is the design variable. It is what you are trying to solve for. – copper.hat Feb 27 '13 at 23:10
Any point will solve $\min_x 0x$. – copper.hat Feb 27 '13 at 23:44

## 1 Answer

Only one of them is right at once. In standard form problem, you have always at least one extreme point hence the condition II cannot be correct with standard form problems.

So only one of them is correct each time with feasible non-empty unbounded set:

1. Optimum exists and it is extreme point

2. Optimum exists but no extreme point

3. The cost in optimum is $-\infty$

where the condition 2 can never occur with standard-form problem, repeating.

-