<a name="docA001">　Index begin　Index this file
2009-06-08-19-10 start
This file http://freeman2.com/tute0008.htm
is Freeman's reading notes. Although Freeman
always keep correct view point. But Freeman's
capability is limited, plus no one proofread
this file. Then you can still find wrong view
point. When read, please put question mark as
often as possible. If you suspect any view 
point wrong, please ask a math expert near by.

<a name="docA002">,<a name="textbook">
This file is a note for reading inequality
book written by Professor J. Michael Steele
The Cauchy-Schwarz Master Class  　★★★★★
Below use 'textbook' as abbreviation.
Freeman also read web pages online, and will 
indicate the source URL at discussion point.

<a name="docA003">
Freeman study mechanical engineering. 
Engineering mathematics do not teach 
inequality. Above book is first inequality
book. First time read, it was very hard.
Although high school time learned
  a*a + b*b >= 2*a*b
But this little knowledge do not help.

<a name="docA004">
This file follow textbook chapter section
order, but not continuous, Freeman skip 
those uncertain sections/problems.

This file first function is to learn 
inequality. Second function is to learn
how to use html code to write math 
equations.

<a name="docA005">　Index begin　Index this file
On 2009-01-27-10-08 Freeman accessed
the next page
http://www.sftw.umac.mo/~fstitl/10mmo/inequality.html
save as sftw.umac.mo_text_math_eqn_good.htm
Above page is the main reference for html
math equation.

In order to let reader to build  html math
equation, previous file tute0007.htm page 
end has math symbol and internal code.

This file third function is to display how
to draw curves in web page. The main engine
is XYGraph v2.3 - Technical Figures

Thank you for read Freeman's inequality page.
2009-06-08-19-47 stop

<a name="docA006">
2009-08-23-15-00 start
□　Exercise 1.14 solution

Exercise 1.14 problem (a) is solved by hint
Exercise 1.14 problem (b) is out of LiuHH's
reach. What is "cardinality of a set B⊂Z3" ?
Without clear understand the definition, 
LiuHH is unable to solve problem (b)
LiuHH major in mechanical engineering.
LiuHH is mathematics admirer and outsider.

<a name="docA007">
To solve problems in
The Cauchy-Schwarz Master Class
LiuHH's goal is to solve 50% of the exercise
problems. In reality, solve 40% is good enough.
Please do not be surprise that LiuHH skip some
text section, skip some problems.
2009-08-23-15-12 stop



2009-12-09-16-49 start
<a name="ch06b001">　Index begin　Index this file
■　Convex function definition
First, review convex set definition

2009-12-03-13-04 LiuHH access next page
http://www.stanford.edu/class/cs229/section/cs229-cvxopt.pdf
page 1/14 (168,829 bytes)
[[
<a name="ch06b002">
2 Convex Sets
We begin our look at convex optimization
 with the notion of a convex set.
Definition 2.1 A set C is convex if, for 
any x, y ∈ C and θ ∈ R with 0 ≤ θ ≤ 1,
  θx + (1 − θ)y ∈ C ---eqn.AQ001

<a name="ch06b003">
Intuitively, this means that if we take 
any two elements in C, and draw a line 
segment between these two elements, then
every point on that line segment also 
belongs to C. 
<a name="ch06b004">
Figure 1 shows an example of one convex 
and one non-convex set. The point
  θx+(1−θ)y  ---eqn.AQ002
is called a convex combination of the 
points x and y.
]]
Figure 1 is same as ConvexA drawing

<a name="ch06b005">
Convex set is a function domain which
satisfy eqn.AQ001 requirement. Roughly
speaking, if function domain like a
circle cookie or like a ball apple, 
no place got a bite (cave inward),
then this domain is a convex domain.
Connect a straight line between any 
two points within domain, all points
on line are within domain.

<a name="ch06b006">　Index begin　Index this file
Next define convex function.
(convex function and convex set
 are different)
A function f:[a,b]→Real is said to be
convex function provided that for all
x,y∈[a,b] and all
  0≦p≦1  ---eqn.AQ003
one has　　Do we prove eqn.6.1?
  f(px +(1-p)y)≦
  pf(x)+(1-p)f(y)    ---eqn.6.1
 xe=px +(1−p)y ∈ [a,b] ---eqn.AQ004
Please pay attention to above three
lines math equation similarity.

<a name="ch06b007">
Explain x,y,p as following.
Assume f(x)=1/sin(x) ---eqn.AQ005
Assume domain = [0.001,3.14] ---eqn.AQ006
Assume x=0.6,  y=2.0,  p=0.55 ---eqn.AQ007
x, y must be within domain [0.001,3.14]
x and y are constant in this analysis.
p=0.55 can be varied between [0,1].
<a name="ch06b008">
Varying p represent vary xe between
constants x and y. See eqn.AQ004
When p=0, xe = constant y
When p=1, xe = constant x, 

<a name="ch06b009">
eqn.6.1 left side is
(interpolation within input domain)
  f(px +(1-p)y)=1/sin(0.55*0.6+(1-0.55)*2)
               =1.06102 ---eqn.AQ008
eqn.6.1 right side is
(interpolation within output range)
  pf(x)+(1-p)f(y)=
   0.55*1/sin(0.6) + (1-0.55)*1/sin(2)
               =1.46895 ---eqn.AQ009
<a name="ch06b010">
eqn.AQ004 let us find point xe
 xe=0.55*0.6 +(1-0.55)*2=1.23 ---eqn.AQ010
1.23 is inside the domain [0.001,3.14]

