Misplaced Pages

#5994

71-499: The Shapley–Folkman  lemma is a result in convex geometry that describes the Minkowski ;addition of sets in a vector space . It is named after mathematicians Lloyd Shapley and Jon Folkman , but was first published by the economist Ross M. Starr . The lemma may be intuitively understood as saying that, if the number of summed sets exceeds the dimension of the vector space, then their Minkowski sum

142-403: A ≤ b . {\displaystyle a\leq b.} When a = b {\displaystyle a=b} in the first case, the resulting interval is the empty set ( a , a ) = ∅ , {\displaystyle (a,a)=\varnothing ,} which is a degenerate interval (see below). The open intervals are those intervals that are open sets for

213-438: A , b ) {\displaystyle (a,b)} is a 1-dimensional open ball with a center at 1 2 ( a + b ) {\displaystyle {\tfrac {1}{2}}(a+b)} and a radius of 1 2 ( b − a ) . {\displaystyle {\tfrac {1}{2}}(b-a).} The closed finite interval [ a , b ] {\displaystyle [a,b]}

284-480: A , b ] {\displaystyle (a,b]} and [ a , b ) {\displaystyle [a,b)} are neither an open set nor a closed set. If one allows an endpoint in the closed side to be an infinity (such as (0,+∞] ), the result will not be an interval, since it is not even a subset of the real numbers. Instead, the result can be seen as an interval in the extended real line , which occurs in measure theory , for example. In summary,

355-422: A d ( Q n ) 2 . {\displaystyle d^{2}(Q,\mathrm {Conv} (Q))~\leq ~\sum _{\max D}rad(Q_{n})^{2}.} where we use the notation ∑ max D {\displaystyle \sum _{\max D}} to mean "the sum of the D largest terms". Note that this upper bound depends on the dimension of ambient space and the shapes of the summands, but not on

426-779: A d ( S ) {\displaystyle rad(S)} to be the infimum of the radius of all balls containing it (as shown in the diagram). More formally, r a d ( S ) ≡ inf x ∈ R N sup y ∈ S ‖ x − y ‖ {\displaystyle rad(S)\equiv \inf _{x\in R^{N}}\sup _{y\in S}\|x-y\|} Now we can state Shapley–Folkman theorem  —  d 2 ( Q , C o n v ( Q ) )   ≤   ∑ max D r

497-507: A Cartesian coordinate system in which every point is identified by an ordered pair of real numbers, called "coordinates", which are conventionally denoted by  x and  y . Two points in the Cartesian ;plane can be added coordinate-wise: further, a point can be multiplied by each real number  λ coordinate-wise: More generally, any real vector space of (finite) dimension  D can be viewed as

568-452: A and b included. The notation [ a .. b ] is used in some programming languages ; in Pascal , for example, it is used to formally define a subrange type, most frequently used to specify lower and upper bounds of valid indices of an array . Another way to interpret integer intervals are as sets defined by enumeration , using ellipsis notation. An integer interval that has

639-424: A convex combination of an indexed subset  { v 1 , v 2 , …, v D } of a vector space is any weighted average  λ 1 v 1 + λ 2 v 2 + … + λ D v D for some indexed set of non-negative real numbers  { λ d } satisfying the equation  λ 0 + λ 1 + … + λ D = 1 . The definition of

710-493: A half-space is taken as a kind of degenerate ball (without a well-defined center or radius), a half-space can be taken as analogous to a half-bounded interval, with its boundary plane as the (degenerate) sphere corresponding to the finite endpoint. A finite interval is (the interior of) a 1-dimensional hyperrectangle . Generalized to real coordinate space R n , {\displaystyle \mathbb {R} ^{n},} an axis-aligned hyperrectangle (or box)

781-419: A ,  a ) , [ a ,  a ) , and ( a ,  a ] represents the empty set , whereas [ a ,  a ] denotes the singleton set  { a } . When a > b , all four notations are usually taken to represent the empty set. Both notations may overlap with other uses of parentheses and brackets in mathematics. For instance, the notation ( a , b ) is often used to denote an ordered pair in set theory,

