BilevelJuMP: Setting start values for lower level dual variables in ProductMode()

Specific Domains Optimization (Mathematical)
1

Hi everyone,

I have started to use BilevelJuMP and I’m really beginning to enjoy its flexibility!
I’m trying to solve a larger scale calibration problem, where the lower level is a QP with affine (in-)equality constraints, and the top-level tries to minimize the squared euclidean distance between some lower level variables and their target values. The problem is fairly complicated to solve at full size, which is why I wanted to use the following approach to ProductMode():
Since the lower level is quick to solve, run it as a separate baseline model with fixed upper level parameters and use primal/dual values as a starting point for the bilevel model.
To set the primal lower variables of the bilevel problem “GGM_calibrator” to the baseline results of “GGM_Baseline”, I used the following code:

for var in all_variables(GGM_Baseline)
            set_start_value(variable_by_name(GGM_calibrator, name(var)), value(variable_by_name(GGM_Baseline, name(var)) ) )
end

In addition, I set the upper level variable start to their fixed value of the baseline run, they are not further restricted by any additional constraints.
This seems to work fine, the objective value at this starting point is approximately as expected (according to the Ipopt log).
However, setting duals of the lower level does not seem to have the desired effect, as there still is a significant primal infeasibility for the single level ProductMode() reformulation:

for (F, S) in list_of_constraint_types(GGM_Baseline)
    if F != VariableRef && S == MOI.EqualTo{Float64}
        for ctr in all_constraints(GGM_Baseline, F, S) 
            set_dual_start_value(constraint_by_name(GGM_calibrator, name(ctr)), dual(constraint_by_name(GGM_Baseline, name(ctr)) ) )
        end
    elseif F != VariableRef && S == MOI.LessThan{Float64}
        for ctr in all_constraints(GGM_Baseline, F, S) 
            set_dual_start_value(constraint_by_name(GGM_calibrator, name(ctr)), dual(constraint_by_name(GGM_Baseline, name(ctr)) ) )
        end
    end
end

The reason for separating equalities from inequalities is to be able to manipulate them individually.
Checking the dual starts using dual_start_value() shows, that the code above seems to do the job as well.
However, Ipopt seems to indicate that the ProductMode() reformulation starting point is still not feasible.
I tried playing around with signs of the equality duals, but this does not help either.
Am I missing something here? Could it be that set_dual_start_value() is an inappropriate choice and does not work as I think it does?

Thanks very much in advance, any help is appreciated.

Also, thanks to @joaquimg and colleagues for this amazing package :smiley:

PS: In addition, I was wondering about what would be the most elegant way to use an iterative procedure, i.e. to decrease the regularization parameter of ProductMode(), while using results from the previous iteration as a starting point?

2

I do not have much experience with using dual starts in Ipopt. Your code seems correct.

You are passing both primal and dual starts at the very same time?

Did you try large regularization values?
I can imagine small ones being infeasible due to tolerances in solving the isolated lower level problem.

In addition, I was wondering about what would be the most elegant way to use an iterative procedure, i.e., to decrease the regularization parameter of ProductMode(), while using results from the previous iteration as a starting point?

This is something I want to automate as well. I would probably do it inside the optimize function to re-use the model already built. We can discuss it in an issue or PR.

3

It’s late so I’m not certain that I understood everything correctly :sweat_smile: If I did though, the dual variables have no influence on primal feasibility.
Edit: an infeasible initial point is not a problem for IPOPT, which is an infeasible interior-point method.

4

Hi @cvanaret,
the model I’m dealing with is a bilevel optimization problem. Reformulating the lower level KKTs in product form and adding a regularization term allows to solve it as a single level model (as implemented in BilevelJuMP via ProductMode() ). That is why the lower level duals are primal variables of the actual model passed to the solver (and should affect primal feasibility).
Since I can solve the lower level for fixed upper level variables and there are no further upper level constraints, the starting point should be feasible (but not necessarily good). My problem is that Ipopt indicates the starting point is infeasible.

5

Thanks for the quick reply @joaquimg.

I’m setting starts at different times, but this should not be an issue.
Since primal infeasibility is usually significant (>1e+1), it should not be related to tolerances.

However, I believe I was able to find the reason for the primal infeasibility.
For some reason, it seems that the lower level dual variables equal to 0 are not correctly set in Ipopt.
Similar to the code above, I was able to query the set starting values (using dual_start_value() and start_value() ) of a toy model. The starting values look as follows:

==, eq_mass_bal[DEU,DEU,L,2015]: 85102.54945586761
==, eq_stor_cycle[(:DEU, :DEU, :SEAS, :L, 2015)]: 472.12310036263966
>=, NNG_D_A[GALB_ITA,2015]: 6522.12
>=, NNG_D_X[DEU,SEAS,2015]: 5000.0
>=, NNG_D_W[DEU,SEAS,2015]: 150.0
>=, NNG_Q_P[(:DEU, :DEU, :R1, :L, 2015)]: 0.0
>=, NNG_Q_S[(:DEU, :DEU, :L, 2015)]: 0.0
>=, NNG_F_A[(:DEU, :GALB_ITA, :L, 2015)]: 4.158
>=, NNG_F_I[(:DEU, :DEU, :SEAS, :L, 2015)]: 0.0
>=, NNG_F_X[(:DEU, :DEU, :SEAS, :L, 2015)]: 1325.9779104954403
<=, eq_cap_a[GALB_ITA,L,2015]: -0.0
<=, eq_cap_p[(:DEU, :DEU, :R1, :L, 2015)]: -75586.5451727892
<=, eq_cap_x[DEU,SEAS,L,2015]: -0.0
<=, eq_cap_w[DEU,SEAS,2015]: -0.0
<=, eq_lim_a[GALB_ITA,2015]: -0.0
<=, eq_lim_x[DEU,SEAS,2015]: -0.0
<=, eq_lim_w[DEU,SEAS,2015]: -0.0
var, Q_S[(:DEU, :DEU, :L, 2015)]: 16.84987
var, Q_P[(:DEU, :DEU, :R1, :L, 2015)]: 16.84987
var, F_A[(:DEU, :GALB_ITA, :L, 2015)]: 0.0
var, F_I[(:DEU, :DEU, :SEAS, :L, 2015)]: 8.71186666981928e-14
var, D_X[DEU,SEAS,2015]: 0.0
var, calib_int[(:DEU, :L, 2015)]: 1.0
var, F_X[(:DEU, :DEU, :SEAS, :L, 2015)]: 8.581188669771992e-14
var, D_W[DEU,SEAS,2015]: 0.0
var, D_A[GALB_ITA,2015]: 0.0

, where ==,>=,<= indicates duals to (in-)equalities, and var indicates a lower level primal variable.
However, when taking a look at the initial points of iteration 0 in IPOPT, this looks as follows:

DenseVector "curr_x" with 26 elements:
curr_x[    1]= 6.5221199999999999e+03	g
curr_x[    2]= 5.0000000000000000e+03	g
curr_x[    3]= 1.5000000000000000e+02	g
curr_x[    4]= 9.9999900000000003e-03    (g)
curr_x[    5]= 9.9999900000000003e-03    (g)
curr_x[    6]= 4.1580000000000004e+00	g
curr_x[    7]= 9.9999900000000003e-03    (g)
curr_x[    8]= 1.3259779104954403e+03	g
curr_x[    9]=-9.9999900000000003e-03    (l)
curr_x[   10]=-7.5586545172789207e+04	l
curr_x[   11]=-9.9999900000000003e-03    (l)
curr_x[   12]=-9.9999900000000003e-03    (l)
curr_x[   13]=-9.9999900000000003e-03    (l)
curr_x[   14]=-9.9999900000000003e-03    (l)
curr_x[   15]=-9.9999900000000003e-03    (l)
curr_x[   16]= 0.0000000000000000e+00	v
curr_x[   17]= 0.0000000000000000e+00	v
curr_x[   18]= 0.0000000000000000e+00	v
curr_x[   19]= 1.6849869999999999e+01	v
curr_x[   20]= 1.6849869999999999e+01	v
curr_x[   21]= 0.0000000000000000e+00	v
curr_x[   22]= 8.7118666698192804e-14	v
curr_x[   23]= 8.5811886697719921e-14	v
curr_x[   24]= 1.0000000000000000e+00	v
curr_x[   25]= 8.5102549455867615e+04	e
curr_x[   26]= 4.7212310036263966e+02	e

, where v,e,l,g are edited and indicate my guess for a corresponding primal variable, or a lower level dual to equalities (e) or lesser/greater inequalites (l,g).

It seems that primals and duals not equal zero are set correctly. Duals equal to zero are not set correctly, they are set to +/- 9.9999900000000003e-03.
This behavior even persists when not explicitly setting lower dual start values to zero (for example by only iterating set_dual_start_value() over nonzero duals).

I guess, setting dual starts to zero does not really set them to zero and the default behavior also does not do this?
If so, does anyone know the recommended way to set the dual start to zero if desired?

Edit: The problem was in my Ipopt settings. While I did use the Ipopt options as indicated here: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.589.5002&rep=rep1&type=pdf (p.672-673), I forgot to set “warm_start_init_point” to “yes”. The solution was rather simple in the end…

PS: I am interested in taking a shot at the iterative product mode, but not sure if I can get it running in reasonable time. I will open an issue in the next few days and take a look at it :smiley:

1 Like