xe=1.23 is a point on x-axis,
eqn.6.1 left side evaluate function
value at xe. No matter what curve
f(x) has, f(xe) is always on function
curve.
<a name="ch06b011">
Interpolate domain point xe by px +(1−p)y
In contrast, eqn.6.1 right side
interpolate function value by pf(x)+(1-p)f(y)
pf(x)+(1-p)f(y) is a value NOT on f(x) 
curve in most case. 
Because evaluate function value at x 
and at y, not evaluate at xe. 
pf(x)+(1-p)f(y) is a value ON f(x) only
if f(x) is a straight line. Or if f(x)
is affine function, multi-dimension
function, every dimension are linear.
2009-12-09-17-55 stop



<a name="ch06b012">　Index begin　Index this file
2009-12-10-10-29 start
■　Jensen's Inequality
(textbook page 87, problem 6.1)
Suppose that f:[a,b]→real is a convex
function and suppose that the non-
negative real numbers pj, j=1,2,...,n
satisfy
  p1+p2+...+pn＝1 ---eqn.AQ011
show that for all xj in [a,b], 
j=1,2,...,n one has

<a name="ch06b013a">
2009-12-13-09-16 add start
We do not prove eqn.6.1, but we need 
to prove eqn.6.2. 
What is the difference?
If n=3, the expanded eqn.6.2 is next
f(p1x1+p2x2+p3x3) ≦ p1f(x1)+p2f(x2)+p3f(x3) ---eqn.6.2 Aux1
and  p1+p2+p3=1 ---eqn.AQ011 aux1
eqn.6.2 Aux1 has three terms, but
eqn.6.1 has only two terms, they
are different.
2009-12-13-09-20 add stop

<a name="ch06b014">
2009-12-10-10-46 here
Compare eqn.6.1 and eqn.6.2, in eqn.6.2 
if set n=2, we find
  f(p1x1+p2x2) ≦ p1f(x1)+p2f(x2) ---eqn.AQ012
rewrite p1 as p, and p2 as (1-p) we get
  f(p * x1 +(1-p) * x2) ≦
    p*f(x1)+(1-p)*f(x2) ---eqn.AQ013

Change x1 as x, and x2 as y
eqn.AQ013 is same as eqn.6.1. Therefore
eqn.6.2 is a generalization equation
eqn.6.2 include eqn.6.1 as a special
case.

<a name="ch06b015"> //2009-12-22-10-19 add start
■　Jensen's Inequality key points
Jensen Inequality use generalized AM
Jensen Ineq.  NOT use generalized GM

<a name="ch06b015a">
If function domain is convex set
If equation is convex function
Jensen's Inequality says:
  AM in domain ≦ AM in range
<a name="ch06b015b">
If function domain is convex set
If equation is concave function
Jensen's Inequality says:
  AM in domain ≧ AM in range
<a name="ch06b015c">
If function domain is NOT convex set, or
If equation is NOT concave/convex
Jensen's Inequality do not apply.
//2009-12-22-10-26 add end

<a name="ch06b016">　Index begin　Index this file
■　Do we prove eqn.6.1 ?
NO, we do not prove eqn.6.1, because
eqn.6.1 is a definition equation for
a convex function. then 
do we prove eqn.6.2 ? yes, we need to 
prove eqn.6.2 and show eqn.6.2 is true
for a convex function.

<a name="ch06b017">
To prove a equation of summation, it 
is naturally first consider the proof
of induction. That is in a sequence 
of summation equations, we assume the 
n-1 th equation is true, and show that
n th equation is also true. We need to
use the average of size n-1 and the
average of size n. Because we assume 
<a name="ch06b018">
the n-1 th equation is true, and show
that n th equation is also true. We 
separate the n th equation to two
parts, one is already true n-1 th 
and earlier terms and the other one
is the unknown n th term. That is
divide n term equation to TWO terms
(Lump first n-1 terms as ONE term)
<a name="ch06b019">
Please register in your brain one 
more time that
  p1+p2+...+pn＝1 ---eqn.AQ011
sum equal to one is just like the
principle of conservation of mass.
(forget relativity here)
If sum more than one, then must be
angel added some thing.
If sum less than one, then must be
devil removed some thing.
Both are suspicious.
<a name="ch06b020">
Now let us write ∑pjxj into two 
terms, one already true, one new
added n th term.

<a name="ch06b021">　Index begin　Index this file
2009-12-10-11-56 here
eqn.AQ014 is for domain elements,
for function inputs, like distance
for gravity equation, or working
hours for salary equation.

Next write the function equation,
that is function output, like force
for gravity equation, or payment in
dollars for salary equation.

<a name="ch06b025">
2009-12-10-12-28 here
In this derivation, we used 
definition equation for a convex
function  eqn.6.1
and used induction assumption: 
previous iteration is true.
Result eqn.AQ017 is same as eqn.6.2
We solved Jensen's Inequality
Problem 6.1, eqn.6.2
2009-12-10-12-32 stop

<a name="ch06b026">
2009-12-11-19-51 start
Today 2009-12-11 wrote program to
calculate Jensen's Inequality.
Document is at tute0022.htm#ch06a063
Program  is at tute0022.htm#Jensen01
You are welcome to test run.
2009-12-11-19-56 stop

<a name="ch06b027">　Index begin　Index this file
2009-12-12-11-27 start
■　When Jensen's Inequality become equality?
A function f:[a,b]→Real is said to be
strict convex function provided that 
for all x,y∈[a,b] and all
  0＜p＜1  ---eqn.AQ018 // Use '＜', not '≦'
and x≠y   ---eqn.AQ019 //not asked in previous text.
<a name="ch06b028">
one has
  f(px +(1-p)y)＜ // Use '＜' instead of '≦'
  pf(x)+(1-p)f(y)    ---eqn.AQ020

