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.     

Iterative methods for the split feasibility problem and the fixed point problem in Banach spaces

ABSTRACT

In this work, we suggest modifications of the self-adaptive method for solving the split feasibility problem and the fixed point problem of nonexpansive mappings in the framework of Banach spaces. Without the assumption on the norm of the operator, we prove that the sequences generated by our algorithms weakly and strongly converge to a solution of the problems. The numerical experiments are demonstrated to show the efficiency and the implementation of our algorithms.     

Strong convergence of two algorithms for the split feasibility problem in Banach spaces

ABSTRACT

In this paper, we consider the split feasibility problem in Banach spaces. By converting it to an equivalent null-point problem, we propose two iterative algorithms, which are new even in Hilbert spaces. The parameter in one algorithm is chosen in such a way that no priori knowledge of the operator norms is required. It is shown that these two algorithms are strongly convergent provided that the involved Banach spaces are smooth and uniformly convex. Finally, we conduct numerical experiments to support the validity of the obtained results.     

Modified subgradient extragradient algorithms for solving monotone variational inequalities

ABSTRACT

In this paper, we introduce two new algorithms for solving classical variational inequalities problem with Lipschitz continuous and monotone mapping in real Hilbert space. We modify the subgradient extragradient methods with a new step size, the convergence of algorithms are established without the knowledge of the Lipschitz constant of the mapping. Finally, some numerical experiments are presented to show the efficiency and advantage of the proposed algorithms.     

Making Augmented Lagrangian Methods Computer Amenable for Equilibrium Problems

ABSTRACT

We develop three algorithms to solve the subproblems generated by the augmented Lagrangian methods introduced by Iusem-Nasri (2010) for the equilibrium problem. The first algorithm that we propose incorporates the Newton method and the other two are instances of the subgradient projection method. One of our algorithms is also capable of solving nondifferentiable equilibrium problems. Using well-known test problems, all algorithms introduced here are implemented and numerical results are reported to compare their performances.     

Hybrid Moreau’s Proximal Algorithms and Convergence Theorems for Minimization Problems in Hilbert Spaces with Applications

Abstract

In this paper, motivated by Moreau’s proximal algorithm, we give several algorithms and related weak and strong convergence theorems for minimization problems under suitable conditions. These algorithms and convergence theorems are different from the results in the literatures. Besides, we also study algorithms and convergence theorems for the split feasibility problem in real Hilbert spaces. Finally, we give numerical results for our main results.     

Global minimization algorithms for concave quadratic programming problems

Abstract: In this article, we consider the concave quadratic programming problem which is known to be NP hard. Based on the improved global optimality conditions by [Dür, M., Horst, R. and Locatelli, M., 1998, Necessary and sufficient global optimality conditions for convex maximization revisited, Journal of Mathematical Analysis and Applications, 217, 637–649] and [Hiriart-Urruty, J.B. and Ledyav, J.S., 1996, A note in the characterization of the global maxima of a convex function over a convex set, Journal of Convex Analysis, 3, 55–61], we develop a new approach for solving concave quadratic programming problems. The main idea of the algorithms is to generate a sequence of local minimizers either ending at a global optimal solution or at an approximate global optimal solution within a finite number of iterations. At each iteration of the algorithms we solve a number of linear programming problems with the same constraints of the original problem. We also present the convergence properties of the proposed algorithms under some conditions. The efficiency of the algorithms has been demonstrated with some numerical examples.     

Continuous Contour Monte Carlo for Marginal Density Estimation With an Application to a Spatial Statistical Model

The problem of marginal density estimation for a multivariate density function f(x) can be generally stated as a problem of density function estimation for a random vector λ(x) of dimension lower than that of x. In this article, we propose a technique, the so-called continuous Contour Monte Carlo (CCMC) algorithm, for solving this problem. CCMC can be viewed as a continuous version of the contour Monte Carlo (CMC) algorithm recently proposed in the literature. CCMC abandons the use of sample space partitioning and incorporates the techniques of kernel density estimation into its simulations. CCMC is more general than other marginal density estimation algorithms. First, it works for any density functions, even for those having a rugged or unbalanced energy landscape. Second, it works for any transformation λ(x) regardless of the availability of the analytical form of the inverse transformation. In this article, CCMC is applied to estimate the unknown normalizing constant function for a spatial autologistic model, and the estimate is then used in a Bayesian analysis for the spatial autologistic model in place of the true normalizing constant function. Numerical results on the U.S. cancer mortality data indicate that the Bayesian method can produce much more accurate estimates than the MPLE and MCMLE methods for the parameters of the spatial autologistic model.     

On extragradient-viscosity methods for solving equilibrium and fixed point problems in a Hilbert space

Abstract

