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.
No comments yet.

Leave a Reply