# 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 for general convex programs. Strong duality.

#### Sample problems

1. Find Fenchel conjugate function for the following functions:

• $f(x)=\ln({e^x+e^{-x}});$

Answer: $$-1/2((1-p)\ln(1+p)+(1+p)\ln(1-p))-\ln2$$.

• $f(x)=|x-1|+|x+1|;$

Answer: $$|p|-2$$ for $$-2\leq p\leq 2$$; $$+\infty$$ elsewhere.
• $f(x)=x^2\ \mathrm{for}\ |x|\leq 1; +\infty \ \mathrm{otherwise}.$

Answer: $$p^2/4$$ for $$-2\leq p\leq 2$$; $$|p|$$ elsewhere.
2. Consider the problem
$\begin{array}{c} ax+by\to\min,\ \mathrm{subject\ to} \\x^2+y^2\leq 1; \\x\leq 0. \end{array}$

• Is it convex?
• Solve it. (Consider $$a,b$$ as unknown parameters; the solutions of the primal and dual problems depend on these parameters.)
• Formulate the dual problem and solve it.