3
$\begingroup$

I'm looking to find a computationally efficient solution to a large system of nonlinear equations. I'm trying to maximize the following function:

$$ f(\vec{x}) = \sum_i^N C_i (x_i-A_i)x_i^{\epsilon_{ii}} \prod_{j\not = i}^N x_j^{\epsilon_{ij}}$$

Subject to the constraints: $$ C_i > 0 \quad\forall\: i$$ $$ x_i > A_i > 0 \quad\forall\: i$$ $$ {\epsilon}_{ii} < -1 \quad\forall\: i$$ $$ {\epsilon}_{ij} \ge 0 \quad\forall\: i,j \quad\text{s.t.}\; i \not= j$$

I've been able to write a few solvers that can solve this, but I'm struggling to find/write a solver that can scale to $N=1000000$ (one million). Unfortunately, the $\epsilon_{ij}$ matrix is dense.

Things I've tried:

  • scipy.optimize BFGS algorithm: takes 8 hours when N = 2000
  • a fixed point solver: takes 3 hours for N = 10000, but seems to get stuck in local maxima

I would really appreciate advice on what to investigate next. I was gonna start going down the path of either (a) hand deriving the Jacobian and Hessian and taking another stab at using a scipy.optimize solver or (b) trying to coerce this to look more like a geometric programming problem and using gpkit. I'm pretty new to optimization so I could very well be missing something obvious - please don't hesitate to point out anything I've overlooked!

If it helps, I do have distributed computing resources available (spark, dask, kubernetes, etc).

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ I think this is non-convex, and not formulatable as a Generalized Geometric Program. The objective function is a posynomial (at least it would be if $y_i = x_i -A$ were introduced in place of $x_a - A$ as a new variable along with the equality constraints). It could then be minimized in gpkit or CVXPY. But I don't believe minimizing the reciprocal (as a way of maximizing $f$) would be allowed, as that would be a non-convex problem. $\endgroup$ – Mark L. Stone Dec 12 '19 at 16:59
  • 4
    $\begingroup$ How would you even store $\epsilon_{ij}$ if you had a million variables? That requires $10^{12}$ memory locations, or about $10^4$ GB in floating point precision. Similarly, evaluating the objective function requires at least reading this many bytes from memory, which will surely take a very long time. $\endgroup$ – Wolfgang Bangerth Dec 13 '19 at 16:40

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.