Optimization – Page 2 – Applied Probability Notes

Optimal Stopping

Optimal Stopping Problems; One-Step-Look-Ahead Rule
The Secretary Problem.
Infinite Time Stopping

Continue reading “Optimal Stopping”

Algorithms for MDPs

High level idea: Policy Improvement and Policy Evaluation.
Value Iteration; Policy Iteration.
Temporal Differences; Q-factors.

Continue reading “Algorithms for MDPs”

Infinite Time Horizon, MDP

Positive Programming, Negative Programming & Discounted Programming.
Optimality Conditions.

Continue reading “Infinite Time Horizon, MDP”

Lagrangian Optimization

We are interested in solving the constrained optimization problem

Continue reading “Lagrangian Optimization”

Talagrand’s Concentration Inequality

We prove a powerful inequality which provides very tight gaussian tail bounds “ $e^{-ct^2}$ ” for probabilities on product state spaces $\Omega^n$ . Talagrand’s Inequality has found lots of applications in probability and combinatorial optimization and, if one can apply it, it generally outperforms inequalities like Azzuma-Hoeffding.

Continue reading “Talagrand’s Concentration Inequality”

Spitzer’s Lyapunov Ergodicity

We show that relative entropy decreases for continuous time Markov chains.

Continue reading “Spitzer’s Lyapunov Ergodicity”

Cross Entropy Method

In the Cross Entropy Method, we wish to estimate the likelihood

$l = {\mathbb P} ( S(X) \geq \gamma ).$

Here $X$ is a random variable whose distribution is known and belongs to a parametrized family of densities $f( , v)$ . Further $S(X)$ is often a solution to an optimization problem.

Continue reading “Cross Entropy Method”

Online Convex Optimization

We consider the setting of sequentially optimizing the average of a sequence of functions, so called online convex optimization.

Continue reading “Online Convex Optimization”

Gradient Descent

We consider one of the simplest iterative procedures for solving the (unconstrainted) optimization

Continue reading “Gradient Descent”

A Network Decomposition

We consider a decomposition of the following network utility optimization problem

SYS:

$\begin{aligned} &\text{maximize} \quad & \sum_{r\in{\mathcal R}} U_r(\Lambda_r) \\ &\text{subject to} &\quad \sum_{r: j\in r} \Lambda_r \leq C_j, \quad j\in{\mathcal J}, \\ &\text{over} &\quad \Lambda_r\geq 0,\quad r\in{\mathcal R}.%\tag{{SYS}{\mathcal R}} \end{aligned}$

Continue reading “A Network Decomposition”