Optimization – Page 3 – Applied Probability Notes

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”

Congestion Control

We argue, in a slightly informal manner, that queueing networks implicitly optimize a utility function subject to constraints on network capacity. We start with the simple example of a closed queueing network and, as we shall discuss, a motivating example is the Transmission Control Protocol which controls the number of packets in transfer on an Internet connection.

Continue reading “Congestion Control”

Gale-Eisenberg Market

The Gale-Eisenberg is a nice example were the distributed decisions of buyers and sellers have an equilibrium which solves an optimization problem.

Continue reading “Gale-Eisenberg Market”