An iterative process for the feasibility-seeking problem with sets that are unions of convex sets

Yair Censor 1,∗ , Alexander J. Zaslavski 2 · 2025

Read An iterative process for the feasibility-seeking problem with sets that are unions of convex sets by Yair Censor 1,∗ , Alexander J. Zaslavski 2 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-04912.txt.

Introduction

Yair Censor and Alexander Zaslavski propose an iterative process for finding a point that lies in all of a family of sets, where each set is a union of convex pieces. Their paper from twenty twenty-five treats the feasibility-seeking problem for such unions. The problem has drawn fresh interest of late. It now serves as a modeling approach in applied fields, and work on handling non-convexity in feasibility problems keeps growing.

Unions of convex sets break the clean tools built for convex ones. A point must land in one piece of each union, and the pieces can pull the search in rival directions. The authors build a step-by-step process aimed at this case. The paper is brief and formal, stating the process for the union setting. It adds a tool for a problem class that applied modelers increasingly meet.

Catalog record

CREATORYair Censor 1,∗ , Alexander J. Zaslavski 2
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE17 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-04912

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An iterative process for the feasibility-seeking problem with sets that are unions of convex sets Yair Censor 1,∗ , Alexander J. Zaslavski 2 Abstract 1 Department of Mathematics, University of Haifa, Mt. Carmel, Haifa 3498838, Israel 2 Department of Mathematics, The Technion-Israel Institute of Technology, Haifa 3200003, Israel This work is dedicated to the memory of Professor Jon Borwein Abstract. In this paper we deal with the feasibility-seeking problem for unions of convex sets (UCS) sets and propose an iterative process for its solution. Renewed interest in this problem stems from the fact that it was recently discovered to serve as a modeling approach in fields of applications and from the ongoing recent research efforts to handle non-convexity in feasibility-seeking. Keywords. Feasibility-seeking; non-convex sets; unions of convex sets; floorplanning; projections onto sets expandable in convex sets. 2020 Mathematics Subject Classification. 90C30, 65K10. † † footnotetext: ∗ Corresponding author. E-mail address: [email protected] (Y. Censor), [email protected] (A.J. Zaslavski). Received May, 17, 2024; Accepted April, 1, 2025. ©2022 Communications in Optimization Theory 1. Introduction The feasibility problem is to find a point in the nonempty intersection of a finite family of sets. It is a modeling framework for many real-world problems and problems in physics and mathematics. The literature about it in the convex case, when all sets are convex, is huge and diverse, see, e.g., [ 1 ] , [ 4 ] and [ 5 ] . The non-convex situation is more difficult to address but has witnessed many works in recent years, see, e.g., [ 12 ] , [ 13 ] , [ 10 ] , [ 3 ] and [ 8 ] , to name but a few. A particular kind of non-convexity that occurs when the sets for the feasibility problem are unions of convex sets was studied by Chrétien and Bondon [ 6 ] , [ 7 ] . This was recently discovered to serve as a modeling approach in the application field of floorplanning with I/O (input/output) assignment [ 15 ] , bringing up again the topic of investigating iterative processes for it. Recent work [ 2 ] discusses the Douglas–Rachford algorithm to solve the feasibility problem for two closed sets that are finite unions of convex sets. Related, although indirectly, to this subject are the recent papers on algorithms that are based on unions of nonexpansive maps, [ 14 ] , [ 9 ] and [ 16 ] . In this paper we deal with the feasibility-seeking problem for unions of convex sets (UCS) sets and propose an iterative process that is different from earlier proposed ones. Further work is needed to assess the practicality of this algorithm as well as that of the earlier proposed ones mentioned above. We use the term “Feasibility-Seeking Problem” and not just “Feasibility Problem” because the latter sometimes refers to the problem of deciding whether or not an intersection of sets is or is not feasible, i.e., nonempty, see, e.g., [ 11 ] . The term we use here more accurately describes that one is interested in finding a point rather than deciding feasibility or manipulating the problem to reach feasibility. 2. Notions and notations Let (\mathcal{H},\langle\cdot,\cdot\rangle) be a real Hilbert space equipped with an inner product \langle\cdot,\cdot\rangle which induces the Euclidean norm \|x\|=\langle x,x\rangle^{1/2} , x\in\mathcal{H} . For each x\in\mathcal{H} and each r>0 the closed ball with radius r centered at x is B(x,r):=\{y\in\mathcal{H}\mid\;\|x-y\|\leq r\}. For each x\in\mathcal{H} and each nonempty set \Omega\subset\mathcal{H} the distance between x and the set \Omega is dist(x,\Omega):=\inf\{\|x-y\|\mid\;x\in\Omega\}. Let \Omega\subset\mathcal{H} be a nonempty, convex and closed set. Then for each x\in\mathcal{H} there exists a unique point P_{\Omega}(x)\in\Omega , called the orthogonal projection of x onto \Omega , such that \|x-P_{\Omega}(x)\|=dist(x,\Omega). (2.1) 3. The feasibility-seeking problem for sets that are unions of convex sets Sets that are unions of convex sets are defined as follows. Definition 3.1 . (union of convex sets set). Let m_{\Omega} be a natural number and let \Omega_{s}\subset\mathcal{H},\;s=1,2,\dots,m_{\Omega}, (3.1) be nonempty closed convex sets that are pairwise disjoint, i.e., \Omega_{s}\cap\Omega_{t}=\emptyset,\text{ \ for all }s,t\in\{1,2,\dots,m_{\Omega}\},\text{ }s\not=t. (3.2) The union of these sets \Omega:=\cup_{s=1}^{m_{\Omega}}\Omega_{s} (3.3) will be called a “ union of convex sets (UCS) set ”. Such sets were called, under different conditions, “expandable in convex sets” in [ 6 , Definition 1] and in [ 7 , Definition 1] . In [ 9 , Subsection 6.1] such sets were considered under the name “union convex sets”. We define, the possibly non-unique, orthogonal projections onto a UCS set as follows. Definition 3.2 . Let \Omega be a UCS set, \Omega:=\cup_{s=1}^{m_{\Omega}}\Omega_{s} . For each x\in\mathcal{H} the standard definition of projection onto \Omega is P_{\Omega}(x):=\{y\in\Omega\mid\;\|x-y\|\leq\|z-x\|,\text{ \ for all }z\in\Omega\}. (3.4) Remark 3.3 . Let T\subset\{1,2,\dots,m_{\Omega}\} be the set of indices of the sets \Omega_{t} whose distances to x are smallest, compared to the distances of x to the other sets \Omega_{s} . Then P_{\Omega}(x) is the, obviously nonempty, set P_{\Omega}(x)=\{P_{\Omega_{t}}(x),\;t\in T\mid\|x-P_{\Omega_{t}}(x)\|\leq\|x-P_{\Omega_{s}}(x)\|,\;s=1,2,\dots,m_{\Omega}\}. (3.5) The feasibility-seeking problem for UCS sets is defined next. Problem 3.4 . ( The feasibility-seeking problem for UCS sets). Let m be a natural number and assume that, for each i\in\{1,2,\dots,m\} , the set C_{i} is a UCS set C_{i}:=\cup_{j=1}^{m_{i}}C_{i,j}, (3.6) so that the integer m_{i} is the number of sets whose union constitutes the set C_{i}. The feasibility-seeking problem for UCS sets is to find a point x^{\ast} in the intersection x^{\ast}\in C:=\cap_{i=1}^{m}C_{i}. (3.7) Throughout this work we assume that the feasibility-seeking problem for UCS sets is feasible, i.e., that the intersection is nonempty C\not=\emptyset. 4. The iterative process During the iterative process we will perform projections onto the sets C_{i} , which are themselves unions of sets. Such projections might not be unique. For the definition of our algorithm † † As common, we use the term algorithm for the iterative process studied here although no termination criteria, which are by definition necessary in an algorithm, are present and only the asymptotic behavior is studied. and for its convergence analysis we use a condition that guarantees the uniqueness of the projections onto the UCS sets involved in the problem. To this end we append Problem 3.4 with an additional UCS set which is a copy of C_{1}. This clearly does not change at all the problem. Thus, we define C_{m+1}=C_{1},\text{ \ }m_{m+1}=m_{1,}\text{ \ }C_{m+1,j}=C_{1,j}\text{ \ for all }j\in\{1,2,\dots,m_{1}\}. (4.1) Condition 4.1 . For each i\in\{1,2,\dots,m\} and each j\in\{1,2,\dots,m_{i}\} there exists a unique integer \theta(i,j)\in\{1,2,\dots,m_{i+1}\} (4.2) such that for every x\in C_{i,j} P_{C_{i+1}}(x)=P_{C_{i+1,\theta(i,j)}}(x), (4.3) and dist(x,C_{i+1,\theta(i,j)})<dist(x,C_{i+1,\ell}),\;\ell\in\{1,2,\dots,m_{i+1}\}\setminus\{\theta(i,j)\}. (4.4) Observe that the inequality ( 4.4 ) does not follow from the pairwise disjointedness condition ( 3.2 ) in Definition 3.1 because the latter does not rule out that there could be two (or more) sets in the union of sets to which they belong that will have equal distances to a point x. Condition 4.1 plays a crucial role in our study. Proposition 4.3 , presented in the sequel, shows that it holds if for each i\in\{1,2,\dots,m-1\} and each x\in C_{i} , P_{C_{i+1}}(x) is a singleton. For all natural numbers k define the cyclic “control sequence” \{i(k)\}_{k=1}^{\infty} such that i(k)\in\{1,2,\dots,m\} for all k and i(k):=(k-1)\operatorname{mod}m+1. (4.5) This sequence serves to index the sets that are used by the algorithm which is now described.

Read the complete text