In this paper, we develop a self-adaptive ADMM that updates the penalty parame-
ter adaptively. When one part of the objective function is strongly convex i.e., the
problem is semi-strongly convex, our algorithm can update the penalty parameter
adaptively with guaranteed convergence. We establish various types of convergence
results including accelerated convergence rate of O(1/k2), linear convergence and
convergence of iteration points. This enhances various previous results because we
allow the penalty parameter to change adaptively. We also develop a partial proximal
point method with the subproblems being solved by our adaptive ADMM. This enables
us to solve problems without semi-strongly convex property. Numerical experiments
are conducted to demonstrate the high efficiency and robustness of our method.
Doubly nonnegative (DNN) relaxation usually provides a tight lower bound for a
mixed-binary quadratic program (MBQP). However, solving DNN problems is chal-
lenging because: (1) the problem size is ((n + l)2) for an MBQP with n variables
and l inequality constraints, and (2) the rank of optimal solutions cannot be estimated
a priori due to the absence of theoretical bounds. In this work, we propose RiNNAL+,
a Riemannian augmented Lagrangian method (ALM) for solving DNN problems. We
prove that the DNN relaxation of an MBQP, with matrix dimension (n + l + 1), is
equivalent to the SDP-RLT relaxation (based on the reformulation-linearization tech-
nique) with a smaller matrix dimension (n + 1). In addition, we develop a hybrid
method that alternates between two phases to solve the ALM subproblems. In phase
one, we apply low-rank matrix factorization and random perturbation to transform the
feasible region into a lower-dimensional manifold so that we can use the Riemannian
gradient descent method. In phase two, we apply a single projected gradient step to
update the rank of the underlying variable and escape from spurious local minima
arising in the first phase if necessary. To reduce the computation cost of the projected
gradient step, we develop pre-processing and warm-start techniques for acceleration.
Unlike traditional rank-adaptive methods that require extensive parameter tuning, our
hybrid method requires minimal tuning. Extensive experiments confirm the efficiency
and robustness of RiNNAL+ in solving various classes of large-scale DNN problems
