A family of projective splitting methods for the sum of two maximal monotone operators

A splitting method for two monotone operators A and B is an algorithm that attempts to converge to a zero of the sum A + B by solving a sequence of subproblems, each of which involves only the operator A, or only the operator B. Prior algorithms of this type can all in essence be categorized into three main classes, the Douglas/Peaceman-Rachford class, the forward-backward class, and the little-used double-backward class. Through a certain “extended” solution set in a product space, we construct a fundamentally new class of splitting methods for pairs of general maximal monotone operators in Hilbert space. Our algorithms are essentially standard projection methods, using splitting decomposition to construct separators. We prove convergence through Fejér monotonicity techniques, but showing Fejér convergence of a different sequence to a different set than in earlier splitting methods. Our projective algorithms converge under more general conditions than prior splitting methods, allowing the proximal parameter to vary from iteration to iteration, and even from operator to operator, while retaining convergence for essentially arbitrary pairs of operators. The new projective splitting class also contains noteworthy preexisting methods either as conventional special cases or excluded boundary cases. Dedicated to Clovis Gonzaga on the occassion of his 60th birthday.     

Higher-order Discretization Methods of Forward-backward SDEs Using KLNV-scheme and Their Applications to XVA Pricing

ABSTRACT

This study proposes new higher-order discretization methods of forward-backward stochastic differential equations. In the proposed methods, the forward component is discretized using the Kusuoka–Lyons–Ninomiya–Victoir scheme with discrete random variables and the backward component using a higher-order numerical integration method consistent with the discretization method of the forward component, by use of the tree based branching algorithm. The proposed methods are applied to the XVA pricing, in particular to the credit valuation adjustment. The numerical results show that the expected theoretical order and computational efficiency could be achieved.     

New algorithms for the split variational inclusion problems and application to split feasibility problems

ABSTRACT

In this paper, we suggest two new iterative methods for finding an element of the solution set of split variational inclusion problem in real Hilbert spaces. Under suitable conditions, we present weak and strong convergence theorems for these methods. We also apply the proposed algorithms to study the split feasibility problem. Finally, we give some numerical results which show that our proposed algorithms are efficient and implementable from the numerical point of view.     

A modified forward-backward splitting methods for the sum of two monotone operators with applications to breast cancer prediction

This work proposes a modified forward-backward splitting algorithm combining an inertial technique for solving the monotone variational inclusion problem. The weak convergence theorem is established under some suitable conditions in Hilbert space, and a new step size is presented for our algorithm to speed up the convergence. We give an example and numerical results for supporting our main theorem in infinite dimensional spaces. We also provide an application to predict breast cancer by using our proposed algorithm for updating the optimal weight in machine learning. Moreover, we use the Wisconsin original breast cancer data set as a training set to show efficiency comparing with the other three algorithms in terms of three key parameters, namely, accuracy, recall, and precision.     

The Generalized Forward-Backward Splitting Method for the Minimization of the Sum of Two Functions in Banach Spaces

We propose a convergence analysis of the generalized forward-backward splitting iterative procedure for the minimization of the sum of two functions in Banach spaces. The generalized forward-backward splitting method is applied to the minimization of functionals of the Tikhonov type with semi-norm regularization. We also investigate the perturbed forward-backward splitting method and prove its stability.     

松弛算子分裂法线性收敛性分析的新框架

提出了一种新的分析框架来研究松弛算子分裂法的线性收敛性,可以将这种框架看成是经典的Krasnosel''-Mann迭代和Banach-Picard收缩的扩展形式.随后,将提出的这个框架应用于分析广义邻近点算法和松弛向前向后分裂算法的线性收敛性,其过程十分简洁和直接.     

A projection algorithm for solving pseudomonotone equilibrium problems and it's application to a class of bilevel equilibria

Abstract

We propose a projection algorithm for solving an equilibrium problem (EP) where the bifunction is pseudomonotone with respect to its solution set. The algorithm is further combined with a cutting technique for minimizing the norm over the solution set of an EP whose bifunction is pseudomonotone with respect to the solution set.     

Comparison of Two Kinds of Prediction-Correction Methods for Monotone Variational Inequalities

In this paper, we study the relationship between the forward-backward splitting method and the extra-gradient method for monotone variational inequalities. Both of the methods can be viewed as prediction-correction methods. The only difference is that they use different search directions in the correction-step. Our analysis explains theoretically why the extra-gradient methods usually outperform the forward-backward splitting methods. We suggest some modifications for the two methods and numerical results are given to verify the superiority of the modified methods.     

Two algorithms for solving systems of inclusion problems

