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.     

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.     

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.     

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.     

Ensemble learning for the partial label ranking problem

The partial label ranking problem is a general interpretation of the preference learning scenario known as the label ranking problem, the goal of which is to learn preference classifiers able to predict a complete ranking with ties over the finite set of labels of the class variable. In this paper, we use unsupervised discretization techniques (equal-frequency and equal-width binning) to heuristically select the threshold for the numerical features in the algorithms based on induction of decision trees (partial label ranking trees algorithm). Moreover, we adapt the most well-known averaging (bootstrap aggregating and random forests) and boosting (adaptive boosting) ensemble methods to the partial label ranking problem, in order to improve the robustness of the built classifiers. We compare the proposed methods with the nearest neighbors-based algorithm (instance based partial label ranking) over the standard benchmark datasets, showing that our versions of the ensemble methods are superior in terms of accuracy. Furthermore, they are affordable in terms of computational efficiency.     

A new exact method for the two-dimensional orthogonal packing problem

The two-dimensional orthogonal packing problem (2OPP) consists in determining if a set of rectangles (items) can be packed into one rectangle of fixed size (bin). In this paper we propose two exact algorithms for solving this problem. The first algorithm is an improvement on a classical branch&bound method, whereas the second algorithm is based on a new relaxation of the problem. We also describe reduction procedures and lower bounds which can be used within enumerative methods. We report computational experiments for randomly generated benchmarks which demonstrate the efficiency of both methods: the second method is competitive compared to the best previous methods. It can be seen that our new relaxation allows an efficient detection of non-feasible instances.     

On the complexity of the multivariate Sturm–Liouville eigenvalue problem

We study the complexity of approximating the smallest eigenvalue of -Δ+q with Dirichlet boundary conditions on the d-dimensional unit cube. Here Δ is the Laplacian, and the function q is non-negative and has continuous first order partial derivatives. We consider deterministic and randomized classical algorithms, as well as quantum algorithms using quantum queries of two types: bit queries and power queries. We seek algorithms that solve the problem with accuracy . We exhibit lower and upper bounds for the problem complexity. The upper bounds follow from the cost of particular algorithms. The classical deterministic algorithm is optimal. Optimality is understood modulo constant factors that depend on d. The randomized algorithm uses an optimal number of function evaluations of q when d≤2. The classical algorithms have cost exponential in d since they need to solve an eigenvalue problem involving a matrix with size exponential in d. We show that the cost of quantum algorithms is not exponential in d, regardless of the type of queries they use. Power queries enjoy a clear advantage over bit queries and lead to an optimal complexity algorithm.     

On randomized algorithms for the majority problem

In the majority problem, we are given n balls coloured black or white and we are allowed to query whether two balls have the same colour or not. The goal is to find a ball of majority colour in the minimum number of queries. The answer is known to be n−B(n) where B(n) is the number of 1’s in the binary representation of n. In this paper we study randomized algorithms for determining majority, which are allowed to err with probability at most ε. We show that any such algorithm must have expected running time at least . Moreover, we provide a randomized algorithm which shows that this result is best possible. These extend a result of De Marco and Pelc [G. De Marco, A. Pelc, Randomized algorithms for determining the majority on graphs, Combin. Probab. Comput. 15 (2006) 823-834].     

A faster polynomial algorithm for the unbalanced Hitchcock transportation problem

We present a new algorithm for the Hitchcock transportation problem. On instances with n sources and k sinks, our algorithm has a worst-case running time of O(nk²(logn+klogk)). It closes a gap between algorithms with running time linear in n but exponential in k and a polynomial-time algorithm with running time O(nk²log²n).     

Hybrid inertial proximal algorithm for the split variational inclusion problem in Hilbert spaces with applications

In this paper, we present hybrid inertial proximal algorithms for the split variational inclusion problems in Hilbert spaces, and provide convergence theorems for the proposed algorithms. In fact, an inertial type algorithm was proposed as an acceleration process. As application, we study split minimization problem, split feasibility problem, relaxed split feasibility problem and linear inverse problem in real Hilbert spaces. Finally, numerical results are given for our main results.     

A greedy approximation algorithm for the group Steiner problem

