Posted in Analysis and Optimization

Computing and Optimization in the Physical and Social Sciences – Slides of Ahmadi

Computing and Optimization in the Physical and Social Sciences:

Index of /~amirali/Public/Teaching/ORF363_COS323/F14

[ICO] Name Last modified Size Description

[PARENTDIR] Parent Directory
[   ] ORF363_COS323_F14_Lec1.pdf 2014-09-13 21:11 2.2M
[   ] ORF363_COS323_F14_Lec1.ppt 2014-09-13 21:15 8.0M
[   ] ORF363_COS323_F14_Lec2.pdf 2014-09-24 19:25 2.2M
[   ] ORF363_COS323_F14_Lec3.pdf 2014-09-25 23:54 5.7M
[   ] ORF363_COS323_F14_Lec4.pdf 2014-10-03 01:42 3.4M
[   ] ORF363_COS323_F14_Lec5.pdf 2014-10-04 12:03 3.1M
[   ] ORF363_COS323_F14_Lec6.pdf 2014-10-19 11:04 2.4M
[   ] ORF363_COS323_F14_Lec7.pdf 2014-10-18 10:18 2.6M
[   ] ORF363_COS323_F14_Lec8.pdf 2014-10-18 12:31 2.6M
[   ] ORF363_COS323_F14_Lec9.pdf 2014-11-03 02:02 4.4M
[   ] ORF363_COS323_F14_Lec10.pdf 2014-11-14 19:59 5.4M
[   ] ORF363_COS323_F14_Lec11.pdf 2015-01-04 16:51 1.5M
[   ] ORF363_COS323_F14_Lec12.pdf 2015-01-04 18:10 1.4M
[   ] ORF363_COS323_F14_Lec13.pdf 2015-01-04 18:28 4.4M
[   ] ORF363_COS323_F14_Lec14.pdf 2014-12-05 18:50 3.4M
[   ] ORF363_COS323_F14_Lec15.pdf 2014-12-11 15:25 4.3M
[   ] ORF363_COS323_F14_Lec16.pdf 2015-01-04 18:29 1.7M
[   ] cvx_examples.m 2014-10-04 01:47 1.1K

Apache/2.4.6 () Server at Port 80
Posted in Analysis and Optimization, Reading-writing

Representation of a linear functional

We review results of Haviland and Riesz on the reperesentation of a linear functional.

Definition 1 Let {X} be a subset of {\mathbb{R}^n} and {C(X)} be algebra of continuous functions on {X}. A positive linear functional on {C(X)} is a linear functional {L} with {L(f) \ge 0} for all {f \in C(X)} such that {f(a) \ge 0, \forall a \in X}.

We recall Haviland’s result in \cite{Marshall2} (also see \cite{Ha1, Ha2}), with {\mathbb{R}[x_1, \dots, x_n]} denotes the ring of real multivariable polynomials:

Theorem 2 (Haviland) For a linear functional {L: \mathbb{R}[x_1, \dots, x_n]} and closed set {K} in {\mathbb{R}^n}, the following are equivalent:

  1. {L} comes from a Borel measure on {K}, i.e., {\exists} a Borel measure {\mu} on {K} such that, {\forall f \in \mathbb{R}[x_1, \dots, x_n], L(f) = \int f d\mu.}
  2. {L(f) \ge 0} holds for all {f \in \mathbb{R}[x_1, \dots, x_n]} such that {f \ge 0} on {K}.

In Haviland’s theorem, a positive linear functional extended from ring of real multivariable polynomials to larger subalgebra and this theorem can be derived as a consequence of the following Riesz Representation Theorem (see \cite[p. 77]{KS}):

Theorem 3 (Riesz Representation Theorem) Let {X} be a locally compact Hausdorff space and let {L: C_c(X) \rightarrow \mathbb{R}} be a positive linear functional. Then there exists a unique Borel measure {\mu} on {X} such that

\displaystyle L(f) = \int f d\mu, \forall f \in C_c(X).

{C_c(X)} is the algebra of continuous functions with compact support.

Posted in Analysis and Optimization, Reading-writing

Riesz Representation Theorem – 1

This paragraph we follow the book of Rudin [1]. On linear functionals, there is special relationship between integration and linear functionals. In {L^1(\mu)}, a vector space, for any positive measure {\mu}, the mapping

