Problem 1. The monotone nonnegative cone. We define the monotone nonnegative cone as $$K_{\mathrm{m}+}=\left\{x \in \mathbf{R}^{n} \mid x_{1} \geq x_{2} \geq \cdots \geq x_{n} \geq 0\right\}$$ i.e., all nonnegative vectors with components sorted in nonincreasing order. (a) Show that $K_{\mathrm{m}+}$ is a proper cone. (b) Find the dual cone $K_{\mathrm{m}+}^{*} .$ Hint. Use the identity \begin{aligned} \sum_{i=1}^{n} x_{i} y_{i}=&\left(x_{1}-x_{2}\right) y_{1}+\left(x_{2}-x_{3}\right)\left(y_{1}+y_{2}\right)+\left(x_{3}-x_{4}\right)\left(y_{1}+y_{2}+y_{3}\right)+\cdots \\ &+\left(x_{n-1}-x_{n}\right)\left(y_{1}+\cdots+y_{n-1}\right)+x_{n}\left(y_{1}+\cdots+y_{n}\right) \end{aligned}
Proof . (a) The set $K_{\mathrm{m}+}$ is defined by $n$ homogeneous linear inequalities, hence it is a closed (polyhedral) cone. The interior of $K_{\mathrm{m}+}$ is nonempty, because there are points that satisfy the inequalities with strict inequality, for example, $x=(n, n-1, n-2, \ldots, 1)$. To show that $K_{\mathrm{m}+}$ is pointed, we note that if $x \in K_{\mathrm{m}+},$ then $-x \in K_{\mathrm{m}+}$ only if $x=0 .$ This implies that the cone does not contain an entire line. (b) Using the hint, we see that $y^{T} x \geq 0$ for all $x \in K_{\mathrm{m}+}$ if and only if $$y_{1} \geq 0, \quad y_{1}+y_{2} \geq 0, \quad \ldots, y_{1}+y_{2}+\cdots+y_{n} \geq 0$$ Therefore $$K_{\mathrm{m}+}^{*}=\left\{y \mid \sum_{i=1}^{k} y_{i} \geq 0, k=1, \ldots, n\right\}$$
Problem 2. Copositive matrices. A matrix $X \in \mathbf{S}^{n}$ is called copositive if $z^{T} X z \geq 0$ for all $z \succeq 0$. Verify that the set of copositive matrices is a proper cone. Find its dual cone.
Proof . We denote by $K$ the set of copositive matrices in $\mathbf{S}^{n} . K$ is a closed convex cone because it is the intersection of (infinitely many) halfspaces defined by homogeneous inequalities $$z^{T} X z=\sum_{i, j} z_{i} z_{j} X_{i j} \geq 0$$ $K$ has nonempty interior, because it includes the cone of positive semidefinite matrices, which has nonempty interior. $K$ is pointed because $X \in K,-X \in K$ means $z^{T} X z=0$ for all $z \succeq 0,$ hence $X=0$. By definition, the dual cone of a cone $K$ is the set of normal vectors of all homogeneous halfspaces containing $K$ (plus the origin). Therefore, $$K^{*}=\operatorname{conv}\left\{z z^{T} \mid z \succeq 0\right\} .$$
Problem 3. Second-order conditions for convexity on an affine set. Let $F \in \mathbf{R}^{n \times m}, \hat{x} \in \mathbf{R}^{n}$. The restriction of $f: \mathbf{R}^{n} \rightarrow \mathbf{R}$ to the affine set $\left\{F z+\hat{x} \mid z \in \mathbf{R}^{m}\right\}$ is defined as the function $\tilde{f}: \mathbf{R}^{m} \rightarrow \mathbf{R}$ with $$\tilde{f}(z)=f(F z+\hat{x}), \quad \operatorname{dom} \tilde{f}=\{z \mid F z+\hat{x} \in \operatorname{dom} f\}$$ Suppose $f$ is twice differentiable with a convex domain. (a) Show that $\tilde{f}$ is convex if and only if for all $z \in \operatorname{dom} \tilde{f}$ $$F^{T} \nabla^{2} f(F z+\hat{x}) F \succeq 0$$ (b) Suppose $A \in \mathbf{R}^{p \times n}$ is a matrix whose nullspace is equal to the range of $F,$ i.e., $A F=0$ and $\operatorname{rank} A=n-\operatorname{rank} F .$ Show that $\tilde{f}$ is convex if and only if for all $z \in \operatorname{dom} \tilde{f}$ there exists a $\lambda \in \mathbf{R}$ such that $$\nabla^{2} f(F z+\hat{x})+\lambda A^{T} A \succeq 0$$ Hint. Use the following result: If $B \in \mathbf{S}^{n}$ and $A \in \mathbf{R}^{p \times n}$, then $x^{T} B x \geq 0$ for all $x \in \mathcal{N}(A)$ if and only if there exists a $\lambda$ such that $B+\lambda A^{\dot{T}} A \succeq 0$
Proof . (a) The Hessian of $\tilde{f}$ must be positive semidefinite everywhere: $$\nabla^{2} \tilde{f}(z)=F^{T} \nabla^{2} f(F z+\hat{x}) F \succeq 0$$ (b) The condition in (a) means that $v^{T} \nabla^{2} f(F z+\hat{x}) v \geq 0$ for all $v$ with $A v=0,$ i.e., $$v^{T} A^{T} A v=0 \Longrightarrow v^{T} \nabla^{2} f(F z+\hat{x}) v \geq 0$$ The result immediately follows from the hint.
Problem 4. Suppose $f: \mathbf{R}^{n} \rightarrow \mathbf{R}$ is convex, $g: \mathbf{R}^{n} \rightarrow \mathbf{R}$ is concave, $\operatorname{dom} f=\operatorname{dom} g=\mathbf{R}^{n},$ and for all $x, g(x) \leq f(x)$. Show that there exists an affine function $h$ such that for all $x$, $g(x) \leq h(x) \leq f(x)$. In other words, if a concave function $g$ is an underestimator of a convex function $f$, then we can fit an affine function between $f$ and $g$.
Proof . Solution. We first note that int epi $f$ is nonempty (since $\operatorname{dom} f=\mathbf{R}^{n}$ ), and does not intersect hypo $g$ (since $f(x)<t$ for $(x, t) \in$ int epi $f$ and $t \geq g(x)$ for $(x, t) \in$ hypo $g$ ). The two sets can therefore be separated by a hyperplane, i.e., there exist $a \in \mathbf{R}^{n}, b \in \mathbf{R}$ not both zero, and $c \in \mathbf{R}$ such that $$a^{T} x+b t \geq c \geq a^{T} y+b v$$ if $t>f(x)$ and $v \leq g(y)$. We must have $b \neq 0$, since otherwise the condition would reduce to $a^{T} x \geq a^{T} y$ for all $x$ and $y,$ which is only possible if $a=0$. Choosing $x=y$, and using the fact that $f(x) \geq g(x)$, we also see that $b>0$. Now we apply the separating hyperplane conditions to a point $(x, t) \in$ int epi $f,$ and $(y, v)=(x, g(x)) \in$ hypo $g,$ and obtain $$a^{T} x+b t \geq c \geq a^{T} x+b g(x)$$ and dividing by $b$, $$t \geq\left(c-a^{T} x\right) / b \geq g(x)$$ for all $t>f(x)$. Therefore the affine function $h(x)=\left(c-a^{T} x\right) / b$ lies between $f$ and $g$.

E-mail: [email protected]  微信:shuxuejun

uprivate™是一个服务全球中国留学生的专业代写公司 专注提供稳定可靠的北美、澳洲、英国代写服务 专注于数学，统计，金融，经济，计算机科学，物理的作业代写服务