In this paper, new numerical algorithms are introduced for finding the solution of a variational inequality problem whose constraint set is the common elements of the set of fixed points of a demicontractive mapping and the set of solutions of an equilibrium problem for a monotone mapping in a real Hilbert space. The strong convergence of the iterates generated by these algorithms is obtained by combining a viscosity approximation method with an extragradient method. First, this is done when the basic iteration comes directly from the extragradient method, under a Lipschitz-type condition on the equilibrium function. Then, it is shown that this rather strong condition can be omitted when an Armijo-backtracking linesearch is incorporated into the extragradient iteration. The particular case of variational inequality problems is also examined.     

Random Variable Generation Using Concavity Properties of Transformed Densities

Abstract

Algorithms are developed for constructing random variable generators for families of densities. The generators depend on the concavity structure of a transformation of the density. The resulting algorithms are rejection algorithms and the methods of this article are concerned with constructing good rejection algorithms for general densities.     

Determinantal representations for the J transformation

Summary. The iterative J transformation [Homeier, H. H. H. (1993): Some applications of nonlinear convergence accelerators. Int. J. Quantum Chem. 45, 545-562] is of similar generality as the well-known E algorithm [Brezinski, C. (1980): A general extrapolation algorithm. Numer. Math. 35, 175-180. Havie, T. (1979): Generalized Neville type extrapolation schemes. BIT 19, 204-213]. The properties of the J transformation were studied recently in two companion papers [Homeier, H. H. H. (1994a): A hierarchically consistent, iterative sequence transformation. Numer. Algo. 8, 47-81. Homeier, H. H. H. (1994b): Analytical and numerical studies of the convergence behavior of the J transformation. J. Comput. Appl. Math., to appear]. In the present contribution, explicit determinantal representations for this sequence transformation are derived. The relation to the Brezinski-Walz theory [Brezinski, C., Walz, G. (1991): Sequences of transformations and triangular recursion schemes, with applications in numerical analysis. J. Comput. Appl. Math. 34, 361-383] is discussed. Overholt's process [Overholt, K. J. (1965): Extended Aitken acceleration. BIT 5, 122-132] is shown to be a special case of the J transformation. Consequently, explicit determinantal representations of Overholt's process are derived which do not depend on lower order transforms. Also, families of sequences are given for which Overholt's process is exact. As a numerical example, the Euler series is summed using the J transformation. The results indicate that the J transformation is a very powerful numerical tool. Received May 24, 1994 / Revised version received November 11, 1994     

On the best mean-square approximation of a real nonnegative finite continuous function of two variables by the modulus of a double Fourier integral. II

We continue the investigation of the nonlinear problem of mean-square approximation of a real finite nonnegative continuous function of two variables by the modulus of a double Fourier integral depending on two parameters begun in the first part of this work [J. Math. Sci., 160, No. 3, 343–356 (2009)]. Finding the solutions of this problem is reduced to the solution of a nonlinear two-dimensional integral equation of the Hammerstein type. We construct and justify numerical algorithms for determination of branching lines and branched solutions of this equation. Numerical examples are presented.     

Proximal type algorithms involving linesearch and inertial technique for split variational inclusion problem in hilbert spaces with applications

ABSTRACT

In convex optimization, numerous problems in applied sciences can be modelled as the split variational inclusion problem (SVIP). In this connection, we aim to design new and efficient proximal type algorithms which are based on the inertial technique and the linesearches terminology. We then discuss its convergence under some suitable conditions without the assumption on the operator norm. We also apply our main result to the split minimization problem, the split feasibility problem, the relaxed split feasibility problem and the linear inverse problem. Finally, we provide some numerical experiments and comparisons to these problems. The obtained result mainly improves the recent results investigated by Chuang.     

Primal interior-point decomposition algorithms for two-stage stochastic extended second-order cone programming

ABSTRACT

We study and solve the two-stage stochastic extended second-order cone programming problem. We show that the barrier recourse functions and the composite barrier functions for this optimization problem are self-concordant families with respect to barrier parameters. These results are used to develop primal decomposition-based interior-point algorithms. The worst case iteration complexity of the developed algorithms is shown to be the same as that for the short- and long-step primal interior algorithms applied to the extensive formulation of our problem.     

