3.7.1. Warm-up worksheets#

(with help from Claude, Gemini, and ChatGPT)

Section 3.2

E3.2.1 Calculate the gradient of the function $f(x_1,x_2)=3x_1^2-2x_1{x}_2+4x_2^2-5x_1+2x_2$ at the point $(1,-1)$.

E3.2.2 Find the Hessian matrix of the function $f(x_1,x_2,x_3)=2x_1{x}_2+3x_2{x}_3-x_1^2-4x_3^2$.

E3.2.3 Compute the partial derivatives $\frac{\partial f}{\partial x_1}$ and $\frac{\partial f}{\partial x_2}$ for the function $f(x_1,x_2)=\sin (x_1)\cos (x_2)$ at the point $(\frac{\pi }{4},\frac{\pi }{3})$.

E3.2.4 Let $f(x_1,x_2)=e^{x_1}+x_1{x}_2-x_2^2$ and $g(t)=(t^2,t)$. Calculate $(f\circ g{)}^{\prime }(1)$ using the Chain Rule.

E3.2.5 Verify the Symmetry of the Hessian for the function $f(x_1,x_2)=x_1^3+3x_1{x}_2^2-2x_2^3$ at the point $(1,2)$.

E3.2.6 Find the gradient of the function $f(x_1,x_2,x_3)=2x_1-3x_2+4x_3$ at the point $(1,-2,3)$.

E3.2.7 Calculate the second-order partial derivatives of the function $f(x_1,x_2)=x_1^2\sin (x_2)$.

E3.2.8 Compute the gradient of the quadratic function $f(x_1,x_2)=3x_1^2+2x_1{x}_2-x_2^2+4x_1-2x_2$ at the point $(1,-1)$.

E3.2.9 Find the Hessian matrix of the function $f(x_1,x_2,x_3)=x_1^2+2x_2^2+3x_3^2-2x_1{x}_2+4x_1{x}_3-6x_2{x}_3$.

E3.2.10 Apply the multivariable Mean Value Theorem to the function $f(x_1,x_2)=x_1^2+x_2^2$ on the line segment joining the points $(0,0)$ and $(1,2)$.

E3.2.11 Find the partial derivatives $\frac{\partial f}{\partial x}$ and $\frac{\partial f}{\partial y}$ of the function $f(x,y)=x^3{y}^2-2x{y}^3+y^4$.

E3.2.12 Compute the gradient $\mathrm{\nabla }f(x,y)$ of the function $f(x,y)=\ln (x^2+2y^2)$ at the point $(1,2)$.

E3.2.13 Find the Hessian matrix of the function $g(x,y)=\sin (x)\cos (y)$.

E3.2.14 If $p(x,y,z)=x^{2}yz+3xy{z}^2$, find all second partial derivatives of $p$.

E3.2.15 Verify that the function $q(x,y)=x^3-3x{y}^2$ satisfies Laplace’s equation: $\frac{{\partial }^{2}q}{\partial x^2}+\frac{{\partial }^{2}q}{\partial y^2}=0$.

E3.2.16 Consider the function $s(x,y)=x^2+4xy+5y^2$. Use the Mean Value Theorem to approximate $s(1.1,0.9)$ using the point $(1,1)$.

E3.2.17 A particle moves along a path given by $c(t)=(t^2,t^3)$. The temperature at a point $(x,y)$ is given by $u(x,y)=e^{-x^2-y^2}$. Find the rate of change of the temperature experienced by the particle at time $t=1$.

E3.2.18 Apply the Chain Rule to find $\frac{d}{dt}f(g(t))$ for $f(x,y)=x^2+y^2$ and $g(t)=(t,\sin t)$.

E3.2.19 Use the Chain Rule to find $\frac{d}{dt}f(g(t))$ for $f(x,y)=xy$ and $g(t)=(t^2,\cos t)$.

Section 3.3

