TU/e EE Notes

Math II - 5EMA0

11 min read

5EMA0 Math II (Optimization and Probability)

Optimizations and Probabilities

Unconstrained optimization
Linear optimization
Convex optimization
Language duality theory

Probabilities
Discrete random variables
Continuous random variables
Pairs and sum of random variables

Unconstrained Optimization


If then → only for convex

Convex Lemma

convex:
for all and all
if then function is convex

affine: (=) instead of () and
f is affine ←> both f and -f are convex

Linear Optimization

Farkas Lemma

One of the following is true
for and for -⇒ feasable solution
, , for -⇒ no feasable solution

Fredholm Alternative Lemma

One of the following is true, special case
for
,

Farkas Extension Lemma

We have for all such that for ⇐> there are so that:
, , and for

Linear Optimization Duality Theorem

Then
for
and for
maximization problem feasable and bounded

Algebraic Formulation:

Duality is the principle that optimization problems may be viewed from either of two perspectives, the primal problem or the dual problem. If the primal is a minimization problem then the dual is a maximization problem (and vice versa).

Any feasible solution to the primal (minimization) problem is at least as large as any feasible solution to the dual (maximization) problem. Therefore, the solution to the primal is an upper bound to the solution of the dual, and the solution of the dual is a lower bound to the solution of the primal. This fact is called weak duality.

Convex Penalty Function:

Lemmas in Dual Analysis

The minimum will not decrease as long the constraints for remain unchanged; even if the constraints for are removed.

If is an optimal solution, then for all .

If are both feasable, then both are optimal.


Convex Optimization


Convex Lemma

If is convex with domain , then is a convex set.

(First-order condition): is convex if and only if:
for all

If is differentiable and convex, then:
if and only if

(Second-order condition): Suppose is twice differentiable with domain . Then is convex ⇐> is convex and for all

Convex Theorem Primary

If are convex, then the function given by:

for all , is convex.

If are convex, then the function given by:

for all , is convex.

If is convex and , then the function given by:

for all , is convex.

If is convex, A is an matrix and , then the function given by:

for all , is convex.

Let and for each let be given by:
for all

Convex Functions Theorem

is NOT convex if and only if there are so that is not convex.

(First-order condition): Let be differentiable. Then is convex if and only if:
for all

Corollary:
Suppose is convex and differentiable, Then:
⇐>

(Second-order condition): Let be twice differentiable, domain Then is convex ⇐>

  1. is a convex set
  2. for all


Lemma Weak Langrange Duality

for

Lagrange Duality Theorem

If are differentiable convex functions and there exists an such that for all , then: Weak Langrange Duality Lemma → provided that minimizaiton problem is attained.

Lagrange Duality Lemmas

Suppse that and If then:
for all sufficiently small .

There is no such that:
and for .

There is a and a with so that:

  3. if then .

Suppose there exists a so that for . Then there is a , so that:

  3. if , then .

Suppose are convex functions. If is a KKT point of (8) with multipliers , then

Definition Karush-Kuhn-Tucker Point

is a KKT point of (8) if there is a and s.t.

  1. for and for
  4. if then
    The numbers and then are KKT multipliers for .

Definition Conjugate

For any function , the conjugate function is defined by:

for each

Lagrange Dual Conjugate Lemmas

The Lagrange dual of:

is

Suppose is convex and differentiable, and let . If , then


Convex Optimization Algorithm Lemmas

Let . If there is a with , then:
for some

How to find z: Newtonian Descent Direction
If is a twice differentiable convex function and is such that is an invertible matrix. Then:

has

Suppose are functions such that for all . Consider fixed such that . Let:
,

Then

Convex Optimization Algorithm Theorems

How to pick d:
Let be a differentiable function, let and . If:

thne for some .

Barrier Method Lemma

If are convex functions, then:

is a berrier function for (1).

For all we have → m is number of constraints.

Theorem: and coverage to optimal solutions as .

Probabilities

Topic: Probability and Random Variables

De Morgans law: ⇒ same for swapped operations
Disjoint:

Probability Axioms

A probability measure is a function that maps events in the sample space to real numbers such that:
Axiom 1: For any event
Axiom 2:
Axiom 3: For any countable collection of disjoint sets:

The probability measures satisfies


For any A and B (not necessarily disjoint):

If , then .

For any event A and partition

Conditional Probability Axioms


Axiom 1:
Axiom 2:
Axiom 3: If and for then:

Probability Theorems

Law of total probability:
For a partition with for all ,

Bayes’ theorem:

Events A and B are independent if and only if:
⇒ and

  • Disjoint events Independent Events

Sampling WITH/WITHOUT Replacement

WITHOUT: Binomial Coefficient:
WITH: Multinomial Coefficient:

Sampling with/without the ability to select an observation more than once.

Independent Trials

Subexperiment probability of success: , probability of failure
Probability of failures and successes

Discrete Random Variables

Topic: Probability and Random Variables

WHEN WHICH:

  • Bernoulli: A random event that results in a success or a failure.
  • Binomial: Number of trials (n) and the probability of success (p), counting amount of (x) successes.
  • Geometric: Counts independent Bernoulli trials (1-p) until a success (p) occurs.
  • Pascal: Until (k) successes, (x) number of trials required.
  • Poisson: Counts the number times event occurs in a given unit of distance. It has one parameter, (a) the mean number of occurrences per specified unit.
  • Uniform: When all outcomes of a random variable have equal probability within a specified range.

Probability Mass Function (PMF)

Properties:
For any

For any event the probability that is in the set is equal to:

Cumulative Distribution Function (CDF)

Properties:
and
for all
for and an arbitrary small positive number:

for all such that

Expectation (MEAN), Variance, Standard Deviation

or

n-th moment:
n-th central moment:


Continuous Random Variables

Topic: Probability and Random Variables

Probability Density Function (PDF)

Properties:
for all

Expectation (MEAN), Variance


or




  • Cumulative Distribution Function (CDF): Integral of PDF.
  • CDF is obtained same way as in Discrete Random Variables.

Standard Normal Random Variable


Delta Function

sifting property:

For a discrete with range we have:

generalized PDF:

Summary

Pairs of Random Variables

Topic: Probability and Random Variables

Joint CDF


Joint PMF


Joint PDF


Marginal

PMF ⇒ ⇒ ⇒ similar for Y
PDF ⇒ ⇒ ⇒ similar for Y

Expectation & Variance

Expectation →
Discrete: ⇒
Continuous: ⇒

Variance

Correlation

always between → negative/positive correlation

Independent Random Variables

Discrete: ⇒
Continuous: ⇒


  • There can be in general more than 2 variables considered in a probability, below is an example and it applies for continuous in same format:

Conditional Probability Models

Conditional PMF/PDF

PMF:
if else

PDF:
if else

Conditioning by Event/Random Variable

Event:
if else
if else


Random Variable:


Conditioning of Independent Random Variables

or
for all

MGF & Sums of Random Variables

Moment Generating Function (MGF)

Purpose → Calculate Moments Through Deriviation

Sum of Random Variables

Expectation

Variance

uncorrelated:
PDF

independent: → Convolution of PDF of X and the PDF of Y.
MGF
independent:

Central Limit Theorem




Cumulative distribution function of a standard normal Gaussian(0,1) Random Variable.

&

Edit this page on GitHub · History

Graph View

Backlinks