Studies On Lagrangian Regularization Approach And Primal-Dual Algorithms For Linear Programs

This dissertation is devoted to studying Lagrangian regularization approach and primal-dual algorithms for linear programming, of which the former is a kind of special smoothing methods that provide a basis for developing the primal-dual interior point and non-interior point algorithms for linear programming.Maximum Entropy Method is an effective smoothing one for the finite min-max problem, which, by adding Shannon's informational entropy as a regularizing term to the Lagrangian function of min-max problem, yields a smooth function that uniformly approaches the non-smooth max-valued function. Due to the excellent properties of this smooth function, this method is extensively applied to many kinds of optimization problems.In this thesis, we extend the entropy regularization method in two ways: from the min-max problem to general inequality constrained optimization problems and from the entropy function to more general functions. To circumvent the non-differentiabledifficulty caused by the positive homogeneously function that is involved in an equivalent unconstrained formulationfor general inequality constrained optimization problems, we turn to the classical Lagrangian function and redefine M (x) by a conic optimization problem with theLagrangian as the objective function. When adding an entropy function as regularizing term to the Lagrangian function, we obtain a smooth approximate function for M(x) , which turns out to be the exponential penalty function.Furthermore, when replacing the entropy function by a general separate multiplier function, we develop a new regularization approach, referred to as Lagrangian regularization approach. This approach does not only provide a unified smoothingtechnique for the non-differentiable M(x) and but also offers a unifiedframework for constructing penalty functions, whereby building a bridge between the penalty functions and the classical Lagrangian.The first part of this dissertation is composed of four chapters, concentrating on the study for Lagrangian regularization approach. The first chapter is the introduction for the entropy regularization method and penalty function method. The second chapter reveals the mathematical essence of entropy regularization method for the finite min-max problem, through exploring the relationship between entropy regularization method and exponential penalty function method. The third chapter extends Maximum Entropy Method to a general inequality constrained optimization problem and establishes the Lagrangian regularization approach. The fourth chapter presents a unified framework for constructing penalty functions by virtue of the Lagrangian regularization approach, and illustrates it by some specific penalty and barrier function examples.The second part of this dissertation is committed to developing the effective primal-dual path following algorithms for linear programming. Among various types of interior point methods, the so-called primal-dual path following algorithm is the most successful and effective one. However, the existing algorithms are almost based on the standard perturbed system, namely the K-K-T system of logarithmic barrier problem for standard linear programming. In this thesis, we modify the perturbed system from three different angles and develop the corresponding primal-dual path following interior point and non-interior point algorithms.By making algebraically equivalent transformation for the standard centering equation Xs=μe, we obtain a new system of perturbed K-K-T equations and, forspecific power transformation, recover the Newton equations that are recently used by J. M. Peng et al to show a lower polynomial complexity bound for large-update algorithm. Motivated by this fact and Peng's promising result, we utilize a special algebraic transformation, namely logarithmic transformation, to establish a non-infeasible long-step primal-dual path following algorithm. This algorithm arrives at the primal-dual solution set along the steepest descent direction of primal-dual...