E3.3.1 Consider the function $f(x_1,x_2)=x_1^2+2x_2^2$. Find all points $(x_1,x_2)$ where $\mathrm{\nabla }f(x_1,x_2)=0$.

E3.3.2 Let $f(x_1,x_2)=x_1^2-x_2^2$. Find the directional derivative of $f$ at the point $(1,1)$ in the direction $v=(\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}})$.

E3.3.3 Consider the function $f(x_1,x_2)=x_1^2+2x_1{x}_2+x_2^2$. Find the second directional derivative of $f$ at the point $(1,1)$ in the direction $v=(\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}})$.

E3.3.4 Consider the optimization problem $\underset{x_1,x_2}{min}{x}_1^2+x_2^2$ subject to $x_1+x_2=1$. Write down the Lagrangian function $L(x_1,x_2,\lambda )$.

E3.3.5 For the optimization problem in E3.3.4, find all points $(x_1,x_2,\lambda )$ satisfying the first-order necessary conditions.

E3.3.6 For the optimization problem in E3.3.4, check the second-order sufficient conditions at the point $(\frac{1}{2},\frac{1}{2},-1)$.

E3.3.7 Consider the function $f(x_1,x_2,x_3)=x_1^2+x_2^2+x_3^2$. Find all points $(x_1,x_2,x_3)$ satisfying the first-order necessary conditions for the optimization problem $\underset{x_1,x_2,x_3}{min}f(x_1,x_2,x_3)$ subject to $x_1+2x_2+3x_3=6$.

E3.3.8 For the optimization problem in E3.3.7, check the second-order sufficient conditions at the point $(\frac{1}{2},1,\frac{3}{2},-1)$.

E3.3.9 Let $f:{\mathbb{R}}^2\to \mathbb{R}$ be defined by $f(x_1,x_2)=x_1^3-3x_1{x}_2^2$. Determine whether the vector $v=(1,1)$ is a descent direction for $f$ at the point $(1,0)$.

E3.3.10 Let $f:{\mathbb{R}}^2\to \mathbb{R}$ be defined by $f(x_1,x_2)=x_1^2+x_2^2-2x_1-4x_2+5$. Find the Hessian matrix of $f$.

E3.3.11 Let $f:{\mathbb{R}}^2\to \mathbb{R}$ be defined by $f(x_1,x_2)=-x_1^2-x_2^2$. Compute the second directional derivative of $f$ at the point $(0,0)$ in the direction $v=(1,0)$.

E3.3.12 Calculate the directional derivative of $f(x,y)=x^2+y^2$ at the point $(1,1)$ in the direction of $\mathbf{v}=(1,1)$.

E3.3.13 Determine the Hessian matrix of $f(x,y)=x^3+y^3-3xy$ at the point $(1,1)$.

Section 3.4

E3.4.1 Find the convex combination of points $(2,3)$ and $(4,5)$ with $\alpha =0.3$.

E3.4.2 Determine whether the following set is convex:

E3.4.3 Let $S_1=\{x\in {\mathbb{R}}^2:x_1+x_2\le 1\}$ and $S_2=\{x\in {\mathbb{R}}^2:x_1-x_2\le 1\}$. Show that $S_1\cap S_2$ is a convex set.

E3.4.4 Verify that the function $f(x)=\log (e^{x_1}+e^{x_2})$ is convex using the Hessian matrix.

E3.4.5 Find the global minimizer of the function $f(x)=x^2+2x+1$.

E3.4.6 Consider the function $f(x)=|x|$. Show that $f$ is convex but not differentiable at $x=0$.

E3.4.7 Verify that the function $f(x)=x^2+2y^2$ is strongly convex with $m=2$.

E3.4.8 Find the projection of the point $x=(1,2)$ onto the set $D=\{(x_1,x_2)\in {\mathbb{R}}^2:x_1+x_2=1\}$.

E3.4.9 Let $f(x)=x^4-2x^2+1$. Determine whether $f$ is convex.

