logsfile/log48.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Pointed fan"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To determine whether a given fan is a pointed fan or not, we may encode it into an linear optimization.\n",
    "\n",
    "##### Observation:\n",
    "\n",
    "If a fan is pointed, then there exists a containing-the-original-point hyperplane that could divide the space into 2 half spaces, one containing the fan and the other not.\n",
    "\n",
    "##### Analysis:\n",
    "We may think about finding the normal vector of this hyperplane via optimzation.\n",
    "Let us encode it.\n",
    "\n",
    "Supposing that the normal vector of this hyperplane is $x$ and 1-norm vectors of the generating rays of all cones in the fan are $r_i, i\\in A $,\n",
    "\n",
    "then we may have let the constraints be:\n",
    "\n",
    "$x \\cdot r_i \\ge 0$\n",
    "\n",
    "Since we do not hope to get $x = 0$, we may add an extra constraint, $x_1 = 1$, for getting one representing element.\n",
    "\n",
    "If we can not find any solution for this system, then the fan is not pointed.\n",
    "If we can find one solution, then the fan is pointed.\n",
    "\n",
    "In practice, in order to give a initial solution for simplex method, we may change the system into the following form:\n",
    "\n",
    "max. : $x_1$\n",
    "\n",
    "s.t. \n",
    "\n",
    "$x \\cdot r_i \\ge 0$\n",
    "\n",
    "$1\\ge x_1 \\ge 0$\n",
    "\n",
    "As is desired, $x = 0$ always be the solution for this system.\n",
    "\n",
    "##### A better hyperplane for generating better projection\n",
    "\n",
    "Seemingly, we may have optional hyperplanes for the same system. The ideal hyperplane would be constraints are all $>$, instead of $\\ge$. We may get rid of $x_1 = 1$ and add a little \"balance\" for each constraints to get it. i.e.\n",
    "\n",
    "$x \\cdot r_i - b_i\\ge 0$\n",
    "\n",
    "$b_i$ are all some given small positive numbers.\n",
    "\n",
    "Similarly, in order to have a initial solution, we may change the system into the following form:\n",
    "\n",
    "max. :$ b_0$\n",
    "\n",
    "$x \\cdot r_i - b_i\\ge 0$\n",
    "\n",
    "$b_i \\ge b_0$\n",
    "\n",
    "$1\\ge b_0 \\ge 0$ \n",
    "\n",
    "As is desired, $x = 0$ always be the solution for this system."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.5.beta0",
   "language": "sage",
   "name": "sagemath"
  },
  "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.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}