The goal of this paper is to present two algorithms for solving systems of inclusion problems, with all components of the systems being a sum of two maximal monotone operators. The algorithms are variants of the forward-backward splitting method and one being a hybrid with the alternating projection method. They consist of approximating the solution sets involved in the problem by separating half-spaces which is a well-studied strategy. The schemes contain two parts, the first one is an explicit Armijo-type search in the spirit of the extragradient-like methods for variational inequalities. The second part is the projection step, this being the main difference between the algorithms. While the first algorithm computes the projection onto the intersection of the separating half-spaces, the second chooses one component of the system and projects onto the separating half-space of this case. In the iterative process, the forward-backward operator is computed once per inclusion problem, representing a relevant computational saving if compared with similar algorithms in the literature. The convergence analysis of the proposed methods is given assuming monotonicity of all operators, without Lipschitz continuity assumption. We also present some numerical experiments.     

On the use of consistent approximations in the solution of semi-infinite optimization and optimal control problems

The purpose of this study is to broaden the scope of projective transformation methods in mathematical programming, both in terms of theory and algorithms. We start by generalizing the concept of the analytic center of a polyhedral system of constraints to the w-center of a polyhedral system, which stands for weighted center, where there is a positive weight on the logarithmic barrier term for each inequality constraint defining the polyhedronX. We prove basic results regarding contained and containing ellipsoids centered at the w-center of the systemX. We next shift attention to projective transformations, and we exhibit an elementary projective transformation that transforms the polyhedronX to another polyhedronZ, and that transforms the current interior point to the w-center of the transformed polyhedronZ. We work throughout with a polyhedral system of the most general form, namely both inequality and equality costraints.This theory is then applied to the problem of finding the w-center of a polyhedral systemX. We present a projective transformation algorithm, which is an extension of Karmarkar's algorithm, for finding the w-center of the systemX. At each iteration, the algorithm exhibits either a fixed constant objective function improvement, or converges superlinearly to the optimal solution. The algorithm produces upper bounds on the optimal value at each iteration. The direction chosen at each iteration is shown to be a positively scaled Newton direction. This broadens a result of Bayer and Lagarias regarding the connection between projective transformation methods and Newton's method. Furthermore, the algorithm specializes to Vaidya's algorithm when used with a line-search, and so shows that Vaidya's algorithm is superlinearly convergent as well. Finally, we show how the algorithm can be used to construct well-scaled containing and contained ellipsoids at near-optimal solutions to the w-center problem.This paper is a revision of the two papers Projective transformations for interior point methods, part I: Basic theory and linear programming, O.R. working paper 179-88 and Projective transformations for interior point methods, part II: Analysis of an algorithm for finding the weighted center of a polyhedral system, O.R. working paper 180-88, M.I.T.     

Minimization of equilibrium problems,variational inequality problems and fixed point problems

In this paper, we devote to find the solution of the following quadratic minimization problem

$\min_{x\in \Omega}\|x\|^2,$

where Ω is the intersection set of the solution set of some equilibrium problem, the fixed points set of a nonexpansive mapping and the solution set of some variational inequality. In order to solve the above minimization problem, we first construct an implicit algorithm by using the projection method. Further, we suggest an explicit algorithm by discretizing this implicit algorithm. Finally, we prove that the proposed implicit and explicit algorithms converge strongly to a solution of the above minimization problem.

     

A splitting preconditioner for saddle point problems

For large sparse systems of linear equations iterative techniques are attractive. In this paper, we study a splitting method for an important class of symmetric and indefinite system. Theoretical analyses show that this method converges to the unique solution of the system of linear equations for all t>0 (t is the parameter). Moreover, all the eigenvalues of the iteration matrix are real and nonnegative and the spectral radius of the iteration matrix is decreasing with respect to the parameter t. Besides, a preconditioning strategy based on the splitting of the symmetric and indefinite coefficient matrices is proposed. The eigensolution of the preconditioned matrix is described and an upper bound of the degree of the minimal polynomials for the preconditioned matrix is obtained. Numerical experiments of a model Stokes problem and a least‐squares problem with linear constraints presented to illustrate the effectiveness of the method. Copyright © 2011 John Wiley & Sons, Ltd.     

Computing the nadir point for multiobjective discrete optimization problems

We investigate the problem of finding the nadir point for multiobjective discrete optimization problems (MODO). The nadir point is constructed from the worst objective values over the efficient set of a multiobjective optimization problem. We present a new algorithm to compute nadir values for MODO with \(p\) objective functions. The proposed algorithm is based on an exhaustive search of the \((p-2)\)-dimensional space for each component of the nadir point. We compare our algorithm with two earlier studies from the literature. We give numerical results for all algorithms on multiobjective knapsack, assignment and integer linear programming problems. Our algorithm is able to obtain the nadir point for relatively large problem instances with up to five-objectives.     

