Cones.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#math and linear algebra stuff\n",
    "import numpy as np\n",
    "import numpy.linalg as la\n",
    "\n",
    "#plots\n",
    "import matplotlib as mpl\n",
    "mpl.rcParams['figure.figsize'] = (15.0, 15.0)\n",
    "#mpl.rc('text', usetex = True)\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Cones and optimization\n",
    "This notebook intends to recall some definitions, and highlight some importants aspects related to cone for convex optimizations.\n",
    "Most definitions and examples here come fronm the book \"Convex Optimization\" from Boyd and Vandenberghe\n",
    "\n",
    "## Cone, conic combination, conic hull\n",
    "A set C is called a cone (or nonnegative homogeneous) if for every $x\\in C$ and $\\theta \\geq 0$ we have $\\theta x \\in C$. a  A set C is a convex cone if it is convex and a cone, which means that for any $x_1, x_2 \\in C$ and $\\theta_1, \\theta_2 \\geq 0$ we have:\n",
    "\n",
    "\\begin{align}\n",
    "  \\theta_1 x_1 + \\theta_2 x_2 \\in C\n",
    "\\end{align}\n",
    "\n",
    "A point of the form $\\theta_1 x_1 + \\dots + \\theta_k x_k $ with $ \\theta_1, \\dots, \\theta_k \\geq 0$ is called a conic combination (or a nonnegative linear combination) of $x_1 , \\dots , x_k$.\n",
    "\n",
    "The conic hull of a set C is the set of all conic combinations of points in C, i.e.,\n",
    "\\begin{align}\n",
    "  \\{\\theta_1 x_1 + \\dots + \\theta_k x_k | x_i \\in C, \\; \\theta_i \\geq 0, \\; i = 1, \\dots , k\\},\n",
    "\\end{align}\n",
    "which is also the smallest convex cone that contains C"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Norm cone\n",
    "Suppose $\\|\\cdot\\|$ is any norm on $\\mathbb{R}^n$. From the general properties of norms it can be shown that a norm ball of radius r and center $x_c$ , given by ${x | \\|x−x_c\\| \\leq r}$, is convex.\n",
    "The norm cone associated with the norm $\\|\\cdot\\|$ is the set C:\n",
    "\n",
    "\\begin{align}\n",
    " C = \\{(x, t) \\; | \\;  \\|x\\| \\leq t\\} \\in \\mathbb{R}^{n+1}\n",
    "\\end{align}\n",
    "\n",
    "One can also define more exotic kinds of cones using the following definitions that rely on a norm defined by a positive definite matrix $A \\in S^{n}_{++}$:\n",
    "\n",
    "\\begin{align}\n",
    " C &= \\{ (x, t) \\; | \\;  \\|x\\|_{A} \\leq t \\} \\in \\mathbb{R}^{n+1}\\\\\n",
    " &= \\left\\{ \\begin{pmatrix} x \\\\ t \\end{pmatrix} \\; | \\;\n",
    " \\begin{pmatrix} x \\\\ t \\end{pmatrix}^{t}\n",
    " \\begin{pmatrix} A & 0 \\\\ 0 & -1 \\end{pmatrix}\n",
    " \\begin{pmatrix} x \\\\ t \\end{pmatrix} \\leq 0, t \\geq 0 \\right\\}\n",
    "\\end{align}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Positive semi definite cone\n",
    "\n",
    "We use the notation $S^n$ to denote the set of symmetric $n \\times n$ matrices, $S^n = \\{ X \\in \\mathbb{R}^{n \\times n} | X = X^t \\}$ which is a vector space with dimension $\\frac{n(n + 1)}{2}$. We use the notation $S^n_+$ to denote the set of symmetric positive semidefinite matrices:\n",
    "\\begin{align}\n",
    "  S^n_+ = \\{ X \\in S^n | X \\geq 0 \\}\n",
    "\\end{align}\n",
    "and the notation $S^n_{++}$ to denote the set of symmetric positive definite matrices:\n",
    "\\begin{align}\n",
    "  S^n_{++} = \\{X \\in S^n | X > 0 \\}\n",
    "\\end{align}\n",
    "\n",
    "This notation is meant to be analogous to $\\mathbb{R}_+$ , which denotes the nonnegative reals, and $\\mathbb{R}_{++}$ which denotes the positive reals.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Proper cone, generalized inequalities\n",
    "A cone $K \\in \\mathbb{R}^n$  is called a proper cone if it satisfies the following:\n",
    "  - K is convex.\n",
    "  - K is closed.\n",
    "  - K is solid, which means it has nonempty interior.\n",
    "  - K is pointed, which means that it contains no line (or equivalently, $x \\in K, − x \\in K \\Leftrightarrow x = 0$).\n",
    "\n",
    "A proper cone K can be used to define a generalized inequality, which is a partial ordering on $\\mathbb{R}^n$ that has many of the properties of the standard ordering on $\\mathbb{R}$.\n",
    "\n",
    "We associate with the proper cone K the partial ordering on $\\mathbb{R}^n$ defined by\n",
    "\\begin{align}\n",
    "  x \\leq_K y \\Leftrightarrow y − x \\in K\n",
    "\\end{align}\n",
    "\n",
    "We also write $x \\geq_K y$ for $y \\leq_K x$. Similarly, we define an associated strict partial ordering by\n",
    "\\begin{align}\n",
    "  x <_K y \\Leftrightarrow y − x \\in int \\, K\n",
    "\\end{align}\n",
    "\n",
    "### Minimum and minimal elements for generalized inequalities\n",
    "\n",
    "It is important to notice that a cone $K$ can be used to define a partial ordering on a set S, which means that we cannot necessarily compare any pair of elements of S. Concepts like minimum and maximum are then more complicated in the context of generalized inequalities.\n",
    "We say that $x \\in S$ is the minimum element of $S$ (with respect to the generalized inequality $\\leq_K$) if for every $y \\in S$ we have $x \\leq_K y$.\n",
    "\n",
    "A related concept is minimal element. We say that $x \\in S$ is a minimal element of S (with respect to the generalized inequality $\\leq K$) if $y \\in S, y \\leq_K x$ only if $y = x$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}