Finding the projection of a point onto the intersection of convex sets via projections onto half-spaces

We present a modification of Dykstra's algorithm which allows us to avoid projections onto general convex sets. Instead, we calculate projections onto either a half-space or onto the intersection of two half-spaces. Convergence of the algorithm is established and special choices of the half-spaces are proposed.The option to project onto half-spaces instead of general convex sets makes the algorithm more practical. The fact that the half-spaces are quite general enables us to apply the algorithm in a variety of cases and to generalize a number of known projection algorithms.The problem of projecting a point onto the intersection of closed convex sets receives considerable attention in many areas of mathematics and physics as well as in other fields of science and engineering such as image reconstruction from projections.In this work we propose a new class of algorithms which allow projection onto certain super half-spaces, i.e., half-spaces which contain the convex sets. Each one of the algorithms that we present gives the user freedom to choose the specific super half-space from a family of such half-spaces. Since projecting a point onto a half-space is an easy task to perform, the new algorithms may be more useful in practical situations in which the construction of the super half-spaces themselves is not too difficult.     

Iterative Algorithms for Equilibrium Problems

We consider equilibrium problems in the framework of the formulation proposed by Blum and Oettli, which includes variational inequalities, Nash equilibria in noncooperative games, and vector optimization problems, for instance, as particular cases. We show that such problems are particular instances of convex feasibility problems with infinitely many convex sets, but with additional structure, so that projection algorithms for convex feasibility can be modified in order to improve their convergence properties, mainly achieving global convergence without either compactness or coercivity assumptions. We present a sequential projections algorithm with an approximately most violated constraint control strategy, and two variants where exact orthogonal projections are replaced by approximate ones, using separating hyperplanes generated by subgradients. We include full convergence analysis of these algorithms.     

Hilbertian convex feasibility problem: Convergence of projection methods

The classical problem of finding a point in the intersection of countably many closed and convex sets in a Hilbert space is considered. Extrapolated iterations of convex combinations of approximate projections onto subfamilies of sets are investigated to solve this problem. General hypotheses are made on the regularity of the sets and various strategies are considered to control the order in which the sets are selected. Weak and strong convergence results are established within thisbroad framework, which provides a unified view of projection methods for solving hilbertian convex feasibility problems. This work was supported by the National Science Foundation under Grant MIP-9308609.     

Modified basic projection methods for a class of equilibrium problems

Projection methods are a popular class of methods for solving equilibrium problems. In this paper, we propose approximate one projection methods for solving a class of equilibrium problems, where the cost bifunctions are paramonotone, the feasible sets are defined by a continuous convex function inequality and not necessarily differentiable in the Euclidean space \(\mathcal R^{s}\). At each main iteration step in our algorithms, the usual projections onto the feasible set are replaced by computing inexact subgradients and one projection onto the intersection of two halfspaces containing the solution set of the equilibrium problems. Then, by choosing suitable parameters, we prove convergence of the whole generated sequence to a solution of the problems, under only the assumptions of continuity and paramonotonicity of the bifunctions. Finally, we present some computational examples to illustrate the assumptions of the proposed algorithms.     

Incomplete oblique projections for solving large inconsistent linear systems

The authors introduced in previously published papers acceleration schemes for Projected Aggregation Methods (PAM), aiming at solving consistent linear systems of equalities and inequalities. They have used the basic idea of forcing each iterate to belong to the aggregate hyperplane generated in the previous iteration. That scheme has been applied to a variety of projection algorithms for solving systems of linear equalities or inequalities, proving that the acceleration technique can be successfully used for consistent problems. The aim of this paper is to extend the applicability of those schemes to the inconsistent case, employing incomplete projections onto the set of solutions of the augmented system Ax − r = b. These extended algorithms converge to the least squares solution. For that purpose, oblique projections are used and, in particular, variable oblique incomplete projections are introduced. They are defined by means of matrices that penalize the norm of the residuals very strongly in the first iterations, decreasing their influence with the iteration counter in order to fulfill the convergence conditions. The theoretical properties of the new algorithms are analyzed, and numerical experiences are presented comparing their performance with several well-known projection methods. Dedicated to Clovis Gonzaga on the occassion of his 60th birthday.     