E3.4.10 Let $f(x)=e^x$. Determine whether $f$ is log-concave.

E3.4.11 Let $f(x)=x^2-2x+2$. Determine whether $f$ is strongly convex.

E3.4.12 Let $A=\left(\begin{array}{cc}1& 2\\ 2& 5\end{array}\right)$ and $b=\left(\begin{array}{c}1\\ 0\end{array}\right)$. Find the vector $x$ that minimizes $\Vert Ax-b{\Vert }_2^2$.

E3.4.13 Given the set $D=\{(x,y)\in {\mathbb{R}}^2:x^2+y^2<4\}$, determine if $D$ is convex.

E3.4.14 Determine if the set $D=\{(x,y)\in {\mathbb{R}}^2:x+y\le 1\}$ is convex.

E3.4.15 Determine if the set $D=\{(x,y)\in {\mathbb{R}}^2:x^2-y^2\le 1\}$ is convex.

Section 3.5

E3.5.1 Given the function $f(x,y)=x^2+4y^2$, find the direction of steepest descent at the point $(1,1)$.

E3.5.2 Consider the function $f(x)=x^2+4x+5$. Compute the gradient $\mathrm{\nabla }f(x)$ and find the direction of steepest descent at $x_0=1$.

E3.5.3 Given the function $f(x)=x^3-6x^2+9x+2$, perform two iterations of gradient descent starting from $x_0=0$ with a step size of $\alpha =0.1$.

E3.5.4 Let $f(x)=x^2$. Show that $f$ is $L$-smooth for some $L>0$.

E3.5.5 Let $f(x)=x^2$. Perform one step of gradient descent starting from $x_0=2$ with step size $\alpha =0.1$.

E3.5.6 Consider the $2$-smooth function $f(x)=x^2$. Starting from $x_0=3$, compute the point $x_1$ obtained after one iteration of gradient descent with step size $\alpha =\frac{1}{2}$.

E3.5.7 Verify that the function $f(x)=2x^2+1$ is $4$-strongly convex.

E3.5.8 For the $4$-strongly convex function $f(x)=2x^2+1$ with global minimizer $x^{\ast }=0$, compute $\frac{1}{2m}\Vert \mathrm{\nabla }f(1){\Vert }^2$ and compare it with $f(1)-f(x^{\ast })$.

E3.5.9 Let $f(x)=x^4$. Is $f$ $L$-smooth for some $L>0$? Justify your answer.

E3.5.10 Let $f(x)=x^3$. Is $f$ $m$-strongly convex for some $m>0$? Justify your answer.

E3.5.11 Let $f(x)=x^2+2x+1$. Show that $f$ is $m$-strongly convex for some $m>0$.

E3.5.12 Let $f(x)=x^2+2x+1$. Perform one step of gradient descent starting from $x_0=-3$ with step size $\alpha =0.2$.

E3.5.13 Given the function $f(x,y)=x^2+y^2$, perform two steps of gradient descent starting at $(1,1)$ with a step size $\alpha =0.1$.

E3.5.14 For a quadratic function $f(x)=a{x}^2+bx+c$, derive the the valuer of $\alpha$ under which gradient descent will converge to the minimum in one step.

Section 3.6

E3.6.1 Compute the log-odds of an event with probability $p=0.25$.

E3.6.2 Given the features $\mathbf{x}=(2,-1)$ and the coefficients $\mathit{\alpha }=(0.5,-0.3)$, compute the linear combination ${\mathit{\alpha }}^T\mathbf{x}$.

E3.6.3 For the data point $\mathbf{x}=(1,3)$ with the label $b=1$ and the coefficients $\mathit{\alpha }=(-0.2,0.4)$, calculate the probability $p(\mathbf{x};\mathit{\alpha })$ using the sigmoid function.

E3.6.4 Compute the cross-entropy loss for a single data point $\mathbf{x}=(1,2)$ with label $b=0$, given $\mathit{\alpha }=(0.3,-0.4)$.

