{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Friends of convex\n",
    "\n",
    "For each of the following statements, determine TRUE or FALSE. If your answer is TRUE, then prove that statement. If your answer is FALSE, then give a counterexample."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(a) (10 points) Hyperbolic function $f(x_{1},x_{2}) = x_{1}x_{2}$ is quasiconcave on ${\\rm{dom}}(f) = \\mathbb{R}^{2}_{>0}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Solution:\n",
    "TRUE. Here $\\mathbf{dom}(f)$ is the positive orthant - a convex set (in fact, a convex cone). Since all superlevel sets of the function $f$, i.e., sets of the form $\\{(x_{1},x_{2})\\in\\mathbb{R}^{2} \\:\\mid\\: f(x_{1},x_{2}) \\geq \\alpha\\}$, $\\alpha \\in \\mathbb{R}$, are convex, hence by Lecture 7, p. 16, the function $f$ is quasiconcave."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(b) (10 points) Logistic function $f(x) = \\displaystyle\\frac{\\exp(x)}{1 + \\exp(x)}$ is log-concave on ${\\rm{dom}}(f) = \\mathbb{R}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Solution:\n",
    "TRUE. We have \n",
    "$$\\log\\left(\\displaystyle\\frac{\\exp(x)}{1 + \\exp(x)}\\right) = x - \\log\\left(1 + \\exp(x)\\right).$$\n",
    "The first term above is linear, hence concave. By second order condition, the function $\\log(1+\\exp(x))$ is convex, so the second term being its negative, is concave. Since the sum of concaves is concave, therefore $\\log(f(x))$ is concave."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(c) (10 points) $f(x) = \\begin{cases}x &\\text{for}\\; x<0,\\\\ x+1 &\\text{for}\\; x>0,\\end{cases}$ is pseudo-convex but not quasiconvex on ${\\rm{dom}}(f) = \\mathbb{R}\\setminus\\{0\\}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Solution:\n",
    "TRUE. Since the domain is non-convex, hence $f(x)$ is NOT quasiconvex. However, the convexity of the domain is not needed in the definition of pseudo-convex function given in Section 1 of the paper sent to the class: O.L. Mangasarian, \"Psedo-convex functions\", J. SIAM Control, 1965. Section 3 of this paper discusses this example."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(d) (15 points) $f(X) = \\log X$ is operator monotone and operator concave on ${\\rm{dom}}(X) = \\mathbb{S}_{++}^{n}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Solution:\n",
    "TRUE. Recall the limiting definition of $\\log(x)$ over $x>0$, given by $\\log(x) = \\lim_{p\\rightarrow 0}\\displaystyle\\frac{1}{p}(x^{p}-1)$. Likewise, for $X\\in\\mathbb{S}^{n}_{++}$, we have\n",
    "$$\\log(X) = \\displaystyle\\lim_{p\\rightarrow 0}\\frac{1}{p}\\left(X^{p}-I\\right).$$\n",
    "Since $X^{p}$ is operator monotone and operator concave for all $0 \\leq p \\leq 1$ [(see p. 10-11 of these notes sent to class)](http://www.ueltschi.org/AZschool/notes/EricCarlen.pdf), hence the same holds in the small $p$ case appearing in the limit above."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(e) (15 points) $f(X) = X^{-1}$ is operator monotone and operator convex on ${\\rm{dom}}(X) = \\mathbb{S}_{++}^{n}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "#### Solution:\n",
    "TRUE. To prove monotonicity, we will show that if $X \\succeq Y$, then $X^{-1} \\preceq Y^{-1}$ for all $X,Y\\in\\mathbb{S}^{n}_{++}$ (this is like decreasing function). Let $Z:= X^{-1/2}YX^{-1/2} \\in \\mathbb{S}^{n}_{++}$ (congruence transform preserves sign-definiteness). Then\n",
    "$$X \\succeq Y \\quad \\Leftrightarrow \\quad X - Y = X^{1/2}\\left(I - X^{-1/2}YX^{-1/2}\\right)X^{1/2} \\succeq 0 \\quad \\Leftrightarrow \\quad I - X^{-1/2}YX^{-1/2} \\succeq 0 \\quad \\Leftrightarrow \\quad Z - I \\preceq 0.$$\n",
    "On the other hand, \n",
    "$$X^{-1} -Y^{-1} = X^{-1/2}\\left(I - Z^{-1}\\right)X^{-1/2} = X^{-1/2}Z^{-1/2}\\left(Z-I\\right)Z^{-1/2}X^{-1/2} \\preceq 0,$$\n",
    "which follows from the fact that the LHS of the last inequality is congruence transform by the non-singular matrix $X^{-1/2}Z^{-1/2}$, and that $Z - I \\preceq 0$. \n",
    "\n",
    "\n",
    "To prove operator convexity of $f(X)$, we need to show\n",
    "$$f(\\theta X + (1-\\theta)Y) \\preceq \\theta f(X) \\: + \\: (1-\\theta)f(Y), \\quad\\text{for all}\\;X,Y\\in\\mathbb{S}^{n}_{++}, \\quad 0\\leq\\theta\\leq 1.$$\n",
    "\n",
    "Since $f$ is continuous, it suffices to prove mid-point convexity, i.e., to prove the above inequality for $\\theta = 1/2$. Thus, we want to prove\n",
    "$$\\begin{aligned}\n",
    "\\left(\\displaystyle\\frac{X+Y}{2}\\right)^{-1} \\preceq \\displaystyle\\frac{1}{2}\\left(X^{-1} + Y^{-1}\\right) \\quad \\Leftrightarrow \\quad \\displaystyle\\frac{1}{2}\\left(X^{-1} + Y^{-1}\\right) - \\left(\\displaystyle\\frac{X+Y}{2}\\right)^{-1} = X^{-1/2}\\left[\\frac{1}{2}I + \\frac{1}{2}Z^{-1} - \\left(\\displaystyle\\frac{I+Z}{2}\\right)^{-1}\\right]X^{-1/2} \\succeq 0,\n",
    "\\end{aligned}$$\n",
    "where $Z:= X^{-1/2}YX^{-1/2} \\in \\mathbb{S}^{n}_{++}$ (congruence transform preserves sign-definiteness). Therefore, it is enough to prove that the matrix within the square bracket appearing in the last inequality is positive semidefinite, i.e., $\\frac{1}{2}(I + Z^{-1}) \\succeq \\left(\\frac{I+Z}{2}\\right)^{-1}$. By arithmetic mean-harmonic mean inequality, we know that $(a+b)/2 \\geq ((a^{-1}+b^{-1})/2)^{-1}$ for all $a,b>0$, specializing which for $a=1$ and $b=$ any eigenvalue of $Z^{-1}\\in\\mathbb{S}^{n}_{++}$, followed by the application of Spectral Theorem, gives us\n",
    "$$\\frac{1}{2}(I + Z^{-1}) \\succeq \\left(\\frac{I+Z}{2}\\right)^{-1} \\quad \\Leftrightarrow \\quad \\frac{1}{2}I + \\frac{1}{2}Z^{-1} - \\left(\\displaystyle\\frac{I+Z}{2}\\right)^{-1} \\succeq 0,$$\n",
    "as desired."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}