Maximize/minimize non-linear equations involving real numbers in Prolog

Help!
1

Hi!

I use clpr (for reals) and clpfd (for integers). clpr can maximize or minimize linear equations but not non-linear ones. Conversely, clpfd can maximize or minimize non-linear equations but only deals with integers. Because i have fractions in my application I end up with expressions like:

X2 #= 8 * X1 * X3 // (10 * 100)

Where 0-1 is transformed to 0-100

But i would like for my end users to be able to just write the simpler {X2 = 0.8 * X1 * X3}, and then maximize/minimize such expressions.

From Stack overflow i got some suggestions about algorithms that might be able to do this. But i was not able to find any libraries that might be used with SWI Prolog (or Swish which would be the ideal). Any suggestions would be appreciated :slight_smile:

Cheers/JCR

2

The general case is exceedingly difficult. I am aware of quadratic optimization as a field, and other domains are possible, but just ‘non-linear’ is unlikely to have an optimal solution of the sort clp varieties are geared to achieve. Do you have specific kinds of non-linears in mind, or are you up for an iterative approximation to maximization?

1 Like
3

@abaljeu, thanks for responding!

The models in my problem are mostly a weighted sum of variables and all possible products between these variables (ANOVA models), e.g.

Y = 2 + 0.5 * X1
Y = 1 + 0.2 * X1 + 0.6 * X2 + 0.2 * X1 * X2
Y = 2 + 0.1 * X1 + 0.9 * X2 + 0.5 * X3 - 0.1 * X1 * X2 * X3

and so on, in which i want to maximise or minimise Y.

Maybe also exponential cases like:

Y = 2 + 3 ^ X

Iteration would be perfectly fine! I don’t think i will have any functions that have local minima/maxima… And the number of Xs won’t be to high either, certainly not more than 10.

Cheers/JC

4

are your variables all positive?

5

Some negative, like X2 in Y = 2 * X1 - 3 * X2.

6

I asked because if you have Y = X1*X2 and X1 and X2 range between [-1,1], you have maxima and (1,1,1) and (-1,-1,1) and minima at (-1,1,-1) and (1,-1,-1). This tends to contradict your expectation that the functions are strictly increasing (don’t have local maxima/minima).

7

Aha i thought you meant the sign in front of a variable like X2. In my application there should not be any negative numbers; i.e. the domain should be X >= 0.

8

I am not aware of libraries to solve your problem, but you might look at a Newton-Raphson type algorithm:

Pick a starting vector X = X_0 (say [0.5, 0.5, 0.5, 0.5] for 4D)
Evaluate Y, and compute a gradient for X.
Adjust X along the gradient.
Repeat.
Stop when the gradient is kind of flat.

9

Thanks; i was thinking along the same lines!

10

You can also use pack lfbgs

https://www.swi-prolog.org/pack/list?p=lbfgs

11

Thanks for the tip!

12

Another option could be to use the pack clpBNR.