Search

The stochastic heavy ball momentum (SHBM) method has gained considerable popularity as a scalable approach for solving large-scale optimization problems. However, one limitation of this method is its reliance on prior knowledge of certain problem parameters, such as singular values of a matrix. In this paper, we propose an adaptive variant of the SHBM method for solving stochastic problems that are reformulated from linear systems using user-defined distributions. Our adaptive SHBM (ASHBM) method utilizes iterative information to update the parameters, addressing an open problem in the literature regarding the adaptive learning of momentum parameters. We prove that our method converges linearly in expectation, with a better convergence bound compared to the basic method. Notably, we demonstrate that the deterministic version of our ASHBM algorithm can be reformulated as a variant of the conjugate gradient (CG) method, inheriting many of its appealing properties, such as finite-time convergence. Consequently, the ASHBM method can be further generalized to develop a brand-new framework of the stochastic CG method for solving linear systems. Our theoretical results are supported by numerical experiments. [ABSTRACT FROM AUTHOR]

The Douglas--Rachford (DR) method is a widely used method for finding a point in the intersection of two closed convex sets (feasibility problem). However, the method converges weakly, and the associated rate of convergence is hard to analyze in general. In addition, the direct extension of the DR method for solving more-than-two-sets feasibility problems, called the -sets-DR method, is not necessarily convergent. To improve the efficiency of the optimization algorithms, the introduction of randomization and the momentum technique has attracted increasing attention. In this paper, we propose the randomized -sets-DR (RrDR) method for solving the feasibility problem derived from linear systems, showing the benefit of the randomization as it brings linear convergence in expectation to the otherwise divergent -sets-DR method. Furthermore, the convergence rate does not depend on the dimension of the coefficient matrix. We also study RrDR with heavy ball momentum and establish its accelerated rate. Numerical experiments are provided to confirm our results and demonstrate the notable improvements in accuracy and efficiency of the DR method brought by the randomization and the momentum technique. [ABSTRACT FROM AUTHOR]

Beamforming is one of the most important techniques to enhance the quality of signal in array sensor signal processing, and the performance of a beamformer is usually related to the design of array configuration and beamformer weight. Recently, it was realized that the sparsity of the filter coefficients can reduce the cost of signal acquisition and communication, and as a consequence, the sparse broadband beamformer design attracts more and more attentions. In this paper, we first propose a proximal sparse beamformer design model which obtains the sparse and robust filter coefficients through solving a composite optimization problem. The objective function of the model is the sum of a least squares term, a proximal term, and an 1-regularization term. The least squares term reflects the data fidelity; the proximal term, whose center is predetermined via a simple least squares, enhances the robustness; while the '1 term ensures the sparsity of the solution. This model not only maintains the authenticity of the least squares solution, but also ensures the sparsity of the filter coefficients. A significant feature of the model is that we use 'partial' data to obtain the least squares solution and use another 'partial' data to construct the data fidelity term, which can evidently decrease the computational cost. For solving the composite optimization problem, we tailor several popular algorithms, such as the alternating direction method of multipliers, the forward-backward splitting method, and the Douglas-Rachford splitting method. Numerical results observably exhibit the improvements of the proposed approach over existing works in both effectiveness and efficiencies. [ABSTRACT FROM AUTHOR]

A novel inertial inverse-free dynamical system is proposed to solve the absolute value equation (AVE). Under mild conditions, the proposed model has a unique solution and its solution trajectories asymptotically converge to the solution of the AVE. Compared with the existing dynamical systems, the presence of the inertial term allows the new model to be more convenient for exploring different solutions of the AVE. Numerical results illustrate the effectiveness of the presented method. [ABSTRACT FROM AUTHOR]

We study box-constrained total least squares problem (BTLS), which minimizes the ratio of two quadratic functions with lower and upper bounded constraints. We first prove that (BTLS) is NP-hard. Then we show that for fixed number of dimension, it is polynomially solvable. When the constraint box is centered at zero, a relative 4/7-approximate solution can be obtained in polynomial time based on SDP relaxation. For zero-centered and unit-box case, we show that the direct nontrivial least square relaxation could provide an absolute (n + 1)/2-approximate solution. In the general case, we propose an enhanced SDP relaxation for (BTLS). Numerical results demonstrate significant improvements of the new relaxation. [ABSTRACT FROM AUTHOR]