\displaystyle f \mapsto \int_X f d\mu.

example, let {C([0,1])} be the set of all continuous functions on the unit interval {I = [0,1]}. Then

\displaystyle \Lambda f = \int_0^1 f(x)dx \quad \ (f \in C([0,1])),

has two properties:

  • {\Lambda(f + g) = \int_0^1[f(x) + g(x)]dx = \int_0^1f(x)dx + \int_0^1g(x)dx = \Lambda(f) + \Lambda(g)}.
  • {\Lambda(c.f) =\int_0^1cf(x)dx = c\int_0^1f(x)dx= c.\Lambda(f)}.

so it is a linear functional on {C([0,1])}. Moreover, this is a positive linear functional: if {f \ge 0} then {\Lambda(f) \ge 0}.

Consider a segment {(a,b) \subset I} and the class of all {f \in C(I)} with {0 \le f(x) \le 1, \forall x \in I} and {f(x) = 0, \forall x \notin (a,b)} or support of {f} is {(a,b) \subset I}. So we get {\Lambda(f) = \int_a^b f(x)dx \le \int_a^bdx = b-a}. It is important that the length of {(a,b)} related to the values of the functional {\Lambda}.

There is an important theorem of F. Riesz, this illustrates to above event

Theorem 1 (F. Riesz) Let X be a closed subset of \mathbb{R}. Then every positive linear functional {\Lambda} on {C(X)} there corresponds a finite positive Borel measure {\mu} on {X} such that

\displaystyle \Lambda(f) = \int_X fd\mu \quad \ (f \in C(X)).


[1] W. Rudin, Real and Complex analysis, Mc.Graw-Hill, 1970.

Posted in Analysis and Optimization, Reading-writing

On a property of holomorphic functions

We can see that a holomorphic functions are the complex functions such that they can express a convergent power series

\displaystyle f(z) = \sum_{i=0}^\infty a_nz^n.

We want to compute {\int\limits_\gamma f(z)dz}. Suppose {\gamma} is closed curve (Jordan curve).

We compute the integral for {\gamma = \mathbb{S}^1}. Firstly, consider {\int_{\mathbb{S}^1}z^ndz, n \ge 1}. Change the variables, {z = e^{2\pi it}, t \in [0,1]}, so

\displaystyle \int_{\mathbb{S}^1}z^ndz = \int_0^1e^{2n\pi it}2 \pi i\cdot e^{2\pi it}dt = \int_0^1e^{2(n+1)\pi it}2 \pi idt = \dfrac{e^{2(n+1)\pi it}}{n+1}\bigg|_0^1 = 0.

This computation, we think that it is important, because it implies a classical result
Theorem 1 (Cauchy integral theorem) Let {f : \mathbb{C} \rightarrow \mathbb{C}} be a holomorphic function on {\mathbb{C}}. Then

\displaystyle \int_\gamma f(z) dz= 0,

with {\gamma} is closed Jordan curve.

Of course it has modulo an any closed Jordan curve: If \gamma_1 and \gamma_2 are two closed Jordan curve with a common fixed point then  \displaystyle \int_{\gamma_1} f(z)dz = \int_{\gamma_2} f(z) dz,

Posted in Analysis and Optimization, Reading-writing

On the classical moment problems

We introduce to the classical moment problem, a short history. We refer to Akhiezer’s book:

N. I, Akhiezer, The Classical Moment Problem and Some Related Questions in
Analysis, Oliver & Boyd, Edinburgh/London, 1965.

and Christiansen’s notes: Moment (on Steven Miller’s page ).

The moment problem is a classical problem in analysis. This problem occurs for the first time in the work of Chebychev in 1873. After that, T.Stieltjes (1894-1895) and A.Markov consider more general case. Chebychev and A.Markov took the moment problem in the relationship with probability theory. The first solution and discussion of extended moment problem is due to Hamburger, he studied Classical moment problem (one-dimensional).
Classical moment problem (one-dimensional) Given an infinite sequence of real numbers {\{s_n\}_n} ({s_0 = 1}). Does there exist a positive Borel measure {\mu} such that:

\displaystyle s_n = \int_{\mathbb{R}}x^nd\mu(x).

