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

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.

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.

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,

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 (*).

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).


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.