  We develop two new proximal alternating penalty algorithms to solve a wide
range class of constrained convex optimization problems. Our approach mainly
relies on a novel combination of the classical quadratic penalty, alternating
minimization, Nesterov's acceleration, and adaptive strategy for parameters.
The first algorithm is designed to solve generic and possibly nonsmooth
constrained convex problems without requiring any Lipschitz gradient continuity
or strong convexity, while achieving the best-known
$O(\frac{1}{k})$-convergence rate in a non-ergodic sense, where $k$ is the
iteration counter. The second algorithm is also designed to solve non-strongly
convex, but semi-strongly convex problems. This algorithm can achieve the
best-known $O(\frac{1}{k^2})$-convergence rate on the primal constrained
problem. Such a rate is obtained in two cases: (i)~averaging only on the
iterate sequence of the strongly convex term, or (ii) using two proximal
operators of this term without averaging. In both algorithms, we allow one to
linearize the second subproblem to use the proximal operator of the
corresponding objective term. Then, we customize our methods to solve different
convex problems, and lead to new variants. As a byproduct, these algorithms
preserve the same convergence guarantees as in our main algorithms. We verify
our theoretical development via different numerical examples and compare our
methods with some existing state-of-the-art algorithms.
