This paper aims to present a fairly accessible generalization of several symmetric Gauss-Seidel decomposition based multi-block proximal alternating direction methods of multipliers (ADMMs) for convex composite optimization problems. The proposed method unifies and refines many constructive techniques that were separately developed for the computational efficiency of multi-block ADMM-type algorithms. Specifically, the majorized augmented Lagrangian functions, the indefinite proximal terms, the inexact symmetric Gauss-Seidel decomposition theorem, the tolerance criteria of approximately solving the subproblems, and the large dual step-lengths, are all incorporated in one algorithmic framework, which we named as sGS-imiPADMM. From the popularity of convergent variants of multi-block ADMMs in recent years, especially for high-dimensional multi-block convex composite conic programming problems, the unification presented in this paper, as well as the corresponding convergence results, may have the great potential of facilitating the implementation of many multi-block ADMMs in various problem settings.

In order to effectively solve the low precision problem of the single gravity density inversion and the magnetic susceptibility inversion, and the limitation of the gravity-magnetic joint inversion method based on the petrophysical parameter constraint, this paper studies the three-dimensional gravity-magnetic cross-gradient joint inversion based on the structural coupling and the fast optimization algorithm. Based on the forward and inversion modeling of three-dimensional gravity density and three-dimensional magnetic susceptibility using the same underground grid, along with cross-gradient coupling as the structural constraint, we propose a new gravity-magnetic joint inversion objective function including the data fitting term, the total variation regularization constraint term and the cross-gradient term induced by the structural coupling. The depth weighted constraint and the data weighting constraint are included into the objective function, which requires different physical property models to minimize their respective data residuals. At the same time, the cross-gradient term tends to zero, so that the structure of the gravity and magnetic models tends to be consistent. In realization, we address a fast and efficient gradient algorithm to iteratively solve the objective function. We apply this new joint inversion algorithm to the 3D gravity-magnetic model inversion test and compare it with the results of a single inversion algorithm. The experimental tests of synthetic data indicate that the gravity-magnetic cross-gradient joint inversion method can effectively improve the accuracy of the anomaly position and numerical accuracy of the inverted anomaly physical parameters compared with the single physical inversion method.

In this paper, we present the proximal-proximal-gradient method (PPG), a novel optimization method that is simple to implement and simple to parallelize. PPG generalizes the proximal-gradient method and ADMM and is applicable to minimization problems written as a sum of many differentiable and many non-differentiable convex functions. The non-differentiable functions can be coupled. We furthermore present a related stochastic variation, which we call stochastic PPG (S-PPG). S-PPG can be interpreted as a generalization of Finito and MISO over to the sum of many coupled non-differentiable convex functions.
We present many applications that can benefit from PPG and S-PPG and prove convergence for both methods. We demonstrate the empirical effectiveness of both methods through experiments on a CUDA GPU. A key strength of PPG and S-PPG is, compared to existing methods, their ability to directly handle a large sum of non-differentiable non-separable functions with a constant step size independent of the number of functions. Such non-diminishing step size allows them to be fast.

A convex two-stage non-cooperative multi-agent game under uncertainty is formulated as a two-stage stochastic variational inequality (SVI). Under standard assumptions, we provide sufficient conditions for the existence of solutions of the two-stage SVI and propose a regularized sample average approximation method for solving it. We prove the convergence of the method as the regularization parameter tends to zero and the sample size tends to infinity. Moreover, our approach is applied to a two-stage stochastic production and supply planning problem with homogeneous commodity in an oligopolistic market. Numerical results based on historical data in crude oil market are presented to demonstrate the effectiveness of the two-stage SVI in describing the market share of oil producing agents.

In this paper we propose an efficient and robust method for computing the analytic center of the polyhedral set $P = \{x \in R^n \mid Ax = b, x \ge 0\}$, where the matrix $A \in R^{m\times n}$ is ill-conditioned, and there are errors in $A$ and $b$.  Besides overcoming the difficulties caused by ill-conditioning of the matrix $A$ and errors in $A$ and $b$, our method can also detect the infeasibility and the unboundedness of the polyhedral set $P$ automatically during the computation. Detailed mathematical analyses for our method are presented and the worst case complexity of the algorithm is also given. Finally some numerical results are presented to show the robustness and effectiveness of the new method.

The modeling flexibility and the optimality guarantees provided by mixed-integer programming greatly aid the design of robust and future-proof decision support systems. The complexity of industrial-scale supply chain optimization, however, often poses limits to the application of general mixed-integer programming solvers. In this paper we describe algorithmic innovations that help to ensure that MIP solver performance matches the complexity of the large supply chain problems and tight time limits encountered in practice. Our computational evaluation is based on a diverse set, modeling real-world scenarios supplied by our industry partner SAP.

Most iterative algorithms for eigenpair computation consist of two main steps: a subspace update (SU) step that generates bases for approximate eigenspaces, followed by a Rayleigh-Ritz (RR) projection step that extracts approximate eigenpairs. So far the predominant methodology for the SU step is based on Krylov subspaces that builds orthonormal bases piece by piece in a sequential manner. In this work, we investigate block methods in the SU step that allow a higher level of concurrency than what is reachable by Krylov subspace methods. To achieve a competitive speed, we propose an augmented Rayleigh-Ritz (ARR) procedure. Combining this ARR procedure with a set of polynomial accelerators, as well as utilizing a few other techniques such as continuation and deflation, we construct a block algorithm designed to reduce the number of RR steps and elevate concurrency in the SU steps. Extensive computational experiments are conducted in $C$ on a representative set of test problems to evaluate the performance of two variants of our algorithm. Numerical results, obtained on a many-core computer without explicit code parallelization, show that when computing a relatively large number of eigenpairs, the performance of our algorithms is competitive with that of several state-of-the-art eigensolvers.

The Barzilai-Borwein (BB) method is a popular and efficient tool for solving large-scale unconstrained optimization problems. Its search direction is the same as the steepest descent (Cauchy) method, but its step size rule is different. Owing to this, it converges much faster than the Cauchy method. A feature of the BB method is that it may generate too long steps, which throw the iterates too far away from the solution. Moreover, it may not converge, even when the objective function is strongly convex. In this paper, a stabilization technique is introduced. It consists in bounding the distance between each pair of successive iterates, which often allows for decreasing the number of BB iterations. When the BB method does not converge, our simple modification of this method makes it convergent. For strongly convex functions with Lipschits gradients, we prove its global convergence, despite the fact that no line search is involved, and only gradient values are used. Since the number of stabilization steps is proved to be finite, the stabilized version inherits the fast local convergence of the BB method. The presented results of extensive numerical experiments show that our stabilization technique often allows the BB method to solve problems in a fewer iterations, or even to solve problems where the latter fails.