Added 18/06/2025
Textbook / dempe_dutta_2012
dempe_dutta_3_4
Dimension
{
"x": 1,
"y": 1,
"F": 1,
"G": 0,
"H": 0,
"f": 1,
"g": 2,
"h": 0
}Solution
{
"optimality": "global",
"x": [0.5],
"y": [0.5],
"F": 0.5,
"G": [],
"H": [],
"f": -0.5,
"g": [0, 1],
"h": []
}$title dempe_dutta_3_4
$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 3.4
Contributor: Samuel Ward 2025
$offText
variables x, y, obj_upper, obj_lower;
equations u1, l1, l2, l3;
u1.. obj_upper =e= sqr( x - 1 ) + sqr( y - 1 );
l1.. obj_lower =e= -y;
l2.. x + y =l= 1;
l3.. - x + y =l= 1;
model dempe_dutta_2_2 / all /;
$echo bilevel x min obj_lower y l1 l2 l3 > "%emp.info%"
solve dempe_dutta_2_2 use emp min obj_upper;\subsection{dempe\_dutta\_3\_4}
\label{subsec:dempe_dutta_3_4}
% Description: dempe_duta_3_4
This second example from Dempe and Dutta's 2012 paper~\cite[Example 3.4]{DempeDutta2012} shows that in the case of multiple Lagrange multipliers and when the constant rank constraint qualification is not satisfied, the KKT-reformulation will have solutions that do not correspond to bilevel solutions.
In particular, this Bilevel program has a unique minimum at $(0.5, 0.5)$.
However, its corresponding KKT-reformulation has multiple minima, including one at $(0, 1)$, which is not the solution to the bilevel.
% Equation: dempe_duta_3_4
\begin{flalign*}
\minimise_{x, \ y^*} \quad & (x-1)^2 + (y^*-1)^2\\
\subjectto \quad
& y^* \in \argmin_{y}
\left\{
\begin{array}{ll}
-y:\\
\textrm{s.t.} &\phantom{-}x+y\leq 1\\
&-x+y\leq 1
\end{array}
\right.
\end{flalign*}
classdef dempe_dutta_3_4
%{
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 3.4
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_3_4';
category = 'textbook';
subcategory = 'dempe_dutta_2012';
datasets = {};
x0 = [0.5];
y0 = [0.5];
end
methods(Static)
% Upper-level objective function
function val = F(x, y, ~)
% Quadratic
val = (x(1) - 1)^2 + (y(1) - 1)^2;
end
% Upper-level inequality constraints (none)
function vals = G(~, ~, ~)
vals = [];
end
% Upper-level equality constraints (none)
function vals = H(~, ~, ~)
vals = [];
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 = [
-x(1) - y(1) + 1;
x(1) - y(1) + 1
];
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', 1, ...
'F', 1, ...
'G', 0, ...
'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 3.4
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_3_4'
category: str = 'textbook'
subcategory: str = 'dempe_dutta_2012'
encoding: str = 'Q1U0-L1L2-Tb'
default_data_path: str = ''
datasets: list = []
# Feasible point
x0 = np.array([0.5])
y0 = np.array([0.5])
# Upper level
def F(x, y, data=None):
"""
Upper-level objective function
(Quadratic)
"""
return (x[0] - 1)**2 + (y[0] - 1)**2
def G(x, y, data=None):
"""
Upper-level inequality constraints
(None)
"""
return np.empty(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([
- x[0] - y[0] + 1,
+ x[0] - y[0] + 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": 1, # Lower-level variables
"F": 1, # Upper-level objective functions
"G": 0, # 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