3224540
Description
Flashcards by Eric Andersen, updated more than 1 year ago
|
Created by Eric Andersen
over 8 years ago
|
|
| Question | Answer |
| Metric Space | A 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. |
| Cauchy-Schwarz Inequality | For 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 \|. \] |
| Discrete Metric | The discrete metric is: \[d \left(x, \, y \right) = \begin{cases} 1 \; \text{if } x \ne y, \\ 0 \; \text{if } x = y \end{cases} \] |
| an \(\epsilon\)-ball of \(x\) in \(S\) | \[ B_\epsilon \left( x \right) \equiv \left\{ y \in S \,|\, d \left( x,\,y \right) < \epsilon \right\} \] |
| Open Set | A set \(U \subseteq S\) is open if \( \forall x \in U, \; \exists \epsilon > 0 \) such that \( B_\epsilon \left( x \right) \subseteq U\) |
| Metric Topology | A 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\} \] |
| Power Set of \( X \) | The power set \( 2^X \) is the set of all subsets of \(X\). |
| Topological Space | A set \( X \) together with a set \(T \subseteq 2^X\) that satisfies the three properties of a metric topology on S |
| Closed Set | A 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\). |
| Sequence | A countably indexed collection of elements \( \left\{ x_n \right\}_{n=1}^{\infty} \subseteq S \) |
| Convergent Sequence | A 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 \) |
| Convergent Subsequence | A 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\) |
| Closure of a Set | This is the smallest closed set containing \( C \). \[ cl \left( C \right) = \bigcap \left\{ K \in 2^S \, | \, C \subseteq K; K \text{ closed.} \right\} \] |
| Cauchy Sequence | A 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\) |
| Bounded Set | A 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 \) |
| Complete Set | A 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 \). |
| Open 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 \). |
| Finite Subcover | An 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 \). |
| Compact Set | A subset \( K \) of a metric space \( \left( S, \, d \right) \) is compact if every open cover of \( K \) has a finite subcover. |
| Finite Intersection Property | A 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} \) |
| Totally Bounded Metric Space | A 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 \). |
| Connected Metric Space | A metric space \( S \) is connected if there do not exist disjoint, nonempty open sets \( U \) and \( U' \) such that \( U \cup U' = S \) |
| Countably Infinite Set | An infinite set \( S \) is countably infinite if there exists a bijection \( f : S \rightarrow \mathbb{N} \). |
| Countable set | A set is called countable if it is finite or countably infinite. |
| Dense Set | A set \( D \) is dense in a metric space \( \left( S, \, d \right) \text{ if } cl \left( D \right) = S \). |
| Separable | A metric space \( \left( S, \, d \right) \) is separable if there exists a countable set \( D \) that is dense in \( S \). |
| Continuity | A 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 \). |
| Pointwise Convergence | The 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) \). |
| Uniform Convergence | The 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 \). |
| Convex Set | Given 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 \] |
| Convex Hull of a Set | \( co \left( U \right) \) is the intersection of all convex sets containing \( U \). |
| Supremum | Least Upper Bound |
| Infinum | Greatest Lower Bound |
| \(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} \] |
| Gradient | \[ \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 \). |
| Hessian Matrix of \( f \text{ at } x \) | matrix of well-defined partial and cross-partial derivatives |
| Jacobian Matrix of \( f \text{ at } x \) | matrix of partial derivatives |
| Differentiable Function | If 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 \] |
| Taylor'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 \] |
| Concave Function | A 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] \) |
| Convex Function | A 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] \) |
| Negative semidefinite matrix | An \( 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. |
| Positive semidefinite matrix | An \( 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. |
| \(t\)-upper contour set | The 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\} \] |
| \(t\)-lower contour set | The 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\} \] |
| Quasiconcave Function | A 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. |
| Quasiconvex Function | A 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] \). |
| Local 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. |
| Global 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. |
| Critical Points of \(f\) | All \( x \in A\) such that \[ \nabla f \left( x \right) = 0 \] |
| Complementary Slackness | requires \(\lambda_k^\ast\) = 0 if the constraint \[ h_i \left(x\right) \le c_i \] does not bind |
| Constraint Qualification | An 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 \). |
| Correspondence | Let \( X \) and \( Y\) be metric spaces. The correspondence \( \Gamma : X \rightrightarrows Y \) is a function from \( X \) to \( 2^Y \setminus \emptyset \). |
| Upper Hemicontinuous Correspondence | A 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 \). |
| Compact-Valued Correspondence \( \Gamma \) | A correspondence \( \Gamma : X \rightrightarrows Y \) is compact valued if \( \Gamma \left( x \right) \) is compact in \(Y\) for each \(x\). |
| Closed-Valued Correspondence \( \Gamma \) | A correspondence \( \Gamma : X \rightrightarrows Y \) is closed valued if \( \Gamma \left( x \right) \) is closed in \(Y\) for each \(x\). |
| Convex-Valued Correspondence \( \Gamma \) | A correspondence \( \Gamma : X \rightrightarrows Y \) is convex valued if \( \Gamma \left( x \right) \) is convex in \(Y\) for each \(x\). |
| Lower Hemicontinuous Correspondence | A 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 \). |
| Upper Inverse Image | \[ \Gamma^{-1} \left( O \right) \equiv \left\{ x \in X \, | \, \Gamma \left(x\right) \subseteq O \right\} \] |
| Lower Inverse Image | \[ \Gamma_{-1} \left( O \right) \equiv \left\{ x \in X \, | \, \Gamma \left(x\right) \cap O \ne \emptyset \right\} \] |
| Continuous Correspondence | A correspondence \(\Gamma\) is called continuous if it is both upper and lower hemicontinuous. |
| Closed Graph Property | A 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. |
| Hyperplane 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. |
| Separating Hyperplane | Let \(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 \) |
| Proper Separation of Sets | The 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 \) |
| Strict Separation of Sets | The 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 \] |
| Partially-Ordered Set (poset) | A pair \( \left(X, \succsim \right) \) where \(X\) is a set and \(\succsim\) is a partial order. |
| Partial Order | A 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\). |
| Chain | A 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 \). |
| Bounds of a Poset | Let \(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\). |
| Supremum 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\). |
| Infimum 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'\). |
| Join 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 \). |
| Meet 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 \). |
| Lattice | A poset \( \left(X,\,\succsim \right) \) such that \(x \vee y \) and \(x \wedge y\) exist for every pair of elements \(x,y \in X\). |
| Sublattice | Let \(\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) \). |
| Induced 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\). |
| Complete Lattice | A 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 \). |
| Subcomplete Sublattice | A 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\). |
| Increasing and Decreasing Monotone Functions | Let \( \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. |
| Increasing Differences | Let \(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 \). |
| Supermodular Function | Let \(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 \). |
| Quasisupermodular Function | Let \(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\). |
| Single Crossing Property | Let \(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 \). |
Want to create your own Flashcards for free with GoConqr? Learn more.