strict convex come from 
use '＜' instead of '≦' and from
 x≠y .

<a name="ch06b029">
use '＜' instead of '≦' rule out the 
flat bottom bowl case.
 x≠y rule out the Jensen's Inequality
become equality case.

<a name="ch06b030">
Next is the Jensen's equality problem.
(textbook page 89, problem 6.2)
Suppose that f:[a,b]→Real is strictly
convex. Sow that if

<a name="ch06b032">　Index begin　Index this file
2009-12-12-12-00 here
where the positive reals pj, 
j=1,2,...,n have sum
  p1+p2+...+pn＝1---eqn.AQ021
then one must have
  x1＝x2＝...＝xn ---eqn.AQ022

<a name="ch06b033">
We prove this problem by contradiction.
We assume equality eqn.6.4 is true,
then we 
take a set of pj which do  satisfy eqn.AQ021
take a set of xj which NOT satisfy eqn.AQ022
We work backward, from unequal xj 
work toward eqn.6.4, if we find 
unequal xj violate eqn.6.4 equality
then the proof is done.

<a name="ch06b034">
In order to build a set of unequal xj
Let us define a set S
  S={j:xj≠max[1≦k≦n]xk} ---eqn.AQ023
A numerical example is next.
Assume whole set of xj 1≦j≦5 is
  S5={1,2,3,3,3} ---eqn.AQ024
Now the set S2 is defined as
  S2={1,2} ---eqn.AQ025
S2 is the set S in eqn.AQ023, because
S2 dropped maximum value elements 3.
<a name="ch06b035">
S2 is a sub-set of S5, since every
elements in S2 are an elements of S5.
We will show that the set S5 (unequal
xj) will NOT satisfy eqn.6.4
Assume probability set is
  p5={0.06,0.18,0.39,0.15,0.22} ---eqn.AQ026
<a name="ch06b036">
Let us define
  p=∑[j∈S]pj ---eqn.AQ027
  x=∑[j∈S]pj*xj/p ---eqn.AQ028
  y=∑[j NOT∈ S]pj*xj/(1-p) ---eqn.AQ029
For above numerical example, we have
  p=0.06+0.18=0.24 ---eqn.AQ030
  x=(0.06*1+0.18*2)/0.24=1.75 ---eqn.AQ031
  y=(0.39*3+0.15*3+0.22*3)/(1-0.24)=3.0 ---eqn.AQ032
<a name="ch06b037">　Index begin　Index this file
Initially there are five points in S5
After eqn.AQ027,eqn.AQ028,eqn.AQ029 we
have only two points x=1.75 and y=3.0
in function domain. Since 1.75≠3.0
this is eqn.AQ019 x≠y condition, then
strict convex function eqn.AQ020 tell
us that
  f(px +(1-p)y)＜ // Use '＜' instead of '≦'
  pf(x)+(1-p)f(y)    ---eqn.AQ020
<a name="ch06b038">
Put eqn.AQ030,eqn.AQ031,eqn.AQ032 into
eqn.AQ020, we have the numerical value
  f(0.24*1.75 +(1-0.24)*3.0)＜
  0.24*f(1.75)+(1-0.24)*f(3.0) ---eqn.AQ033
To see a real numerical example, need
give f(x) definition. We know exp(x)
is always convex for all real x. Now
<a name="ch06b039">
assume f(x)=exp(x), then
  exp(0.24*1.75 +(1-0.24)*3.0)＜
  0.24*exp(1.75)+(1-0.24)*exp(3.0) ---eqn.AQ034
give us
  14.8797 ＜ 16.6461
which is correct. Numerical example
is specific, and easier to understand.
<a name="ch06b040">
Symbolic equation is general, we need
continue work with symbolic equation.
Because x=1.75 ≠ y=3.0
strict convex function implies

<a name="ch06b041">
2009-12-12-13-10 here
x=1.75 ≠ y=3.0 cause inequality in 
eqn.6.6, then in tern lead us get a 
contradiction result. Continue as 
following.

<a name="ch06b042">　Index begin　Index this file
eqn.6.6 right side two terms 
  pf(x)+(1－p)f(y) ---eqn.AQ035
are several pj and xj combined
terms. Let us un-tie them now
  pf(x)=∑[j∈S]{pj}*f(∑[j∈S]{xj}) ---eqn.AQ036
and
  (1－p)f(y)=(1-∑[j∈S]{pj})*f(∑[j NOT∈ S]{xj}) ---eqn.AQ037
Above numerical example has
  pf(x)=0.24*f(1.75) ---eqn.AQ038
and
  (1－p)f(y)=(1-0.24)*f(3.0) ---eqn.AQ039
<a name="ch06b043">
Numerical example is just auxiliary.
Continue symbolic equation.
eqn.AQ036 f(∑[j∈S]{xj}) can be
un-tie (un-group) by plane vanilla 
convexity inequality as
  f(∑[j∈S]{xj}) ≦
  ∑[j∈S]{pjf(xj)/p} ---eqn.AQ040
here we used eqn.AQ027 and eqn.AQ028 
to release both pj and xj.

<a name="ch06b044">
eqn.AQ037
 (1-∑[j∈S]{pj})*f(∑[j NOT∈ S]{xj})
can be
un-tie (un-group) by plane vanilla 
convexity inequality as
  (1－p)f(y) ≦  ---eqn.AQ041
  (1-p)*∑[j NOT∈ S]{pj*f(xj)/(1-p)}
here we used eqn.AQ027 and eqn.AQ029 
to release both pj and xj.

