Conjugate sets

Conjugate sets

  1. Prove that S^* = \left(\overline{S}\right)^*

  2. Prove that \left( \mathbf{conv}(S) \right)^* = S^*

  3. Prove that if B(0,r) is a ball of radius r at some norm with the center in zero, then \left( B(0,r) \right)^* = B(0,1/r)

  4. Find a dual cone for a monotonous non-negative cone:

    K = \{ x \in \mathbb{R}^n \mid x_1 \ge x_2 \ge \ldots \ge x_n \ge 0\}

  5. Find and sketch on the plane a conjugate set to a multi-faceted cone: S = \mathbf{cone} \{ (-3,1), (2,3), (4,5)\}

  6. Derive the definition of the cone from the definition of the conjugate set.

  7. Name any 3 non-trivial facts about conjugate sets.

  8. How to write down a set conjugate to the polyhedron?

  9. Draw a conjugate set by hand for simple sets. Conjugate to zero, conjugate to the halfline, to two random points, to their convex hull, etc.

  10. Give examples of self-conjugate sets.

  11. Using a lemma about a cone conjugate, conjugate to the sum of cones and a lemma about a cone, conjugate to the intersection of closed convex cones, prove that cones

    K_1 = \{x \in \mathbb{R}^n \mid x = Ay, y \ge 0, y \in \mathbb{R}^m, A \in \mathbb{R}^{n \times}, \}, \;\; K_2 = \{p \in \mathbb{R}^n \mid A^Tp \ge 0\}

    are inter conjugated.

  12. Find the sets S^{*}, S^{**}, S^{***}, if

    S = \{ x \in \mathbb{R}^2 \mid x_1 + x_2 \ge 0, \;\; 2x_1 + x_2 \ge -4, \;\; -2x_1 + x_2 \ge -4\}

  13. Find the sets S^{*}, S^{**}, S^{***}, if

    S = \{ x \in \mathbb{R}^2 \mid x_1 + x_2 \ge -1, \;\; 2x_1 - x_2 \ge 0, \;\; -x_1 + 2x_2 \ge -2\}

  14. Find conjugate cone for the cone of positive definite (semi-definite) matrices.

  15. Find the conjugate cone for the exponential cone:

    K = \{(x, y, z) \mid y > 0, y e^{x/y} \leq z\}

  16. Prove that’s fair for closed convex cones:

    (K_1 \cap K_2)^* = K_1^* + K_2^*

  17. Find the dual cone for the following cones:

    • K = \{0\}
    • K = \mathbb{R}^2
    • K = \{(x_1, x_2) \mid \vert x_1\vert \leq x_2\}
    • K = \{(x_1, x_2) \mid x_1 + x_2 = 0\}
  18. Find and sketch on the plane a conjugate set to a multifaced cone:

    S = \mathbf{conv} \left\{ (-4,-1), (-2,-1), (-2,1)\right\} + \mathbf{cone} \left\{ (1,0), (2,1)\right\}

  19. Find and sketch on the plane a conjugate set to a polyhedra:

    S = \left\{ x \in \mathbb{R}^2 \mid -3x_1 + 2x_2 \le 7, x_1 + 5x_2 \le 9, x_1 - x_2 \le 3, -x_2 \le 1\right\}

  20. Prove that if we define the conjugate set to S as follows:

    S^* = \{y \ \in \mathbb{R}^n \mid \langle y, x\rangle \le 1 \;\; \forall x \in S\},

    then unit ball with the zero point as the center is the only self conjugate set in \mathbb{R}^n.

  21. Find the conjugate set to the ellipsoid:

    S = \left\{ x \in \mathbb{R}^n \mid \sum\limits_{i = 1}^n a_i^2 x_i^2 \le \varepsilon^2 \right\}

  22. Let L be the subspace of a Euclidian space X. Prove that L^* = L^\bot, where L^\bot - orthogonal complement to L.

  23. Let \mathbb{A}_n be the set of all n dimensional antisymmetric matrices. Show that \left( \mathbb{A}_n\right)^* = \mathbb{S}_n.

  24. Prove, that B_p and B_{p_*} are inter-conjugate, i.e. (B_p)^* = B_{p_*}, (B_{p_*})^* = B_p, where B_p is the unit ball (w.r.t. p - norm) and p, p_* are conjugated, i.e. p^{-1} + p^{-1}_* = 1. You can assume, that p_* = \infty if p = 1 and vice versa.

  25. Prove, that K_p and K_{p_*} are inter-conjugate, i.e. (K_p)^* = K_{p_*}, (K_{p_*})^* = K_p, where K_p = \left\{ [x, \mu] \in \mathbb{R}^{n+1} : \|x\|_p \leq \mu \right\}, \; 1 < p < \infty is the norm cone (w.r.t. p - norm) and p, p_* are conjugated, i.e. p^{-1} + p^{-1}_* = 1. You can assume, that p_* = \infty if p = 1 and vice versa.

  26. Suppose, S = S^*. Could the set S be anything, but a unit ball? If it can, provide an example of another self-conjugate set. If it couldn’t, prove it.

  27. Let \mathbb{A}_n be the set of all n dimensional antisymmetric matrices (s.t. X^T = - X). Show that \left( \mathbb{A}_n\right)^* = \mathbb{S}_n.

  28. Find the sets S^{\star}, S^{\star\star}, S^{\star\star\star}, if

    S = \{ x \in \mathbb{R}^2 \mid x_1 + x_2 \ge 0, \;\; -\dfrac12x_1 + x_2 \ge 0, \;\; 2x_1 + x_2 \ge -1 \;\; -2x_1 + x_2 \ge -3\}

  29. Prove, that B_p and B_{p_\star} are inter-conjugate, i.e. (B_p)^\star = B_{p_\star}, (B_{p_\star})^\star = B_p, where B_p is the unit ball (w.r.t. p - norm) and p, p_\star are conjugated, i.e. p^{-1} + p^{-1}\_\star = 1. You can assume, that p_\star = \infty if p = 1 and vice versa.