# 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.