On inertial proximal algorithm for split variational inclusion problems

ABSTRACT

In this paper, a hybrid proximal algorithm with inertial effect is introduced to solve a split variational inclusion problem in real Hilbert spaces. Under mild conditions on the parameters, we establish weak convergence results for the proposed algorithm. Unlike the earlier iterative methods, we do not impose any conditions on the sequence generated by the proposed algorithm. Also, we extend our results to find a common solution of a split variational inclusion problem and a fixed-point problem. Finally, some numerical examples are given to discuss the convergence and superiority of the proposed iterative methods.     

The corrected Uzawa method for solving saddle point problems

In this paper, we consider the solution of linear systems of saddle point type by correcting the Uzawa algorithm, which has been proposed in [K. Arrow, L. Hurwicz, H. Uzawa, Studies in nonlinear programming, Stanford University Press, Stanford, CA, 1958]. We call this method as corrected Uzawa (CU) method. The convergence of the CU method is analyzed for solving nonsingular saddle point problem as well as the semi‐convergence for the singular case. First, the corrected model for the Uzawa algorithm is established, and the CU algorithm is presented. Then we study the geometric meaning of the CU model. Moreover, we introduce the overall reduction coefficient α to measure the effect of the CU process. It is shown that the CU method converges faster than the Uzawa method and several other methods if the overall reduction coefficient α satisfies certain conditions. Numerical experiments are presented to illustrate the theoretical results and examine the numerical effectiveness of the CU method. Copyright © 2015 John Wiley & Sons, Ltd.     

Improved convergence theorems of the two-step modulus-based matrix splitting and synchronous multisplitting iteration methods for solving linear complementarity problems

Abstract

In this paper, the convergence conditions of the two-step modulus-based matrix splitting and synchronous multisplitting iteration methods for solving linear complementarity problems of H-matrices are weakened. The convergence domain given by the proposed theorems is larger than the existing ones.     

Deepest point of a polyhedron and linear programming

Abstract

The problem of finding a deepest point (a ball centre) of a polyhedron is studied. A finite combinatorial interior point method is presented for this problem which yields an algorithm for linear programming. We conjecture that this is a strongly polynomial algorithm. Meanwhile developing the algorithm, several auxiliary results were found; among others, Gorokh and Werner’s algorithm for linear inequalities is slightly extended. Our numerical experiments with the problem detected bugs in a linear interior point solver used in MATLAB 6 Optimization Toolbox.     

Matrix stretching for sparse least squares problems

For linear least squares problems min _x ‖Ax − b‖₂, where A is sparse except for a few dense rows, a straightforward application of Cholesky or QR factorization will lead to catastrophic fill in the factor R. We consider handling such problems by a matrix stretching technique, where the dense rows are split into several more sparse rows. We develop both a recursive binary splitting algorithm and a more general splitting method. We show that for both schemes the stretched problem has the same set of solutions as the original least squares problem. Further, the condition number of the stretched problem differs from that of the original by only a modest factor, and hence the approach is numerically stable. Experimental results from applying the recursive binary scheme to a set of modified matrices from the Harwell‐Boeing collection are given. We conclude that when A has a small number of dense rows relative to its dimension, there is a significant gain in sparsity of the factor R. A crude estimate of the optimal number of splits is obtained by analysing a simple model problem. Copyright © 2000 John Wiley & Sons, Ltd.     

On generalized Nash equilibrium problems with linear coupling constraints and mixed-integer variables

ABSTRACT

We define and discuss different enumerative methods to compute solutions of generalized Nash equilibrium problems with linear coupling constraints and mixed-integer variables. We propose both branch-and-bound methods based on merit functions for the mixed-integer game, and branch-and-prune methods that exploit the concept of dominance to make effective cuts. We show that under mild assumptions the equilibrium set of the game is finite and we define an enumerative method to compute the whole of it. We show that our branch-and-prune method can be suitably modified in order to make a general equilibrium selection over the solution set of the mixed-integer game. We define an application in economics that can be modelled as a Nash game with linear coupling constraints and mixed-integer variables, and we adapt the branch-and-prune method to efficiently solve it.     

An efficient numerical method for preconditioned saddle point problems

In this paper, we consider the solution of linear systems of saddle point type by a preconditioned numerical method. We first transform the original linear system into two sub-systems with small size by a preconditioning strategy, then employ the conjugate gradient (CG) method to solve the linear system with a SPD coefficient matrix, and a splitting iteration method to solve the other sub-system, respectively. Numerical experiments show that the new method can achieve faster convergence than several effective preconditioners published in the recent literature in terms of total runtime and iteration steps.