E3.6.5 Prove that the logistic function $\sigma (z)=\frac{1}{1+e^{-z}}$ satisfies ${\sigma }^{\prime }(z)=\sigma (z)(1-\sigma (z))$.

E3.6.6 Given the feature vectors ${\alpha }_1=(1,2)$, ${\alpha }_2=(-1,1)$, ${\alpha }_3=(0,-1)$, and the corresponding labels $b_1=1$, $b_2=0$, $b_3=1$, compute the logistic regression objective function $\ell (x;A,b)$ for $x=(1,1)$.

E3.6.7 For the same data as in E3.6.6, compute the gradient of the logistic regression objective function $\mathrm{\nabla }\ell (x;A,b)$ at $x=(1,1)$.

E3.6.8 For the same data as in E3.6.6, compute the Hessian $H_{\ell }(x;A,b)$ of the logistic regression objective function at $x=(1,1)$.

E3.6.9 For the same data as in E3.6.6, perform one step of gradient descent with step size $\beta =0.1$ starting from $x^0=(0,0)$.

E3.6.10 For the same data as in E3.6.6, compute the smoothness parameter $L$ of the logistic regression objective function.

3.7.2. Problems#

3.1 Let $f:\mathbb{R}\to \mathbb{R}$ be twice continuously differentiable, let ${\mathbf{a}}_1,{\mathbf{a}}_2$ be vectors in ${\mathbb{R}}^d$, and let $b_1,b_2\in \mathbb{R}$. Consider the following real-valued function of $\mathbf{x}\in {\mathbb{R}}^d$:

a) Compute the gradient of $g$ in vector form in terms of the derivative $f^{\prime }$ of $f$. (By vector form, we mean that it is not enough to write down each element of $\mathrm{\nabla }g(\mathbf{x})$ separately.)

b) Compute the Hessian of $g$ in matrix form in terms of the first derivative $f^{\prime }$ and second derivative $f^{″}$ of $f$. (By matrix form, we mean that it is not enough to write down each element of $H_g(\mathbf{x})$ or each of its columns separately.)

3.2 Give an alternative proof of the Descent Direction and Directional Derivative Lemma using the definition of the directional derivative. [Hint: Mimic the proof of the single-variable case.] $⊲$

3.3 (Adapted from [CVX]) Show that if $S_1$ and $S_2$ are convex sets in ${\mathbb{R}}^{m+n}$, then so is their partial sum

$⊲$

3.4 A convex combination of ${\mathbf{z}}_1,\dots ,{\mathbf{z}}_m\in {\mathbb{R}}^d$ is a linear combination of the form

where ${\alpha }_i\ge 0$ for all $i$ and $\sum _{i=1}^m{\alpha }_i=1$. Show that a set is convex if and only if it contains all convex combinations of its elements. [Hint: Use induction on $m$.] $⊲$

3.5 A set $C\subseteq {\mathbb{R}}^d$ is a cone if, for all $\mathbf{x}\in C$ and all $\alpha \ge 0$, $\alpha \mathbf{x}\in C$. A conic combination of ${\mathbf{z}}_1,\dots ,{\mathbf{z}}_m\in {\mathbb{R}}^d$ is a linear combination of the form

where ${\alpha }_i\ge 0$ for all $i$. Show that a set $C$ is a convex cone if and only if it contains all conic combinations of its elements. $⊲$

3.6 Show that any linear subspace of ${\mathbb{R}}^d$ is convex. $⊲$

3.7 Show that the set

is convex. $⊲$

3.8 Let $f:{\mathbb{R}}^d\to \mathbb{R}$ be a strictly convex function. Assume further that there is a global minimizer ${\mathbf{x}}^{\ast }$. Show that it is unique. $⊲$

3.9 Show that ${\mathbf{S}}_{+}^n$ is a convex cone. $⊲$

