We propose a novel decomposition framework for the distributed optimization of general nonconvex sum-utility functions arising naturally in the system design of wireless multi-user interfering systems. Our main contributions are i) the development of the first class of (inexact) Jacobi best-response algorithms with provable convergence, where all the users simultaneously and iteratively solve a suitably convexified version of the original sum-utility optimization problem; ii) the derivation of a general dynamic pricing mechanism that provides a unified view of existing pricing schemes that are based, instead, on heuristics; and iii) a framework that can be easily particularized to well-known applications, giving rise to very efficient practical (Jacobi or Gauss-Seidel) algorithms that outperform existing ad hoc methods proposed for very specific problems. Interestingly, our framework contains as special cases well-known gradient algorithms for nonconvex sum-utility problems, and many block-coordinate descent schemes for convex functions.
In wireless cellular or ad hoc networks where Quality of Service (QoS) is interference-limited, a variety of power control problems can be formulated as nonlinear optimization with a system-wide objective, e.g., maximizing the total system throughput or the worst user throughput, subject to QoS constraints from individual users, e.g., on data rate, delay, and outage probability. We show that in the high Signal-to- interference Ratios (SIR) regime, these nonlinear and apparently difficult, nonconvex optimization problems can be transformed into convex optimization problems in the form of geometric programming; hence they can be very efficiently solved for global optimality even with a large number of users. In the medium to low SIR regime, some of these constrained nonlinear optimization of power control cannot be turned into tractable convex formulations, but a heuristic can be used to compute in most cases the optimal solution by solving a series of geometric programs through the approach of successive convex approximation. While efficient and robust algorithms have been extensively studied for centralized solutions of geometric programs, distributed algorithms have not been explored before. We present a systematic method of distributed algorithms for power control that is geometric-programming-based. These techniques for power control, together with their implications to admission control and pricing in wireless networks, are illustrated through several numerical examples. Inner approximation algorithms have had two major roles in the mathematical programming literature. Their first role was in the construction of algorithms for the decomposition of large-scale mathematical programs, such as in the Dantzig-Wolfe decomposition principle. However, recently they have been used in the creation of algorithms that locate Kuhn-Tucker solutions to nonconvex programs. Avriel and Williams' Avriel, M., A. C. Williams. 1970. Complementary geometric programming. SIAM J. Appl. Math.19 125-141. complementary geometric programming algorithm, Duffin and Peterson's Duffin, R. J., E. L. Peterson. 1972. Reversed geometric programs treated by harmonic means. Indiana Univ. Math. J.22 531-550. reversed geometric programming algorithms, Reklaitis and Wilde's Reklaitis, G. V., D. J. Wilde. 1974. Geometric programming via a primal auxiliary problem. AIIE Trans.6 308-317. primal reversed geometric programming algorithm, and Bitran and Novaes' Bitran, G. R., A. G. Novaes. 1973. Linear programming with a fractional objective function. Opns. Res.21 22-29. linear fractional programming algorithm are all examples of this class of inner approximation algorithms. A sequence of approximating convex programs are solved in each of these algorithms. Rosen's Rosen, J. B. 1966. Iterative solution of nonlinear optimal control problems. SIAM J. Control4 223-244. inner approximation algorithm is a special case of the general inner approximation algorithm presented in this note. 