<a name="ch06b045">
eqn.AQ040 is for j ∈ S
eqn.AQ041 is for j NOT∈ S
Add eqn.AQ040 and eqn.AQ041 get whole
equation, pay attention to that
in eqn.AQ040 cancel common factor p
in eqn.AQ041 cancel common factor (1-p)
whole equation result is
  pf(x)+(1－p)f(y)≦
  ∑[j=1,n]{pj*f(xj} ---eqn.AQ042
eqn.AQ042 left side is eqn.6.6 right
side, put two equation together, get

<a name="ch06b047">
2009-12-12-13-51 here
This inequality come from
x=1.75 ≠ y=3.0 and
strict convex function definition.
(inequality not come from eqn.AQ042
 eqn.AQ042 include strict inequality
 also include non-strict inequality)
Then start from x ≠ y, we can not 
reach the equality eqn.6.4
<a name="ch06b048">
This contradiction tell us that 
only if satisfy
  x1＝x2＝...＝xn ---eqn.AQ022
then
Jensen's Inequality become equality.

textbook page 89, problem 6.2 solved.
2009-12-12-13-55 stop



<a name="ch06b049">　Index begin　Index this file
2009-12-12-15-22 start
■　Twice differentiation ≧0 get convexity
(textbook page 90, problem 6.3)
Show that if f:(a,b)→real is twice
differentiable, then
  f''(x)≧0 for all x∈(a,b)---eqn.AQ044
implies f(.) is convex on (a,b)
and in parallel, show that
  f''(x)＞0 for all x∈(a,b)---eqn.AQ045
implies f(.) is strictly convex on
(a,b).

<a name="ch06b050">
To prove we need fundamental theorem
of calculus. Assume 
x0 is a fixed value in domain [a,b], 
we can find

<a name="ch06b051">
2009-12-12-15-46 here
From basic calculus, we know
if f'(x)＞0, then f(x) is increasing
at that point.
if f'(x)≧0, then f(x) is non-decreasing
at that point.
<a name="ch06b052">
Similarly (we need the following)
if f''(x)＞0, then f'(x) is increasing
at that point.
if f''(x)≧0, then f'(x) is non-decreasing
at that point.

<a name="ch06b053">
Now problem 6.3 give 
  f''(x)≧0 for all x∈(a,b)---eqn.AQ044
then we have f'(x) is non-decreasing
in hand. This means that if x move
toward greater domain value, then
f'(x) increase its function value.
f(x)=exp(x) have such property.

<a name="ch06b054">　Index begin　Index this file
Another example
g(x)=x*log(x) differentiation 
g'(x)=log(x)+1
g''(x)=1/x
Between g'(x) and g''(x) also have
such property (increase g'(x) value)
2009-12-12-15-59 stop

<a name="ch06b055">
2009-12-12-17-18 start
Our basic assumption is
  f''(x)≧0 ---eqn.AQ044
We assume further condition
  a≦x＜y≦b ---eqn.AQ045
and
  0＜p＜1 ---eqn.AQ046
<a name="ch06b056">
we set
  q=1-p ---eqn.AQ047
we require a constant point
  x0=px+qy ---eqn.AQ048
All above assumption and setting
serve for
  f(px +(1-p)y)≦
  pf(x)+(1-p)f(y)    ---eqn.6.1
<a name="ch06b057">
Let us use ∆ denote eqn.6.1 two
side difference as following
  ∆=pf(x)+(1-p)f(y)-f(px+(1-p)y) ---eqn.AQ049
Use eqn.AQ047, eqn.AQ049 become
  ∆=pf(x)+qf(y)-f(px+qy) ---eqn.AQ050
Use eqn.AQ048, eqn.AQ050 become
  ∆=pf(x)+qf(y)-f(x0) ---eqn.AQ051
<a name="ch06b058">
re-write eqn.AQ051 as
  ∆=pf(x)+qf(y)-1*f(x0)
and use eqn.AQ047 get
  ∆=pf(x)+qf(y)-(p+q)*f(x0) ---eqn.AQ052
that is
  ∆=pf(x)+qf(y)-p*f(x0)-q*f(x0) ---eqn.AQ053
regroup
  ∆=[pf(x)-p*f(x0)]+[qf(y)-q*f(x0)]
or
  ∆=q*[f(y)-f(x0)]-p*[f(x0)-f(x)] ---eqn.AQ054
<a name="ch06b059">　Index begin　Index this file
review
  a≦x＜y≦b ---eqn.AQ045
  0＜p＜1 ---eqn.AQ046
  q=1-p ---eqn.AQ047
  x0=px+qy ---eqn.AQ048
Assume a=1, b=5, p=0.7 ---eqn.AQ055
Assume x=2, y=4 ---eqn.AQ056
then
  x0=px+qy=0.7*2+0.3*4=2.6 ---eqn.AQ057
p,x,q,y may vary, but x0=2.6 is fixed.
<a name="ch06b060">
this tell us
  ∆=q*[f(y)-f(x0)]-p*[f(x0)-f(x)] ---eqn.AQ054
can be written as two integration
at two side of the fixed point x0

<a name="ch06b061">
Because  x＜x0＜y ---eqn.AQ058a
and because f''(x)≧0
therefore  f'(x)＜f'(x0)＜f'(y) ---eqn.AQ058b
q*[f'(y)-f'(x0)] is greater function
   value side integration
p*[f'(x0)-f'(x)] is smaller function
   value side integration.
[f'(x) is non-decreasing function]

The following, we want to show that
 ∆ in eqn.AQ054 is a positive value.

For p*[f(x0)-f(x)] its domain is 
x to x0 (numerical [2,2.6],
        smaller f'(x) side)
Write p*[f'(x0)-f'(x)] as

<a name="ch06b063">
2009-12-12-18-19 here
eqn.6.9 left side is p*[f'(x0)-f'(x)] 
which is based on fundamental theorem
of calculus.
Explain inequality in eqn.6.9 as
following.

<a name="ch06b064">　Index begin　Index this file
We have given condition
 f''(x)≧0 for all x∈(a,b)---eqn.AQ044
and the simple calculus truth
f'(x) is increasing
eqn.6.9 domain is u∈[x, x0]
(u is variable, x is constant here)
then  f'(u)≦f'(x0) ---eqn.AQ059
(f'(x) is increasing and u≦x0)
x0 is a fixed value
<a name="ch06b065">
In eqn.6.9 left side, replace all
f'(u) by f'(x0) then constant f'(x0)
can be move out of integration sign.
At the same time, replaced term has
greater value than original term. 
After f'(x0) pull out of integration
sign, what left in integral sign is
  f'(px+qy)*p*∫du from u=x to u=x0 ---eqn.AQ060
<a name="ch06b066">
which is
  f'(px+qy)*p*(x0-x) ---eqn.AQ061
remember x0=px+qy ---eqn.AQ048 
then eqn.AQ061 become
  f'(px+qy)*p*(px+qy-x) ---eqn.AQ062
<a name="ch06b067">
use q=1-p ---eqn.AQ047
to eliminate p, eqn.AQ062 become
  f'(px+qy)*p*(+qy-qx)
or (we get q factor here look back)
  f'(px+qy)*p*q*(y-x) ---eqn.AQ063
Put eqn.AQ063 to eqn.6.9
Here done shown that eqn.6.9 is true.
eqn.6.9 is half of eqn.6.8

<a name="ch06b068">
The other half of eqn.6.8 is same as
above analysis. But reverse inequality
sign. Because other half, x0 is
lower bound, not upper bound. Domain
of other half is u∈[x0,y]=[2.6, 4]
Other half result is

<a name="ch06b070">
2009-12-12-19-00 here
Compare eqn.6.9 with eqn.6.10, find
  eqn.6.9 ≦ qp(y-x)*f ' (px+qy) ≦ eqn.6.10

Then eqn.6.8 two side unequal value
is proved, we conclude that ∆≧0,
that is (see eqn.AQ049)
  f(px +(1-p)y)≦
  pf(x)+(1-p)f(y)    ---eqn.6.1
is true.

We start from twice differentiation ≧0
end at get convex conclusion eqn.6.1

<a name="ch06b071">
Above is f''(x)≧0 imply convex.
Below is f''(x)＞0 imply strict convex.
We only need to know that if f''(x)＞0 
then both of eqn.6.9 and eqn.6.10 are
strict, and eqn.6.8 gives us ∆＞0 ,
we get the strict convexity.

Textbook page 90, problem 6.3 is done.
2009-12-12-19-12 stop

<a name="alertwordy">
This is a wordy page.
This is no star page.
If you like to read to the 
point directly textbook, 
and expert writing with
better English,
please read The 
Cauchy-Schwarz Master Class
by Prof. J. Michael Steele
Five stars ★★★★★ book
ISBN 978-0-521-54677-5
2009-12-12-19-27

<a name="ch06b072">　Index begin　Index this file
2009-12-13-12-03 start
■　Jensen express to AM-GM
Jensen's Inequality eqn.6.2 allow us to
reach AM-GM inequality in one step.
Assume y1,y2,...,yn are all real numbers.
Assume p1,p2,...,pn are all non-negative.
with
  p1+p2+...+pn＝1 ---eqn.AQ064
<a name="ch06b073">
Jensen's Inequality also need a convex
function. exp() is a convex function 
for all real domain. Please see graph
for exp(), please click button '1'.
The exponential function exp() do the 
right job for AM-GM inequality. Now put 
everything into Jensen's Inequality 
eqn.6.2, we find

<a name="ch06b075">
2009-12-13-12-18 here
eqn.AQ065 is same as eqn.6.2 with a
simple replacement 'f' change to 'exp'.
Now define
  xj＝exp(yj) ---eqn.AQ066
Assume n=3, eqn.AQ065 become
  exp(p1y1+p2y2+p3y3) ≦  ---eqn.AQ067
  p1exp(y1)+p2exp(y2)+p3exp(y3)
eqn.AQ067 is same as
  exp(p1y1)*exp(p2y2)*exp(p3y3) ≦  ---eqn.AQ068
  p1exp(y1)+p2exp(y2)+p3exp(y3)

<a name="ch06b076">
Because (e^a)^b = e^(a*b) ---eqn.AQ069
eqn.AQ068 is same as
  [exp(y1)]^p1*[exp(y2)]^p2*[exp(y3)]^p3 ≦ ---eqn.AQ070
  p1exp(y1)+p2exp(y2)+p3exp(y3)
Now apply eqn.AQ066 to eqn.AQ070
we get
  [x1]^p1*[x2]^p2*[x3]^p3 ≦ ---eqn.AQ071
  p1x1+p2x2+p3x3
eqn.AQ071 is for n=3 case, 
For general n we have

<a name="ch06b078">
2009-12-13-12-40 here
Who else ?! 
eqn.AQ072 is AM-GM Inequality eqn.2.9 !
2009-12-13-12-42 stop

<a name="ch06b079">
2009-12-13-19-51 start
■　On the maximum of the product 
　　of two edges
(textbook page 92, problem 6.4)
In an equilateral triangle with area
A, the product of any two sides is
equal to (4/√3)*A. Show that this
represents the extreme case in the
sense that for a triangle with area 
A there must exist two sides the
lengths of which have a product that
is at least as large as (4/√3)*A

<a name="ch06b080">
From trigonometry, we know that the 
triangle area A relates to three 
sides and angle as following
  A=ab*sin(γ)/2 ---eqn.AQ073a
  A=ac*sin(β)/2 ---eqn.AQ073b
  A=bc*sin(α)/2 ---eqn.AQ073c
then we have
  ab=2*A/sin(γ) ---eqn.AQ074
  bc=2*A/sin(α) ---eqn.AQ075
  ca=2*A/sin(β) ---eqn.AQ076
<a name="ch06b081">
To keep symmetry, we average above 
three equations.

<a name="ch06b082">
2009-12-13-20-17 here
eqn.6.11 right side has function 1/sin(x)
We know triangle each angle range from
zero degree to 180 degree. Function
domain is (0,PI), within this domain
function 1/sin(x) is convex.
It is easy to see that 
  f(x)=1/sin(x)  ---eqn.AQ077
  f'(x)=-cos(x)/sin(x)/sin(x)  ---eqn.AQ078
  f''(x)=1/sin(x) +2*[cos(x)]^2/[sin(x)]^3  ---eqn.AQ079

<a name="ch06b084">　Index begin　Index this file
2009-12-13-20-29 here
Please click Draw 1/sin(x) button to
see f(x)=1/sin(x), f'(x), and f''(x).

eqn.AQ079 and eqn.6.12 are same 
equation. 
eqn.AQ079 is simple expression
eqn.6.12  is better expression

Because f''(x) is positive in (0,PI)
therefore, f(x) is convex in (0,PI)
we can use Jensen's Inequality to get

<a name="ch06b086">
2009-12-13-20-45 here
eqn.AQ080 multiply whole equation by
2*A, then eqn.AQ080 left side is same
as eqn.6.11 right side. We get
eqn.6.11 left side ≧ (2A)*2/√3
that is
<a name="ch06b087">
  (ab+bc+ca)/3 ≧ (2A)*2/√3 = 4A/√3 ---eqn.AQ081
eqn.AQ081 left side is average of
ab, bc, ca three two sides product.
The maximum of ab, bc, ca must be
greater than or equal to this average.
Finally we find
  max(ab,bc,ca)≧(ab+bc+ca)/3≧4A/√3 ---eqn.6.13
Problem 6.4 is solved.
2009-12-13-20-55 stop

<a name="ch06b088">　Index begin　Index this file
2009-12-14-08-15 start
■　Why normalize by the factor "1/(1-pn)"?
In eqn.AQ014 we have "1/(1-pn)" The
reason is simple.
In n th step, we require
  p1+p2+...+pn＝1 ---eqn.AQ011
This sum pj to one is demanded in 
each step.
For previous n-1 th step, we require
  p'1+p'2+...+p'n-1＝1 ---eqn.AQ082
<a name="ch06b089">
But eqn.AQ011 give us n-1 th step 
  p1+p2+...+pn-1＝1-pn ---eqn.AQ083
eqn.AQ083 whole equation divide by
(1-pn) then eqn.AQ082 and eqn.AQ083
are identical.
We use n th step p to express
 n-1 th step p', isn't that smart?
eqn.AQ083/(1-pn) is exactly what we
need. This divide by (1-pn) show up
at eqn.AQ014 as "1/(1-pn)"

<a name="ch06b090">
If not do "1/(1-pn)" in eqn.AQ014
we can not use previous iteration
result, we can not change from 
eqn.AQ015 to eqn.AQ016, that is we
can not finish the proof.
2009-12-14-08-46 stop

<a name="ch06b091">　Index begin　Index this file
2009-12-14-09-27 start
■　Weitzenbock's inequality
We proved eqn.6.13. There is another
inequality relate to eqn.6.13 closely.
It is Weitzenbock's inequality.
In any triangle with sides a,b,c and
area A, we have
  a2+b2+c2 ≧ 4√3A ---eqn.6.14
<a name="ch06b092">
If we start from eqn.6.13 then just
one step get the answer. This step
is that 
  a2+b2+c2 ≧ ab+bc+ca ---eqn.AQ084
2009-12-14-09-37 here

<a name="ch06b093">
To prove eqn.AQ084, assume we have
two sequences
  seq1=[a,b,c] ---eqn.AQ085
  seq2=[b,c,a] ---eqn.AQ086
then Cauchy's inequality give us
  seq1 dot seq2 ≦
  √(seq1 dot seq1) * √(seq2 dot seq2)
<a name="ch06b094">
then we have
  ab+bc+ca ≦ √(a*a+b*b+c*c)*√(b*b+c*c+a*a)
this is
  ab+bc+ca ≦ a*a+b*b+c*c  ---eqn.AQ087

<a name="ch06b095">　Index begin　Index this file
Second proof, assume a≦b≦c, then
rearrangement inequality tell us
that same order two sequence
  seq3=[a,b,c] ---eqn.AQ088
  seq4=[a,b,c] ---eqn.AQ089
<a name="ch06b096">
product sum a*a+b*b+c*c
is greater than or equal to random
order two sequence
  seq3=[a,b,c] ---eqn.AQ088
  seq5=[b,c,a] ---eqn.AQ090
product sum a*b+b*c+c*a
that is 
  ab+bc+ca ≦ a*a+b*b+c*c  ---eqn.AQ087
again
2009-12-14-09-58 stop

<a name="ch06b097">
2009-12-14-11-28 start
Third method to prove eqn.AQ084
is the basic arithmetic calculation
  (a-b)*(a-b)=aa+bb-2ab ≧0 ---eqn.AQ090
  aa+bb ≧ 2ab ---eqn.AQ091
similarly
  bb+cc ≧ 2bc ---eqn.AQ092
  cc+aa ≧ 2ca ---eqn.AQ093
<a name="ch06b098">
Add eqn.AQ091, eqn.AQ092, eqn.AQ093
get
  2*a*a+2*b*b+2*c*c ≧ 2*ab+2*bc+2*ca 
cancel 2 get eqn.AQ084.

<a name="ch06b099">
Above is three proofs for eqn.AQ084.
Now put
  a2+b2+c2 ≧ ab+bc+ca ---eqn.AQ084
and
  (ab+bc+ca)/3 ≧ 4A/√3 ---eqn.6.13
side by side. If multiply 3 in eqn.6.13
and write above two equation as one,
<a name="ch06b100">
we get
  a2+b2+c2 ≧ ab+bc+ca ≧ 3*4A/√3 
finally get
  a2+b2+c2 ≧ 4*√3A ---eqn.AQ094
eqn.AQ094 is same as eqn.6.14.
Weitzenbock's inequality is solved
easily with the help of eqn.6.13
2009-12-14-11-47 stop

<a name="ch06b101">　Index begin　Index this file
2009-12-14-16-49 start
■　Holder's Defect Formula　　NOT DONE
(textbook page 94, problem 6.5)

If f:[a,b]→real is twice differentiable
and if we have the bound
  0≦m≦f''(x)≦M ---eqn.6.15
for all x∈[a,b].
then for any real values
  a≦x1≦x2≦...≦xn≦b ---eqn.AQ095
<a name="ch06b101A">
and any non negative reals pk
 k=1,2,...,n with
  p1+p2+...+pn＝1 ---eqn.AQ096
there exist a real value μ∈[m,M]
for which one has the formula

<a name="ch06b103">
2009-12-14-17-14 here
There are few points need your attention
before continue.

First: eqn.6.16 left side f(x) is any
  convex function. for example
  f(x) = exp(x), x∈(-inf, +inf)
  f(x) = x*log(x), x∈(0, +inf)
  f(x) = 1/sin(x), x∈(0, PI)   etc.
  All of these functions are highly
  nonlinear, but eqn.6.16 right side 
  f(x) is replaced by x*x, yet 
  eqn.6.16 is equality equation !
  This mean that during prove process
  we will replace any convex function
  by x*x.

<a name="ch06b104">
Second: whether eqn.6.16 is reasonable
  in terms of physics dimension
  consistency check? We can not
  equate area with velocity !!
  LOOK! eqn.6.16 right side has x*x
  and has μ and has twice pjpk
  But eqn.6.16 left side do not have
  x*x, and have just one pj, and 
  left side no μ at all !

<a name="ch06b105">　Index begin　Index this file
Can you answer second attention ?
Please think first. LiuHH reasoning 
is here.
2009-12-14-17-32 stop



The following is uncertain notes.
Definitely contain error. BE ALERT !!



<a name="ch06b106">
If the difference M-m is small, the
bound eqn.6.16 tell us that f behave
rather like a quadratic function on
[a,b]. In the extreme case, if M=m≠0
then f(x) is exactly quadratic.

<a name="ch06b107">
Similarly, if M≧0 and M is very close
to zero, then f behave rather like a 
affine function (linear function in
multi dimension). If f(x) is affine
exactly, then eqn.6.16 left side is
zero exactly. That is for a linear
function, Jensen's Inequality　become
equality. 

<a name="ch06b108">
We are given the condition
  0≦m≦f''(x)≦M ---eqn.6.15
for all x∈[a,b].
which is the soul of this specific 
problem, how do we use eqn.6.15?
eqn.6.15 give us two inequalities
<a name="ch06b109">
Let us define
  g''(x)=M-f''(x)≧0 ---eqn.AQ097
and
  h''(x)=f''(x)-m≧0 ---eqn.AQ098
Both g''(x) and h''(x) come from the
given condition eqn.6.15.



<a name="ch06b110">　Index begin　Index this file
 g''(x) is a positive function, we
integrate g''(x) along x axis in
positive direction, the integration
result g'(x) is positive again. 
Integrate one more time, get
  g(x)= 0.5*M*x*x - f(x)≧0 ---eqn.AQ099
<a name="ch06b111">
Similarly, integrate h''(x) twice
get
  h(x)= f(x) - 0.5*m*x*x≧0 ---eqn.AQ100

eqn.AQ099 and eqn.AQ100 are two 
equations help us to replace ANY
highly non-linear convex function
by x*x.
[[
2009-12-15-10-17 change above to gray color
2009-12-15-10-19 Int[sin(x)]dx=-cos(x)+const.
here -cos(x) is not all positive.
]]
<a name="ch06b112">
Because starting point g''(x)≧0 and
h''(x)≧0, the section
Twice differentiation ≧0 get convexity
tell us that g(x) and h(x) are convex.
Then we can apply Jensen's Inequality　
for convex function to both g(x), h(x).
Now let us exam //2009-12-15-10-23 gray
  g(x)= 0.5*M*x*x - f(x)≧0 ---eqn.AQ099
<a name="ch06b113">
We need apply Jensen's Inequality　for
  a≦x1≦x2≦...≦xn≦b ---eqn.AQ095
and
  p1+p2+...+pn＝1 ---eqn.AQ096
Let us define
  x_bar=p1x1+p2x2+...+pnxn ---eqn.AQ101
Jensen's Inequality　let us write

<a name="ch06b116">
2009-12-14-18-40 here
eqn.AQ103 right side has f(x), 
f(x) can be ANY convex function
use eqn.AQ099
  g(x)= 0.5*M*x*x - f(x)≧0 ---eqn.AQ099
rewrite as
  -f(x) ≧ -0.5*M*x*x  ---eqn.AQ104
wrong direction !!
2009-12-14-18-46 here
<a name="ch06b117">
f(x_bar)=f(∑pkxk) ≦ ∑pk*f(xk)
Why ∑pk*f(xk) can be replaced by
0.5*M*x_bar*x_bar ?
here f(xk) is any nonlinear
convex function. and x_bar*x_bar
is quadratic.
2009-12-14-18-52 stop

<a name="ch06b118">
2009-12-14-20-41 start
In an inequality,
if increase greater than side value,
inequality stand firmly.
if decrease less than side value,
inequality stand firmly.
<a name="ch06b119">
But if do the opposite
decrease greater than side value,
or
increase less than side value,
inequality become uncertain.
Now we need to show

<a name="ch06b121">
2009-12-14-20-58 here
eqn.AQ105 left side is eqn.AQ103 
right side. It has highly 
nonlinear f(x) convex function.

eqn.AQ105 right side is textbook
page 95 line 27 middle term.
nonlinear f(x) replaced by x*x

<a name="ch06b122">
How this replacement take place?
LiuHH guess that 
  g(x)= 0.5*M*x*x - f(x)≧0 ---eqn.AQ099
help. But set x=x_bar get
  0.5*M*x_bar*x_bar ≧ f(x_bar) ---eqn.AQ106
eqn.AQ103 right side subtract
f(x_bar) which is smaller, 
change to 
eqn.AQ103 right side subtract
0.5*M*x_bar*x_bar which is bigger.

<a name="ch06b123">
For example, 3 is bigger than 2
10-2 compare with 10-3, that is
8 compare with 7, value reduced.
This is inequality greater than 
side. After replace, value reduced
cause inequality uncertainty.
LiuHH's reading and thinking must
miss something. Still try to figure
how nonlinear f(x) can be replaced
by x*x.
2009-12-14-21-10 stop








<a name="ch06b124">
2009-12-15-10-28 start
LiuHH try to fill in detail for
Holder's Defect Formula, but fail
to figure out how to replace any
  convex function. for example
  f(x) = exp(x), x∈(-inf, +inf)
  f(x) = x*log(x), x∈(0, +inf)
  f(x) = 1/sin(x), x∈(0, PI)   etc.
by x*x quadratic function. The trouble
step is from

<a name="ch06b127">
how to change from f(xk)
to x_bar*x_bar? LiuHH is till try
to figure out.
2009-12-15-10-42


Above is uncertain notes.
Definitely contain error. BE ALERT !!


<a name="ch06b128">　Index begin　Index this file
2009-12-15-11-00
■　eqn.6.16 physics dimension consistency check
Whether eqn.6.16 is reasonable
  in terms of physics dimension
  consistency check?
Answer is OK, consistency correct.

<a name="ch06b129">
pk sum to one, pk is probability, 
pk is a pure number, 
eqn.6.16 left side 
pkf(xk) - f(pkxk)
both have f(x) dimension.

<a name="ch06b130">
eqn.6.16 right side pj and pk are 
both pure number.
μ and xk2 cary physics dimension.
What is μ? Problem given μ∈[m,M]
so, μ and m and M have same physics
dimension. Then what is M,m?

<a name="ch06b131">
eqn.6.15
  0≦m≦f''(x)≦M ---eqn.6.15
tell us that m and f''(x) and M
have same physics dimension.
Finally link to f(x).

<a name="ch06b132">
Assume x is time
Assume f(x) is distance
then f'(x) = d[f(x)]/dx is velocity
and f''(x) =dd[f(x)]/dx/dx is acceleration
Under above assumption, μ and m and M 
all have acceleration physics dimension.

<a name="ch06b133">
μ * xk2 is 
acceleration * time * time
get f(x) physics dimension distance
again.

μ * xk2 has same physics dimension
as pkf(xk) - f(pkxk)

<a name="ch06b134">　Index begin　Index this file
Here conclude YES,
eqn.6.16 IS reasonable
  in terms of physics dimension
  consistency check !
2009-12-15-11-13

2009-12-15-13-00
2009-12-16-13-00
twenty four hours break away from computer.

2009-12-16-20-12 done proofread
2009-12-17-12-27 done update all tute*.htm
2009-12-17-16-55 done spelling check

<a name=20091217>
2009-12-17-11-09 start
Upload 2009-12-17 change all tute*.htm
(from tute0007.htm to tute0023.htm)
first:
Correct 'Limit' link from '#docA06'
to '#docA006'
second:
Change Javascript index to read from
jslist1e.js so that update jslist1e.js
then update ALL tute*.htm.
2009-12-17-11-23 stop

<a name=20091222>
2009-12-22-10-47 start
Update 2009-12-22 add
<a name="ch06b015">
■　Jensen's Inequality key points
2009-12-22-10-48 stop

<a name="Copyright">　Index begin　Index this file
2009-06-19-10-48
If you are interested in inequality,
suggest you buy the book
The Cauchy-Schwarz Master Class
written by Prof. J. Michael Steele
The Cauchy-Schwarz Master Class is
this web page's textbook.

To buy textbook, that is to show thanks
to Prof. J.M. Steele's great work.
and it is also respect copyright law.
Thank you. Freeman 2009-06-19

The Cauchy-Schwarz Master Class
J. Michael Steele ★★★★★
ISBN 978-0-521-54677-5
2009-06-19-10-56