In this paper, we aim to prove the linear rate convergence of the alternating direction method of multipliers (ADMM) for solving linearly constrained convex composite optimization problems. Under a mild calmness condition, which holds automatically for convex composite piecewise linear-quadratic programming, we establish the global Q-linear rate of convergence for a general semi-proximal ADMM with the dual step-length being taken in (0; (1+51/2)/2). This semi-proximal ADMM, which covers the classic one, has the advantage to resolve the potentially nonsolvability issue of the subproblems in the classic ADMM and possesses the abilities of handling the multi-block cases efficiently. We demonstrate the usefulness of the obtained results when applied to two- and multi-block convex quadratic (semidefinite) programming. [ABSTRACT FROM AUTHOR]

We consider the convergence of the Douglas-Rachford splitting method (DRSM) for minimizing the sum of a strongly convex function and a weakly convex function; this setting has various applications, especially in some sparsity-driven scenarios with the purpose of avoiding biased estimates which usually occur when convex penalties are used. Though the convergence of the DRSM has been well studied for the case where both functions are convex, its results for some nonconvex-function-involved cases, including the "strongly + weakly" convex case, are still in their infancy. In this paper, we prove the convergence of the DRSM for the "strongly + weakly" convex setting under relatively mild assumptions compared with some existing work in the literature. Moreover, we establish the rate of asymptotic regularity and the local linear convergence rate in the asymptotical sense under some regularity conditions. [ABSTRACT FROM AUTHOR]

The augmented Lagrangian method (ALM) is a benchmark for solving convex minimization problems with linear constraints. Solving the augmented subproblems over the primal variables can be regarded as sequentially providing inputs for updating the Lagrange multiplier (i.e., the dual variable). We consider the separable case of a convex minimization problem where its objective function is the sum of more than two functions without coupled variables. When applying the ALM to this case, at each iteration we can (sometimes must) split the resulting augmented subproblem in order to generate decomposed subproblems which are often easy enough to have closedform solutions. But the decomposition of primal variables only provides less accurate inputs for updating the Lagrange multiplier, and it points out the lack of convergence for such a decomposition scheme. To remedy this difficulty, we propose to update the Lagrange multiplier sequentially once each decomposed subproblem over the primal variables is solved. This scheme updates both the primal and dual variables in Gauss-Seidel fashion. In addition to the exact version which is useful enough for the case where the functions in the objective are all simple such that the decomposed subproblems all have closed-form solutions, we investigate an inexact version of this scheme which allows the decomposed subproblems to be solved approximately subject to certain inexactness criteria. Some preliminary numerical results when the proposed scheme is respectively applied to an image decomposition problem and an allocation problem are reported. [ABSTRACT FROM AUTHOR]

In diffusion-weighted magnetic resonance imaging, the estimation of the orientations of multiple nerve fibers in each voxel (the fiber orientation distribution (FOD)) is a critical issue for exploring the connection of cerebral tissue. In this paper, we establish a convex semidefinite programming (CSDP) model for the FOD estimation. One feature of the new model is that it can ensure the statistical meaning of FOD since as a probability density function, FOD must be nonnegative and have a unit mass. To construct such a statistically meaningful FOD, we consider its approximation by a sum of squares (SOS) polynomial and impose the unit-mass by a linear constraint. Another feature of the new model is that it introduces a new regularization based on the sparsity of nerve fibers. Due to the sparsity of the orientations of nerve fibers in cerebral white matter, a heuristic regularization is raised, which is inspired by the Z-eigenvalue of a symmetric tensor that closely relates to the SOS polynomial. To solve the CSDP efficiently, we propose a new Peaceman-Rachford splitting method and prove its global convergence. Numerical experiments on synthetic and real-world human brain data show that, when compared with some existing approaches for fiber estimations, the new method gives a sharp and smooth FOD. Further, the proposed Peaceman-Rachford splitting method is shown to have good numerical performances comparing several existing methods. [ABSTRACT FROM AUTHOR]

The numerical success of the alternating direction method of multipliers (ADMM) inspires much attention in analyzing its theoretical convergence rate. While there are several results on the iterative complexity results implying sublinear convergence rate for the general case, there are only a few results for the special cases such as linear programming, quadratic programming, and nonlinear programming with strongly convex functions. In this paper, we consider the convergence rate of ADMM when applying to the convex optimization problems that the subdifferentials of the underlying functions are piecewise linear multifunctions, including LASSO, a well-known regression model in statistics, as a special case. We prove that due to its inherent polyhedral structure, a recent global error bound holds for this class of problems. Based on this error bound, we derive the linear rate of convergence for ADMM. We also consider the proximal based ADMM and derive its linear convergence rate. [ABSTRACT FROM AUTHOR]

