Added 18/06/2025
Textbook / bard_1998
bard851
Dimension
{
"x": 1,
"y": 2,
"F": 1,
"G": 1,
"H": 0,
"f": 1,
"g": 6,
"h": 0
}Solution
{
"optimality": "stationary",
"x": [1.8888888888888888],
"y": [0.8888888888888888,0],
"F": -1.4074074074074074,
"G": [1.8888888888888888],
"H": [],
"f": 7.617283950617285,
"g": [0,8,0,8,0.8888888888888888,0],
"h": []
}$title Practical Bilevel Optimization Example 8.5.1 (BARD851,SEQ=7)
$onText
Example from Chapter 8, example 8.5.1, page 336
John F. Bard, Practical Bilevel Optimization: Algorithms and Applications,
Kluwer Academic Publishers, Dordrecht, 1998.
Contributor: Jan-H. Jagla, January 2009
$offText
*The reported solution is
scalar x_l
y1_l
y2_l
tol / 1e-6/;
x_l = 17/9;
y1_l = 8/9;
y2_l = 0;
positive variables x, y1, y2;
variables objout,objin;
equations defout,defin,e1,e2,e3,e4;
defout.. objout =e= sqr(x-1) + 2*sqr(y1) - 2*x;
defin.. objin =e= sqr(2*y1-4) + sqr(2*y2-1) + x*y1;
e1.. 4*x + 5*y1 + 4*y2 =l= 12;
e2.. - 4*x - 5*y1 + 4*y2 =l= -4;
e3.. 4*x - 4*y1 + 5*y2 =l= 4;
e4.. - 4*x + 4*y1 + 5*y2 =l= 4;
model bard / all /;
$echo bilevel x min objin y1 y2 defin e1 e2 e3 e4 > "%emp.info%"
*Start from reported solution
x.l = x_l ;
y1.l = y1_l;
y2.l = y2_l;
solve bard us emp min objout;
abort$( (abs(y1.l - y1_l ) > tol)
or (abs(y2.l - y2_l ) > tol)
or (abs( x.l - x_l ) > tol)) 'Deviated from known solution';\subsection{bard851}
\label{subsec:bard851}
% Description bard511
This example was first presented in~\cite[Fig. 1]{Savard1994} and then later in~\cite[Chapter 8, example 8.5.1, page 336]{Bard2000}.
The feasible set is a polyhedron with a global optimum at $(x,y_1,y_2) = (\frac{17}{9},\frac{8}{9},0)$.
% Equation: bard511
\begin{flalign*}
\minimise_{x, y_1^*, y_2^*}\quad
& (x-1)^2 + 2y_1^{*2} - 2x \\
\subjectto\quad
& x \geq 0 \\
& (y_1^*, y_2^*) \in \argmin_{y_1, y_2}
\left\{
\begin{aligned}
&(2y_1 - 4)^2 + (2y_2 -1 )^2 + xy_1 \\
&\begin{array}{llll}
\textrm{s.t.}
& \quad 4x + 5y_1 + 4y_2 \leq 12\\
& \, -4x + 5y_1 + 4y_2 \leq -4 \\
& \quad 4x - 4y_1 + 5y_2 \leq \; \; 4 \\
& \, -4x + 4y_1 + 5y_2 \leq -4 \\
& \quad y_1, y_2 \geq 0
\end{array}
\end{aligned}
\right.
\end{flalign*}
classdef bard851
%{
Reference 1:
G. Savard and J. Gauvin,
The Steepest Descent Direction for the Nonlinear Bilevel Programming Problem
in Operations Research Letters, Vol. 15, page 265-272, year 1994
Reference 2:
Jonathan F. Bard
Practical Bilevel Optimization: Algorithms And Applications
Chapter 8, page 336, example 8.5.1
%}
properties(Constant)
name = 'bard851';
category = 'textbook';
subcategory = 'bard_1998';
datasets = {};
paths = {};
x0 = [1.8888888888888888];
y0 = [0.8888888888888888, 0.0];
end
methods(Static)
% Upper-level objective function (quadratic)
function val = F(x, y, ~)
val = (x(1) - 1)^2 + 2*y(1)^2 - 2*x(1);
end
% Upper-level inequality constraints (bounds)
function val = G(x, ~, ~)
val = x;
end
% Upper-level equality constraints (none)
function val = H(~, ~, ~)
val = [];
end
% Lower-level objective function (quadratic)
function val = f(x, y, ~)
val = (2*y(1) - 4)^2 + (2*y(2) - 1)^2 + x(1)*y(1);
end
% Lower-level inequality constraints (linear)
function val = g(x, y, ~)
val = [
-4*x(1) - 5*y(1) - 4*y(2) + 12;
+4*x(1) + 5*y(1) - 4*y(2) - 4;
-4*x(1) + 4*y(1) - 5*y(2) + 4 ;
+4*x(1) - 4*y(1) - 5*y(2) + 4 ;
y(1);
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 = dimention(key, ~)
n = dictionary( ...
'x', 1, ...
'y', 2, ...
'F', 1, ...
'G', 1, ...
'H', 0, ...
'f', 1, ...
'g', 6, ...
'h', 0 ...
);
if isKey(n,key)
n = n(key);
end
end
end
endfrom bolib3 import np
"""
Reference 1:
G. Savard and J. Gauvin,
The Steepest Descent Direction for the Nonlinear Bilevel Programming Problem
in Operations Research Letters, Vol. 15, page 265-272, year 1994
Reference 2:
Jonathan F. Bard
Practical Bilevel Optimization: Algorithms And Applications
Chapter 8, page 336, example 8.5.1
"""
# Properties
name: str = 'bard851'
category: str = 'textbook'
subcategory: str = 'bard_1998'
datasets: list = []
paths: list = []
# Methods
# Upper level
def F(x, y, data=None):
"""
Upper level objective function
(quadratic)
"""
return (x[0] - 1)**2 + 2*y[0]**2 - 2*x[0]
def G(x, y, data=None):
"""
Upper level inequality constraints
(bounds)
x >= 0
"""
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
(quadratic)
"""
return (2*y[0] - 4)**2 + (2*y[1] - 1)**2 + x[0]*y[0]
Ax_lower_ineq = np.array([
[-4.],
[+4.],
[-4.],
[+4.],
[0.],
[0.],
])
Ay_lower_ineq = np.array([
[-5., -4.],
[+5., -4.],
[+4., -5.],
[-4., -5.],
[1., 0.],
[0., 1.],
])
b_lower_ineq = np.array([12., -4., 4., 4., 0, 0])
def g(x, y, data=None):
"""
Lower level inequality constraints
(linear)
"""
return np.matmul(Ax_lower_ineq, x) + np.matmul(Ay_lower_ineq, y) + b_lower_ineq
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 feasible_point(data=None):
"""
Returns a feasible point (x0, y0) satisfying:
G(x0, y0) >= 0,
H(x0, y0) == 0,
g(x0, y0) >= 0,
h(x0, y0) == 0.
"""
x0 = np.array([1.8888888888888888])
y0 = np.array([0.8888888888888888, 0.0])
return x0, y0
def dimension(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": 6, # Lower-level inequality constraints
"h": 0 # Lower-level equality constraints
}
if key in n:
return n[key]
return n
##################################################
# First order derivatives
##################################################
# def dF_dx(x, y):
# """
# First order derivative of F(x,y) with respect to x
# """
# return 2*x[0]
#
#
# def dF_dy(x, y):
# """
# First order derivative of F(x,y) with respect to y
# """
# return np.array([4*y[0], 0.])
#
#
# def dF(x, y):
# """
# First order derivative of F(x,y) with respect to x and y
# """
# return np.concatenate((dF_dx(x, y), dF_dy(x, y)))
#
#
# ##################################################
# # Second order derivatives
# ##################################################
# def d2F_dxx(x, y):
# return np.array([[1.]])
#
#
# def d2F_dyy(x, y):
# return np.array([
# [4., 0.],
# [0., 0.],
# ])
#
#
# def d2F_dxy(x, y):
# return np.array([
# [0., 0.],
# ])
#
#
# def d2F_dyx(x, y):
# return np.array([
# [0.],
# [0.]
# ])
#
#
# def d2F(x, y):
# return np.block([
# [d2F_dxx(x, y), d2F_dxy(x, y)],
# [d2F_dyx(x, y).T, d2F_dyy(x, y)]
# ])