Next  |  Prev  |  Top  |  Index  |  JOS Index  |  JOS Pubs  |  JOS Home  |  Search

Concavity (Convexity)



Definition. A set $ S$ is said to be concave if for every vector $ x$ and $ y$ in $ S$, $ \lambda x + (1-\lambda) y$ is in $ S$ for all $ 0\leq
\lambda \leq 1$. In other words, all points on the line between two points of $ S$ lie in $ S$.



Definition. A functional is a mapping from a vector space to the real numbers $ \Re $.

Thus, for example, every norm is a functional.



Definition. A linear functional is a functional $ f$ such that for each $ x$ and $ y$ in the linear space $ X$, and for all scalars $ \alpha$ and $ \beta$, we have $ f(\alpha x + \beta y) = \alpha f(x) +
\beta f(y)$.



Definition. The norm of a linear functional $ f$ is defined on the normed linear space $ X$ by

$\displaystyle \left\Vert\,f\,\right\Vert \mathrel{\stackrel{\mathrm{\Delta}}{=}}\sup_{x\in X} \frac{\left\vert f(x)\right\vert}{ \left\Vert\,x\,\right\Vert}.
$



Definition. A functional $ f$ defined on a concave subset $ S$ of a vector space $ X$ is said to be concave on $ S$ if for every vector $ x$ and $ y$ in $ S$,

$\displaystyle \lambda f(x) + (1-\lambda) f(y) \geq f\left(\lambda x + (1-\lambda) y\right)
,\qquad 0\leq \lambda \leq 1.
$

A concave functional has the property that its values along a line segment lie below or on the line between its values at the end points. The functional is strictly concave on $ S$ if strict inequality holds above for $ \lambda\in(0,1)$. Finally, $ f$ is uniformly concave on $ S$ if there exists $ c>0$ such that for all $ x,y\in S$,

$\displaystyle \lambda f(x) + (1-\lambda) f(y) - f\left(\lambda x + (1-\lambda) ...
...\lambda(1-\lambda)\left\Vert\,x-y\,\right\Vert^2
,\qquad 0\leq \lambda \leq 1.
$

We have

$\displaystyle \hbox{Uniformly}\;\; \hbox{Concave}\quad\implies\quad
\hbox{Strictly}\;\; \hbox{Concave}\quad\implies\quad \hbox{Concave}
$



Definition. A local minimizer of a real-valued function $ f(x)$ is any $ x^\ast$ such that $ f(x^\ast)<f(x)$ in some neighborhood of $ x$.



Definition. A global minimizer of a real-valued function $ f(x)$ on a set $ S$ is any $ x^\ast\in S$ such that $ f(x^\ast)<f(x)$ for all $ x\in S$.



Definition. A cluster point $ x$ of a sequence $ x_n$ is any point such that every neighborhood of $ x$ contains at least one $ x_n$.



Definition. The concave hull of a set $ S$ in a metric space is the smallest concave set containing $ S$.



Subsections
Next  |  Prev  |  Top  |  Index  |  JOS Index  |  JOS Pubs  |  JOS Home  |  Search

Download gradient.pdf
Download the whole thesis containing this material.

``Elementary Gradient-Based Parameter Estimation'', by Julius O. Smith III, from ``Techniques for Digital Filter Design and System Identification, with Application to the Violin,'' Julius O. Smith III, Ph.D. Dissertation, CCRMA, Department of Electrical Engineering, Stanford University, June 1983.
Copyright © 2006-01-03 by Julius O. Smith III
Center for Computer Research in Music and Acoustics (CCRMA),   Stanford University
CCRMA  [Automatic-links disclaimer]