  We introduce a new weighted averaging scheme using "Fenchel-type" operators
to recover primal solutions in the alternating minimization-type algorithm
(AMA) for prototype constrained convex optimization. Our approach combines the
classical AMA idea in \cite{Tseng1991} and Nesterov's prox-function smoothing
technique without requiring the strong convexity of the objective function. We
develop a new non-accelerated primal-dual AMA method and estimate its primal
convergence rate both on the objective residual and on the feasibility gap.
Then, we incorporate Nesterov's accelerated step into this algorithm and obtain
a new accelerated primal-dual AMA variant endowed with a rigorous convergence
rate guarantee. We show that the worst-case iteration-complexity in this
algorithm is optimal (in the sense of first-oder black-box models), without
imposing the full strong convexity assumption on the objective.
