We propose an inexact proximal augmented Lagrangian framework with explicit inner problem termination rule for composite convex optimization problems. We consider arbitrary linearly convergent inner solver including in particular stochastic algorithms, making the resulting framework more scalable facing the ever-increasing problem dimension. Each subproblem is solved inexactly with an explicit and self-adaptive stopping criterion, without requiring to set an a priori target accuracy. When the primal and dual domain are bounded, our method achieves O(1/ϵ√) and O(1/ϵ) complexity bound in terms of number of inner solver iterations, respectively for the strongly convex and non-strongly convex case. Without the boundedness assumption, only logarithm terms need to be added and the above two complexity bounds increase respectively to O~(1/ϵ√) and O~(1/ϵ), which hold both for obtaining ϵ-optimal and ϵ-KKT solution. Within the general framework that we propose, we also obtain O~(1/ϵ) and O~(1/ϵ2) complexity bounds under relative smoothness assumption on the differentiable component of the objective function. We show through theoretical analysis as well as numerical experiments the computational speedup possibly achieved by the use of randomized inner solvers for large-scale problems.
We consider the problem of maximizing a convex quadratic function over a bounded
polyhedral set. We design a new framework based on SDP relaxations and cutting
plane methods for solving the associated reference value problem. The major novelty
is a new way to generate valid cuts through the doubly nonnegative (DNN) relaxation.
We establish various theoretical properties of the DNN relaxation, including its equiv-
alence with the Shor relaxation of an equivalent quadratically constrained problem,
the strong duality, and the generation of valid cuts from an approximate solution of
the DNN relaxation returned by an arbitrary SDP solver. Computational results on
both real and synthetic data demonstrate the efficiency of the proposed method and
its ability to solve high-dimensional problems with dense data. In particular, our new
algorithm successfully solves in 3 days the reference value problem arising from com-
putational biology for a dataset containing more than 300,000 instances of dimension
78. In contrast, CPLEX or Gurobi is estimated to require years of computational time
for the same dataset on the same computing platform.