Alternating convex projection methods for discrete-time covariance control design

The problem of designing a controller for a linear, discretetime system is formulated as a problem of designing an appropriate plant-state covariance matrix. Closed-loop stability and multiple-output performance constraints are expressed geometrically as requirements that the covariance matrix lies in the intersection of some specified closed, convex sets in the space of symmetric matrices. We solve a covariance feasibility problem to determine the existence and compute a covariance matrix to satisty assignability and output-norm performance constraints. In addition, we can treat a covariance optimization problem to construct an assignable covariance matrix which satisfies output performance constraints and is as close as possible to a given desired covariance. We can also treat inconsistent constraints, where we look for an assignable covariance which best approximates desired but unachievable output performance objectives; we call this the infeasible covariance optimization problem. All these problems are of a convex nature, and alternating convex projection methods are proposed to solve them, exploiting the geometric formulation of the problem. To this end, analytical expressions for the projections onto the covariance assignability and the output covariance inequality constraint sets are derived. Finally, the problem of designing low-order dynamic controllers using alternating projections is discussed, and a numerical technique using alternating projections is suggested for a solution, although convergence of the algorithm is not guaranteed in this case. A control design example for a fighter aircraft model illustrates the method.This research was completed while the first author was with the Space Systems Control Laboratory at Purdue University. Support from the Army Research Office Grant ARO-29029-EG is gratefully acknowledged.     

A multiprojection algorithm using Bregman projections in a product space

Generalized distances give rise to generalized projections into convex sets. An important question is whether or not one can use within the same projection algorithm different types of such generalized projections. This question has practical consequences in the area of signal detection and image recovery in situations that can be formulated mathematically as a convex feasibility problem. Using an extension of Pierra's product space formalism, we show here that a multiprojection algorithm converges. Our algorithm is fully simultaneous, i.e., it uses in each iterative stepall sets of the convex feasibility problem. Different multiprojection algorithms can be derived from our algorithmic scheme by a judicious choice of the Bregman functions which govern the process. As a by-product of our investigation we also obtain blockiterative schemes for certain kinds of linearly constraned optimization problems.     

Remark on the Successive Projection Algorithm for the Multiple-Sets Split Feasibility Problem

Recently, assuming that the metric projection onto a closed convex set is easily calculated, Liu et al. (Numer. Func. Anal. Opt. 35:1459–1466, 2014) presented a successive projection algorithm for solving the multiple-sets split feasibility problem (MSFP). However, in some cases it is impossible or needs too much work to exactly compute the metric projection. The aim of this remark is to give a modification to the successive projection algorithm. That is, we propose a relaxed successive projection algorithm, in which the metric projections onto closed convex sets are replaced by the metric projections onto halfspaces. Clearly, the metric projection onto a halfspace may be directly calculated. So, the relaxed successive projection algorithm is easy to implement. Its theoretical convergence results are also given.     

The composition of projections onto closed convex sets in Hilbert space is asymptotically regular

The composition of finitely many projections onto closed convex sets in Hilbert space arises naturally in the area of projection algorithms. We show that this composition is asymptotically regular, thus proving the so-called ``zero displacement conjecture' of Bauschke, Borwein and Lewis. The proof relies on a rich mix of results from monotone operator theory, fixed point theory, and convex analysis.

     

Proximal level bundle methods for convex nondifferentiable optimization,saddle-point problems and variational inequalities

We study proximal level methods for convex optimization that use projections onto successive approximations of level sets of the objective corresponding to estimates of the optimal value. We show that they enjoy almost optimal efficiency estimates. We give extensions for solving convex constrained problems, convex-concave saddle-point problems and variational inequalities with monotone operators. We present several variants, establish their efficiency estimates, and discuss possible implementations. In particular, our methods require bounded storage in contrast to the original level methods of Lemaréchal, Nemirovskii and Nesterov.This research was supported by the Polish Academy of Sciences.Supported by a grant from the French Ministry of Research and Technology.     

