global_lipsheets_optimization_2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Глобальная оптимизация липшицевых функций"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$f(x)=|x-10|$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "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": 40,
   "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": 41,
   "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)$.$$l(c)={f(x_2)+f(x_1)\\over2}-L{x_2-x_1\\over2}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "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": 43,
   "metadata": {},
   "outputs": [],
   "source": [
    "def lipsheets(x1, x2):\n",
    "    assert(x1 < x2)\n",
    "    trace = [[x1,func(x1), 0], [intersection_point(x1, x2), lower_grade(x1, x2), 1], [x2, func(x2), 0]]\n",
    "    upper_bound = min(trace[0][1], trace[2][1])\n",
    "    lower_bound = lower_grade(x1, x2)\n",
    "    while upper_bound - lower_bound > EPS:\n",
    "        _min, _w = upper_bound, 0\n",
    "        for w in range(len(trace)):\n",
    "            if trace[w][2] != 0 and lower_bound <= trace[w][1] < _min:\n",
    "                _min = trace[w][1]\n",
    "                _w = w\n",
    "                \n",
    "        upper_bound = min(upper_bound, func(trace[_w][0]))\n",
    "        lower_bound = _min\n",
    "        \n",
    "        trace[_w][1] = func(trace[_w][0])\n",
    "        trace[_w][2] = 0 \n",
    "        p1 = [intersection_point(trace[_w-1][0], trace[_w][0]), lower_grade(trace[_w-1][0], trace[_w][0]), 1]\n",
    "        p2 = [intersection_point(trace[_w][0], trace[_w+1][0]), lower_grade(trace[_w][0], trace[_w+1][0]), 1]\n",
    "        trace.insert(_w, p1)\n",
    "        trace.insert(_w+2, p2)\n",
    "    return {'interval': (lower_bound, upper_bound), 'trace': [(i[0], i[1]) for i in trace]}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'interval': (0.0, 0.0), 'touch': 18}\n"
     ]
    }
   ],
   "source": [
    "touch = 0\n",
    "result = lipsheets(A, B)\n",
    "print({'interval': result['interval'], 'touch':touch})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(5, 5), (10.0, 0.0), (10.0, 0.0), (10.0, 0.0), (12, 2)]"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "result['trace']"
   ]
  },
  {
   "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
}