  Many contemporary signal processing, machine learning and wireless
communication applications can be formulated as nonconvex nonsmooth
optimization problems. Often there is a lack of efficient algorithms for these
problems, especially when the optimization variables are nonlinearly coupled in
some nonconvex constraints. In this work, we propose an algorithm named penalty
dual decomposition (PDD) for these difficult problems and discuss its various
applications. The PDD is a double-loop iterative algorithm. Its inner
iterations is used to inexactly solve a nonconvex nonsmooth augmented
Lagrangian problem via block-coordinate-descenttype methods, while its outer
iteration updates the dual variables and/or a penalty parameter. In Part I of
this work, we describe the PDD algorithm and rigorously establish its
convergence to KKT solutions. In Part II we evaluate the performance of PDD by
customizing it to three applications arising from signal processing and
wireless communications.
