# Archive | ece490

## mock final

Here. (Disregard the points for the problems.)final_mock

## week 14

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

#### Dynamic programming

Finite horizon problems. Cost function. Backward induction. Idempotent rings.

(Use Blum’s notes.)

#### Sample problems

• If erasing a digit costs 2 cents, and correcting, 3 cents, what is the

## week 13

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

#### Interior point methods

Logarithmic barriers. Central path. Convergence and quality of solution estimates from duality. (Boyd, chapt.11).

#### Ellipsoid method

(Use Boyd’s notes).

#### Sample problems

• Find the central path for the

## week 12

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

Material:Guler, ch. 14.7-9

Conjugate directions. Gram-Schmidt algorithm. Conjugate directions algorithm. Performance estimates via spectral data.

#### Sample problems

• Consider the 4-dimensional space spanned by the polynomials
$p(x)=ax^3+bx^2+cx+d ## 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 …