Extending Dantzig's bound to the bounded multiple-class binary Knapsack problem

 The bounded multiple-class binary knapsack problem is a variant of the knapsack problem where the items are partitioned into classes and the item weights in each class are a multiple of a class weight. Thus, each item has an associated multiplicity. The constraints consists of an upper bound on the total item weight that can be selected and upper bounds on the total multiplicity of items that can be selected in each class. The objective is to maximize the sum of the profits associated with the selected items. This problem arises as a sub-problem in a column generation approach to the cutting stock problem. A special case of this model, where item profits are restricted to be multiples of a class profit, corresponds to the problem obtained by transforming an integer knapsack problem into a 0-1 form. However, the transformation proposed here does not involve a duplication of solutions as the standard transformation typically does. The paper shows that the LP-relaxation of this model can be solved by a greedy algorithm in linear time, a result that extends those of Dantzig (1957) and Balas and Zemel (1980) for the 0-1 knapsack problem. Hence, one can derive exact algorithms for the multi-class binary knapsack problem by adapting existing algorithms for the 0-1 knapsack problem. Computational results are reported that compare solving a bounded integer knapsack problem by transforming it into a standard binary knapsack problem versus using the multiple-class model as a 0-1 form. Received: May 1998 / Accepted: February 2002-09-04 Published online: December 9, 2002 Key Words. Knapsack problem – integer programming – linear programming relaxation     

Parallel Algorithms for Solving a Class of Variational Inequalities over the Common Fixed Points Set of a Finite Family of Demicontractive Mappings

Abstract

We propose parallel algorithms for solving a class of variational inequalities over the set of common fixed points for a finite family of demicontractive mappings in real Hilbert spaces. Under some suitable conditions, we prove that the sequence generated by the proposed algorithms converges strongly to a solution of the problem. We apply the proposed algorithms to strongly monotone variational inequality problems with pseudomonotone equilibrium constraints by defining a quasi-nonexpansive and demi-closed mapping whose fixed point set coincides with the solution set of the equilibrium problem.     

New subgradient extragradient methods for solving monotone bilevel equilibrium problems

ABSTRACT

In this paper, we propose new subgradient extragradient methods for finding a solution of a strongly monotone equilibrium problem over the solution set of another monotone equilibrium problem which usually is called monotone bilevel equilibrium problem in Hilbert spaces. The first proposed algorithm is based on the subgradient extragradient method presented by Censor et al. [Censor Y, Gibali A, Reich S. The subgradient extragradient method for solving variational inequalities in Hilbert space. J Optim Theory Appl. 2011;148:318–335]. The strong convergence of the algorithm is established under monotone assumptions of the cost bifunctions with Lipschitz-type continuous conditions recently presented by Mastroeni in the auxiliary problem principle. We also present a modification of the algorithm for solving an equilibrium problem, where the constraint domain is the common solution set of another equilibrium problem and a fixed point problem. Several fundamental experiments are provided to illustrate the numerical behaviour of the algorithms and to compare with others.     

Primal and dual algorithms for optimization over the efficient set

ABSTRACT

Optimization over the efficient set of a multi-objective optimization problem is a mathematical model for the problem of selecting a most preferred solution that arises in multiple criteria decision-making to account for trade-offs between objectives within the set of efficient solutions. In this paper, we consider a particular case of this problem, namely that of optimizing a linear function over the image of the efficient set in objective space of a convex multi-objective optimization problem. We present both primal and dual algorithms for this task. The algorithms are based on recent algorithms for solving convex multi-objective optimization problems in objective space with suitable modifications to exploit specific properties of the problem of optimization over the efficient set. We first present the algorithms for the case that the underlying problem is a multi-objective linear programme. We then extend them to be able to solve problems with an underlying convex multi-objective optimization problem. We compare the new algorithms with several state of the art algorithms from the literature on a set of randomly generated instances to demonstrate that they are considerably faster than the competitors.     

Fast Wavelet Transform for Toeplitz Matrices and Property Analysis

Fast wavelet transform algorithms for Toeplitz matrices are proposed in this paper. Distinctive from the well known discrete trigonometric transforms, such as the discrete cosine transform （DCT） and the discrete Fourier transform （DFT） for Toeplitz matrices, the new algorithms are achieved by compactly supported wavelet that preserve the character of a Toeplitz matrix after transform, which is quite useful in many applications involving a Toeplitz matrix. Results of numerical experiments show that the proposed method has good compression performance similar to using wavelet in the digital image coding. Since the proposed algorithms turn a dense Toeplitz matrix into a band-limited form, the arithmetic operations required by the new algorithms are O（N） that are reduced greatly compared with O（N log N） by the classical trigonometric transforms.     

Dual Representation of the Cost of Designing a Portfolio Satisfying Multiple Risk Constraints

ABSTRACT

We consider, within a Markovian complete financial market, the problem of finding the least expensive portfolio process meeting, at each payment date, three different types of risk criterion. Two of them encompass an expected utility-based measure and a quantile hedging constraint imposed at inception on all the future payment dates, while the other one is a quantile hedging constraint set at each payment date over the next one. The quantile risk measures are defined with respect to a stochastic benchmark and the expected utility-based constraint is applied to random payment dates. We explicit the Legendre-Fenchel transform of the pricing function. We also provide, for each quantile hedging problem, a backward dual algorithm allowing to compute their associated value function by backward recursion. The algorithms are illustrated with a numerical example.