Finding a best approximation pair of points for two polyhedra

Given two disjoint convex polyhedra, we look for a best approximation pair relative to them, i.e., a pair of points, one in each polyhedron, attaining the minimum distance between the sets. Cheney and Goldstein showed that alternating projections onto the two sets, starting from an arbitrary point, generate a sequence whose two interlaced subsequences converge to a best approximation pair. We propose a process based on projections onto the half-spaces defining the two polyhedra, which are more negotiable than projections on the polyhedra themselves. A central component in the proposed process is the Halpern–Lions–Wittmann–Bauschke algorithm for approaching the projection of a given point onto a convex set.     

Almost sure convergence of random projected proximal and subgradient algorithms for distributed nonsmooth convex optimization

Two distributed algorithms are described that enable all users connected over a network to cooperatively solve the problem of minimizing the sum of all users’ objective functions over the intersection of all users’ constraint sets, where each user has its own private nonsmooth convex objective function and closed convex constraint set, which is the intersection of a number of simple, closed convex sets. One algorithm enables each user to adjust its estimate using the proximity operator of its objective function and the metric projection onto one constraint set randomly selected from a number of simple, closed convex sets. The other determines each user’s estimate using the subdifferential of its objective function instead of the proximity operator. Investigation of the two algorithms’ convergence properties for a diminishing step-size rule revealed that, under certain assumptions, the sequences of all users generated by each of the two algorithms converge almost surely to the same solution. It also showed that the rate of convergence depends on the step size and that a smaller step size results in quicker convergence. The results of numerical evaluation using a nonsmooth convex optimization problem support the convergence analysis and demonstrate the effectiveness of the two algorithms.     

Deterministic global optimization with partition sets whose feasibility is not known: Application to concave minimization,reverse convex constraints,DC-programming,and Lipschitzian optimization

A crucial problem for many global optimization methods is how to handle partition sets whose feasibility is not known. This problem is solved for broad classes of feasible sets including convex sets, sets defined by finitely many convex and reverse convex constraints, and sets defined by Lipschitzian inequalities. Moreover, a fairly general theory of bounding is presented and applied to concave objective functions, to functions representable as differences of two convex functions, and to Lipschitzian functions. The resulting algorithms allow one to solve any global optimization problem whose objective function is of one of these forms and whose feasible set belongs to one of the above classes. In this way, several new fields of optimization are opened to the application of global methods.     

Risk-Averse Stochastic Programming and Distributionally Robust Optimization Via Operator Splitting

This work deals with a broad class of convex optimization problems under uncertainty. The approach is to pose the original problem as one of finding a zero of the sum of two appropriate monotone operators, which is solved by the celebrated Douglas-Rachford splitting method. The resulting algorithm, suitable for risk-averse stochastic programs and distributionally robust optimization with fixed support, separates the random cost mapping from the risk function composing the problem’s objective. Such a separation is exploited to compute iterates by alternating projections onto different convex sets. Scenario subproblems, free from the risk function and thus parallelizable, are projections onto the cost mappings’ epigraphs. The risk function is handled in an independent and dedicated step consisting of evaluating its proximal mapping that, in many important cases, amounts to projecting onto a certain ambiguity set. Variables get updated by straightforward projections on subspaces through independent computations for the various scenarios. The investigated approach enjoys significant flexibility and opens the way to handle, in a single algorithm, several classes of risk measures and ambiguity sets.

     

Steered sequential projections for the inconsistent convex feasibility problem

We study a steered sequential gradient algorithm which minimizes the sum of convex functions by proceeding cyclically in the directions of the negative gradients of the functions and using steered step-sizes. This algorithm is applied to the convex feasibility problem by minimizing a proximity function which measures the sum of the Bregman distances to the members of the family of convex sets. The resulting algorithm is a new steered sequential Bregman projection method which generates sequences that converge if they are bounded, regardless of whether the convex feasibility problem is or is not consistent. For orthogonal projections and affine sets the boundedness condition is always fulfilled.     

On the convergence of inexact block coordinate descent methods for constrained optimization