In general, we have Classical moment problem (multidimensional)
Given a function {s : \mathbb{N}^k \rightarrow \mathbb{R}}. Does there exist a positive Borel measure {\mu} such that:

\displaystyle s(n) = \int_{\mathbb{R}^k}x_1^{n_1}\dots x_n^{n_k}d\mu(x_1,\dots,x_k)<\infty \quad (*).

In the case one-dimensional moments, the sequence {\{s_n\}} is a function and we have {s_n = s(n), n \in \mathbb{N}}.
Two measure {\mu} and {\nu} are called equivalent if they satisfy:

\displaystyle s_n = \int_{\mathbb{R}^k}x^n d\mu(x) = \int_{\mathbb{R}^k}x^n d\nu(x).

In other words, we say they have same moments.
The measure {\mu} is called determinate if there only exists {\mu} such that {s_n = \int_{\mathbb{R}^k}x^n d\mu(x)} and indeterminate otherwise.
The aims of the multidimensional moment problem are:

  1. To find necessary and sufficient conditions for existence of measure {\mu} satisfying (*).
  2. To be able to decide determinacy.
  3. In the indeterminate case to give a complete description of all measures satisfying (*).
Posted in Analysis and Optimization, Reading-writing

On the Spectral Theorem (from Linear algebra)

The form we prefers says that every bounded self-adjoint operator is a multiplication operator. This means that given a bounded self-adjoint operator on a Hilbert space {\mathcal{H}}, we can always find a measure {\mu} on a measure space {M} and a unitary operator {U: \mathcal{H} \rightarrow L^2(M, d\mu)} so that

\displaystyle (UAU^{-1}f)(x) = F(x)f(x),

for some bounded real-valued measurable function {F} on {M}.

In the case of real, the Hilbert space \mathcal{H} becomes a Euclidean space with an inner product. So an operator in \mathcal{H} corresponds with an orthogonal matrix A. And an orthogonal matrix can be diagonalized, i.e. there exists \lambda_1, \dots, \lambda_n \in \mathbb{R} and S^{-1} = S^T such that

\displaystyle S^TAS = diag(\lambda_1, \dots, \lambda_n).


Posted in Analysis and Optimization

Metric map

I don’t know about this concept. In fact the metric map is the nonexpansive map.

A continuous function between two metric spaces that does not increase distance, i.e.

d(f(x),f(y) \le d(x,y) with f: X \to Y.

There are many names for this concept: metric map, nonexpansive map, Lipschitz map with constant K=1, short map, weak contraction, nonexpanding map.

Posted in Analysis and Optimization

Lipschitz continuity

In this note, we talk about the Lipschitz continuity of a function on a metric space. We followed wikipedia.

Def. Given two metric space X, Y. A function f: X \to Y is called Lipschitz continuous if there exists a real constant K \ge 0 such that for all x_1, x_2 \in X, d(f(x_1), f(x_2)) \le K d(x_1, x_2).

The smallest constant is sometimes called the (best) Lipschitz constant.

A function is called locally Lipschitz continuous if for every x \in X, there exists a neighborhood U of x such that f restricted ti U is Lipschitz continuous. Equivalently, if X is a locally compact metric space, then f is locally Lipschitz if and only if it is Lipschitz continuous on every compact subset of X. In spaces that are not locally compact, this is a necessary but not a sufficient condition.

More generally, a function f defined on X is said to be Holder continuous or to satisfy a Holder condition of order \alpha > 0 on X if there exists a constant M > 0 such that d(f(x), f(y)) \le M d(x, y)^{\alpha}.

Posted in Analysis and Optimization, Calculus

Directional derivative

In multivariable calculus, there is  a notion of derivative, that is directional derivative.

Directional derivative is special derivative, follows a vector.

Definition. Let U \subset \mathbb{R}^m and U is open set. Let f: U \to \mathbb{R}^n. Suppose a \in U. Given v \in \mathbb{R}^m with v \ne 0, the directional of f at a corresponding to v is:

Df_v(a) = \lim\limits_{t \to 0}\dfrac{f(a + tu) - f(a)}{t}, if the limit exists.

Another definition: The directional derivative of f at a \in U corresponding to v is Df(a)\cdot v.

Theorem. Two above definitions are equivalent.