6
$\begingroup$

How do I turn my convex constraints (described below) into constraints that are DCP so that I can solve them in CVXPy? Is there some ``cheat sheet'' of standard tricks?

I'm trying to implement the convex program highlighted in section 3.2 of the paper Equilibria for Economies with Production: Constant-Returns Technologies and Production Planning Constraints by Drs. Kamal Jain and Kasturi Varadarajany. I've reduced a model I am working on in my research to a special case of Arrow-Debreu with Constant Returns Technology (AD economy) and would like to implement the constraint satisfaction problem in that paper to run some simulations/find equilibria.

In case it is helps, I will describe the convex program specifically in my setting now (depending on the reader, it may be easier to just glance at the paper's section 3). If you'd rather look at the paper skip the bit between lines:


Using CVXPy I am trying to solve a convex program in terms of non-negative variables

  1. $p_1,\dots,p_n,p_{n+1},\dots,p_{n+m}$ which represent prices of the goods. Here $n$ is the number of goods in the AD economy and $m$ is the number of consumers in the AD economy. They introduce the goods $n+1$ through $n+m$ for the sake of writing convex constraints (basically they treat utility as a commodity and force consumers to by their utility from an exclusive producer which produces their utility instead of having them directly buy goods which they derive utility from). I'm implementing this as a vector form CVXPy variable of length $n+m$.
  2. $x_{1},\dots,x_{m}$ which, for each consumer $i$, represents the demand of that consumer for good $n+i$. As I described briefly in above, consumers have utility only for a good representing their own utility which a special producer will produce for them and they will sell their endowments to maximize the amount of this good they receive. I'm implementing this as a vector CVXPy variable of length $m$.
  3. $z_1,\dots,z_{n+m}$ which, for each producer $k$, is a vector $z_k = (z_{k1},\dots,z_{kn})$ describing the inputs used by the $k^{th}$ producer. Note that, each producer has a function (described in the convex program below) describing how to turn these input into output. I'm implementing this as a matrix CVXPy variable of dimensions $(n+m, n)$.
  4. $q_1,\dots,q_{n+m}$ which, for each producer $k$, is the scalar output of their production function (which outputs only good $j$). In other words, this variable described $q_k = f_k(z_k)$. I'm implementing this as a vector CVXPy variable of length $n+m$.

I'm writing the convex program as:

\begin{align}\min&\quad1\\\text{s.t.}&\quad p_{n+i}x_{i} \geq \sum\limits_{j=1}^{n} p_{j} E_{ij} \text{, for } 1 \leq i \leq m\\&\quad q_k \leq \sum\limits_{j=1}^{n} z_{kj} \text{, for } 1 \leq k \leq n\\&\quad q_{n+k} \leq \left(\sum\limits_{j=1}^{n} U_{kj} z_{(n+k),j}^{\rho}\right)^{\frac{1}{\rho}} \text{, for } 1 \leq k \leq m\\&\quad p_k \leq A_{kj} \cdot p_{j} \text{, for } 1 \leq k \leq n \text{ and for } 1 \leq j \leq n\\&\quad p_{n+k}^{1-\frac{1}{1-\rho}} \geq \sum\limits_{j=1}^{n} U_{kj}^{\frac{1}{1-\rho}} p_{j}^{1-\frac{1}{1-\rho}} \text{, for } 1 \leq k \leq m\\&\quad\sum\limits_{k=1}^{n+m} z_{kj} \leq q_j + \sum_{i=1}^{m} E_{ij} \text{, for } 1 \leq j \leq n\\&\quad x_i \leq q_{n+i} \text{, for } 1 \leq i \leq m\end{align}

Where $E$ is a constant matrix of dimension $(m,n)$ denoting the consumers' initial "endowment" of goods, $U$ is a constant matrix of dimension $(m,n)$ denoting the utility coefficient of each good for each consumer, $\rho$ is a scalar constant on the open interval $[0,1]$ which describes the "elasticity of substitution" in the economy, and finally $A$ is a constant binary matrix (used to encode a "local" notion on goods).

Finally, notice that when we make the substitution $p_j = e^{\psi_j}$ in these constraints all of them become convex.


After writing this into CVXPy (with the substitution to $e^{\psi_j}$ done), I am having problems in the first constraint with $p_{n+i}x_{i}$ not being dcp, in the third constraint where the CES (constant elasticity of substitution) utility function is not dcp, and in the fifth constraint since again the CES function is not dcp.

Could anybody help me massage these three sub-expressions into dcp sub-expressions? I'm at a loss and this would be a huge help! Thanks!

Some Notes:

  • By DCP I mean "Disciplined Convex Programming." More info can be found here.
  • You may have noticed that in my AD economy I have exactly $n$ producers and $n$ goods (i.e. one producer per good that produces an amount of it's output good exactly equal to the sum of the amount of other goods it take as input). In reality there are fewer producers than goods, but explaining this number is rather involved (it comes out of the proof that my model reduces to it, but it shouldn't affect anything in this case.)
  • Simply stated I am having trouble getting CVXPy to accept the following constraints: \begin{align}e^{\psi_{n+1}}x_{i} &\geq \sum\limits_{j=1}^{n} e^{\psi_{j}} E_{ij}\\e^{\psi_{n+k}\left(1-\frac{1}{1-\rho}\right)} &\geq \sum\limits_{j=1}^{n} U_{kj}^{\frac{1}{1-\rho}} e^{\psi_{j}\left(1-\frac{1}{1-\rho}\right)}\\q_{n+k} &\leq \left(\sum\limits_{j=1}^{n} U_{kj} z_{(n+k),j}^{\rho}\right)^{\frac{1}{\rho}}\end{align} where the $\psi$'s, $z$'s, and $x$'s are the non-negative variables in these constraints.
$\endgroup$
  • 1
    $\begingroup$ Start off with this quick read ask.cvxr.com/t/why-isnt-cvx-accepting-my-model-read-this-first/… Mosek Modeling Cookbook docs.mosek.com/modeling-cookbook/index.html will help you with convex optimization modeling, including DCP and "Extreme" DCP (as Mosek calls it). Also, read and work the problems in web.stanford.edu/~boyd/cvxbook .As for this problem, how have YOU proved all the constraints are convex? That may provide you a roadmap as to how to get a DCP formulation, it such a formulation is possible (not all convex optimization problems can be formulated via DCP). $\endgroup$ – Mark L. Stone Oct 19 '19 at 22:57
  • $\begingroup$ Thanks! Proving this is convex is rather straightforward. In fact, focusing on the constraints that are causing problems (since the rest clearly by DCP): one is a multiplication of two non-negative variables (which live in convex domains)) the other two are easy to check are concave since they are CES utilities (this is a rather straightforward proof). Neither requires any fancy machinery so hopefully they are susceptible to DCP. I'll definitely be checking out this sources though (haven't seen anything that does it yet, but I also haven't fully dived deep in them)! Thanks again! $\endgroup$ – Dupin Oct 20 '19 at 4:39
  • $\begingroup$ Could you maybe add a note at the end, highlight the first problem that you have issues with, already using the variable transformation? Without the transformation, the constraint looks a little like a rotated second-order cone. Did you also consider geometric programming, where the same variable transformation is used? web.stanford.edu/~boyd/papers/gp_tutorial.html $\endgroup$ – Robert Schwarz Oct 20 '19 at 5:21
  • 1
    $\begingroup$ The third constraint is directly the concave variant of the pnorm atom in CVXPy for the pseudo-p-norm. It is an instance of the last sentence of docs.mosek.com/modeling-cookbook/powo.html#norm-cones if you want to split it into individual cones. After the $\exp$ substitution, the first and fifth constraint are both of the form $\sum\limits_i\exp y_i<C$, so it should not be a problem. $\endgroup$ – Michal Adamaszek Oct 22 '19 at 7:34
  • 2
    $\begingroup$ Just wanted to report in. Managed to get it working. Thanks for all the help! The key was in setting dummy variables like Michal's $y_i$ above. $\endgroup$ – Dupin Oct 22 '19 at 22:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.