Primal-Dual Algorithms for Linear Optimization Based
on Self-Regular Proximities
The notion of self-regular functions is extended to the positive orthant ℜn++. Then, self-regular proximities of LO are introduced based on self-regular functions and the so-called υ-space. Several attractive features of self-regular proximity are explored. A new class of primal-dual Newton-type methods relying on these self-regular proximities for solving LO problems is proposed and the complexity results of large-update and small-update algorithms are established. The procedure of complexity analysis in this chapter sets up a pattern for the complexity analysis in later chapters. The possibility of relaxing the self-regularity requirement on the proximity used in the algorithm for solving LO is also discussed.