Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
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
show 7 more comments

1 Answer

up vote 0 down vote accepted

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.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.