Added 18/06/2025
Textbook / bard_1998
bard871
Dimension
{
"x": 1,
"y": 1,
"F": 1,
"G": 2,
"H": 0,
"f": 1,
"g": 2,
"h": 0
}Solution
{
"optimality": "global",
"x": [11.25],
"y": [5],
"F": 2250,
"G": [11.25, 40],
"H": [],
"f": 197.75390625,
"g": [5, 0],
"h": []
}$title Practical Bilevel Optimization Example 8.7.1 (BARD871,SEQ=8)
$onText
Example from Chapter 8, example 8.7.1, page 358
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 /11.25/
y_l / 5/
tol / 1e-3/;
positive variables x,y;
variables objout,objin;
equations defout,defin,e1,e2;
defout.. objout =e= 16*sqr(x) + 9*sqr(y);
defin.. objin =e= power(x+y-20,4);
e1.. -4*x + y =l= 0;
e2.. 4*x + y =l= 50;
model bard / all /;
$echo bilevel x min objin y defin e2 > "%emp.info%"
* Start from reported solution
x.l = x_l ;
y.l = y_l;
solve bard us emp min objout;
abort$( (abs(x.l - x_l ) > tol)
or (abs(y.l - y_l ) > tol) ) 'Deviated from known solution';\subsection{bard871}
\label{subsec:bard871}
% Description bard871
With a quartic lower-level objective function, this example remains convex but cannot be solved with quadratic methods.
\cite[Chapter 8, example 8.7.1, page 358]{Bard2000}.
It has a global solution at $(x,y) = (11.25, 5)$ and a local solution at $(x,y) = (7.2, 12.8)$.
% Equation: bard871
\begin{align*}
&\minimise_{x} \quad && 16x^2 +9y^{*2} \\
&\subjectto
&& x \geq 0, \\
&&& 4x-y^*\geq 0, \\
&&& y^* \in \argmin_{y}
\left\{
\begin{array}{lr}
(x + y - 20)^4\\
\subjectto\quad & - 4x - y + 50 \geq 0,\\
& y \geq 0.
\end{array}
\right.
\end{align*}
classdef bard871
%{
Reference:
Jonathan F. Bard
Practical Bilevel Optimization: Algorithms And Applications
Chapter 8, example 8.7.1, page 358
%}
properties(Constant)
name = 'bard871';
category = 'textbook';
subcategory = 'bard_1998';
datasets = {};
x0 = [11.25];
y0 = [5.0];
end
methods(Static)
% Upper-level objective function (quadratic)
function val = F(x, y, ~)
val = 16*x(1)^2 + 9*y(1)^2;
end
% Upper-level inequality constraints (linear)
function val = G(x, y, ~)
val = [x(1); 4*x(1)-y(1)];
end
% Upper-level equality constraints (none)
function val = H(~, ~, ~)
val = [];
end
% Lower-level objective function (convex)
function val = f(x, y, ~)
val = (x(1) + y(1) - 20)^4;
end
% Lower-level inequality constraints (linear)
function val = g(x, y, ~)
val = [y(1); - 4*x(1) - y(1) + 50];
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', 2, ...
'H', 0, ...
'f', 1, ...
'g', 2, ...
'h', 0 ...
);
if isKey(n,key)
n = n(key);
end
end
end
endfrom bolib3 import np
"""
Reference:
Jonathan F. Bard
Practical Bilevel Optimization: Algorithms And Applications
Chapter 8, example 8.7.1, page 358
"""
# Properties
name: str = 'bard871'
category: str = 'textbook'
subcategory: str = 'bard_1998'
datasets: list = []
# Feasible point
x0 = np.array([11.25])
y0 = np.array([5.0])
# Methods
def F(x, y, data=None):
"""
Upper-level objective function
(quadratic)
"""
return 16*x[0]**2 + 9*y[0]**2
def G(x, y, data=None):
"""
Upper-level inequality constraints
(linear)
"""
return np.array([x[0], 4*x[0]-y[0]])
def H(x, y, data=None):
"""
Upper-level equality constraints
(none)
"""
return np.empty(0)
def f(x, y, data=None):
"""
Lower-level objective function
(convex)
"""
return (x[0] + y[0] - 20)**4
def g(x, y, data=None):
"""
Lower-level inequality constraints
(linear)
"""
return np.array([y[0], - 4*x[0] - y[0] + 50])
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": 2, # 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