3.10 Prove (a)-(e) from the Operations that Preserve Convexity Lemma. $⊲$

3.11 Let $f:{\mathbb{R}}^d\to \mathbb{R}$ be a function. The eipgraph of $f$ is the set

Show that $f$ is convex if and only if $\mathbf{epi}f$ is a convex set. $⊲$

3.12 Let $f_1,\dots ,f_m:{\mathbb{R}}^d\to \mathbb{R}$ be convex functions and let ${\beta }_1,\dots ,{\beta }_m\ge 0$. Show that

is convex. $⊲$

3.13 Let $f_1,f_2:{\mathbb{R}}^d\to \mathbb{R}$ be convex functions. Show that the pointwise maximum function

is convex. [Hint: First show that $max\{\alpha +\beta ,\eta +\varphi \}\le max\{\alpha ,\eta \}+max\{\beta ,\varphi \}$.]$⊲$

3.14 Prove the following composition theorem: if $f:{\mathbb{R}}^d\to \mathbb{R}$ is convex and $g:\mathbb{R}\to \mathbb{R}$ is convex and nondecreasing, then the composition $h=g\circ f$ is convex. $⊲$

3.15 Show that $f(x)=e^{\beta x}$, where $x,\beta \in \mathbb{R}$, is convex. $⊲$

3.16 Let $f:\mathbb{R}\to \mathbb{R}$ be twice continuously differentiable. Show that $f$ is $L$-smooth if $|f^{″}(x)|\le L$ for all $x\in \mathbb{R}$. $⊲$

3.17 For $a\in [-1,1]$ and $b\in \{0,1\}$, let $\hat{f}(x,a)=\sigma (xa)$ where

be a classifier parametrized by $x\in \mathbb{R}$. For a dataset $a_i\in [-1,1]$ and $b_i\in \{0,1\}$, $i=1,\dots ,n$, let the cross-entropy loss be

where

a) Show that ${\sigma }^{\prime }(t)=\sigma (t)(1-\sigma (t))$ for all $t\in \mathbb{R}$.

b) Use (a) to show that

c) Use (b) to show that

d) Use © to show that, for any dataset $\{(a_i,b_i){\}}_{i=1}^n$, $\mathcal{L}$ is convex and $1$-smooth as a function of $x$. $⊲$

3.18 Prove the Quadratic Bound for Strongly Convex Functions. [Hint: Adapt the proof of the Quadratic Bound for Smooth Functions.] $⊲$

3.19 Show that $\log x\le x-1$ for all $x>0$. [Hint: Compute the derivative of $s(x)=x-1-\log x$ and the value $s(1)$.] $⊲$

3.20 Consider the affine function

where $\mathbf{x}=(x_1,\dots ,x_d{)}^T,\mathbf{q}=(q_1,\dots ,q_d{)}^T\in {\mathbb{R}}^d$ and $r\in \mathbb{R}$. Fix a value $c\in \mathbb{R}$. Assume that

Show that

$⊲$

3.21 Let $f:D_1\to \mathbb{R}$, where $D_1\subseteq {\mathbb{R}}^d$, and let $\mathbf{g}:D_2\to {\mathbb{R}}^d$, where $D_2\subseteq \mathbb{R}$. Assume that $f$ is continuously differentiable at $\mathbf{g}(t_0)$, an interior point of $D_1$, and that $\mathbf{g}$ is continuously differentiable at $t_0$, an interior point of $D_2$. Assume further that there is a value $c\in \mathbb{R}$ such that

Show that ${\mathbf{g}}^{\prime }(t_0)$ is orthogonal to $\mathrm{\nabla }f(\mathbf{g}(t_0))$. $⊲$

3.22 Fix a partition $C_1,\dots ,C_k$ of $[n]$. Under the $k$-means objective, its cost is

where

with ${\mathit{\mu }}_i\in {\mathbb{R}}^d$, the center of cluster $C_i$.

