global_lipsheets_optimization.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Глобальная оптимизация липшицевых функций"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$f(x)=|x-10|$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [],
   "source": [
    "def func(x):\n",
    "    global touch\n",
    "    touch += 1\n",
    "    return abs(x-10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$L=\\max|f'(x)|, x\\in[a, b]$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [],
   "source": [
    "L = 1\n",
    "EPS = 0.05\n",
    "A, B = 5, 12"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$${c(x_1, x_2)={1\\over2L}\\left[L(x_1+x_2)+f(x_1)-f(x_2)\\right]}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [],
   "source": [
    "def intersection_point(x1, x2):\n",
    "    return 1/(2*L)*(L*(x1+x2)+func(x1)-func(x2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Функция $l(c)$ задает пряму прямую, определенную на $[x_1, x_2]$. Совокупность отрезков $l_n$ позволяет построить ломанную линию нижней оценки функции $f(x)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$l(c)={f(x_2)+f(x_1)\\over2}-L{x_2-x_1\\over2}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [],
   "source": [
    "def lower_grade(x1, x2):\n",
    "    return 1/2*(func(x2)+func(x1)-L*(x2-x1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\min(l_{n+2}(c))\\le f(x^*)\\le \\min(f(a), f(b), f(c_1),\\ldots,f(c_n)))$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [],
   "source": [
    "def lipsheets(x1, x2):\n",
    "    assert(x1 <= x2)\n",
    "    upper_bound = min(func(x1), func(x2))\n",
    "    lower_bound = lower_grade(x1, x2)\n",
    "    while upper_bound - lower_bound > EPS:\n",
    "        cp = intersection_point(x1, x2)\n",
    "        c1 = lower_grade(x1, cp)\n",
    "        c2 = lower_grade(cp, x2)\n",
    "        if c1 < c2:\n",
    "            x2 = cp\n",
    "        else:\n",
    "            x1 = cp\n",
    "        upper_bound = min(upper_bound, func(cp))\n",
    "        lower_bound = lower_grade(x1, x2)\n",
    "    return lower_bound, upper_bound"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'interval': (0.0, 0.0), 'touch': 13}\n"
     ]
    }
   ],
   "source": [
    "touch = 0\n",
    "print({'interval':lipsheets(A, B), 'touch':touch})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "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.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}