Solving linear optimization problems using a simplex like boundary point method in dual space

Abstract: This thesis treats an algorithm that solves linear optimization problems. The algorithm is based on a similar idea as the simplex method but in this algorithm the start value also might be an inner point or a boundary point at the feasible region. The start value does not necessarily have to be a corner point that the simplex algorithm demands. The algorithm solves problems in standard form. That means that the constraints are with equality and every variable must be positive. The algorithm operates in the dual space to the original problem. During the progress of the algorithm the iteration points will be on the boundary at the feasible region to the dual problem and finally end up in a corner. Afterwards the iteration values go from corner to corner until finally the optimum is reached, just like the simplex algorithm. The expected time to solve linear optimization problems with this algorithm seems to be polynomial in time with respect to the size of the problem, thought the worst case behavior has not been analyzed. If the last iteration value is just an approximate solution to the dual problem the algorithm will transfer it to a quite good approximation to the primal problem. Much of the development in this thesis is a continuation of a similar algorithm which was done one year ago. In the introduction and in the second chapter different forms of linear optimization problems are described. The algorithm is implemented in Matlab and the code can be find in the appendices of this paper. There are also different versions, which solve different types of problems. One for general problems and one for network flow problems.