a) Suppose ${\mathit{\mu }}_i^{\ast }$ is a global minimizer of

for each $i$. Show that ${\mathit{\mu }}_1^{\ast },\dots ,{\mathit{\mu }}_k^{\ast }$ is a global minimizer of $G(C_1,\dots ,C_k;{\mathit{\mu }}_1,\dots ,{\mathit{\mu }}_k)$.

b) Compute the gradient of $F_i({\mathit{\mu }}_i)$.

c) Find the stationary points of $F_i({\mathit{\mu }}_i)$.

d) Compute the Hessian of $F_i({\mathit{\mu }}_i)$.

e) Show that $F_i({\mathit{\mu }}_i)$ is convex.

f) Compute the global minimizer of $G(C_1,\dots ,C_k;{\mathit{\mu }}_1,\dots ,{\mathit{\mu }}_k)$. Justify your answer. $⊲$

3.23 Consider the quadratic function

where $P$ is symmetric. Show that, if $P$ is positive definite, then $f$ is strongly convex. $⊲$

3.24 A closed halfspace is a set of the form

for some $\mathbf{a}\in {\mathbb{R}}^d$ and $b\in \mathbb{R}$.

a) Show that $K$ is convex.

b) Show that there exists ${\mathbf{x}}_0\in {\mathbb{R}}^d$ such that

$⊲$

3.25 A hyperplane is a set of the form

for some $\mathbf{a}\in {\mathbb{R}}^d$ and $b\in \mathbb{R}$.

a) Show that $H$ is convex.

b) Assume $b=0$. Compute $H^{\perp }$ and justify your answer. $⊲$

3.26 Recall that the ${\ell }^1$-norm is defined as

a) Show that the ${\ell }^1$-norm satisfies the triangle inequality.

b) Show that the closed ${\ell }^1$ ball

for some $r>0$, is convex. $⊲$

3.27 The Lorentz cone is the set

Show that $C$ is convex. $⊲$

3.28 A polyhedron is a set of the form

for some ${\mathbf{a}}_i\in {\mathbb{R}}^d$, $b_i\in \mathbb{R}$, $i=1,\dots ,m$ and ${\mathbf{c}}_j\in {\mathbb{R}}^d$, $d_j\in \mathbb{R}$, $j=1,\dots ,n$. Show that $K$ is convex. $⊲$

3.29 The probability simplex in ${\mathbb{R}}^d$ is the set

Show that

$\mathrm{\Delta }$ is convex. $⊲$

3.30 Consider the function

a) Show that if $\Vert \mathbf{y}{\Vert }_2\le 1$ then $f^{\ast }(\mathbf{y})=0$.

b) Show that if $\Vert \mathbf{y}{\Vert }_2>1$ then $f^{\ast }(\mathbf{y})=+\mathrm{\infty }$. $⊲$

3.31 Let $f,g:D\to \mathbb{R}$ for some $D\subseteq {\mathbb{R}}^d$ and let ${\mathbf{x}}_0$ be an interior point of $D$. Assume $f$ and $g$ are continuously differentiable at ${\mathbf{x}}_0$. Let $h(\mathbf{x})=f(\mathbf{x})g(\mathbf{x})$ for all $\mathbf{x}$ in $D$. Compute $\mathrm{\nabla }h({\mathbf{x}}_0)$. [Hint: You can make use of the corresponding single variable result.] $⊲$

3.32 Let $f:D\to \mathbb{R}$ for some $D\subseteq {\mathbb{R}}^d$ and let ${\mathbf{x}}_0$ be an interior point of $D$ where $f({\mathbf{x}}_0)\ne 0$. Assume $f$ is continuously differentiable at ${\mathbf{x}}_0$. Compute $\mathrm{\nabla }(1/f)$. [Hint: You can make use of the corresponding single variable result without proof.] $⊲$

