primal-dual interior- point methods for linear problems

Hi,

I would like to write an algorithm in matlab and I have a problem. I hope you can help me.

The algorithm is supposed to solve linear programm min c'x s.t. Ax=b, with A being a sparse matrix (for example dimension 153x366).

First some definitions

A \in R^(mxn), b \in R^m, c \in R^n, y \in R^m, x \in R^n, s \in R^n

F={(x,y,s) | Ax=b, A'y+s=c,x>0,s>0}

A,b,c are given

In the first step I have to find a starting point

(x0,y0,s0) \in F

I found a way to receive an infeasible starting point that holds x>0,s>0, but with this starting point the algorithm doesn't terminate and runs on forever.

Is there a way for Matlab to find (x0,y0,s0) \in F ?

Tanks for your help in advance.

Answer 1

[Torsten]

Use "linprog" with objective function min: 0'*x.