Description:
The Douglas–Rachford algorithm is a popular algorithm for solving both convex and nonconvex feasibility problems. While its behaviour is settled in the convex inconsistent case, the general nonconvex inconsistent case is far from being fully understood. In this paper, we focus on the most simple nonconvex inconsistent case: when one set is a hyperplane and the other a doubleton (i.e., a two-point set). We present a characterization of cycling in this case which—somewhat surprisingly—depends on whether the ratio of the distance of the points to the hyperplane is rational or not. Furthermore, we provide closed-form expressions as well as several concrete examples which illustrate the dynamical richness of this algorithm.
Description:
The Douglas–Rachford algorithm is a simple yet effective method for solving convex feasibility problems. However, if the underlying constraints are inconsistent, then the convergence theory is incomplete. We provide convergence results when one constraint is an affine subspace. As a consequence, we extend a result by Spingarn from halfspaces to general closed convex sets admitting least-squares solutions.
Description:
The Douglas–Rachford algorithm is a classical and very successful method for solving optimization and feasibility problems. In this paper, we provide novel conditions sufficient for finite convergence in the context of convex feasibility problems. Our analysis builds upon, and considerably extends, pioneering work by Spingarn. Specifically, we obtain finite convergence in the presence of Slater’s condition in the affine-polyhedral and in a hyperplanar-epigraphical case. Various examples illustrate our results. Numerical experiments demonstrate the competitiveness of the Douglas–Rachford algorithm for solving linear equations with a positivity constraint when compared to the method of alternating projections and the method of reflection–projection.
Description:
We propose a flexible approach for computing the resolvent of the sum of weakly monotone operators in real Hilbert spaces. This relies on splitting methods where strong convergence is guaranteed. We also prove linear convergence under Lipschitz continuity assumption. The approach is then applied to computing the proximity operator of the sum of weakly convex functions, and particularly to finding the best approximation to the intersection of convex sets.
Description:
Delamination is a typical failure mode of composite materials caused by weak bonding. It arises when a crack initiates and propagates under a destructive loading. Given the physical law characterizing the properties of the interlayer adhesive between the bonded bodies, we consider the problem of computing the propagation of the crack front and the stress field along the contact boundary. This leads to a hemivariational inequality, which after discretization by finite elements we solve by a nonconvex bundle method, where upper- C 1 criteria have to be minimized. As this is in contrast with other classes of mechanical problems with non-monotone friction laws and in other applied fields, where criteria are typically lower- C 1 , we propose a bundle method suited for both types of nonsmoothness. We prove its global convergence in the sense of subsequences and test it on a typical delamination problem of material sciences.
Description:
Mobile devices are widely used for uploading/downloading media files such as audio, video and images to/from the remote servers. These devices have limited resources and are required to offload resource-consuming media processing tasks to the clouds for further processing. Migration of these tasks means that the media services provided by the clouds need to be authentic and trusted by the mobile users. The existing schemes for secure exchange of media files between the mobile devices and the clouds have limitations in terms of memory support, processing load, battery power, and data size. These schemes lack the support for large-sized video files and are not suitable for resource-constrained mobile devices. This paper proposes a secure, lightweight, robust, and efficient scheme for data exchange between the mobile users and the media clouds. The proposed scheme considers High Efficiency Video Coding (HEVC) Intra-encoded video streams in unsliced mode as a source for data hiding. Our proposed scheme aims to support real-time processing with power-saving constraint in mind. Advanced Encryption Standard (AES) is used as a base encryption technique by our proposed scheme. The simulation results clearly show that the proposed scheme outperforms AES-256 by decreasing the processing time up to 4.76% and increasing the data size up to 0.72% approximately. The proposed scheme can readily be applied to real-time cloud media streaming.
Description:
In this paper, we introduce and study a class of structured set-valued operators, which we call union averaged nonexpansive . At each point in their domain, the value of such an operator can be expressed as a finite union of single-valued averaged nonexpansive operators. We investigate various structural properties of the class and show, in particular, that is closed under taking unions, convex combinations, and compositions, and that their fixed point iterations are locally convergent around strong fixed points. We then systematically apply our results to analyze proximal algorithms in situations, where union averaged nonexpansive operators naturally arise. In particular, we consider the problem of minimizing the sum two functions, where the first is convex and the second can be expressed as the minimum of finitely many convex functions.
Description:
This paper is concerned with the linkedness of Cartesian products of complete graphs. A graph with at least 2k vertices is k-linked if, for every set of 2k distinct vertices organised in arbitrary k pairs of vertices, there are k vertex-disjoint paths joining the vertices in the pairs. We show that the Cartesian product Kd1+1 × Kd2+1 of complete graphs Kd1+1 and Kd2+1 is
Description:
This paper is concerned with the linkedness of Cartesian products of complete graphs. A graph with at least 2k vertices is k-linked if, for every set of 2k distinct vertices organised in arbitrary k pairs of vertices, there are k vertex-disjoint paths joining the vertices in the pairs. We show that the Cartesian product Kd1+1 × Kd2+1 of complete graphs Kd1+1 and Kd2+1 is