Author Archive | yuliy

## week 11

$$\def\Real{\mathbb{R}} \def\Comp{\mathbb{C}} \def\Rat{\mathbb{Q}} \def\Field{\mathbb{F}} \def\Fun{\mathbf{Fun}} \def\e{\mathbf{e}} \def\f{\mathbf{f}} \def\bv{\mathbf{v}}$$

Gradient descent methods. Step size choices. Backtracking rule.

Newton algorithm. Solving systems of nonlinear equations. Quadratic convergence,

#### Sample problems

• Compute first 5 iterations $$x_0=2,x_1,\ldots, x_5$$ of Newton method to solve

## programming exercise 2

$$\def\Real{\mathbb{R}} \def\Comp{\mathbb{C}} \def\Rat{\mathbb{Q}} \def\Field{\mathbb{F}} \def\Fun{\mathbf{Fun}} \def\e{\mathbf{e}} \def\f{\mathbf{f}} \def\bv{\mathbf{v}}$$

Set $$d=18$$.

Consider the $$d\times d$$ matrix
$C=\left(c_{ij}\right)_{i,j}$
where
$c_{ij}=a_{ij}+n_i-n_j.$
The base matrix of coefficients $$a_{ij}, 1\leq i,j\leq d$$ is given here; the modifier $$n_j$$ is …

## week 10

$$\def\Real{\mathbb{R}} \def\Comp{\mathbb{C}} \def\Rat{\mathbb{Q}} \def\Field{\mathbb{F}} \def\Fun{\mathbf{Fun}} \def\e{\mathbf{e}} \def\f{\mathbf{f}} \def\bv{\mathbf{v}}$$

#### Simplex method

Tableau, pivot step, pivot rules. Exceptions. Phase one (finding a feasible point).

#### Sample problem

1. For which $$h$$ the following system is feasible?
$\begin{array}{ccc} &y&\leq 0\\ x&&\geq 0\\ x&-y&\leq ## mock midterm 2 $$\def\Real{\mathbb{R}} \def\Comp{\mathbb{C}} \def\Rat{\mathbb{Q}} \def\Field{\mathbb{F}}$$ #### Sample problems 1. Find Fenchel dual (conjugate, or $$\check{f}(p):=\sup_x px-f(x)$$) for 1. $$f(x)=|x-1|+x/2$$; Answer: \[ \check{f}(p)=p-1/2 \mathrm{\ if}\ -1/2\leq p\leq 3/2; +\infty \mathrm{\ otherwise}.$
2. f$$(x)=x^2/2+1/2 \ \mathrm{for} \ |x|\leq 1; |x| \ \mathrm{otherwise}$$.

\[
\check{f}(p)=p^2/2-1/2

## week 9

$$\def\Real{\mathbb{R}} \def\Comp{\mathbb{C}} \def\Rat{\mathbb{Q}} \def\Field{\mathbb{F}} \def\Fun{\mathbf{Fun}} \def\e{\mathbf{e}} \def\f{\mathbf{f}} \def\bv{\mathbf{v}}$$

#### Linear Proramming

Barvinok, 4.

Convex closed cones, their polars.

General LP problems. Dual problems for general LP.

Polyhedral cones, strong duality.

#### Sample problems

1. Let $$K=\Real_+^3$$ be the cone of vectors with

## week 8

$$\def\Real{\mathbb{R}} \def\Comp{\mathbb{C}} \def\Rat{\mathbb{Q}} \def\Field{\mathbb{F}} \def\Fun{\mathbf{Fun}} \def\e{\mathbf{e}} \def\f{\mathbf{f}} \def\bv{\mathbf{v}}$$

#### Convex optimization

Lange, ch.5.

Convex programs. Convexity of the set of optima.

Constraint qualification: Slater condition.

#### Duality

Boyd-Vandenberghe, 5.1-3,5.6.

Lagrange dual functions. Dual optimization problems. Fenchel duals (conjugate) functions.

Weak duality …

## week 7

$$\def\Real{\mathbb{R}} \def\Comp{\mathbb{C}} \def\Rat{\mathbb{Q}} \def\Field{\mathbb{F}} \def\Fun{\mathbf{Fun}} \def\e{\mathbf{e}} \def\f{\mathbf{f}} \def\bv{\mathbf{v}}$$

#### Convexity

Convex sets. Convex hulls. Supporting hyperplanes.

Convex functions; properties. Log-convex functions.

#### Sample problems

1. Is the set of continuous functions on $$\Real^2$$ positive at all points with rational coordinates numbers convex?

## weeks 5 and 6

$$\def\Real{\mathbb{R}} \def\Comp{\mathbb{C}} \def\Rat{\mathbb{Q}} \def\Field{\mathbb{F}} \def\Fun{\mathbf{Fun}} \def\e{\mathbf{e}} \def\f{\mathbf{f}} \def\bv{\mathbf{v}}$$

Positive definite quadratic forms. Signatures, and relations between the indices of inertia of the (that is the number $$n_+$$ of positive, $$n_-$$ negative and $$n_0$$ ,zero coefficients in the …

## programming exercise 1.

$$\def\Real{\mathbb{R}} \def\Comp{\mathbb{C}} \def\Rat{\mathbb{Q}} \def\Field{\mathbb{F}} \def\Fun{\mathbf{Fun}} \def\e{\mathbf{e}} \def\f{\mathbf{f}} \def\bv{\mathbf{v}}$$

Use any language or library. The assignments are due by midnight of 3.14 (Monday).

#### 3 credits students

Consider the piecewise linear function $$f$$ on $$[-4,4]$$
with nodes at the integer …

## Topologically constrained models of statistical physics.

$$\def\Real{\mathbb{R}} \def\Int{\mathbb{Z}} \def\Comp{\mathbb{C}} \def\Rat{\mathbb{Q}} \def\Field{\mathbb{F}} \def\Fun{\mathbf{Fun}} \def\e{\mathbf{e}} \def\f{\mathbf{f}} \def\bv{\mathbf{v}} \def\blob{\mathcal{B}}$$

### The Blob

Consider the following planar “spin model”: the state of the system is a function from $$\Int^2$$ into $$\{0,1\}$$ (on and off states). We interpret the site \((i,j), …