Controlled Dual Perturbations for Lp-Programming.

Lp-programming is a common generalization of linear programming, quadratically constrained quadratic programming, lp-constrained lp-approximation, and multiple criteria compromise programming. It is a type of convex programming with objective function and inequality constraints expressed by means of lp-norms. The dual program established by Peterson and Ecker is a maximization problem with a concave, upper-semicontinuous objective function over a set of constraints that are essentially linear. In developing a dual method for this problem, we face two major difficulties. One is the non-differentiability of the dual objective function and the other one is an efficient dual-to-primal conversion. In this paper, we introduce a mechanism to construct a suitably perturbed dual program with a differentiable concave objective function over linear constraints. Solving this well- constructed perturbed dual program, we can obtain an epsilon- optimal dual solution for an arbitrarily small number epsilon. Moreover, we show a way of constructing a linear program based on this dual solution. Then an epsilon-optimal primal solution can be obtained by solving the dual of this simple linear program.