GoConqr has a new look! Let us know what you think.

Sign up free

Flashcards

Micro Math Camp Definitions

Eric Andersen English 84 cards

Cards in this deck (84)

  1. 1Metric SpaceA pair \(\left(S, d \right)\) where \( S \) is a collection of points and \( d \) is a distance function on \( S \) that satisfies the properties of a metric.
  2. 2Cauchy-Schwarz InequalityFor any vectors \( x, \, y \) of an inner product space,
    \[ \left| \langle x, \, y \rangle \right|^2 \le \langle x, \, x \rangle \cdot \langle y, \, y \rangle. \]
    Equivalently, \[ \left| \langle x, \, y \rangle \right| \le \| x \| \cdot \| y \|. \]
  3. 3Discrete MetricThe discrete metric is: \[d \left(x, \, y \right) = \begin{cases} 1 \; \text{if } x \ne y, \\ 0 \; \text{if } x = y \end{cases} \]
  4. 4an \(\epsilon\)-ball of \(x\) in \(S\)\[ B_\epsilon \left( x \right) \equiv \left\{ y \in S \,|\, d \left( x,\,y \right) < \epsilon \right\} \]
  5. 5Open SetA set \(U \subseteq S\) is open if \( \forall x \in U, \; \exists \epsilon > 0 \) such that \( B_\epsilon \left( x \right) \subseteq U\)
  6. 6Metric TopologyA metric topology of a metric space \( \left(S, \, d \right) \) is the set of all open sets in \(S \). That is: \[ \mathcal{T} \equiv \left\{ U \subseteq S \, | \, U \text{ is open} \right\} \]
  7. 7Power Set of \( X \)The power set \( 2^X \) is the set of all subsets of \(X\).
  8. 8Topological SpaceA set \( X \) together with a set \(T \subseteq 2^X\) that satisfies the three properties of a metric topology on S
  9. 9Closed SetA set \(U \subseteq S\) is closed if \( S \setminus U \) is open. Alternatively, a set \( C \subseteq S \) is closed if \( \forall \left\{ x_n \right\}_{n=1}^{\infty} \subseteq C \) for which \( \exists x \in S \) such that \( x_n \rightarrow x, \, x \in C\).
  10. 10SequenceA countably indexed collection of elements \( \left\{ x_n \right\}_{n=1}^{\infty} \subseteq S \)
  11. 11Convergent SequenceA sequence converges to a limit point \( x \in S \) if \( \forall \epsilon \in \mathbb{R}_+, \; \exists N_\epsilon \) such that \( d \left(x_m, \, x \right) < \epsilon \) for all \( m > N_\epsilon \)
  12. 12Convergent SubsequenceA sequence contains a convergent subsequence if there exists an index set \( N \subset \mathbb{N} \) such that \( \left\{ x_n \right\}_{n \in \hat{N}} \rightarrow x \) for some \(x \in S\)
  13. 13Closure of a SetThis is the smallest closed set containing \( C \). \[ cl \left( C \right) = \bigcap \left\{ K \in 2^S \, | \, C \subseteq K; K \text{ closed.} \right\} \]
  14. 14Cauchy SequenceA sequence \( \left\{x_n\right\}_{n=1}^{\infty} \subseteq S \) such that \( \forall \epsilon \in \mathbb{R}_+, \; \exists N_\epsilon \in \mathbb{N} \) such that \( d \left(x_m,\,x_l\right) < \epsilon \) for all \(m, l > N_\epsilon\)
  15. 15Bounded SetA set \(U \subseteq S \) is bounded if \( \exists M \in \mathbb{R}_+ \) such that \( \forall x,y \in U, \; d \left(x,\,y\right) \le M \)
  16. 16Complete SetA set \( U \subseteq S \) is complete if for every Cauchy sequence \( \left\{x_n\right\}_{n=1}^{\infty} \subseteq U, \; \exists x \in U \) such that \( x_n \rightarrow x \).
  17. 17Open Cover of a set \( K \)A collection of sets \( \left\{ U_\alpha \right\}_{\alpha \in A} \) such that \( U_\alpha \in \mathcal{T} \) for all \( \alpha \in A \) and \( K \subseteq \bigcup_{\alpha \in A} U_\alpha \).
  18. 18Finite SubcoverAn open cover of \( K \) admits a finite subcover if there exists a finite set \( A' \subseteq A \) such that \( K \subseteq \bigcup_{\alpha \in A'} U_\alpha \).
  19. 19Compact SetA subset \( K \) of a metric space \( \left( S, \, d \right) \) is compact if every open cover of \( K \) has a finite subcover.
  20. 20Finite Intersection PropertyA collection \( \mathcal{A} \subseteq 2^S \) has the finite intersection property if \( \bigcap \mathcal{A}' \ne \emptyset \) for any finite, nonempty collection \( \mathcal{A}' \subseteq \mathcal{A} \)
  21. 21Totally Bounded Metric SpaceA metric space \( S \) is totally bounded if for any \( \epsilon > 0 \), there exists a finite collection of points \( x_1, \, \ldots, \, x_N \) such that the open balls \( B_\epsilon \left( x_1 \right), \ldots, \, B_\epsilon \left(x_N\right) \) cover \( S \).
  22. 22Connected Metric SpaceA metric space \( S \) is connected if there do not exist disjoint, nonempty open sets \( U \) and \( U' \) such that \( U \cup U' = S \)
  23. 23Countably Infinite SetAn infinite set \( S \) is countably infinite if there exists a bijection \( f : S \rightarrow \mathbb{N} \).
  24. 24Countable setA set is called countable if it is finite or countably infinite.
  25. 25Dense SetA set \( D \) is dense in a metric space \( \left( S, \, d \right) \text{ if } cl \left( D \right) = S \).
  26. 26SeparableA metric space \( \left( S, \, d \right) \) is separable if there exists a countable set \( D \) that is dense in \( S \).
  27. 27ContinuityA function \( f : X \rightarrow Y \) is continuous at \( x \in X \text{ if } \forall \left\{x_n\right\}_{n=1}^{\infty} \subseteq X \) such that \( x_n \rightarrow x \in X \), we have \( f \left( x_n \right) \rightarrow f \left( x \right) \). Alternatively, if \( \forall \epsilon > 0, \, \exists \delta > 0 \) such that for all \( z \in X \) such that \( d_X \left( x, \, z \right) < \delta, \, d_Y \left( f \left( x \right), \, f \left( z \right) \right) < \epsilon \).
  28. 28Pointwise ConvergenceThe sequence of functions \( \left\{f_n\right\}_{n=1}^{\infty} \) converges pointwise to the function \( f \text{ if } \forall x \in X \), the sequence \( f_n \left( x \right) \) converges to \( f \left( x \right) \).
  29. 29Uniform ConvergenceThe sequence of functions \( \left\{f_n\right\}_{n=1}^{\infty} \) converges pointwise to the function \( f \text{ if } \forall \epsilon > 0 \) there exists \( N_\epsilon \) such that \( \forall x \in S \text{ and all } n \ge N_\epsilon, \, d \left( f_n \left(x \right), \, f \left( x \right) \right) < \epsilon \).
  30. 30Convex SetGiven a vector space \( \left( S, \, +, \, \cdot \right) \), a set \( U \subseteq S \) is convex if \( \forall x, \, y \in U \text{ and } \forall \alpha \in \left[0, \, 1 \right], \) \[ \alpha x + \left(1-\alpha\right)y \in U \]
  31. 31Convex Hull of a Set\( co \left( U \right) \) is the intersection of all convex sets containing \( U \).
  32. 32SupremumLeast Upper Bound
  33. 33InfinumGreatest Lower Bound
  34. 34\(i\)-th partial derivative\[ \lim_{h \rightarrow 0} \frac{ f \left( \tilde{x}_1, \ldots, \, \tilde{x}_i + h, \, \tilde{x}_{i+1}, \ldots, \, \tilde{x}_n \right) - f \left( \tilde{x}_1, \ldots, \, \tilde{x}_i, \, \tilde{x}_{i+1}, \ldots, \, \tilde{x}_n \right) }{h} \]
  35. 35Gradient\[ \nabla f \left( x \right) = \left[ \frac{ \partial f }{ \partial x_i} \right] \] is the \( N \times 1 \) vector of first partial derivatives of \( f \text{ at } x \).
  36. 36Hessian Matrix of \( f \text{ at } x \)matrix of well-defined partial and cross-partial derivatives
  37. 37Jacobian Matrix of \( f \text{ at } x \)matrix of partial derivatives
  38. 38Differentiable FunctionIf there is an \( M \times N \) matrix \( Df\left(x\right) \) such that for any sequence of vectors \( w \rightarrow 0 \) \[ \lim_{w \rightarrow 0} \frac{ \| f \left( x + w \right) - f \left( x \right) - Df\left(x\right)w \|}{\|w\|} = 0 \]
  39. 39Taylor's Approximation\[ f\left(x\right) \approx f \left(x_0 \right) + \sum_{k=1}^{n} \frac{f^k \left(x_0 \right)}{k!} \left(x - x_0 \right)^k \]
  40. 40Concave FunctionA function \( f : A \rightarrow \mathbb{R} \) defined on a convex set \( A \subset \mathbb{R}^N \) is concave if and and only if \[ f \left( \alpha x' + \left(1-\alpha\right)x\right) \ge \alpha f\left(x'\right) + \left(1-\alpha\right)f\left(x\right) \] for all \( x, \, x' \in A \) and all \( \alpha \in \left[0,\,1\right] \)
  41. 41Convex FunctionA function \( f : A \rightarrow \mathbb{R} \) defined on a convex set \( A \subset \mathbb{R}^N \) is concave if and and only if \[ f \left( \alpha x' + \left(1-\alpha\right)x\right) \le \alpha f\left(x'\right) + \left(1-\alpha\right)f\left(x\right) \] for all \( x, \, x' \in A \) and all \( \alpha \in \left[0,\,1\right] \)
  42. 42Negative semidefinite matrixAn \( N \times N \) matrix \(A\) is negative semidefinite if \( z'Az \le 0 \) for all \(z\in\mathbb{R}^{N}\). A strict inequality implies negative definiteness.
  43. 43Positive semidefinite matrixAn \( N \times N \) matrix \(A\) is positive semidefinite if \( z'Az \ge 0 \) for all \(z\in\mathbb{R}^{N}\). A strict inequality implies positive definiteness.
  44. 44\(t\)-upper contour setThe set of all points in \(A\) with values greater than \(t\). \[ C_t^+ \left(f\right) = \left\{x\in A \, | \, f\left(x\right) \ge t \right\} \]
  45. 45\(t\)-lower contour setThe set of all points in \(A\) with values less than \(t\). \[ C_t^- \left(f\right) = \left\{x\in A \, | \, f\left(x\right) \le t \right\} \]
  46. 46Quasiconcave FunctionA function \(f: A \rightarrow \mathbb{R}\) is quasiconcave if its upper contour sets \(C_t^+ \left( f \right)\) are convex for any \(t\in\mathbb{R}\).
    That is, \(\forall t\in\mathbb{R}\) and \(\forall\, x,\,x'\in A\): \[ \min \left\{ f\left(x\right),\, f\left(x'\right) \right\} \ge t \implies f\left(\alpha x + \left[1-\alpha\right]x'\right) \ge t. \] Equivalently, \( f \) is quasiconcave if and only if \[ f \left(\alpha x + \left(1-\alpha\right)x^\prime\right) \ge \min \left\{ f\left(x\right),\, f\left(x'\right) \right\} \] for all \(x, \, x^\prime \in A \) and \( \alpha \in \left[0, \, 1 \right] \).
    Any concave function is quasiconcave. Any increasing function \( f: \mathbb{R} \rightarrow \mathbb{R} \) is quasiconcave.
  47. 47Quasiconvex FunctionA function \(f: A \rightarrow \mathbb{R}\) is quasiconvex if its lower contour sets \(C_t^- \left( f \right)\) are convex for any \(t\in\mathbb{R}\).
    That is, \(\forall t\in\mathbb{R}\) and \(\forall\, x,\,x'\in A\): \[ \max \left\{ f\left(x\right),\, f\left(x'\right) \right\} \le t \implies f\left(\alpha x + \left[1-\alpha\right]x'\right) \le t. \]
    Equivalently, \( f \) is quasiconex if and only if \[ f \left(\alpha x + \left(1-\alpha\right)x^\prime\right) \le \max \left\{ f\left(x\right),\, f\left(x'\right) \right\} \] for all \(x, \, x^\prime \in A \) and \( \alpha \in \left[0, \, 1 \right] \).
  48. 48Local Maximizer/Minimizer of \(f\)A local maximizer is a vector \(x^\ast \in A\) where for a \(\delta > 0 \) \[ f\left(x^\ast\right) \ge f\left(x\right) \text{ for all } x \in B_\delta \left(x^\ast\right) \]. A local minimizer is defined by reversing the inequality.
  49. 49Global Maximizer/Minimizer of \(f\)A global maximizer is a vector \(x^\ast \in A\) where for a \(\delta > 0 \) \[ f\left(x^\ast\right) \ge f\left(x\right) \text{ for all } x \in A \]. A local minimizer is defined by reversing the inequality.
  50. 50Critical Points of \(f\)All \( x \in A\) such that \[ \nabla f \left( x \right) = 0 \]
  51. 51Complementary Slacknessrequires \(\lambda_k^\ast\) = 0 if the constraint \[ h_i \left(x\right) \le c_i \] does not bind
  52. 52Constraint QualificationAn optimization problem satisfies constraint qualification if and only if the \( M \times N \) matrix \[ G \left( x^\ast \right) = \left[ \begin{matrix}
    \frac{\partial g_1 \left( x^\ast \right)}{\partial x_1} & \ldots & \frac{\partial g_1 \left( x^\ast \right)}{\partial x_N} \\
    \vdots & \ddots & \vdots \\
    \frac{\partial g_M \left( x^\ast \right)}{\partial x_1} & \ldots & \frac{\partial g_M \left( x^\ast \right)}{\partial x_N} \\
    \end{matrix} \right] \] satisfies \( \operatorname{rank} \left(G\right) = M \) at an optimum \( x^\ast \in A \).
  53. 53CorrespondenceLet \( X \) and \( Y\) be metric spaces. The correspondence \( \Gamma : X \rightrightarrows Y \) is a function from \( X \) to \( 2^Y \setminus \emptyset \).
  54. 54Upper Hemicontinuous CorrespondenceA correspondence \( \Gamma \) is upper hemicontinuous at \(x \in X\) if for every open set \( O \subseteq Y \) with \( \Gamma \left( x \right) \subseteq O \), there exists \( \delta > 0 \) such that \( \Gamma \left( B_\delta \left( x \right) \right) \subseteq O \). \( \Gamma \) is upper hemicontinuous if this holds for every \( x \in X \).
  55. 55Compact-Valued Correspondence \( \Gamma \)A correspondence \( \Gamma : X \rightrightarrows Y \) is compact valued if \( \Gamma \left( x \right) \) is compact in \(Y\) for each \(x\).
  56. 56Closed-Valued Correspondence \( \Gamma \)A correspondence \( \Gamma : X \rightrightarrows Y \) is closed valued if \( \Gamma \left( x \right) \) is closed in \(Y\) for each \(x\).
  57. 57Convex-Valued Correspondence \( \Gamma \)A correspondence \( \Gamma : X \rightrightarrows Y \) is convex valued if \( \Gamma \left( x \right) \) is convex in \(Y\) for each \(x\).
  58. 58Lower Hemicontinuous CorrespondenceA correspondence \( \Gamma : X \rightrightarrows Y \) is lower hemicontinuous at \(x \in X\) if for every open set \(O \subseteq Y \) with \( \Gamma \left( x \right) \cap O \ne \emptyset \), there exists a \( \delta > 0 \) such that \( \Gamma \left( x' \right) \cap O \ne \emptyset \) for all \( x' \in B_\delta \left(x\right)\). \( \Gamma\) is lower hemicontinuous if this holds at each \(x \in X \).
  59. 59Upper Inverse Image\[ \Gamma^{-1} \left( O \right) \equiv \left\{ x \in X \, | \, \Gamma \left(x\right) \subseteq O \right\} \]
  60. 60Lower Inverse Image\[ \Gamma_{-1} \left( O \right) \equiv \left\{ x \in X \, | \, \Gamma \left(x\right) \cap O \ne \emptyset \right\} \]
  61. 61Continuous CorrespondenceA correspondence \(\Gamma\) is called continuous if it is both upper and lower hemicontinuous.
  62. 62Closed Graph PropertyA correspondence is closed at \(x \in X\) if for all sequences \(x_n \rightarrow x \text{ and } y_n \rightarrow y \), we have \( y \in \Gamma \left( x \right) \) whenever \( y_n \in \Gamma \left( x_n \right) \) for all \( n \). If \(\Gamma\) is closed at every \(x\), then it has the closed graph property.
  63. 63Hyperplane in \( \mathbb{R}^{N} \)A \(N-1\) dimensional subset of \(\mathbb{R}^{N}\) that can be described by a single linear equation: \[ H \left(p,\,r\right) = \left\{ x \in \mathbb{R}^N \, | \, p \cdot x = r \right\} \] where \(p\) is a non-zero vector in \(\mathbb{R}^N\) and \(r\) is a real number.
  64. 64Separating HyperplaneLet \(A, B \subset \mathbb{R}^N, \, p \in \mathbb{R}^N \setminus \left\{ 0 \right\} \). The hyperplane \( H \left( p, \, r \right) \) separates \(A\) and \(B\) if \( p \cdot r \ge r \forall x \in A \) and \( p \cdot y \le r \forall y \in B \)
  65. 65Proper Separation of SetsThe separation of sets \(A, \, B \subset \mathbb{R}^N \text{ by } H \left(p, \, r \right) \) is proper if there exists \(x \in A \text{ and } y \in B \text{ such that } p \cdot x \ne p \cdot y \)
  66. 66Strict Separation of SetsThe hyperplane \(H \left(p, \, r \right)\) strictly separates sets \(A, \, B \subset \mathbb{R}^N\) if \[ p \cdot x > r \text{ for all} x \in A \text{ and } p \cdot y < r \text{ for all } y \in B \]
  67. 67Partially-Ordered Set (poset)A pair \( \left(X, \succsim \right) \) where \(X\) is a set and \(\succsim\) is a partial order.
  68. 68Partial OrderA binary relation \( \succsim \subseteq X \times X \) that satisfies: (a) reflexivity: \( \forall x \in X, \, x \succsim x \), (b) antisymmetry: \(\forall x, y \in X\) if \(x \succsim y\) and \(y \succsim x\) then \(x = y\), and (c) transitivity: \(\forall x, y, z \in X\) if \(x \succsim y\) and \(y \succsim z\) then \(x \succsim z\).
  69. 69ChainA poset is called a chain if the partial order \( \succsim \) is complete on \( X \). That is, for all \(x, y \in X \) either \( x \succsim y \) or \( y \succsim x \).
  70. 70Bounds of a PosetLet \(E \subseteq X \) be a subset of a poset. If we have \(x^\prime \succsim x\) for all \(x \in E\), then \( x^\prime \) is an upper bound for E; similarly if \(x \succsim x^\prime \) for all \(x \in E\) then \( x^\prime \) is a lower bound for \(E\).
  71. 71Supremum of \(E\) in \(X\)Denoted \(\sup_X \left(E \right) \), the supremum of \(E\) in \(X\) is an element \( x^\ast \in X \) such that \(x^\ast \) is an upper bound of \( E \) and if \( x^\prime \) is an upper bound of \( E \), then \( x^\prime \succsim x^\ast\).
  72. 72Infimum of \(E\) in \(X\)Denoted \(\inf_X \left(E \right) \), the infimum of \(E\) in \(X\) is an element \( x_\ast \in X \) such that \(x_\ast\) is a lower bound of \(E\) and if \(x'\) is a lower bound of \(E\), then \(x_\ast \succsim x'\).
  73. 73Join of \(x \text{ and } y\)For a two element subset \( \left\{x,\,y\right\} \subseteq X\), the supremum of \( \left\{x,\,y\right\}\) in \(X\) is called the join and is denoted \(x \vee y \).
  74. 74Meet of \(x \text{ and } y\)For a two element subset \( \left\{x,\,y\right\} \subseteq X\), the infimum of \( \left\{x,\,y\right\}\) in \(X\) is called the meet and is denoted \( x \wedge y \).
  75. 75LatticeA poset \( \left(X,\,\succsim \right) \) such that \(x \vee y \) and \(x \wedge y\) exist for every pair of elements \(x,y \in X\).
  76. 76SublatticeLet \(\left(X,\,\succsim\right)\) be a lattice. A set \( E \subseteq X \) is called a sublattice of \(X\) if \(\forall x, y \in E\), we have \(\sup_X \left(\left\{x,\,y\right\}\right) \in E \) and \( \inf_X \left( \left\{x,\,y\right\}\right) \in E \). That is, \(E\) contains the meet and join of all combinations of its elements. The collection of all nonempty sublattices for a lattice \( \left(X, \, \succsim \right) \) is denoted \( \mathcal{L} \left( X \right) \).
  77. 77Induced Set Ordering on \( \mathcal{L} \left( X \right) \)Denoted \( \sqsubseteq \) and defined by \( A \sqsubseteq B \) if and only if for all \( x \in A \text{ and } y \in B \), we have \(x \wedge y \in A \) and \(x \vee y \in B\).
  78. 78Complete LatticeA lattice \( \left(X, \, \succsim \right) \) is called complete if \( \sup_X \left( E \right) \) and \( \inf_X \left( E \right) \) both exist for every nonempty subset \( E \subseteq X \).
  79. 79Subcomplete SublatticeA sublattice \(E\) of \(X\) is subcomplete if \( \sup_X \left( F \right) \) and \( \inf_X \left( F \right) \) are both in \(E \) for every nonempty set \( F \subseteq E\).
  80. 80Increasing and Decreasing Monotone FunctionsLet \( \left(X,\,\succsim_X\right)\) and \( \left( Y, \, \succsim_Y \right) \) be posets.
    A function \(f \,: \, X \rightarrow Y \) is increasing if \(x \succsim_X x' \implies f \left(x\right) \succsim_Y f\left(x'\right)\) for all \(x, x' \in X\).
    A function \(f \,: \, X \rightarrow Y \) is decreasing if \(x \succsim_X x' \implies f \left(x'\right) \succsim_Y f \left( x \right) \) for all \( x, x' \in X\). The function is monotone if it is either increasing or decreasing.
  81. 81Increasing DifferencesLet \(X\) and \(T\) be posets and let \(S \subseteq X \times T\). A function \(f \, : \, S \rightarrow \mathbb{R} \) has increasing differences on \(S\) if \(f \left(x, \, t'\right) - f\left(x, \, t \right) \) is increasing in \(x\) on the set \(\left\{ x \in X \, | \, \left( x, \, t' \right) \in S \text{ and } \left(x, \, t \right) \in S \right\} \) for all \(t' \succ t \).
  82. 82Supermodular FunctionLet \(X\) be a lattice. A function \(f \, : \, X \rightarrow \mathbb{R} \) is called supermodular iff \[ f \left( x \right) + f \left( x' \right) \le f \left( x \vee x' \right) + f \left( x \wedge x' \right)\] for all \(x, x' \in X \).
  83. 83Quasisupermodular FunctionLet \(X\) be a lattice and \(Y\) be a poset. A function \(f : \, X \rightarrow Y \) is quasisupermodular if \[
    f \left( x \right) \succsim \left( \succ \right) f \left( x \wedge x' \right) \implies f \left( x \vee x' \right) \succsim \left( \succ \right) f \left( x' \right) \] for all \(x, \, x' \in X\).
  84. 84Single Crossing PropertyLet \(X, \, T, \text{ and } Y\) be posets and \( S \subseteq X \times T \).
    A function \( f : \, S \rightarrow Y \) satisfies the single crossing property on \(S\) if \[ f \left( x', \, t \right) \succsim \left( \succ \right) f \left( x, \, t \right) \] \[ \implies \] \[ f \left( x', \, t' \right) \succsim \left( \succ \right) \, f \left( x, \, t' \right) \] for all \( x' \succ x \) and \( t' \succ t \) with \( \left\{x, \, x'\right\} \times \left\{t, \, t' \right\} \subseteq S \).

Information

Description
Flashcards on Micro Math Camp Definitions, created by Eric Andersen on 18/08/2015.
Created by
Eric Andersen
Views
32
Rating

Feedback

What is it about?

What do you think of the new look?

How do you like it?