  This paper suggests two novel ideas to develop new proximal variable-metric
methods for solving a class of composite convex optimization problems. The
first idea is a new parameterization of the optimality condition which allows
us to develop a class of homotopy proximal variable-metric methods. We show
that under appropriate assumptions such as strong convexity-type and
smoothness, or self-concordance, our new schemes can achieve finite global
iteration-complexity bounds. Our second idea is a primal-dual-primal framework
for proximal-Newton methods which can lead to some useful computational
features for a subclass of nonsmooth composite convex optimization problems.
Starting from the primal problem, we formulate its dual problem, and use our
homotopy proximal Newton method to solve this dual problem. Instead of solving
the subproblem directly in the dual space, we suggest to dualize this
subproblem to go back to the primal space. The resulting subproblem shares some
similarity promoted by the regularizer of the original problem and leads to
some computational advantages. As a byproduct, we specialize the proposed
algorithm to solve covariance estimation problems. Surprisingly, our new
algorithm does not require any matrix inversion or Cholesky factorization, and
function evaluation, while it works in the primal space with sparsity
structures that are promoted by the regularizer. Numerical examples on several
applications are given to illustrate our theoretical development and to compare
with state-of-the-arts.
