Introductory Lectures on Convex Optimization: A Basic Course

It was in the middle of the 1980s, when the seminal paper by Kar- markar opened a new epoch in nonlinear optimization. The importance of this paper, containing a new algorithm for linear op- timization problems, was not only in its complexity bound. At that time, the most surprising feature of this algorithm was that the theoretical pre- diction of its high efficiency was supported by excellent computational results. This unusual fact dramatically changed the style and direc- tions of the research in nonlinear optimization. Thereafter it became more and more common that the new methods were provided with a complexity analysis, which was considered a better justification of their efficiency than computational…