SECTION 10

#1732787128006

852-491: A , +∞) are all meaningful and distinct. In particular, (−∞, +∞) denotes the set of all ordinary real numbers, while [−∞, +∞] denotes the extended reals. Even in the context of the ordinary reals, one may use an infinite endpoint to indicate that there is no bound in that direction. For example, (0, +∞) is the set of positive real numbers , also written as R + . {\displaystyle \mathbb {R} _{+}.} The context affects some of

923-456: A ball B {\displaystyle B} of radius r {\displaystyle r} such that x ∈ C o n v ( S ∩ B ) {\displaystyle x\in \mathrm {Conv} (S\cap B)} . For example, let B ′ ⊂ B ⊂ R D {\displaystyle B'\subset B\subset \mathbb {R} ^{D}} be two nested balls, then

994-432: A convex set implies that the intersection of two convex sets is a convex set. More generally, the intersection of a family of convex sets is a convex set. In particular, the intersection of two disjoint sets is the empty set, which is convex. For every subset  Q of a real vector space, its convex hull   Conv( Q ) is the minimal convex set that contains  Q . Thus  Conv( Q )

1065-454: A finite lower or upper endpoint always includes that endpoint. Therefore, the exclusion of endpoints can be explicitly denoted by writing a .. b  − 1  , a  + 1 .. b  , or a  + 1 .. b  − 1 . Alternate-bracket notations like [ a .. b ) or [ a .. b [ are rarely used for integer intervals. The intervals are precisely the connected subsets of R . {\displaystyle \mathbb {R} .} It follows that

1136-452: A guaranteed enclosure of the result of a numerical computation, even in the presence of uncertainties of input data and rounding errors . Intervals are likewise defined on an arbitrary totally ordered set, such as integers or rational numbers . The notation of integer intervals is considered in the special section below . An interval is a subset of the real numbers that contains all real numbers lying between any two numbers of

1207-425: A line segment joining its points  ⊘ {\displaystyle \oslash } ; the non-convex set of three integers  {0,1,2} is contained in the interval  [0,2] , which is convex. For example, a solid cube is convex; however, anything that is hollow or dented, for example, a crescent shape, is non-convex. The empty set is convex, either by definition or vacuously , depending on

1278-410: A maximum or is right unbounded; it is simply closed if it is both left-closed and right closed. So, the closed intervals coincide with the closed sets in that topology. The interior of an interval I is the largest open interval that is contained in I ; it is also the set of points in I which are not endpoints of I . The closure of I is the smallest closed interval that contains I ; which

1349-525: A real vector space, X , the convex hull of their Minkowski sum is the Minkowski sum of their convex hulls. That is, And by induction it follows that for any N ∈ ℕ and non-empty subsets Q n ⊆ X , 1 ≤ n ≤ N . D and N represent positive integers. D is the dimension of the ambient space ℝ . Q 1 , …, Q N are nonempty, bounded subsets of ℝ . They are also called "summands". N

1420-409: A real vector space, a non-empty set  Q is defined to be convex if, for each pair of its points, every point on the line segment that joins them is still in  Q . For example, a solid disk   ∙ {\displaystyle \bullet } is convex but a circle   ∘ {\displaystyle \circ } is not, because it does not contain

1491-441: A set of the real numbers is an interval, if and only if it is an open interval, a closed interval, or a half-open interval. A degenerate interval is any set consisting of a single real number (i.e., an interval of the form [ a , a ] ). Some authors include the empty set in this definition. A real interval that is neither empty nor degenerate is said to be proper , and has infinitely many elements. An interval

SECTION 20

#1732787128006

1562-415: A subset X ⊆ R {\displaystyle X\subseteq \mathbb {R} } is also the convex hull of X . {\displaystyle X.} The closure of an interval is the union of the interval and the set of its finite endpoints, and hence is also an interval. (The latter also follows from the fact that the closure of every connected subset of a topological space

1633-461: A well-defined manner to recursive forms ∑ n = 1 N Q n = Q 1 + Q 2 + … + Q N . {\displaystyle \sum _{n=1}^{N}Q_{n}=Q_{1}+Q_{2}+\ldots +Q_{N}.} By the principle of induction it is easy to see that Minkowski addition behaves well with respect to taking convex hulls. Specifically, for all subsets A , B ⊆ X of

1704-448: Is a bounded real interval whose endpoints are j 2 n {\displaystyle {\tfrac {j}{2^{n}}}} and j + 1 2 n , {\displaystyle {\tfrac {j+1}{2^{n}}},} where j {\displaystyle j} and n {\displaystyle n} are integers. Depending on the context, either endpoint may or may not be included in

1775-516: Is a connected subset.) In other words, we have The intersection of any collection of intervals is always an interval. The union of two intervals is an interval if and only if they have a non-empty intersection or an open end-point of one interval is a closed end-point of the other, for example ( a , b ) ∪ [ b , c ] = ( a , c ] . {\displaystyle (a,b)\cup [b,c]=(a,c].} If R {\displaystyle \mathbb {R} }

1846-553: Is a measure of how "close" two sets are. In particular, if two sets are compact, then their squared Euclidean distance is zero if and only if they are equal. Thus, we may quantify how close to convexity Q is by upper-bounding d 2 ( C o n v ( Q ) , Q ) . {\displaystyle d^{2}(\mathrm {Conv} (Q),Q).} For any bounded subset S ⊂ R D , {\displaystyle S\subset \mathbb {R} ^{D},} define its circumradius r

1917-441: Is also the set I augmented with its finite endpoints. For any set X of real numbers, the interval enclosure or interval span of X is the unique interval that contains X , and does not properly contain any other interval that also contains X . An interval I is a subinterval of interval J if I is a subset of J . An interval I is a proper subinterval of J if I is a proper subset of J . However, there

1988-522: Is an interval, denoted (−∞, ∞) ; and any single real number a is an interval, denoted [ a , a ] . Intervals are ubiquitous in mathematical analysis . For example, they occur implicitly in the epsilon-delta definition of continuity ; the intermediate value theorem asserts that the image of an interval by a continuous function is an interval; integrals of real functions are defined over an interval; etc. Interval arithmetic consists of computing with intervals instead of real numbers for providing

2059-752: Is approximately convex. Related results provide more refined statements about how close the approximation is. For example, the Shapley–Folkman theorem provides an upper bound on the distance between any point in the Minkowski sum and its convex hull . This upper bound is sharpened by the Shapley–Folkman–Starr theorem (alternatively, Starr's corollary ). The Shapley–Folkman lemma has applications in economics , optimization and probability theory . In economics, it can be used to extend results proved for convex preferences to non-convex preferences. In optimization theory, it can be used to explain

2130-449: Is conflicting terminology for the terms segment and interval , which have been employed in the literature in two essentially opposite ways, resulting in ambiguity when these terms are used. The Encyclopedia of Mathematics defines interval (without a qualifier) to exclude both endpoints (i.e., open interval) and segment to include both endpoints (i.e., closed interval), while Rudin's Principles of Mathematical Analysis calls sets of

2201-438: Is contained in the interval of real numbers   [0,2] , which is convex. The Shapley–Folkman lemma implies that every point in  [0,2] is the sum of an integer from  {0,1} and a real number from  [0,1] . The distance between the convex interval  [0,2] and the non-convex set  {0,1,2} equals one-half: However, the distance between the average Minkowski sum and its convex hull  [0,1]

Shapley–Folkman lemma - Misplaced Pages Continue

2272-434: Is left-closed and right-open. The empty set and the set of all reals are both open and closed intervals, while the set of non-negative reals, is a closed interval that is right-open but not left-open. The open intervals are open sets of the real line in its standard topology , and form a base of the open sets. An interval is said to be left-closed if it has a minimum element or is left-unbounded, right-closed if it has

2343-416: Is not, because the line segment joining two distinct points  ⊘ {\displaystyle \oslash } is not a subset of the circle. The convex hull of a set  Q is the smallest convex set that contains  Q . This distance is zero if and only if the sum is convex. Minkowski addition is the addition of the set members . For example, adding the set consisting of

2414-482: Is only  1/4 , which is half the distance ( 1/2 ) between its summand  {0,1} and  [0,1] . As more sets are added together, the average of their sum "fills out" its convex hull: The maximum distance between the average and its convex hull approaches zero as the average includes more summands . The Shapley–Folkman lemma depends upon the following definitions and results from convex geometry . A real vector space of two  dimensions can be given

2485-414: Is said to be left-bounded or right-bounded , if there is some real number that is, respectively, smaller than or larger than all its elements. An interval is said to be bounded , if it is both left- and right-bounded; and is said to be unbounded otherwise. Intervals that are bounded at only one end are said to be half-bounded . The empty set is bounded, and the set of all reals is the only interval that

2556-750: Is the Cartesian product of n {\displaystyle n} finite intervals. For n = 2 {\displaystyle n=2} this is a rectangle ; for n = 3 {\displaystyle n=3} this is a rectangular cuboid (also called a " box "). Allowing for a mix of open, closed, and infinite endpoints, the Cartesian product of any n {\displaystyle n} intervals, I = I 1 × I 2 × ⋯ × I n {\displaystyle I=I_{1}\times I_{2}\times \cdots \times I_{n}}

2627-404: Is the corresponding closed ball, and the interval's two endpoints { a , b } {\displaystyle \{a,b\}} form a 0-dimensional sphere . Generalized to n {\displaystyle n} -dimensional Euclidean space , a ball is the set of points whose distance from the center is less than the radius. In the 2-dimensional case, a ball is called a disk . If

2698-428: Is the intersection of all the convex sets that cover   Q . The convex hull of a set can be equivalently defined to be the set of all convex combinations of points in  Q . For example, the convex hull of the set of integers   {0,1} is the closed interval of real numbers   [0,1] , which contains the integer end-points. The convex hull of the unit circle is the closed unit disk , which contains

2769-408: Is the interval of all real numbers greater than 0 and less than 1 . (This interval can also be denoted by ]0, 1[ , see below). The open interval (0, +∞) consists of real numbers greater than 0 , i.e., positive real numbers. The open intervals are thus one of the forms where a {\displaystyle a} and b {\displaystyle b} are real numbers such that

2840-1114: Is the number of summands. Q = ∑ n = 1 N Q n {\displaystyle Q=\sum _{n=1}^{N}Q_{n}} is the Minkowski sum of the summands. x represents an arbitrary vector in Conv( Q ) . Since C o n v ( Q ) = ∑ n = 1 N C o n v ( Q n ) {\displaystyle \mathrm {Conv} (Q)=\sum _{n=1}^{N}\mathrm {Conv} (Q_{n})} , for any x ∈ Conv( Q ) , there exist elements q n ∈ Conv( Q n ) such that ∑ n = 1 N q n = x {\displaystyle \sum _{n=1}^{N}q_{n}=x} . The Shapley–Folkman lemma refines this statement. Shapley–Folkman lemma  —  For any x ∈ Conv( Q ) , there exist elements q n such that ∑ n = 1 N q n = x {\displaystyle \sum _{n=1}^{N}q_{n}=x} , and at most D of

2911-407: Is unbounded at both ends. Bounded intervals are also commonly known as finite intervals . Bounded intervals are bounded sets , in the sense that their diameter (which is equal to the absolute difference between the endpoints) is finite. The diameter may be called the length , width , measure , range , or size of the interval. The size of unbounded intervals is usually defined as +∞ , and

Shapley–Folkman lemma - Misplaced Pages Continue

2982-484: Is viewed as a metric space , its open balls are the open bounded intervals  ( c  +  r ,  c  −  r ) , and its closed balls are the closed bounded intervals  [ c  +  r ,  c  −  r ] . In particular, the metric and order topologies in the real line coincide, which is the standard topology of the real line. Any element  x of an interval  I defines a partition of  I into three disjoint intervals I 1 ,  I 2 ,  I 3 : respectively,

3053-749: The Ancient Greek λῆμμα, (perfect passive εἴλημμαι) something received or taken. Thus something taken for granted in an argument. There is no formal distinction between a lemma and a theorem , only one of intention (see Theorem terminology ). However, a lemma can be considered a minor result whose sole purpose is to help prove a more substantial theorem – a step in the direction of proof. Some powerful results in mathematics are known as lemmas, first named for their originally minor purpose. These include, among others: While these results originally seemed too simple or too technical to warrant independent interest, they have eventually turned out to be central to

3124-408: The coordinates of a point or vector in analytic geometry and linear algebra , or (sometimes) a complex number in algebra . That is why Bourbaki introduced the notation ] a , b [ to denote the open interval. The notation [ a , b ] too is occasionally used for ordered pairs, especially in computer science . Some authors such as Yves Tillé use ] a , b [ to denote the complement of

3195-501: The endpoints of the interval. In countries where numbers are written with a decimal comma , a semicolon may be used as a separator to avoid ambiguity. To indicate that one of the endpoints is to be excluded from the set, the corresponding square bracket can be either replaced with a parenthesis, or reversed. Both notations are described in International standard ISO 31-11 . Thus, in set builder notation , Each interval (

3266-2107: The infimum d 2 ( x , S ) = inf y ∈ S ‖ x − y ‖ 2 . {\displaystyle d^{2}(x,S)=\inf _{y\in S}\|x-y\|^{2}.} More generally, for any two nonempty subsets S , S ′ ⊆ R D , {\displaystyle S,S'\subseteq \mathbb {R} ^{D},} define d 2 ( S , S ′ ) = inf x ∈ S , y ∈ S ′ ‖ x − y ‖ 2 . {\displaystyle d^{2}(S,S')=\inf _{x\in S,y\in S'}\|x-y\|^{2}.} Note that d 2 ( x , S ) = ( inf y ∈ S ‖ x − y ‖ ) 2 , {\displaystyle d^{2}(x,S)=(\inf _{y\in S}\|x-y\|)^{2},} so we can simply write d 2 ( x , S ) = d ( x , S ) 2 , {\displaystyle d^{2}(x,S)=d(x,S)^{2},} where d ( x , S ) = inf y ∈ S ‖ x − y ‖ . {\displaystyle d(x,S)=\inf _{y\in S}\|x-y\|.} Similarly, d 2 ( S , S ′ ) = d ( S , S ′ ) 2 . {\displaystyle d^{2}(S,S')=d(S,S')^{2}.} For example, d 2 ( [ 0 , 2 ] , { 0 , 1 , 2 } ) = 1 / 4 = d ( [ 0 , 2 ] , { 0 , 1 , 2 } ) 2 . {\displaystyle d^{2}([0,2],\{0,1,2\})=1/4=d([0,2],\{0,1,2\})^{2}.} The squared Euclidean distance

3337-401: The integers zero and one to itself yields the set consisting of zero, one, and two: { 0 , 1 } + { 0 , 1 } = { 0 + 0 , 0 + 1 , 1 + 0 , 1 + 1 } = { 0 , 1 , 2 } . {\displaystyle \{0,1\}+\{0,1\}=\{0+0,0+1,1+0,1+1\}=\{0,1,2\}.} The subset of the integers  {0,1,2}

3408-417: The set of all D -tuples of  D real numbers {( v 1 , v 2 , …, v D )} on which two  operations are defined: vector addition and multiplication by a real number . For finite-dimensional vector spaces, the operations of vector addition and real-number multiplication can each be defined coordinate-wise, following the example of the Cartesian plane. In

3479-428: The above definitions and terminology. For instance, the interval (−∞, +∞)  =  R {\displaystyle \mathbb {R} } is closed in the realm of ordinary reals, but not in the realm of the extended reals. When a and b are integers , the notation ⟦ a, b ⟧, or [ a .. b ] or { a .. b } or just a .. b , is sometimes used to indicate the interval of all integers between

3550-414: The author. More formally, a set  Q is convex if, for all points  v 1 and  v 2 in  Q and for every real number  λ in the unit interval   [0,1] , the point is a member of  Q . By mathematical induction , a set  Q is convex if and only if every convex combination of members of  Q also belongs to  Q . By definition,

3621-533: The circumradius of B ∖ B ′ {\displaystyle B\setminus B'} is the radius of B {\displaystyle B} , but its inner radius is the radius of B ′ {\displaystyle B'} . Since r ( S ) ≤ r a d ( S ) {\displaystyle r(S)\leq rad(S)} for any bounded subset S ⊂ R D {\displaystyle S\subset \mathbb {R} ^{D}} ,

SECTION 50

#1732787128006

3692-438: The elements of  I that are less than  x , the singleton  [ x , x ] = { x } , {\displaystyle [x,x]=\{x\},} and the elements that are greater than  x . The parts I 1 and I 3 are both non-empty (and have non-empty interiors), if and only if x is in the interior of  I . This is an interval version of the trichotomy principle . A dyadic interval

3763-399: The following theorem is a refinement: Shapley–Folkman–Starr theorem  —  d 2 ( Q , C o n v ( Q ) ) ≤ ∑ max D r ( Q n ) 2 {\displaystyle d^{2}(Q,\mathrm {Conv} (Q))\leq \sum _{\max D}r(Q_{n})^{2}} . Lemma (mathematics) From

3834-420: The following theorem, which quantifies the difference between Q and Conv( Q ) using squared Euclidean distance . For any nonempty subset S ⊆ R D {\displaystyle S\subseteq \mathbb {R} ^{D}} and any point x ∈ R D , {\displaystyle x\in \mathbb {R} ^{D},} define their squared Euclidean distance to be

3905-415: The form Every closed interval is a closed set of the real line , but an interval that is a closed set need not be a closed interval. For example, intervals ( − ∞ , b ] {\displaystyle (-\infty ,b]} and [ a , + ∞ ) {\displaystyle [a,+\infty )} are also closed sets in the real line. Intervals (

3976-412: The form [ a , b ] intervals and sets of the form ( a , b ) segments throughout. These terms tend to appear in older works; modern texts increasingly favor the term interval (qualified by open , closed , or half-open ), regardless of whether endpoints are included. The interval of numbers between a and b , including a and b , is often denoted [ a ,  b ] . The two numbers are called

4047-407: The image of an interval by any continuous function from R {\displaystyle \mathbb {R} } to R {\displaystyle \mathbb {R} } is also an interval. This is one formulation of the intermediate value theorem . The intervals are also the convex subsets of R . {\displaystyle \mathbb {R} .} The interval enclosure of

4118-419: The interval extends without a bound . A real interval can contain neither endpoint, either endpoint, or both endpoints, excluding any endpoint which is infinite. For example, the set of real numbers consisting of 0 , 1 , and all numbers in between is an interval, denoted [0, 1] and called the unit interval ; the set of all positive real numbers is an interval, denoted (0, ∞) ; the set of all real numbers

4189-405: The interval  ( a ,  b ) ; namely, the set of all real numbers that are either less than or equal to a , or greater than or equal to b . In some contexts, an interval may be defined as a subset of the extended real numbers , the set of all real numbers augmented with −∞ and +∞ . In this interpretation, the notations [−∞,  b ]  , (−∞,  b ]  , [ a , +∞]  , and [

4260-439: The interval. Dyadic intervals have the following properties: The dyadic intervals consequently have a structure that reflects that of an infinite binary tree . Dyadic intervals are relevant to several areas of numerical analysis, including adaptive mesh refinement , multigrid methods and wavelet analysis . Another way to represent such a structure is p-adic analysis (for p = 2 ). An open finite interval (

4331-461: The interval. This is a consequence of the least-upper-bound property of the real numbers. This characterization is used to specify intervals by mean of interval notation , which is described below. An open interval does not include any endpoint, and is indicated with parentheses. For example, ( 0 , 1 ) = { x ∣ 0 < x < 1 } {\displaystyle (0,1)=\{x\mid 0<x<1\}}

SECTION 60

#1732787128006

4402-462: The number of summands. Define the inner radius r ( S ) {\displaystyle r(S)} of a bounded subset S ⊂ R D {\displaystyle S\subset \mathbb {R} ^{D}} to be the infimum of r {\displaystyle r} such that, for any x ∈ C o n v ( S ) {\displaystyle x\in \mathrm {Conv} (S)} , there exists

4473-512: The reindexing depends on the point x . The lemma may be stated succinctly as converse of Shapley–Folkman lemma  —  If a vector space obeys the Shapley–Folkman lemma for a natural number  D , and for no number less than  D , then its dimension is finite, and exactly  D . In particular, the Shapley–Folkman lemma requires the vector space to be finite-dimensional. Shapley and Folkman used their lemma to prove

4544-575: The size of the empty interval may be defined as 0 (or left undefined). The centre ( midpoint ) of a bounded interval with endpoints a and b is ( a  +  b )/2 , and its radius is the half-length | a  −  b |/2 . These concepts are undefined for empty or unbounded intervals. An interval is said to be left-open if and only if it contains no minimum (an element that is smaller than all other elements); right-open if it contains no maximum ; and open if it contains neither. The interval [0, 1) = { x | 0 ≤ x < 1} , for example,

4615-528: The subset. The endpoints of an interval are its supremum , and its infimum , if they exist as real numbers. If the infimum does not exist, one says often that the corresponding endpoint is − ∞ . {\displaystyle -\infty .} Similarly, if the supremum does not exist, one says that the corresponding endpoint is + ∞ . {\displaystyle +\infty .} Intervals are completely determined by their endpoints and whether each endpoint belong to

4686-453: The successful solution of minimization problems that are sums of many functions . In probability, it can be used to prove a law of large numbers for random sets . A set is convex if every line segment joining two of its points is a subset in the set: For example, the solid disk   ∙ {\displaystyle \bullet } is a convex set but the circle   ∘ {\displaystyle \circ }

4757-502: The summands q n ∈ Conv( Q n ) \ Q n , while the others q n ∈ Q n . For example, every point in [0,2] = [0,1] + [0,1] = Conv({0,1}) + Conv({0,1}) is the sum of an element in {0,1} and an element in [0,1] . Shuffling indices if necessary, this means that every point in Conv( Q ) can be decomposed as where q n ∈ Conv( Q n ) for 1 ≤ n ≤ D and q n ∈ Q n for D + 1 ≤ n ≤ N . Note that

4828-534: The theories in which they occur. This article incorporates material from Lemma on PlanetMath , which is licensed under the Creative Commons Attribution/Share-Alike License . Interval (mathematics) In mathematics , a real interval is the set of all real numbers lying between two fixed endpoints with no "gaps". Each endpoint is either a real number or positive or negative infinity , indicating

4899-458: The unit circle. In any vector space (or algebraic structure with addition), X , the Minkowski sum of two non-empty sets A , B ⊆ X is defined to be the element-wise operation A + B = { x + y | x ∈ A , y ∈ B } (See also .) For example, This operation is clearly commutative and associative on the collection of non-empty sets. All such operations extend in

4970-506: The usual topology on the real numbers. A closed interval is an interval that includes all its endpoints and is denoted with square brackets. For example, [0, 1] means greater than or equal to 0 and less than or equal to 1 . Closed intervals have one of the following forms in which a and b are real numbers such that a ≤ b : {\displaystyle a\leq b\colon } The closed intervals are those intervals that are closed sets for

5041-627: The usual topology on the real numbers. The empty set and R {\displaystyle \mathbb {R} } are the only intervals that are both open and closed. A half-open interval has two endpoints and includes only one of them. It is said left-open or right-open depending on whether the excluded endpoint is on the left or on the right. These intervals are denoted by mixing notations for open and closed intervals. For example, (0, 1] means greater than 0 and less than or equal to 1 , while [0, 1) means greater than or equal to 0 and less than 1 . The half-open intervals have

#5994