Added 18/06/2025
Textbook / dempe_dutta_2012
dempe_dutta_2_2
Dimension
{
"x": 1,
"y": 2,
"F": 1,
"G": 1,
"H": 0,
"f": 1,
"g": 2,
"h": 0
}Solution
{
"optimality": "global",
"x": [0],
"y": [0, 0],
"F": 0,
"G": [0],
"H": [],
"f": 0,
"g": [0, 0],
"h": []
}$title dempe_dutta_2_2
$onText
Stephan Dempe and Joydeep Dutta.
Is bilevel programming a special case of a mathematical program with complementarity constraints?
Mathematical Programming, volume 131, pages 37–48, year 2012.
Example 2.2
Contributor: Samuel Ward 2025
$offText
positive variables x;
variables y1, y2, obj_upper, obj_lower;
equations u1, l1, l2, l3;
u1.. obj_upper =e= x;
l1.. obj_lower =e= y1;
l2.. - x + sqr(y1) - y2 =l= 0;
l3.. sqr(y1) + y2 =l= 0;
model dempe_dutta_2_2 / all /;
$echo bilevel x min obj_lower y1 y2 l1 l2 l3 > "%emp.info%"
solve dempe_dutta_2_2 use emp min obj_upper;\subsection{dempe\_dutta\_2\_2}
\label{subsec:dempe_dutta_2_2}
% Description: dempe_dutta_2_2
This classic example from Dempe and Dutta's 2012 paper~\cite[Example 2.2]{DempeDutta2012} demonstrates that the KKT-reformulation of a bilevel program may not have a global optimal solution even if its feasible set is not empty and bounded.
% Equation: dempe_dutta_2_2
\begin{flalign*}
\minimise_{x, \ y_1^*, y_2^*} \quad & x\\
\subjectto \quad
& x \geq 0\\
& y_1^*, y_2^* \in \argmin_{y_1, y_2}
\left\{
\begin{array}{ll}
y_1\\
\textrm{s.t.} &y_1^2-y_2\leq x\\
&y_1^2+y_2\leq 0
\end{array}
\right.
\end{flalign*}
classdef dempe_dutta_2_2
%{
Reference:
Stephan Dempe and Joydeep Dutta.
Is bilevel programming a special case of a mathematical program with complementarity constraints?
Mathematical Programming, volume 131, pages 37–48, year 2012.
Example 2.2
Upper level program:
minimise x,y F(x,y)
subject to G(x,y) >= 0
H(x,y) == 0
y solves the lower level program
Lower level program:
minimise y f(x,y)
subject to g(x,y) >= 0
h(x,y) == 0
%}
properties(Constant)
name = 'dempe_dutta_2_2';
category = 'textbook';
subcategory = 'dempe_dutta_2012';
datasets = {};
x0 = [0.0];
y0 = [0.0, 0.0];
end
methods(Static)
% Upper-level objective function (linear)
function val = F(x, ~, ~)
val = x(1);
end
% Upper-level inequality constraints (bound)
function val = G(x, ~, ~)
val = [x(1)];
end
% Upper-level equality constraints (none)
function val = H(~, ~, ~)
val = [];
end
% Lower-level objective function (linear)
function val = f(~, y, ~)
val = y(1);
end
% Lower-level inequality constraints (quadratic)
function val = g(x, y, ~)
val = [
y(1)^2 - y(2) - x(1);
y(1)^2 + y(2)
];
end
% Lower-level equality constraints (none)
function val = h(~, ~, ~)
val = [];
end
% If the bilevel program is parameterized by data, this function should
% provide code to read data file and return an appropriate structure.
function val = read_data(~)
val = [];
end
% Key are the function/variable names
% Values are their dimention
function n = dimentions(key, ~)
n = dictionary( ...
'x', 1, ...
'y', 2, ...
'F', 1, ...
'G', 1, ...
'H', 0, ...
'f', 1, ...
'g', 2, ...
'h', 0 ...
);
if isKey(n,key)
n = n(key);
end
end
end
endimport numpy as np
"""
Reference:
Stephan Dempe and Joydeep Dutta.
Is bilevel programming a special case of a mathematical program with complementarity constraints?
Mathematical Programming, volume 131, pages 37–48, year 2012.
Example 2.2
Upper level program:
minimise x,y F(x,y)
subject to G(x,y) >= 0
H(x,y) == 0
y solves the lower level program
Lower level program:
minimise y f(x,y)
subject to g(x,y) >= 0
h(x,y) == 0
"""
# Properties
name: str = 'dempe_dutta_2_2'
category: str = 'textbook'
subcategory: str = 'dempe_dutta_2012'
encoding: str = 'L1U0-L2Q2-Tb'
datasets: list = []
# Feasible point
x0 = np.array([0.0])
y0 = np.array([0.0, 0.0])
# Upper level
def F(x, y, data=None):
"""
Upper-level objective function
(linear)
"""
return x[0]
def G(x, y, data=None):
"""
Upper-level inequality constraints
(bound)
"""
return np.array((x[0],))
def H(x, y, data=None):
"""
Upper-level equality constraints
(none)
"""
return np.empty(0)
# Lower level
def f(x, y, data=None):
"""
Lower-level objective function
(linear)
"""
return y[0]
def g(x, y, data=None):
"""
Lower-level inequality constraints
(quadratic)
"""
return np.array([
y[0]**2 - y[1] - x[0],
y[0]**2 + y[1],
])
def h(x, y, data=None):
"""
Lower-level equality constraints
(none)
"""
return np.empty(0)
def read_data(filepath=''):
"""
If the bilevel program is parameterized by data, this function should
provide code to read data file and return an appropriate python structure.
"""
pass
def dimensions(key='', data=None):
"""
If the argument 'key' is not specified, then:
- a dictionary mapping variable/function names (str) to the corresponding dimension (int) is returned.
If the first argument 'key' is specified, then:
- a single integer representing the dimension of the variable/function with the name {key} is returned.
"""
n = {
"x": 1, # Upper-level variables
"y": 2, # Lower-level variables
"F": 1, # Upper-level objective functions
"G": 1, # Upper-level inequality constraints
"H": 0, # Upper-level equality constraints
"f": 1, # Lower-level objective functions
"g": 2, # Lower-level inequality constraints
"h": 0, # Lower-level equality constraints
}
if key in n:
return n[key]
return n