Recent studies on the new congestion reduction method--tradable credit scheme rely on the full information of speed-flow relationship, demand function, and generalized cost. As analytical travel demand, functions are difficult to establish in practice. This paper develops a trial and error method for selecting optimal credit schemes for general networks in the absence of demand functions. After each trial of tradable credit scheme, the credit charging scheme and total amount of credits to be distributed are updated by both observed link flows at traffic equilibrium and revealed credit price at market equilibrium. The updating strategy is based on the method of successive averages and its convergence is established theoretically. Our numerical experiments demonstrate that the method of successive averages based trial and error method for tradable credit schemes has a lower convergence speed in comparison with its counterpart for congestion pricing and could be enhanced by exploring more efficient methods that make full use of credit price information. [ABSTRACT FROM AUTHOR]

This paper considers the convex minimization problem with linear constraints and a separable objective function which is the sum of many individual functions without coupled variables. An algorithm is developed by splitting the augmented Lagrangian function in a parallel way. The new algorithm differs substantially from existing splitting methods in alternating style which require solving the decomposed subproblems sequentially, while it remains the main superiority of existing splitting methods in that the resulting subproblems could be simple enough to have closed-form solutions for such an application whose functions in the objective are simple. We show applicability and encouraging efficiency of the new algorithm by some applications in image processing. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new parallel splitting descent method for solving a class of variational inequalities with separable structure. The new method can be applied to solve convex optimization problems in which the objective function is separable with three operators and the constraint is linear. In the framework of the new algorithm, we adopt a new descent strategy by combining two descent directions and resolve the descent direction which is different from the methods in He (Comput. Optim. Appl., 2009, 42: 195-212.) and Wang et al. (submitted to J. Optimiz. Theory App.). Theoretically, we establish the global convergence of the new method under mild assumptions. In addition, we apply the new method to solve problems in management science and traffic equilibrium problem. Numerical results indicate that the new method is efficient and reliable. [ABSTRACT FROM AUTHOR]

The Douglas-Rachford alternating direction method of multipliers (ADMM) has been widely used in various areas. The global convergence of ADMM is well known, while research on its convergence rate is still in its infancy. In this paper, we show the local linear convergence rate of ADMM for a quadratic program which includes some important applications of ADMM as special cases. [ABSTRACT FROM AUTHOR]

The positive definiteness of a diffusion tensor is important in magnetic resonance imaging because it reflects the phenomenon of water molecular diffusion in complicated biological tissue environments. To preserve this property, we represent it as an explicit positive semidefinite (PSD) matrix constraint and some linear matrix equalities. The objective function is the regularized linear least squares fitting for the log-linearized Stejskal-Tanner equation. The regularization term is the heuristic nuclear norm of the PSD matrix, since we expect it to be of low rank. In this way, we establish a convex quadratic semidefinite programming (SDP) model, whose global solution exists. The optimal solution could be solved by three efficient methods. While there are two state-of-the-art solvers--SDPT3 and QSDP--for the primal problem, we design a new augmented Lagrangian based alternating direction method (ADM) for the dual problem. Sensitivity analyses on the coefficients of the optimal diffusion tensor and the optimal objective function value with respect to noise-corrupted signals are presented. Experiments on synthetic data with multiple fibers show that the new method is robust to the Rician noise and outperforms several existing methods. Furthermore, when the fiber orientation distribution function is considered, the new method is competitive with the Q-ball imaging. Using the human brain data, we illustrate that the new method could capture the crossing of three nervous fiber bundles. Additionally, the new method generates positive definite generalized diffusion tensors in all voxels, while the unconstrained least squares fitting fails. Finally, we confirm that the ADM solver is more efficient than SDPT3 and QSDP for this special problem. [ABSTRACT FROM AUTHOR]

In this paper, we propose a modification of the forward-backward splitting method for maximal monotone mappings, where we adopt a new stepsize scheme in generating the next iterate. This modification is motivated by the ingenious rule proposed by He and Liao in modified Korpelevich's extragradient method [13]. Under suitable conditions, we prove the global convergence of the new algorithm. We apply our method to solve some monotone variational inequalities and report its numerical results. Comparisons with modified Khobotov-Korpelevich's extragradient method [13, 14] and Tseng's method [30] show the significance of our work. [ABSTRACT FROM AUTHOR]