3.33 Let $f,g:D\to \mathbb{R}$ for some $D\subseteq {\mathbb{R}}^d$ and let ${\mathbf{x}}_0$ be an interior point of $D$. Assume $f$ and $g$ are twice continuously differentiable at ${\mathbf{x}}_0$. Let $h(\mathbf{x})=f(\mathbf{x})g(\mathbf{x})$ for all $\mathbf{x}$ in $D$. Compute ${\mathbf{H}}_h({\mathbf{x}}_0)$. $⊲$

3.34 (Adapted from [Rud]) Let $f:D\to \mathbb{R}$ for some convex open set $D\subseteq {\mathbb{R}}^d$. Assume that $f$ is continuously differentiable everywhere on $D$ and that further $\frac{\partial f}{\partial x_1}({\mathbf{x}}_0)=0$ for all ${\mathbf{x}}_0\in D$. Show that $f$ depends only on $x_2,\dots ,x_d$. $⊲$

3.35 (Adapted from [Rud]) Let $\mathbf{g}:D\to {\mathbb{R}}^d$ for some open set $D\subseteq \mathbb{R}$. Assume that $\mathbf{g}$ is continuously differentiable everywhere on $D$ and that further

Show that ${\mathbf{g}}^{\prime }(t{)}^T\mathbf{g}(t)=0$ for all $t\in D$. [Hint: Use composition.] $⊲$

3.36 (Adapted from [Khu]) Let $f:D\to \mathbb{R}$ for some open set $D\subseteq {\mathbb{R}}^d$. Assume that $f$ is continuously differentiable everywhere on $D$ and that further

for any $\mathbf{x}\in D$ and any scalar $t$ such that $t\mathbf{x}\in D$. In that case, $f$ is said to be homogeneous of degree $n$. Prove that for all $\mathbf{x}\in D$ we have

$⊲$

3.37 (Adapted from [Khu]) Apply Taylor’s Theorem in the neighborhood of $\mathbf{0}$ to the function

[Hint: You can use standard formulas for the derivatives of single-variable functions without proof.] $⊲$

3.38 (Adapted from [Khu]) Apply Taylor’s Theorem in the neighborhood of $\mathbf{0}$ to the function

[Hint: You can use standard formulas for the derivatives of single-variable functions without proof.] $⊲$

3.39 (Adapted from [Khu]) Apply Taylor’s Theorem in the neighborhood of $\mathbf{0}$ to the function

[Hint: You can use standard formulas for the derivatives of single-variable functions without proof.] $⊲$

3.40 (Adapted from [Khu]) Consider the function

a) Compute the gradient and Hessian of $f$ at $(0,0)$.

b) Show that $(0,0)$ is not a strict local minimizer of $f$. [Hint: Consider a parametric curve of the form $x_1=t^{\alpha }$ and $x_2=t^{\beta }$.]

c) Let $\mathbf{g}(t)=\mathbf{a}t$ for some nonzero vector $\mathbf{a}=(a_1,a_2{)}^T\in {\mathbb{R}}^2$. Show that $t=0$ is a strict local minimizer of $h(t)=f(\mathbf{g}(t))$. $⊲$

3.41 Suppose $f:{\mathbb{R}}^d\to \mathbb{R}$ is convex. Let $A\in {\mathbb{R}}^{d\times m}$ and $\mathbf{b}\in {\mathbb{R}}^d$. Show that

is convex over ${\mathbb{R}}^m$. $⊲$

3.42 (Adapted from [CVX]) For $\mathbf{x}=(x_1,\dots ,x_n)\in {\mathbb{R}}^n$, let

be the coordinates of $\mathbf{x}$ in non-increasing order. Let $1\le r\le n$ be an integer and $w_1\ge w_2\ge \cdots \ge w_r\ge 0$. Show that

is convex. $⊲$

3.43 For a fixed $\mathbf{z}\in {\mathbb{R}}^d$, let

a) Compute the gradient and Hessian of $f$.

b) Show that $f$ is strongly convex.

