ترغب بنشر مسار تعليمي؟ اضغط هنا

Differentiating through Log-Log Convex Programs

213   0   0.0 ( 0 )
 نشر من قبل Akshay Agrawal
 تاريخ النشر 2020
  مجال البحث
والبحث باللغة English




اسأل ChatGPT حول البحث

We show how to efficiently compute the derivative (when it exists) of the solution map of log-log convex programs (LLCPs). These are nonconvex, nonsmooth optimization problems with positive variables that become convex when the variables, objective functions, and constraint functions are replaced with their logs. We focus specifically on LLCPs generated by disciplined geometric programming, a grammar consisting of a set of atomic functions with known log-log curvature and a composition rule for combining them. We represent a parametrized LLCP as the composition of a smooth transformation of parameters, a convex optimization problem, and an exponential transformation of the convex optimization problems solution. The derivative of this composition can be computed efficiently, using recently developed methods for differentiating through convex optimization problems. We implement our method in CVXPY, a Python-embedded modeling language and rewriting system for convex optimization. In just a few lines of code, a user can specify a parametrized LLCP, solve it, and evaluate the derivative or its adjoint at a vector. This makes it possible to conduct sensitivity analyses of solutions, given perturbations to the parameters, and to compute the gradient of a function of the solution with respect to the parameters. We use the adjoint of the derivative to implement differentiable log-log convex optimization layers in PyTorch and TensorFlow. Finally, we present applications to designing queuing systems and fitting structured prediction models.



قيم البحث

اقرأ أيضاً

108 - Steven Diamond 2020
We present log-linear dynamical systems, a dynamical system model for positive quantities. We explain the connection to linear dynamical systems and show how convex optimization can be used to identify and control log-linear dynamical systems. We ill ustrate system identification and control with an example from predator-prey dynamics. We conclude by discussing potential applications of the proposed model.
We consider the problem of efficiently computing the derivative of the solution map of a convex cone program, when it exists. We do this by implicitly differentiating the residual map for its homogeneous self-dual embedding, and solving the linear sy stems of equations required using an iterative method. This allows us to efficiently compute the derivative operator, and its adjoint, evaluated at a vector. These correspond to computing an approximate new solution, given a perturbation to the cone program coefficients (i.e., perturbation analysis), and to computing the gradient of a function of the solution with respect to the coefficients. Our method scales to large problems, with numbers of coefficients in the millions. We present an open-source Python implementation of our method that solves a cone program and returns the derivative and its adjoint as abstract linear maps; our implementation can be easily integrated into software systems for automatic differentiation.
The goal of this paper is to derive new classes of valid convex inequalities for quadratically constrained quadratic programs (QCQPs) through the technique of lifting. Our first main result shows that, for sets described by one bipartite bilinear con straint together with bounds, it is always possible to sequentially lift a seed inequality that is valid for a restriction obtained by fixing variables to their bounds, when the lifting is accomplished using affine functions of the fixed variables. In this setting, sequential lifting involves solving a non-convex nonlinear optimization problem each time a variable is lifted, just as in Mixed Integer Linear Programming. To reduce the computational burden associated with this procedure, we develop a framework based on subadditive approximations of lifting functions that permits sequence-independent lifting of seed inequalities for separable bipartite bilinear sets. In particular, this framework permits the derivation of closed-form valid inequalities. We then study a separable bipartite bilinear set where the coefficients form a minimal cover with respect to the right-hand-side. For this set, we introduce a bilinear cover inequality, which is second-order cone representable. We argue that this bilinear cover inequality is strong by showing that it yields a constant-factor approximation of the convex hull of the original set. We study its lifting function and construct a two-slope subadditive upper bound. Using this subadditive approximation, we lift fixed variable pairs in closed-form, thus deriving a lifted bilinear cover inequality that is valid for general separable bipartite bilinear sets with box constraints.
We study three different measures of quantum correlations -- entanglement spectrum, entanglement entropy, and logarithmic negativity -- for (1+1)-dimensional massive scalar field in flat spacetime. The entanglement spectrum for the discretized scalar field in the ground state indicates a cross-over in the zero-mode regime, which is further substantiated by an analytical treatment of both entanglement entropy and logarithmic negativity. The exact nature of this cross-over depends on the boundary conditions used -- the leading order term switches from a $log$ to $log-log$ behavior for the Periodic and Neumann boundary conditions. In contrast, for Dirichlet, it is the parameters within the leading $log-log$ term that are switched. We show that this cross-over manifests as a change in the behavior of the leading order divergent term for entanglement entropy and logarithmic negativity close to the zero-mode limit. We thus show that the two regimes have fundamentally different information content. Furthermore, an analysis of the ground state fidelity shows us that the region between critical point $Lambda=0$ and the crossover point is dominated by zero-mode effects, featuring an explicit dependence on the IR cutoff of the system. For the reduced state of a single oscillator, we show that this cross-over occurs in the region $Nam_fsim mathscr{O}(1)$.
We analyze the set ${cal A}_N^Q$ of mixed unitary channels represented in the Weyl basis and accessible by a Lindblad semigroup acting on an $N$-level quantum system. General necessary and sufficient conditions for a mixed Weyl quantum channel of an arbitrary dimension to be accessible by a semigroup are established. The set ${cal A}_N^Q$ is shown to be log--convex and star-shaped with respect to the completely depolarizing channel. A decoherence supermap acting in the space of Lindblad operators transforms them into the space of Kolmogorov generators of classical semigroups. We show that for mixed Weyl channels the hyper-decoherence commutes with the dynamics, so that decohering a quantum accessible channel we obtain a bistochastic matrix form the set ${cal A}_N^C$ of classical maps accessible by a semigroup. Focusing on $3$-level systems we investigate the geometry of the sets of quantum accessible maps, its classical counterpart and the support of their spectra. We demonstrate that the set ${cal A}_3^Q$ is not included in the set ${cal U}^Q_3$ of quantum unistochastic channels, although an analogous relation holds for $N=2$. The set of transition matrices obtained by hyper-decoherence of unistochastic channels of order $Nge 3$ is shown to be larger than the set of unistochastic matrices of this order, and yields a motivation to introduce the larger sets of $k$-unistochastic matrices.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا