Optimization

Table of Contents

• Gradient Descent
• Convexity
  • Convex Sets
    • Properties -
  • Convex Combinations
  • Convex Functions
    • Properties -
• Questions

Gradient Descent

<Intentionally left blank for now>

Convexity

Convex Sets

A set is a convex set if $\forall x_1,x_2\in S$, $\lambda x_1+(1-\lambda )x_2\in S$ where $\lambda \in [0,1]$. Geometrically speaking, the below sets are a convex set -

Properties -

1. If $A$ and $B$ are two convex sets then $A\cap B$ is also a convex set.

$$\begin{array}{rl}\text{Let }{x}_1\text{ and }{x}_2\in A\cap B.& \text{We can say,}\\ \lambda x_1+(1-\lambda )x_2& \in A\text{ because }{x}_1,x_2\in A\\ \lambda x_1+(1-\lambda )x_2& \in B\text{ because }{x}_1,x_2\in B\\ \text{Thus we can say that }{x}_1,& x_2\in A\cap B.\end{array}$$

This property is helpful in showing if a set is convex, by showing that the set is formed by intersection of two other convex sets.

Convex Combinations

Let $S=\{x_1,x_2,\dots ,x_n\}\subseteq {\mathbb{R}}^n$. Then we say that $z\in {\mathbb{R}}^n$ is a convex combination of vectors in $S$ if $\exists {\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n$ such that ${\lambda }_i\ge 0$ and $\sum {\lambda }_i=1$ and

$$z={\lambda }_1{x}_1+{\lambda }_2{x}_2+\cdots +{\lambda }_n{x}_n$$

The convex hull of a set $S$, denoted by $\mathrm{conv}(S)$ or $\mathrm{CH}(S)$ is the set of all convex combinations of the elements of the set $S$.

$$CH(\{x_1,x_2,\dots ,x_n\})=\left\{z|z=\sum _{i=1}^n{\lambda }_i{x}_i,{\lambda }_i\ge 0\text{ and }\sum _{i=1}^n{\lambda }_i=1\right\}$$

An alternate definition of a convex hull can be that, the convex hull of a set is the intersection of all convex sets that contain $\{x_1,x_2,\dots ,x_n\}$. The two definitions can be shown to be equivalent.

Important Exercise – Show that Euclidean Balls are Convex Sets

Convex Functions

$\underline{\text{Definition 1}}$ – A function $f:{\mathbb{R}}^d\to \mathbb{R}$ is a convex function iff $\mathrm{epi}(f)\in {\mathbb{R}}^{d+1}$ is a convex set.

$\mathrm{epi}$ stands for epigraph of a function. An epigraph is the set of all points above the graph’s curve -

$$\begin{array}{r}\mathrm{epi}(f)=\{(x,y)\in {\mathbb{R}}^n\times \mathbb{R}|t\ge f(x)\}\end{array}$$

The opposite of an epigraph is a hypograph.

$\underline{\text{Definition 2}}$ – A function $f:{\mathbb{R}}^d\to \mathbb{R}$ is a convex function iff $\forall x_1,x_2\in {\mathbb{R}}^d$ and all $\lambda \in [0,1]$

$$\begin{array}{rl}f(\lambda x_1+(1-\lambda x_2))& \le \lambda f(x_1)+(1-\lambda )f(x_2)\\ \text{OR more}& \text{ generalized}\\ f\left(\sum _{k=1}{\lambda }_k{a}_k\right)& \le \sum _{k=1}{\lambda }_{k}f(a_k)\end{array}$$

For concave functions this inequality becomes,

$$f\left(\sum _{k=1}{\lambda }_k{a}_k\right)\ge \sum _{k=1}{\lambda }_{k}f(a_k)$$

$\underline{\text{Definition 3}}$ – A function $f:{\mathbb{R}}^d\to \mathbb{R}$ is a convex function iff $f$ is differentiable and,

$$f(y)\ge f(x)+\nabla f(x{)}^T(y-x)\forall x,y\in {\mathbb{R}}^d$$

This means that the tangent plane lower bounds the function for every point in its domain.

$\underline{\text{Definition 4}}$ – A function $f:{\mathbb{R}}^d\to \mathbb{R}$ is a convex function iff it is twice differentiable.

Properties -

1) In a convex function f, x* is a global minima iff its gradient is 0.

$\underline{\text{Proof}}-$ $(1)$ We need to first show that if $x^{\ast }$ is a global minima, $\nabla f(x^{\ast })=0$. This can be shown easily by using the concept of steepest descent. At any point, the direction of steepest descent is $-\nabla f(x^{\ast })$. So if $\nabla f(x)\ne 0$ for any point $x$, we can show that there exists another point in the direction of steepest descent such that $f(x-\eta \nabla f(x^{\ast }))<f(x)$. Thus if $\nabla f(x^{\ast })\ne 0$ then $x^{\ast }$ can’t be a minima, let alone a global minima.

Thus points where no such direction of steepest descent would exist will have $\nabla f(x^{\ast })=0$. Thus the gradient at the global minima must be $0$.

$(2)$ Now we need to show the reverse, that in convex functions if $\nabla f(x^{\ast })=0$ then $x^{\ast }$ is a global minima. We know by Definition 3 that the tangent plane at any point of the graph lower bounds the function. So even at the global minima $x^{\ast }$ we can say,

$$\begin{array}{rlrl}& & f(y)& \ge f(x)+\nabla f(x{)}^T(y-x)\forall x,y\in {\mathbb{R}}^d\\ & \Rightarrow & f(y)& \ge f(x^{\ast })+\nabla f(x^{\ast }{)}^T(y-x^{\ast })\\ & \Rightarrow & f(y)& \ge f(x^{\ast })\end{array}$$

Hence we can say that $x^{\ast }$ is a global minima.

2) If f and g are two convex functions, then h(x) = f(x) + g(x) is also a convex function.

This can be proved easily using Jensen’s Inequality of convex functions. Try it out!

3) If f is a convex and non-decreasing function and g is any convex function, then h(x) = fog(x) is also a convex function.

This can again be proved easily using Jensen’s Inequality of convex functions. Try it out!

4) If f is a convex function and g is a linear function, then h(x) = fog(x) is also a convex function.

This can again be proved easily using [[#^bec74f|Jensen's Inequality]] of convex functions along with the property of linear functions. Try it out!

Note - In general if $f$ and $g$ are convex, the composition $h(x)=fog(x)$ may not be convex.

---

Questions

Q1) Show that log is a concave function -

$\underline{\text{Sol}^n} -$ We can use the reverse of [[#^bec74f|Jensen's Inequality]] for this purpose. If we are able to show that, $$\log (\lambda x+(1-\lambda )y)\ge \lambda \log (x)+(1-\lambda )\log (y)x,y>0,\lambda \in [0,1]$$

For this we can try removing the $\log$ from both sides and put everything to the left side and show that the unified equation is greater than or equal to $0$. So we can rewrite the above requirement as,

$$\begin{array}{rlrlr}& & \log (\lambda x+(1-\lambda )y)& \ge \lambda \log (x)+(1-\lambda )\log (y)& \\ & \Rightarrow & \log (\lambda x+(1-\lambda )y)& \ge \log (x^{\lambda })+\log (y^{(1-\lambda )})& \\ & \Rightarrow & \log (\lambda x+(1-\lambda )y)& \ge \log (x^{\lambda }\cdot y^{(1-\lambda )})& \\ & \Rightarrow & \lambda x+(1-\lambda )y& \ge x^{\lambda }\cdot y^{(1-\lambda )}& \\ & \Rightarrow & \lambda \frac{x}{y}+(1-\lambda )& \ge x^{\lambda }\cdot y^{-\lambda }& \\ & \Rightarrow & \lambda t+(1-\lambda )& \ge t^{\lambda }& \because t=\frac{x}{y}\\ & \Rightarrow & \lambda t+(1-\lambda )-t^{\lambda }& \ge 0& \end{array}\text{\hspace{1em}(1)}$$

We can differentiate this term to get its minima, and if the minima is $\ge 0$ then we can say that the entire equation is always non-negative.

$$\begin{array}{rlrl}& & q(t)& =\lambda t+(1-\lambda )-t^{\lambda }\\ & \Rightarrow & q^{\prime }(t)& =\lambda +-\lambda t^{\lambda -1}\end{array}$$

For the some $t^{\ast }$ to be the minima of $q$, $q^{\prime }(t^{\ast })=0$. So,

$$\begin{array}{rlrl}& & q^{\prime }(t^{\ast })& =\lambda +-\lambda t^{{\ast }^{\lambda -1}}\\ & \Rightarrow & 0& =\lambda (1-t^{{\ast }^{\lambda -1}})\end{array}$$

If $\lambda \ne 0$ then then only $t^{\ast }=1$ can satisfy the above equation. Because $q(1)=0$, we can say that $\forall t>0,q(t)\ge 0$. Hence we have proven that $(1)$ is true and consequently proven that $\log$ is a concave function.