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.     

Some properties of generalized proximal point methods for quadratic and linear programming

The proximal point method for convex optimization has been extended recently through the use of generalized distances (e.g., Bregman distances) instead of the Euclidean one. One advantage of these extensions is the possibility of eliminating certain constraints (mainly positivity) from the subproblems, transforming an inequality constrained problem into a sequence of unconstrained or equality constrained problems. We consider here methods obtained using a certain class of Bregman functions applied to convex quadratic (including linear) programming, which are of the interior-point type. We prove that the limit of the sequence generated by the method lies in the relative interior of the solution set, and furthermore is the closest optimal solution to the initial point, in the sense of the Bregman distance. These results do not hold for the standard proximal point method, i.e., when the square of the Euclidean norm is used as the Bregman distance.The research leading to this paper was partially supported by CNPq Grant 301280/86.We thank two anonymous referees whose comments and suggestions allowed us to improve our results in a significant way.     

Approximating a Zero of Sum of Two Monotone Operators Which Solves a Fixed Point Problem in Reflexive Banach Spaces

Abstract

The purpose of this paper is to introduce an iterative method for approximating a point in the set of zeros of the sum of two monotone mappings, which is also a solution of a fixed point problem for a Bregman strongly nonexpansive mapping in a real reflexive Banach space. With our iterative technique, we state and prove a strong convergence theorem for approximating an element in the intersection of the set of solutions of a variational inclusion problem for sum of two monotone mappings and the set of solutions of a fixed point problem for Bregman strongly nonexpansive mapping. We give applications of our result to convex minimization problem, convex feasibility problem, variational inequality problem, and equilibrium problem. Our result complements and extends some recent results in literature.     

Generalized Bregman Projections in Convex Feasibility Problems

We present a method for finding common points of finitely many closed convex sets in Euclidean space. The Bregman extension of the classical method of cyclic orthogonal projections employs nonorthogonal projections induced by a convex Bregman function, whereas the Bauschke and Borwein method uses Bregman/Legendre functions. Our method works with generalized Bregman functions (B-functions) and inexact projections, which are easier to compute than the exact ones employed in other methods. We also discuss subgradient algorithms with Bregman projections.     

Proximity Function Minimization Using Multiple Bregman Projections, with Applications to Split Feasibility and Kullback–Leibler Distance Minimization

Problems in signal detection and image recovery can sometimes be formulated as a convex feasibility problem (CFP) of finding a vector in the intersection of a finite family of closed convex sets. Algorithms for this purpose typically employ orthogonal or generalized projections onto the individual convex sets. The simultaneous multiprojection algorithm of Censor and Elfving for solving the CFP, in which different generalized projections may be used at the same time, has been shown to converge for the case of nonempty intersection; still open is the question of its convergence when the intersection of the closed convex sets is empty.Motivated by the geometric alternating minimization approach of Csiszár and Tusnády and the product space formulation of Pierra, we derive a new simultaneous multiprojection algorithm that employs generalized projections of Bregman to solve the convex feasibility problem or, in the inconsistent case, to minimize a proximity function that measures the average distance from a point to all convex sets. We assume that the Bregman distances involved are jointly convex, so that the proximity function itself is convex. When the intersection of the convex sets is empty, but the closure of the proximity function has a unique global minimizer, the sequence of iterates converges to this unique minimizer. Special cases of this algorithm include the Expectation Maximization Maximum Likelihood (EMML) method in emission tomography and a new convergence result for an algorithm that solves the split feasibility problem.     

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.     

Bregman distances and Chebyshev sets

A closed set of a Euclidean space is said to be Chebyshev if every point in the space has one and only one closest point in the set. Although the situation is not settled in infinite-dimensional Hilbert spaces, in 1932 Bunt showed that in Euclidean spaces a closed set is Chebyshev if and only if the set is convex. In this paper, from the more general perspective of Bregman distances, we show that if every point in the space has a unique nearest point in a closed set, then the set is convex. We provide two approaches: one is by nonsmooth analysis; the other by maximal monotone operator theory. Subdifferentiability properties of Bregman nearest distance functions are also given.     

A proximal method with separable Bregman distances for quasiconvex minimization over the nonnegative orthant

We present an interior proximal method with Bregman distance, for solving the minimization problem with quasiconvex objective function under nonnegative constraints. The Bregman function is considered separable and zone coercive, and the zone is the interior of the positive orthant. Under the assumption that the solution set is nonempty and the objective function is continuously differentiable, we establish the well definedness of the sequence generated by our algorithm and obtain two important convergence results, and show in the main one that the sequence converges to a solution point of the problem when the regularization parameters go to zero.     

On inexact generalized proximal methods with a weakened error tolerance criterion

Two inexact versions of a Bregman-function-based proximal method for finding a zero of a maximal monotone operator, suggested in [J. Eckstein (1998). Approximate iterations in Bregman-function-based proximal algorithms. Math. Programming, 83, 113–123; P. da Silva, J. Eckstein and C. Humes (2001). Rescaling and stepsize selection in proximal methods using separable generalized distances. SIAM J. Optim., 12, 238–261], are considered. For a wide class of Bregman functions, including the standard entropy kernel and all strongly convex Bregman functions, convergence of these methods is proved under an essentially weaker accuracy condition on the iterates than in the original papers.

Also the error criterion of a logarithmic–quadratic proximal method, developed in [A. Auslender, M. Teboulle and S. Ben-Tiba (1999). A logarithmic-quadratic proximal method for variational inequalities. Computational Optimization and Applications, 12, 31–40], is relaxed, and convergence results for the inexact version of the proximal method with entropy-like distance functions are described.

For the methods mentioned, like in [R.T. Rockafellar (1976). Monotone operators and the proximal point algorithm. SIAM J. Control Optim., 14, 877–898] for the classical proximal point algorithm, only summability of the sequence of error vector norms is required.     

Computational Experience with a New Class of Convex Underestimators: Box-constrained NLP Problems

In Akrotirianakis and Floudas (2004) we presented the theoretical foundations of a new class of convex underestimators for C ² nonconvex functions. In this paper, we present computational experience with those underestimators incorporated within a Branch-and-Bound algorithm for box-conatrained problems. The algorithm can be used to solve global optimization problems that involve C ² functions. We discuss several ways of incorporating the convex underestimators within a Branch-and-Bound framework. The resulting Branch-and-Bound algorithm is then used to solve a number of difficult box-constrained global optimization problems. A hybrid algorithm is also introduced, which incorporates a stochastic algorithm, the Random-Linkage method, for the solution of the nonconvex underestimating subproblems, arising within a Branch-and-Bound framework. The resulting algorithm also solves efficiently the same set of test problems.     

Strong Restricted-Orientation Convexity

Strong restricted-orientation convexity is a generalization of standard convexity. We explore the properties of strongly convex sets in multidimensional Euclidean space and identify major properties of standard convex sets that also hold for strong convexity. We characterize strongly convex flats and halfspaces, and establish the strong convexity of the affine hull of a strongly convex set. We then show that, for every point in the boundary of a strongly convex set, there is a supporting strongly convex hyperplane through it. Finally, we show that a closed set with nonempty interior is strongly convex if and only if it is the intersection of strongly convex halfspaces; we state a condition under which this result extends to sets with empty interior.     

An interior points algorithm for the convex feasibility problem

The problem of finding a point in the intersection of a finite family of convex sets in the Euclidean space R″ is considered here. We present a general algorithmic scheme which employs projections onto separating hyperplanes instead of projections onto the convex sets. This scheme includes the method of successive projections of Gubin et al., USSR Comp. Math. and Math. Phys. 7 (1967), 1–24, as a special case. A different realization proposed here is capable of handling the problem when the sets are solid and an interior point of each set is available. This alternative algorithm may, in certain cases, be more attractive than the method of Gubin et al.     

On finitely convergent iterative methods for the convex feasibility problem

Iterative algorithms for the Convex Feasibility Problem can be modified so that at iterationk the original convex sets are perturbed with a parameter ε_k which tends to zero ask increases. We establish conditions on such algorithms which guarantee existence of a sequence of perturbation parameters which make them finitely convergent when applied to a convex feasibility problem whose feasible set has non empty interior.     

Well-positioned Closed Convex Sets and Well-positioned Closed Convex Functions

We characterize the class of those closed convex sets which have a barrier cone with a nonempty interior. As a consequence, we describe the set of those proper extended-real-valued functionals for which the domain of their Fenchel conjugate has a nonempty interior. As an application, we study the stability of the solution set of a semi-coercive variational inequality.     

Dykstras algorithm with bregman projections: A convergence proof

