Downgrading NonlinearExpr to QuadExpr or AffExpr

Specific Domains Optimization (Mathematical)
,
1

Hi!

My question is related to Evaluating nonlinear expressions with variable references · Issue #4044 · jump-dev/JuMP.jl · GitHub

TL;DR: I want to take a JuMP expression and replace some of the VariableRef by numerical values. Although value(...) works for AffExpr and QuadExpr, it doesn’t for NonlinearExpr.

What I am doing right now is I recursively explore the NonlinearExpr and replace the VariableRef based on a dictionary. That works, but often the resulting NonlinearExpr is actually quadratic. Is there any way to downgrade that NonlinearExpr to QuadExpr or AffExpr?

Example:

julia> using JuMP

julia> m = Model(); @variable(m, x); @variable(m, y);

julia> expr = x / y
x / y

julia> expr.args[2] = 1
1

julia> expr.args[2] = 1;

julia> expr
x / 1

julia> typeof(expr)
NonlinearExpr (alias for GenericNonlinearExpr{GenericVariableRef{Float64}})

I feel like there should be something useful in the @expression implementation, but I don’t know enough metaprogramming to understand what’s going on there.

2

Is there any way to downgrade that NonlinearExpr to QuadExpr or AffExpr?

Nope.

I’d encourage you to just think up alternative input syntaxes.

using JuMP
model_1 = Model()
@variable(model_1, x_1)
payoff_1(x_1, p_2) = -x_1 * x_1 + x_1 * p_2
@objective(model_1, Max, payoff_1(x_1, 0.0))

model_2 = Model()
@variable(model_2, x_2)
payoff_2(p_1, x_2) = -x_2 * x_2 + p_1 * x_2
@objective(model_2, Max, payoff_2(0.0, x_2))

@objective(model_1, Max, 0.5 * payoff_1(x_1, 0.0) + 0.5 * payoff_1(x_1, 5.0))

It’s tricky to mix variables and parameters from multiple JuMP models because it is also conceptually tricky for the user. What variables and what constraints belong to which model, etc.

Make something that is very clear, even if it means more typing. If player 1 expects player 2 to follow a mixed strategy, perhaps something like:

using JuMP
model_1 = Model()
@variable(model_1, x_1)
@variable(model_1, p_2[1:3] in Parameter(0))
p_w = [0.2, 0.5, 0.3]
@objective(model_1, Max, sum(p_w[i] * (-x_1 * x_1 + x_1 * p_2[i]) for i in 1:3))
3

variable-model mismatch?

4

variable-model mismatch?

Edited :smile: I think it makes my point. This is tricky for users to get right.

5

The size of this parameter array wouldn’t be known before-hand. I could maybe dynamically add more parameters to this vector. I don’t know, however, how having a ton of parameters would impact the performance. I will give it a shot.

I noticed that something like x / p, where x is a variable and p is a parameter, results in a NonlinearExpr. So the processing of that “nonlinearity” is done by the solver? That is, it is the solver that must check that since p is a parameter, the objective is not actually nonlinear?

On the creation of the parameters, with the idea of simplifying the definition of the players, I tried making this behind the scenes. When the user defines the payoff, I go through the expression and replace each “unknown” VariableRef by a new parameter. But if I understood correctly, your suggestion is that making the user define the parameters, although more lengthy, would lead to less confusion. Is that right?

6

If you’re happy walking the expressions, then another alternative is for you to implement your own value function.

That is, it is the solver that must check that since p is a parameter, the objective is not actually nonlinear?

This depends on the solver. Some, like Ipopt, will replace the parameter by a constant. Others, like Gurobi, will implement the parameter by adding a new decision variable with fixed bounds. Thus, the objective will still be “nonlinear”. The solver internally may then be able to presolve the expression, but this is also solver- and problem-dependent.

7

I’ve opened a PR that adds simplify: Add simplify, derivative, and gradient from MOI.Nonlinear.SymbolicAD by odow · Pull Request #4047 · jump-dev/JuMP.jl · GitHub, which would help once you have replaced the parameters.