In the last decade, as calibrations of the classical traffic equilibrium problems, various models of traffic equilibrium problems with nonadditive route costs have been proposed. For solving such models, this paper develops a self-adaptive projection-auxiliary problem method for monotone variational inequality (VI) problems. It first converts the original problem where the feasible set is the intersection of a linear manifold and a simple set to an augmented VI with simple set, which makes the projection easy to implement. The self-adaptive strategy avoids the difficult task of choosing 'suitable' parameters, and leads to fast convergence. Under suitable conditions, we prove the global convergence of the method. Some preliminary computational results are presented to illustrate the ability and efficiency of the method. [ABSTRACT FROM AUTHOR]

Consider a class of variational inequality problems of finding $${x^*\in S}$$, such that where the underlying mapping f is hard to evaluate (sometimes its explicit form is unknown), and S has the following structure For any given Lagrangian multiplier y associated with the linear inequality constraint in S, a solution of the relaxed variational inequality problem of finding $${\hat x\in K}$$, such that can be given by an oracle. This class of problems arises frequently in economics and engineering. In this paper, we focus on considering the above problems where the underlying mapping f, though is unknown, is strongly monotone. We propose an iterative method for solving this class of variational inequality problems. At each iteration, the method consists of two steps: predictor and corrector. At the predictor step, a trial multiplier is given and the oracle is called for a solution of the relaxed variational inequality problem (1); then at the corrector step, the multiplier y is updated, using the information from the predictor step. We allow the oracle to give just an inexact solution of the relaxed variational inequality problem at the predictor step, which makes the method very efficient and practical. Under some suitable conditions, the global convergence of the method is proved. Some numerical examples are presented to illustrate the method. [ABSTRACT FROM AUTHOR]

Abstract  In this paper, we derive necessary and sufficient conditions for the strong ellipticity condition of anisotropic elastic materials. We first observe that the strong ellipticity condition holds if and only if a second order tensor function is positive definite for any unit vectors. Then we further link this condition to the rank-one positive definiteness of three second-order tensors, three fourth-order tensors and a sixth-order tensor. In particular, we consider conditions of strong ellipticity of the rhombic classes, for which we need to check the copositivity of three second-order tensors and the positive definiteness of a sixth-order tensor. A direct method is presented to verify our conditions. [ABSTRACT FROM AUTHOR]

The efficiency of the implicit method proposed by He (1999) depends on the parameter β heavily; while it varies for individual problem, that is, different problem has different "suitable" parameter, which is difficult to find. In this paper, we present a modified implicit method, which adjusts the parameter β automatically per iteration, based on the message from former iterates. To improve the performance of the algorithm, an inexact version is proposed, where the subproblem is just solved approximately. Under mild conditions as those for variational inequalities, we prove the global convergence of both exact and inexact versions of the new method. We also present several preliminary numerical results, which demonstrate that the self-adaptive implicit method, especially the inexact version, is efficient and robust. [ABSTRACT FROM AUTHOR]

Abstract  In this paper, we propose a new operator splitting method for solving a class of variational inequality problems in which part of the underlying mappings are unknown. This class of problems arises frequently from engineering, economics and transportation equilibrium problems. At each iteration, by using the information observed from the system, the method solves a system of nonlinear equations, which is well-defined. Under mild assumptions, the global convergence of the method is proved, and its efficiency is demonstrated with numerical examples. [ABSTRACT FROM AUTHOR]

The alternating direction method solves large scale variational inequality problems with linear constraints via solving a series of small scale variational inequality problems with simple constraints. The algorithm is attractive if the subproblems can be solved efficiently and exactly. However, the subproblem is itself variational inequality problem, which is structurally also difficult to solve. In this paper, we develop a new decomposition algorithm, which, at each iteration, just solves a system of well-conditioned linear equations and performs a line search. We allow to solve the subproblem approximately and the accuracy criterion is the constructive one developed recently by Solodov and Svaiter. Under mild assumptions on the problem's data, the algorithm is proved to converge globally. Some preliminary computational results are also reported to illustrate the efficiency of the algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we propose a modified Bregman-function-based proximal point algorithm for solving variational inequality problems. The algorithm adopts a similar constructive approximate criterion as the one developed by Solodov and Svaiter (Set Valued Analysis 7 (1999) 323) for solving the classical proximal subproblems. Under some suitable conditions, we can get an approximate solution satisfying the accuracy criterion via a single Newton-type step. We obtain the Fejér monotonicity to solutions of VIP for paramonotone operators. Some preliminary computational results are also reported to illustrate the method. [ABSTRACT FROM AUTHOR]