# Minimizing a logsumexp function with many terms (Convex.jl)

**URL:** <https://discourse.julialang.org/t/minimizing-a-logsumexp-function-with-many-terms-convex-jl/110853>\
**Category:** Optimization (Mathematical)\
**Tags:** convex-optimization\
**Created:** [February 27, 2024, 3:57pm UTC](https://discourse.julialang.org/t/minimizing-a-logsumexp-function-with-many-terms-convex-jl/110853 "2024-02-27T15:57:34Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![leapsheep](https://avatars.discourse-cdn.com/v4/letter/l/ccd318/32.png) [@leapsheep](https://discourse.julialang.org/u/leapsheep)\
**Post date:** [February 27, 2024, 3:57pm UTC](https://discourse.julialang.org/t/minimizing-a-logsumexp-function-with-many-terms-convex-jl/110853/1 "2024-02-27T15:57:35Z")

</div>

I am trying to minimize a function that depends on only few parameters, but contains a logsumexp with many terms in the sum, i.e. a function of the form

f(x) = \log \left(\sum\_{i=1}^n e^{a\_i \cdot x}\right)

where where a\_i, x \in \mathbb{R}^m. In my case, the number of terms n is very large, but the number of parameters m is small. Typically, I might have n \sim 10^5 and m \sim 10.

Naively putting this function into Convex.jl will result in O(n) variables and constraints being passed to the solver, which I am hoping to avoid.

Is there any way of representing this function efficiently?

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [February 27, 2024, 6:21pm UTC](https://discourse.julialang.org/t/minimizing-a-logsumexp-function-with-many-terms-convex-jl/110853/2 "2024-02-27T18:21:51Z")

</div>

Have you tried JuMP?

---

<div class="post-metadata">

**Author:** ![ericphanson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ericphanson/32/215186_2.png) [@ericphanson](https://discourse.julialang.org/u/ericphanson)\
**Post date:** [February 27, 2024, 6:49pm UTC](https://discourse.julialang.org/t/minimizing-a-logsumexp-function-with-many-terms-convex-jl/110853/3 "2024-02-27T18:49:53Z")

</div>

Could you post a minimal example? (See also [Please read: make it easier to help you](https://discourse.julialang.org/t/please-read-make-it-easier-to-help-you/14757)). It looks like one might be able to avoid `~n` variables/constraints but it would be easier to figure it out with some code to work with.

---

<div class="post-metadata">

**Author:** ![leapsheep](https://avatars.discourse-cdn.com/v4/letter/l/ccd318/32.png) [@leapsheep](https://discourse.julialang.org/u/leapsheep)\
**Post date:** [February 28, 2024, 8:52am UTC](https://discourse.julialang.org/t/minimizing-a-logsumexp-function-with-many-terms-convex-jl/110853/4 "2024-02-28T08:52:26Z")

</div>

Thanks for your replies. Here is a minimal example for a moderate number of terms:

```julia
using Convex, SCS
A = randn(1000, 10)
x = Variable(10)
problem = minimize(Convex.logsumexp(A*x))
solve!(problem, SCS.Optimizer)

```

This example has 10 variables and 1000 terms, and looking at the output of SCS shows that 1012 variables and 3002 constraints are passed to the solver:

```julia
problem: variables n: 1012, constraints m: 3002
cones: z: primal zero / dual free vars: 1
          l: linear vars: 1
          e: exp vars: 3000, dual exp vars: 0
settings: eps_abs: 1.0e-04, eps_rel: 1.0e-04, eps_infeas: 1.0e-07
          alpha: 1.50, scale: 1.00e-01, adaptive_scale: 1
          max_iters: 100000, normalize: 1, rho_x: 1.00e-06
          acceleration_lookback: 10, acceleration_interval: 10
lin-sys: sparse-direct-amd-qdldl
          nnz(A): 13002, nnz(P): 0

```

I found that problems with more than 10.000 terms easily consume \>20GB of memory.

It is my understanding that JuMP would require me to formulate the problem in a solver-compatible way on my own, which I am not sure how to do (with less than O(n) variables).

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [February 28, 2024, 9:25am UTC](https://discourse.julialang.org/t/minimizing-a-logsumexp-function-with-many-terms-convex-jl/110853/5 "2024-02-28T09:25:22Z")

</div>

> [@leapsheep](#):
>
> It is my understanding that JuMP would require me to formulate the problem in a solver-compatible way on my own, which I am not sure how to do

I found a relevant section of the docs, haven’t tried it myself though:

[https://jump.dev/JuMP.jl/stable/tutorials/conic/tips\_and\_tricks/#Log-sum-exp](https://jump.dev/JuMP.jl/stable/tutorials/conic/tips_and_tricks/#Log-sum-exp)

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [February 28, 2024, 9:32am UTC](https://discourse.julialang.org/t/minimizing-a-logsumexp-function-with-many-terms-convex-jl/110853/6 "2024-02-28T09:32:12Z")

</div>

The following seems to work but it has many variables still

```julia
using JuMP, SCS

N, M = 10, 1000
A = randn(M, N)

model = Model(SCS.Optimizer)

@variable(model, x[j = 1:N])
@variable(model, y[i = 1:M])
@variable(model, u[i = 1:M])
@variable(model, t)

@objective(model, Min, t)

@constraint(model, A * x .== y)
@constraint(model, sum(u) <= 1)
@constraint(model, [i = 1:M], [y[i] - t, 1, u[i]] in MOI.ExponentialCone())

optimize!(model)
value(t)

```

---

<div class="post-metadata">

**Author:** ![leapsheep](https://avatars.discourse-cdn.com/v4/letter/l/ccd318/32.png) [@leapsheep](https://discourse.julialang.org/u/leapsheep)\
**Post date:** [February 28, 2024, 9:57am UTC](https://discourse.julialang.org/t/minimizing-a-logsumexp-function-with-many-terms-convex-jl/110853/7 "2024-02-28T09:57:01Z")

</div>

Thanks a lot! I just tried your JuMP code with a larger number of terms and it seems to work. While this actually creates more variables and constraints than the Convex.jl version, the memory requirement is much, much lower (50000 terms seem to use ~1GB). So maybe a clever reformulation of the problem is actually not needed.

Maybe the excess memory requirement is an issue with Convex.jl (possibly related to [this](https://github.com/jump-dev/Convex.jl/issues/254))?

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [February 28, 2024, 10:14am UTC](https://discourse.julialang.org/t/minimizing-a-logsumexp-function-with-many-terms-convex-jl/110853/8 "2024-02-28T10:14:29Z")

</div>

More generally, Convex.jl is not actively maintained, whereas the JuMP people are extremely reactive, so betting on the latter is a good call for current projects

---

<div class="post-metadata">

**Author:** ![ericphanson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ericphanson/32/215186_2.png) [@ericphanson](https://discourse.julialang.org/u/ericphanson)\
**Post date:** [February 28, 2024, 11:03am UTC](https://discourse.julialang.org/t/minimizing-a-logsumexp-function-with-many-terms-convex-jl/110853/9 "2024-02-28T11:03:59Z")

</div>

You could try Convex#master. Convex has not been maintained much over the years but we merged a big refactor and Oscar (who does an amazing job maintaining tons of JuMP packages) also spent some time cleaning up Convex, fixing bugs and writing tests. Those changes haven’t made it to a release yet though.

---

<div class="post-metadata">

**Author:** ![odow](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/odow/32/28685_2.png) [@odow](https://discourse.julialang.org/u/odow)\
**Post date:** [February 29, 2024, 7:17am UTC](https://discourse.julialang.org/t/minimizing-a-logsumexp-function-with-many-terms-convex-jl/110853/10 "2024-02-29T07:17:39Z")

</div>

The smaller JuMP formulation is:

```julia
using JuMP, SCS
N, M = 10, 1_000
A = randn(M, N)
model = Model(SCS.Optimizer)
@variable(model, x[1:N])
@variable(model, u[1:M])
@variable(model, t)
@objective(model, Min, t)
@constraint(model, sum(u) <= 1)
@constraint(model, [i in 1:M], [A[i, :]' * x - t, 1, u[i]] in MOI.ExponentialCone())
optimize!(model)
value(t)

```

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [February 29, 2024, 9:38am UTC](https://discourse.julialang.org/t/minimizing-a-logsumexp-function-with-many-terms-convex-jl/110853/11 "2024-02-29T09:38:58Z")

</div>

Do you think it changes anything in terms of performance?

---

<div class="post-metadata">

**Author:** ![odow](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/odow/32/28685_2.png) [@odow](https://discourse.julialang.org/u/odow)\
**Post date:** [February 29, 2024, 6:02pm UTC](https://discourse.julialang.org/t/minimizing-a-logsumexp-function-with-many-terms-convex-jl/110853/12 "2024-02-29T18:02:26Z")

</div>

Not really. It just avoids adding the `y` variable and constraints.