In the group Steiner problem we are given an edge-weighted graph G=(V,E,w) and m subsets of vertices . Each subset g_i is called a group and the vertices in ?_ig_i are called terminals. It is required to find a minimum weight tree that contains at least one terminal from every group.We present a poly-logarithmic ratio approximation for this problem when the input graph is a tree. Our algorithm is a recursive greedy algorithm adapted from the greedy algorithm for the directed Steiner tree problem [Approximating the weight of shallow Steiner trees, Discrete Appl. Math. 93 (1999) 265-285, Approximation algorithms for directed Steiner problems, J. Algorithms 33 (1999) 73-91]. This is in contrast to earlier algorithms that are based on rounding a linear programming based relaxation for the problem [A polylogarithmic approximation algorithm for the Group Steiner tree problem, J. Algorithms 37 (2000) 66-84, preliminary version in Proceedings of SODA, 1998 pp. 253-259, On directed Steiner trees, Proceedings of SODA, 2002, pp. 59-63]. We answer in positive a question posed in [A polylogarithmic approximation algorithm for the Group Steiner tree problem, J. Algorithms 37 (2000) 66-84, preliminary version in Proceedings of SODA, 1998 pp. 253-259] on whether there exist good approximation algorithms for the group Steiner problem that are not based on rounding linear programs. For every fixed constant ε>0, our algorithm gives an approximation in polynomial time. Approximation algorithms for trees can be extended to arbitrary undirected graphs by probabilistically approximating the graph by a tree. This results in an additional multiplicative factor of in the approximation ratio, where |V| is the number of vertices in the graph. The approximation ratio of our algorithm on trees is slightly worse than the ratio of O(log(max_i|g_i|)·logm) provided by the LP based approaches.     

Optimizing garbage collection vehicle routing problem with alternative fuel-powered vehicles

Abstract

This paper considers the garbage collection problem in which vehicles with multiple compartments are used to collect the garbage. The vehicles are considered to be Alternative Fuel-powered Vehicles (AFVs). Compared with the traditional fossil fuel powered vehicles, the AFVs have limited fuel tank capacity. In addition, AFVs are allowed to refuel only at the depot. We provide a mathematical formulation and develop two solution approaches to solve the problem. The first approach is based on the saving algorithm, while the second is based on the ant colony system (ACS) metaheuristic. New problem instances have been generated to evaluate the performance of the proposed algorithms.     

A note on a symmetrical set covering problem: The lottery problem

In a lottery, n numbers are drawn from a set of m numbers. On a lottery ticket we fill out n numbers. Consider the following problem: what is the minimum number of tickets so that there is at least one ticket with at least p matching numbers? We provide a set-covering formulation for this problem and characterize its LP solution. The existence of many symmetrical alternative solutions, makes this a very difficult problem to solve, as our computational results indicate.     

Filtering Problem for Discrete Volterra Equations with Combined Disturbances

Abstract

A minimax filtering problem for discrete Volterra equations with combined noise models is considered. The combined models are defined as the sums of uncertain bounded deterministic functions and stochastic white noises. However, the corresponding variational problem turns out to be very difficult for direct solution. Therefore, simplified filtering algorithms are developed. The levels of nonoptimality for these simplified algorithms are introduced as the ratios of the filtering performances for the simplified and optimal estimators.

In opposite to the original variational problem, these levels can be easily evaluated numerically. Thus, simple filtering algorithms with guaranteed performance are obtained. Numerical experiments confirm the efficiency of our approach.     

Algorithms for nonexpansive self-mappings with application to the constrained multiple-set split convex feasibility fixed point problem in Hilbert spaces

In this article we devise two iteration schemes for approximating common fixed points of a finite family of nonexpansive mappings and establish the corresponding strong convergence theorem for the sequence generated by any one of our algorithms. Then we apply our results to approximate a solution of the so-called constrained multiple-set convex feasibility fixed point problem for firmly nonexpansive mappings which covers the multiple-set convex feasibility problem in the literature. In particular, our algorithms can be used to approximate the zero point problem of maximal monotone operators, and the equilibrium problem. Furthermore, the unique minimum norm solution can be obtained through our algorithms for each mentioned problem.     

An active index algorithm for the nearest point problem in a polyhedral cone

We consider the problem of finding the nearest point in a polyhedral cone C={x∈R ⁿ :D x≤0} to a given point b∈R ⁿ , where D∈R ^m×n . This problem can be formulated as a convex quadratic programming problem with special structure. We study the structure of this problem and its relationship with the nearest point problem in a pos cone through the concept of polar cones. We then use this relationship to design an efficient algorithm for solving the problem, and carry out computational experiments to evaluate its effectiveness. Our computational results show that our proposed algorithm is more efficient than other existing algorithms for solving this problem.     

Modified extragradient algorithms for solving equilibrium problems

ABSTRACT

In this paper, we introduce some new algorithms for solving the equilibrium problem in a Hilbert space which are constructed around the proximal-like mapping and inertial effect. Also, some convergence theorems of the algorithms are established under mild conditions. Finally, several experiments are performed to show the computational efficiency and the advantage of the proposed algorithm over other well-known algorithms.