I am trying to find a “real-valued” solution of a fixed point problem which nests a constrained linear programming problem by using NLsolve.jl and Gurobi.jl. Concretely, the outer problem is a nonlinear system of equations to find a fixed point given the inner solution by NLsolve.jl, whereas the inner problem solves a linear programming given the outer solution by Gurobi.jl. Technically, it is a bilevel problem. Here is the example code.
using Gurobi, NLsolve N = 2 function inner_linear_programming(outer_sol) utility = zeros(N,N) # coefficients of utility are arbitrary but continuous in outer_sol utility[1,1] = 2 * outer_sol[1,1]; utility[1,2] = 2 * outer_sol[2,1]-1; utility[2,1] = 2 * outer_sol[1,2]; utility[2,2] = 2 * outer_sol[1,1]-1; # vectorize utility term for Gurobi format f_utility = zeros(N*N) for i in 1:N for j in 1:(N) f_utility[(i-1)*N+j] = utility[i,j]; end end # feasibility constraints mu: A_feas_mu_const = [0.0 1.0 1.0 0.0] b_feas_mu_const = 1.0 # feasibility constraints rho(measure const): A_feas_rho_const = [1.0 1.0 0.0 0.0; 0.0 0.0 1.0 1.0] b_feas_rho_const = ones(N) A_feas_mu_rho = vcat(A_feas_mu_const, A_feas_rho_const) b_feas_mu_rho = vcat(b_feas_mu_const, b_feas_rho_const) # solve inner problem by plain-Gurobi env = Gurobi.Env() setparam!(env, "Presolve", 0) # For Gurobi format @time model = gurobi_model(env; name = "lp_01", # minimizing problem f = -f_utility, # vectorized coefficients in LP objective function Aeq = A_feas_mu_rho, # LHS of equality constraints matrix beq = b_feas_mu_rho, # RHS of equality constraints (vector) lb = zeros(N*N), # inequality consraints vectorized ub = ones(N*N) # inequality consraints vectorized ) @time Gurobi.optimize(model) sol = get_solution(model) opt_x = convert(Array, transpose(reshape(sol, N, N))) return opt_x end function f!(F, x) # outer fixed point problem # solve 0 = inner_linear_programming(x) - x F = inner_linear_programming(x) - x @show inner_linear_programming(x) @show x end res=NLsolve.nlsolve(f!, [0.0 1.0; 1.0 0.0]) res.zero # solution found by NLsolve (not converged) @show inner_linear_programming(res.zero) - res.zero # it should be zeros if it is evaluated at fixed point
The problem has a real-valued fixed point solution theoretically by Kakutani’s fixed point theorem, allowing arbitrary (continuous) specification of coefficients of objective function. However, NLsolve.jl (root-finding)solver cannot find the “real-valued” solution and the inner linear programming problem oscillates between integer solutions. If the true solution is integer, NLsolve.jl can find it. Other minimization solvers such as NLopt.jl and Optim.jl work. However, these solve the inner and outer problem iteratively so oscillate between integer solutions similarly. This type of linear programming is likely to have an integer solution if solved iteratively, so I ideally need to solve whole problem simultaneously as a root-finding problem.
My question is whether Julia can solve nonlinear system of equations nesting linear programming solver such as Gurobi “simultaneously” to find a “real-valued” solution.
Thanks in advance.