About yuliy

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
Read full story Comments { 0 }

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 …

Read full story Comments { 20 }

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
Read full story Comments { 2 }

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}\).

      Answer:
      \[
      \check{f}(p)=p^2/2-1/2
Read full story Comments { 12 }

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
Read full story Comments { 10 }

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 …

Read full story Comments { 0 }

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?
Read full story Comments { 4 }

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}}
\)

Quadratic forms

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 …

Read full story Comments { 4 }

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 …

Read full story Comments { 16 }

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), …

Read full story Comments { 0 }