Dykstra’s algorithm and the method of cyclic Bregman projections are often employed to solve best approximation and convex feasibility problems, which are fundamental in mathematics and the physical sciences. Censor and Reich very recently suggested a synthesis of these methods, Dykstra’s algorithm with Bregman projections, to tackle a non-orthogonal best approximation problem, They obtained convergence when each constraint is a halfspace. It is shown here that this new algorithm works for general closed convex constraints; this complements Censor and Reich’s result and relates to a framework by Tseng. The proof rests on Boyle and Dykstra’s original work and on strong properties of Bregman distances corresponding to Legendre functions. Special cases and observations simplifying the implementation of the algorithm are aiso discussed     

A sequential iteration algorithm with non-monotoneous behaviour in the method of projections onto convex sets

The method of projections onto convex sets to find a point in the intersection of a finite number of closed convex sets in a Euclidean space, may lead to slow convergence of the constructed sequence when that sequence enters some narrow “corridor” between two or more convex sets. A way to leave such corridor consists in taking a big step at different moments during the iteration, because in that way the monotoneous behaviour that is responsible for the slow convergence may be interrupted. In this paper we present a technique that may introduce interruption of the monotony for a sequential algorithm, but that at the same time guarantees convergence of the constructed sequence to a point in the intersection of the sets. We compare experimentally the behaviour concerning the speed of convergence of the new algorithm with that of an existing monotoneous algorithm.     

A majorization–minimization algorithm for split feasibility problems

The classical multi-set split feasibility problem seeks a point in the intersection of finitely many closed convex domain constraints, whose image under a linear mapping also lies in the intersection of finitely many closed convex range constraints. Split feasibility generalizes important inverse problems including convex feasibility, linear complementarity, and regression with constraint sets. When a feasible point does not exist, solution methods that proceed by minimizing a proximity function can be used to obtain optimal approximate solutions to the problem. We present an extension of the proximity function approach that generalizes the linear split feasibility problem to allow for non-linear mappings. Our algorithm is based on the principle of majorization–minimization, is amenable to quasi-Newton acceleration, and comes complete with convergence guarantees under mild assumptions. Furthermore, we show that the Euclidean norm appearing in the proximity function of the non-linear split feasibility problem can be replaced by arbitrary Bregman divergences. We explore several examples illustrating the merits of non-linear formulations over the linear case, with a focus on optimization for intensity-modulated radiation therapy.     

A Bregman projection method for approximating fixed points of quasi-Bregman nonexpansive mappings

We introduce an abstract algorithm that aims to find the Bregman projection onto a closed convex set. As an application, the asymptotic behavior of an iterative method for finding a fixed point of a quasi-Bregman nonexpansive mapping with the fixed-point closedness property is analyzed. We also show that our result is applicable to Bregman subgradient projectors.     

Simplicial Branch-and-Reduce Algorithm for Convex Programs with a Multiplicative Constraint

Optimization problems that involve products of convex functions in the objective function or in the constraints arise in a variety of applications. These problems are difficult global optimization problems. During the past 15 years, however, a number of practical algorithms have been proposed for globally solving these types of problems. In this article, we present and validate a branch-and-reduce algorithm for finding a global optimal solution to a convex program that contains an additional constraint on the product of several convex functions. To globally solve this problem, the algorithm instead globally solves an equivalent master problem. At any stage of the algorithm, a disconnected set consisting of a union of simplices is constructed. This set is guaranteed to contain a portion of the boundary of the feasible region of the master problem where a global optimal solution lies. The algorithm uses a new branch-and-reduce scheme to iteratively reduce the sizes of these sets until a global optimal solution is found. Several potential computational advantages of the algorithm are explained, and a numerical example is solved.     

Pebble Sets in Convex Polygons

Lukács and András posed the problem of showing the existence of a set of n−2 points in the interior of a convex n-gon so that the interior of every triangle determined by three vertices of the polygon contains a unique point of S. Such sets have been called pebble sets by De Loera, Peterson, and Su. We seek to characterize all such sets for any given convex polygon in the plane. We first consider a certain class of pebble sets, called peripheral because they consist of points that lie close to the boundary of the polygon. We characterize all peripheral pebble sets, and show that for regular polygons, these are the only ones. Though we demonstrate examples of polygons where there are other pebble sets, we nevertheless provide a characterization of the kinds of points that can be involved in non-peripheral pebble sets. We furthermore describe algorithms to find such points.