week 8


Convex optimization

Lange, ch.5.

Convex programs. Convexity of the set of optima.

Constraint qualification: Slater condition.


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:

    • \[

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

    • \[

      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
    ax+by\to\min,\ \mathrm{subject\ to} \\x^2+y^2\leq 1; \\x\leq 0.

    • 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