c) For a finite set $Z\subseteq {\mathbb{R}}^d$, let

Use Problem 3.13 to show that $g$ is convex. $⊲$

3.44 Let $S_i$, $i\in I$, be a collection of convex subsets of ${\mathbb{R}}^d$. Here $I$ can be infinite. Show that

is convex. $⊲$

3.45 a) Let $f_i$, $i\in I$, be a collection of convex real-valued functions over ${\mathbb{R}}^d$. Use Problems 3.11, 3.44 to show that

is convex.

b) Let $f:{\mathbb{R}}^{d+f}\to \mathbb{R}$ be a convex function and let $S\subseteq {\mathbb{R}}^f$ be a (not necessarily convex) set. Use (a) to show that the function

is convex. You can assume that $g(\mathbf{x})<+\mathrm{\infty }$ for all $\mathbf{x}\in {\mathbb{R}}^d$. $⊲$

3.46 Use Problem 3.45 to show that the largest eigenvalue of a matrix is a convex function over the set of all symmetric matrices. [Hint: First show that $⟨\mathbf{x},A\mathbf{x}⟩$ is a linear function of $A$. $⊲$

3.47 Let $f:{\mathbb{R}}^d\to \mathbb{R}$ be a convex function. Show that the set of global minimizers is convex. $⊲$

3.48 Consider the set of symmetric $n\times n$ matrices

a) Show that ${\mathbf{S}}^n$ is a linear subspace of the vector space of $n\times n$ matrices in the sense that for all $X_1,X_2\in {\mathbf{S}}^n$ and $\alpha \in \mathbb{R}$

and

b) Show that there exists a basis of ${\mathbf{S}}^n$ of size $d=(\genfrac{}{}{0ex}{}{n}{2})+n$, that is, a collection of symmetric matrices $X_1,\dots ,X_d\in {\mathbf{S}}^n$ such that any matrix $Y\in {\mathbf{S}}^n$ can be written as a linear combination

for some ${\alpha }_1,\dots ,{\alpha }_d\in \mathbb{R}$.

c) Show that the matrices $X_1,\dots ,X_d\in {\mathbf{S}}^n$ you constructed in (b) are linearly independent in the sense that

$⊲$

3.49 Let $f:D\to \mathbb{R}$ be a convex function over the set

a) Show that $D$ is convex.

b) Show that the First-Order Optimality Conditions for a Convex Functions on Convex Sets reduces to

and

[Hint: Choose the right $\mathbf{y}$ in the condition of the theorem.] $⊲$

3.50 Let $f:{\mathbb{R}}^d\to \mathbb{R}$ be twice continuously differentiable and $m$-strongly convex with $m>0$.

a) Show that

along any sequence $({\mathbf{y}}_n)$ such that $\Vert {\mathbf{y}}_n\Vert \to +\mathrm{\infty }$ as $n\to +\mathrm{\infty }.$

b) Show that, for any ${\mathbf{x}}^0$, the set

is closed and bounded.

c) Show that there exists a unique global minimizer ${\mathbf{x}}^{\ast }$ of $f$. $⊲$

3.51 Suppose that $f:{\mathbb{R}}^d\to \mathbb{R}$ is $L$-smooth and $m$-strongly convex with a global minimizer at ${\mathbf{x}}^{\ast }$. Apply gradient descent with step size $\alpha =1/L$ started from an arbitrary point ${\mathbf{x}}^0$.

a) Show that ${\mathbf{x}}^t\to {\mathbf{x}}^{\ast }$ as $t\to +\mathrm{\infty }$. [Hint: Use the Quadratic Bound for Strongly Convex Functions at ${\mathbf{x}}^{\ast }$.]

b) Give a bound on $\Vert {\mathbf{x}}^t-{\mathbf{x}}^{\ast }\Vert$ depending on $t,m,L,f({\mathbf{x}}^0)$ and $f(\mathbf{x}{)}^{\ast }$.