We consider the problem of minimizing a smooth function over a feasible set defined as the Cartesian product of convex compact sets. We assume that the dimension of each factor set is huge, so we are interested in studying inexact block coordinate descent methods (possibly combined with column generation strategies). We define a general decomposition framework where different line search based methods can be embedded, and we state global convergence results. Specific decomposition methods based on gradient projection and Frank–Wolfe algorithms are derived from the proposed framework. The numerical results of computational experiments performed on network assignment problems are reported.     

Convex feasibility modeling and projection methods for sparse signal recovery

A computationally-efficient method for recovering sparse signals from a series of noisy observations, known as the problem of compressed sensing (CS), is presented. The theory of CS usually leads to a constrained convex minimization problem. In this work, an alternative outlook is proposed. Instead of solving the CS problem as an optimization problem, it is suggested to transform the optimization problem into a convex feasibility problem (CFP), and solve it using feasibility-seeking sequential and simultaneous subgradient projection methods, which are iterative, fast, robust and convergent schemes for solving CFPs. As opposed to some of the commonly-used CS algorithms, such as Bayesian CS and Gradient Projections for sparse reconstruction, which become inefficient as the problem dimension and sparseness degree increase, the proposed methods exhibit robustness with respect to these parameters. Moreover, it is shown that the CFP-based projection methods are superior to some of the state-of-the-art methods in recovering the signal’s support. Numerical experiments show that the CFP-based projection methods are viable for solving large-scale CS problems with compressible signals.     

Reflection-Projection Method for Convex Feasibility Problems with an Obtuse Cone

The convex feasibility problem asks to find a point in the intersection of finitely many closed convex sets in Euclidean space. This problem is of fundamental importance in the mathematical and physical sciences, and it can be solved algorithmically by the classical method of cyclic projections.In this paper, the case where one of the constraints is an obtuse cone is considered. Because the nonnegative orthant as well as the set of positive-semidefinite symmetric matrices form obtuse cones, we cover a large and substantial class of feasibility problems. Motivated by numerical experiments, the method of reflection-projection is proposed: it modifies the method of cyclic projections in that it replaces the projection onto the obtuse cone by the corresponding reflection.This new method is not covered by the standard frameworks of projection algorithms because of the reflection. The main result states that the method does converge to a solution whenever the underlying convex feasibility problem is consistent. As prototypical applications, we discuss in detail the implementation of two-set feasibility problems aiming to find a nonnegative [resp. positive semidefinite] solution to linear constraints in ⁿ [resp. in , the space of symmetric n×n matrices] and we report on numerical experiments. The behavior of the method for two inconsistent constraints is analyzed as well.     

Charged ball method for solving some computational geometry problems

The concept of replacement of the initial stationary optimization problem with some nonstationary mechanical system tending with time to the position of equilibrium, which coincides with the solution of the initial problem, makes it possible to construct effective numerical algorithms. First, differential equations of the movement should be derived. Then we pass to the difference scheme and define the iteration algorithm. There is a wide class of optimization methods constructed in such a way. One of the most known representatives of this class is the heavy ball method. As a rule, such type of algorithms includes parameters that highly affect the convergence rate. In this paper, the charged ball method, belonging to this class, is proposed and investigated. It is a new effective optimization method that allows solving some computational geometry problems. A problem of orthogonal projection of a point onto a convex closed set with a smooth boundary and the problem of finding the minimum distance between two such sets are considered in detail. The convergence theorems are proved, and the estimates for the convergence rate are found. Numerical examples illustrating the work of the proposed algorithms are given.     

Perturbed projections and subgradient projections for the multiple-sets split feasibility problem

We study the multiple-sets split feasibility problem that requires to find a point closest to a family of closed convex sets in one space such that its image under a linear transformation will be closest to another family of closed convex sets in the image space. By casting the problem into an equivalent problem in a suitable product space we are able to present a simultaneous subgradients projections algorithm that generates convergent sequences of iterates in the feasible case. We further derive and analyze a perturbed projection method for the multiple-sets split feasibility problem and, additionally, furnish alternative proofs to two known results.