# Non-linear gradient descent under linear constraints?

**URL:** <https://discourse.julialang.org/t/non-linear-gradient-descent-under-linear-constraints/66965>\
**Category:** Optimization (Mathematical)\
**Created:** [August 25, 2021, 8:40am UTC](https://discourse.julialang.org/t/non-linear-gradient-descent-under-linear-constraints/66965 "2021-08-25T08:40:20Z")\
**Posts on this page:** 10\
**Page:** 1

<div class="post-metadata">

**Author:** ![lrnv](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lrnv/32/19373_2.png) [@lrnv](https://discourse.julialang.org/u/lrnv)\
**Post date:** [August 25, 2021, 8:40am UTC](https://discourse.julialang.org/t/non-linear-gradient-descent-under-linear-constraints/66965/1 "2021-08-25T08:40:20Z")

</div>

Hey,

Is there a pure julia implementation of a non-linear gradient descent under linear matrix/vector equality and inequality constraints ?  
My problem is given as :

\min\limits\_{Ax=b,\, x\ge 0}\, f(x)

where f is non-linear (but written in Julia, differentiable and stuff), A is a matrix and b a vector. Im looking for a local gradient descent under constraints, but I need pure Julia code (to pass in custom types of numbers).

---

<div class="post-metadata">

**Author:** ![mohamed82008](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mohamed82008/32/18171_2.png) [@mohamed82008](https://discourse.julialang.org/u/mohamed82008)\
**Post date:** [August 25, 2021, 10:09am UTC](https://discourse.julialang.org/t/non-linear-gradient-descent-under-linear-constraints/66965/2 "2021-08-25T10:09:35Z")

</div>

Check [FrankWolfe.jl: scalable constrained optimization | Mathieu Besançon | JuliaCon2021 - YouTube](https://www.youtube.com/watch?v=GIVLzBeoPuU).

---

<div class="post-metadata">

**Author:** ![mohamed82008](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mohamed82008/32/18171_2.png) [@mohamed82008](https://discourse.julialang.org/u/mohamed82008)\
**Post date:** [August 25, 2021, 10:16am UTC](https://discourse.julialang.org/t/non-linear-gradient-descent-under-linear-constraints/66965/3 "2021-08-25T10:16:35Z")

</div>

Percival.jl and MadNLP.jl should also solve this problem.

---

<div class="post-metadata">

**Author:** ![lrnv](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lrnv/32/19373_2.png) [@lrnv](https://discourse.julialang.org/u/lrnv)\
**Post date:** [August 25, 2021, 10:18am UTC](https://discourse.julialang.org/t/non-linear-gradient-descent-under-linear-constraints/66965/4 "2021-08-25T10:18:14Z")

</div>

The FrankWolfe.jl looks promissing, i’ll start by this one. I knew about Percival (already tried, not working well since it does not ‘use’ the fact that the constraints are linear…), and I do not know about MadNLP.jl, i’ll try this one next.

Thanks a lot !

---

<div class="post-metadata">

**Author:** ![mohamed82008](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mohamed82008/32/18171_2.png) [@mohamed82008](https://discourse.julialang.org/u/mohamed82008)\
**Post date:** [August 25, 2021, 10:20am UTC](https://discourse.julialang.org/t/non-linear-gradient-descent-under-linear-constraints/66965/5 "2021-08-25T10:20:06Z")

</div>

Some algorithms in ProximalAlgorithms.jl or COSMO.jl may also be able to handle this problem but their API is not straightforward and I can’t confirm for sure if the implementation supports nonlinear f although some algorithms should.

---

<div class="post-metadata">

**Author:** ![lrnv](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lrnv/32/19373_2.png) [@lrnv](https://discourse.julialang.org/u/lrnv)\
**Post date:** [August 25, 2021, 10:21am UTC](https://discourse.julialang.org/t/non-linear-gradient-descent-under-linear-constraints/66965/6 "2021-08-25T10:21:10Z")

</div>

I can confirm that COSMO does not handle non linear objective, only quadratic ones (but it’s great, and can be interfaced via MathOpt so Convex.jl and JuMP are working with it). I do not know about ProximalAlgorithms.

---

<div class="post-metadata">

**Author:** ![mohamed82008](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mohamed82008/32/18171_2.png) [@mohamed82008](https://discourse.julialang.org/u/mohamed82008)\
**Post date:** [August 25, 2021, 10:23am UTC](https://discourse.julialang.org/t/non-linear-gradient-descent-under-linear-constraints/66965/7 "2021-08-25T10:23:24Z")

</div>

If factorising A is an option, consider using a nullspace formulation. Then Percival will probably do better. Also MMA from Nonconvex can be used in this case. MMA only support inequality constraints not equality.

---

<div class="post-metadata">

**Author:** ![lrnv](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lrnv/32/19373_2.png) [@lrnv](https://discourse.julialang.org/u/lrnv)\
**Post date:** [August 25, 2021, 10:38am UTC](https://discourse.julialang.org/t/non-linear-gradient-descent-under-linear-constraints/66965/8 "2021-08-25T10:38:04Z")

</div>

A is ‘wide’, so that there are fewer constraints than variables. Factorising it is an option yes, I can construct a generator for elements of \{x,\, Ax = b\}. Is that the nullspace formulation you are taling about ? Would’nt that complexify the conic x \ge 0 constraint ?

Anyway you gave me a few options 🙂

---

<div class="post-metadata">

**Author:** ![mohamed82008](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mohamed82008/32/18171_2.png) [@mohamed82008](https://discourse.julialang.org/u/mohamed82008)\
**Post date:** [August 25, 2021, 11:01am UTC](https://discourse.julialang.org/t/non-linear-gradient-descent-under-linear-constraints/66965/9 "2021-08-25T11:01:51Z")

</div>

If you find the nullspace Y of A such that A Y = 0 and you have a single feasible solution x\_0 = A \backslash b then every feasible solution can be written as x\_0 + N y where y is a vector of “free” nullspace coordinates. The constraints x \geq 0 then become linear inequality constraints x\_0 + N y \geq 0 and f(x) is replaced by f(x\_0 + N y).

---

<div class="post-metadata">

**Author:** ![lrnv](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lrnv/32/19373_2.png) [@lrnv](https://discourse.julialang.org/u/lrnv)\
**Post date:** [August 25, 2021, 1:46pm UTC](https://discourse.julialang.org/t/non-linear-gradient-descent-under-linear-constraints/66965/10 "2021-08-25T13:46:19Z")

</div>

Yes, that I can do. But it does not help me that much.

Actually, the constraints can also be given i another form, for which I managed to derive the LMO from FranckWolfe.jl. I’m now gonna try to to make FranckWolfe work 🙂