{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Perron-Frobenius matrix completion\n",
    "\n",
    "The DGP atom library has several functions of positive matrices, including the trace, (matrix) product, sum, Perron-Frobenius eigenvalue, and $(I - X)^{-1}$ (eye-minus-inverse). In this notebook, we use some of these atoms to formulate and solve an interesting matrix completion problem.\n",
    "\n",
    "In this problem, we are given some entries of an elementwise positive matrix $A$, and the goal is to choose the missing entries so as to minimize the Perron-Frobenius eigenvalue or spectral\n",
    "radius. Letting $\\Omega$ denote the set of indices $(i, j)$ for which $A_{ij}$ is known, the optimization problem is\n",
    "\n",
    "$$\n",
    "\\begin{equation}\n",
    "\\begin{array}{ll}\n",
    "\\mbox{minimize} & \\lambda_{\\text{pf}}(X) \\\\\n",
    "\\mbox{subject to} & \\prod_{(i, j) \\not\\in \\Omega} X_{ij} = 1 \\\\\n",
    "& X_{ij} = A_{ij}, \\, (i, j) \\in \\Omega,\n",
    "\\end{array}\n",
    "\\end{equation}\n",
    "$$\n",
    "\n",
    "which is a log-log convex program.  Below is an implementation of this problem, with specific problem data\n",
    "\n",
    "$$\n",
    "A = \\begin{bmatrix}\n",
    "1.0 & ? &  1.9 \\\\\n",
    "? & 0.8 &  ? \\\\\n",
    "3.2 & 5.9&  ?\n",
    "\\end{bmatrix},\n",
    "$$\n",
    "\n",
    "where the question marks denote the missing entries."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Optimal value:  4.702374203221372\n",
      "X:\n",
      " [[1.         4.63616907 1.9       ]\n",
      " [0.49991744 0.8        0.37774148]\n",
      " [3.2        5.9        1.14221476]]\n"
     ]
    }
   ],
   "source": [
    "import cvxpy as cp\n",
    "\n",
    "n = 3\n",
    "known_value_indices = tuple(zip(*[[0, 0], [0, 2], [1, 1], [2, 0], [2, 1]]))\n",
    "known_values = [1.0, 1.9, 0.8, 3.2, 5.9]\n",
    "X = cp.Variable((n, n), pos=True)\n",
    "objective_fn = cp.pf_eigenvalue(X)\n",
    "constraints = [\n",
    "  X[known_value_indices] == known_values,\n",
    "  X[0, 1] * X[1, 0] * X[1, 2] * X[2, 2] == 1.0,\n",
    "]\n",
    "problem = cp.Problem(cp.Minimize(objective_fn), constraints)\n",
    "problem.solve(gp=True)\n",
    "print(\"Optimal value: \", problem.value)\n",
    "print(\"X:\\n\", X.value)"
   ]
  }
 ],
 "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.7.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}