Bilevel Disjunctive Optimization on Affine Manifolds

Abstract

Bilevel optimization is a special kind of optimization where one problem is embedded within another. The outer optimization task is commonly referred to as the upper-level optimization task, and the inner optimization task is commonly referred to as the lower-level optimization task. These problems involve two kinds of variables: upper-level variables and lower-level variables. Bilevel optimization was first realized in the field of game theory by a German economist von Stackelberg who published a book (1934) that described this hierarchical problem. Now the bilevel optimization problems are commonly found in a number of real-world problems: transportation, economics, decision science, business, engineering, and so on. In this chapter, we provide a general formulation for bilevel disjunctive optimization problem on affine manifolds. These problems contain two levels of optimization tasks where one optimization task is nested within the other. The outer optimization problem is commonly referred to as the leaders (upper level) optimization problem and the inner optimization problem is known as the followers (or lower level) optimization problem. The two levels have their own objectives and constraints. Topics affine convex functions, optimizations with auto-parallel restrictions, affine convexity of posynomial functions, bilevel disjunctive problem and algorithm, models of bilevel disjunctive programming problems, and properties of minimum functions.

1. Affine convex functions

In optimization problems [16, 17, 19, 23, 24, 25, 26, 27], one can use an affine manifold as a pair $\left(M,\mathrm{\Gamma }\right)$, where $M$ is a smooth real $n$-dimensional manifold, and $\mathrm{\Gamma }$ is an affine symmetric connection on $M$. The connection $\mathrm{\Gamma }$ produces auto-parallel curves $x\left(t\right)$ via ODE system

$${\ddot{x}}^h\left(t\right)+{\mathrm{\Gamma }}_{\mathit{ij}}^h\left(x\left(t\right)\right){\dot{x}}^i\left(t\right){\dot{x}}^j\left(t\right)=0.$$

They are used for defining the convexity of subsets in $M$ and convexity of functions $f:D\subset M\to \mathbb{R}$ (see also [3, 6]).

Definition 1.1 An affine manifold $\left(M,\mathrm{\Gamma }\right)$ is called autoparallely complete if any auto-parallel $x\left(t\right)$ starting at $p\in M$ is defined for all values of the parameter $t\in \mathbb{R}$.

Theorem 1.1 [1] Let $M$ be a (Hausdorff, connected, smooth) compact $n$-manifold endowed with an affine connection $\mathrm{\Gamma }$ and let $p\in M$. If the holonomy group ${\mathit{Hol}}_p\left(\mathrm{\Gamma }\right)$ (regarded as a subgroup of the group $\mathit{Gl}\left(T_{p}M\right)$ of all the linear automorphisms of the tangent space $T_{p}M$) has compact closure, then $\left(M,\mathrm{\Gamma }\right)$ is autoparallely complete.

Let $\left(M,\mathrm{\Gamma }\right)$ be an auto-parallely complete affine manifold. For a $C^2$ function $f:M\to \mathbb{R}$, we define the tensor ${\mathit{\text{Hess}}}_{\mathrm{\Gamma }}f$ of components

$${\left({\mathit{\text{Hess}}}_{\mathrm{\Gamma }}f\right)}_{\mathit{ij}}=\frac{{\partial }^{2}f}{\partial x^i\partial x^j}-{\mathrm{\Gamma }}_{\mathit{ij}}^h\frac{\partial f}{\partial x^h}.$$

Definition 1.2 A $C^2$ function $f:M\to \mathbb{R}$ is called:

(1) linear affine with respect to $\mathrm{\Gamma }$ if ${\mathit{\text{Hess}}}_{\mathrm{\Gamma }}f=0$, throughout;

(2) affine convex (convex with respect to $\mathrm{\Gamma }$) if ${\mathit{\text{Hess}}}_{\mathrm{\Gamma }}f\succcurlyeq 0$ (positive semidefinite), throughout.

The function $f$ is: (1) linear affine if its restriction $f\left(x\left(t\right)\right)$ on each autoparallel $x\left(t\right)$ satisfies $f\left(x\left(t\right)\right)=\mathit{at}+b$, for some numbers $a,b$ that may depend on $x\left(t\right)$; (2) affine convex if its restriction $f\left(x\left(t\right)\right)$ is convex on each auto-parallel $x\left(t\right)$.

Theorem 1.2 If there exists a linear affine nonconstant function $f$ on $\left(M,\mathrm{\Gamma }\right)$, then the curvature tensor field ${R^h}_{\mathit{ikj}}$ is in $\mathit{Ker}\mathit{df}$.

Proof. For given $\mathrm{\Gamma }$, if we consider

$$\frac{{\partial }^{2}f}{\partial x^i\partial x^j}={\mathrm{\Gamma }}_{\mathit{ij}}^h\frac{\partial f}{\partial x^h}$$

as a PDEs system (a particular case of a Frobenius-Mayer system of PDEs) with $\frac{1}{2}n\left(n+1\right)$ equations and the unknown function $f$, then we need the complete integrability conditions

$$\frac{{\partial }^{3}f}{\partial x^i\partial x^j\partial x^k}=\frac{{\partial }^{3}f}{\partial x^k\partial x^i\partial x^j}.$$

Since,

$$\frac{{\partial }^{3}f}{\partial x^i\partial x^j\partial x^k}=\left(\frac{\partial {\mathrm{\Gamma }}_{\mathit{ij}}^h}{\partial x^k}+{\mathrm{\Gamma }}_{\mathit{ij}}^l{\mathrm{\Gamma }}_{\mathit{kl}}^h\right)\frac{\partial f}{\partial x^h},$$

it follows

$$\frac{\partial f}{\partial x^h}{R^h}_{\mathit{ikj}}=0,{R^h}_{\mathit{ikj}}=\frac{\partial {\mathrm{\Gamma }}_{\mathit{ij}}^h}{\partial x^k}-\frac{\partial {\mathrm{\Gamma }}_{\mathit{ki}}^h}{\partial x^j}+{\mathrm{\Gamma }}_{\mathit{ij}}^l{\mathrm{\Gamma }}_{\mathit{kl}}^h-{\mathrm{\Gamma }}_{\mathit{ki}}^l{\mathrm{\Gamma }}_{\mathit{jl}}^h.$$

Corollary 1.1 If there exists $n$ linear affine functions $f_l,l=1,\dots ,n$ on $\left(M,\mathrm{\Gamma }\right)$, whose ${\mathit{df}}_l$ are linearly independent, then $\mathrm{\Gamma }$ is flat, that is, ${R^h}_{\mathit{ikj}}=0$.

Of course this only means the curvature tensor is zero on the topologically trivial region we used to set up our co-vector fields ${\mathit{df}}_l\left(x\right)$. But we can always cover any manifold by an atlas of topologically trivial regions, so this allows us to deduce that the curvature tensor vanishes throughout the manifold.

Remark 1.1 There is actually no need to extend ${\mathit{df}}_l\left(x\right)$ to the entire manifold. If this could be done, then ${\mathit{df}}_l\left(x\right)$ would now be everywhere nonzero co-vector fields; but there are topologies, for example, $S^2$, for which we know such things do not exist. Therefore, there are topological manifolds for which we are forced to work on topologically trivial regions.

The following theorem is well-known [16, 17, 19, 23]. Due to its importance, now we offer new proofs (based on catastrophe theory, decomposing a tensor into a specific product, and using slackness variables).

Theorem 1.3 Let $f:M\to \mathbb{R}$ be a $C^2$ function.

(1) If $f$ is regular or has only one minimum point, then there exists a connection $\mathrm{\Gamma }$ such that $f$ is affine convex.

(2) If $f$ has a maximum point $x_0$, then there is no connection $\mathrm{\Gamma }$ making $f$ affine convex throughout.

Proof. For the Hessian ${\left({\mathit{\text{Hess}}}_{\mathrm{\Gamma }}f\right)}_{\mathit{ij}}$ be positive semidefinite, we need $n$ conditions like inequalities and equalities. The number of unknowns ${\mathrm{\Gamma }}_{\mathit{ij}}^h$ is $\frac{1}{2}{n}^2\left(n+1\right).$ The inequalities can be replaced by equalities using slackness variables.

The first central idea for the proof is to use the catastrophe theory, since almost all families $f\left(x,c\right)$, $x=\left(x^1,\dots ,x^n\right)\in {\mathbb{R}}^n$, $c=\left(c_1,\dots ,c_m\right)\in {\mathbb{R}}^m$, of real differentiable functions, with $m\le 4$ parameters, are structurally stable and are equivalent, in the vicinity of any point, with one of the following forms [15]:

We eliminate the case with maximum point, that is., Morse $0$-saddle and the saddle point. Around each critical point (in a chart), the canonical form $f\left(x,c\right)$ is affine convex, with respect to appropriate locally defined linear connections that can be found easily. Using change of coordinates and the partition of unity, we glue all these connections to a global one, making $f\left(x,c\right)$ affine convex on $M$.

At any critical point $x_0$, the affine Hessian ${\mathit{\text{Hess}}}_{\mathrm{\Gamma }}f$ is reduced to Euclidean Hessian, $\frac{{\partial }^{2}f}{\partial x^i\partial x^j}\left(x_0\right)$. Then the maximum point condition or the saddle condition is contradictory to affine convexity condition.

A direct proof based on decomposition of a tensor: Let $\left(M,\mathrm{\Gamma }\right)$ be an affine manifold and $f:M\to \mathbb{R}$ be a $C^2$ function.

Suppose $f$ has no critical points (is regular). If the function $f$ is not convex with respect to $\mathrm{\Gamma }$, we look to find a new connection ${\overline{\mathrm{\Gamma }}}_{\mathit{ij}}^h={\mathrm{\Gamma }}_{\mathit{ij}}^h+T_{\mathit{ij}}^h$, with the unknown a tensor field $T_{\mathit{ij}}^h$, such that

$$\frac{{\partial }^{2}f}{\partial x^i\partial x^j}\left(x\right)-{\overline{\mathrm{\Gamma }}}_{\mathit{ij}}^h\left(x\right)\frac{\partial f}{\partial x^h}\left(x\right)={\sigma }_{\mathit{ij}}\left(x\right),x\in M,$$

where ${\sigma }_{\mathit{ij}}\left(x\right)$ is a positive semi-definite tensor. A very particular solution is the decomposition $T_{\mathit{ij}}^h\left(x\right)=a^h\left(x\right)b_{\mathit{ij}}\left(x\right)$, where the vector field $a$ has the property

$$D_{a}f=a^h\left(x\right)\frac{\partial f}{\partial x^h}\left(x\right)\ne 0,x\in M$$

and the tensor $b_{\mathit{ij}}$ is

$$b_{\mathit{ij}}\left(x\right)=\frac{1}{D_{a}f}\left(\frac{{\partial }^{2}f}{\partial x^i\partial x^j}\left(x\right)-{\mathrm{\Gamma }}_{\mathit{ij}}^h\left(x\right)\frac{\partial f}{\partial x^h}\left(x\right)-{\sigma }_{\mathit{ij}}\left(x\right)\right),x\in M.$$

Remark 1.2 The connection ${\overline{\mathrm{\Gamma }}}_{\mathit{ij}}^h$ is strongly dependent on both the function $f$ and the tensor field ${\sigma }_{\mathit{ij}}$.

Suppose $f$ has a minimum point $x_0$. In this case, observe that we must have the condition ${\sigma }_{\mathit{ij}}\left(x_0\right)=\frac{{\partial }^{2}f}{\partial x^i\partial x^j}\left(x_0\right)$. Can we make the previous reason for $x\ne x_0$ and then extend the obtained connection by continuity? The answer is generally negative. Indeed, let us compute

$$b_{\mathit{ij}}\left(x_0\right)=\underset{x\to x_0}{lim}\frac{1}{D_{a}f}\left(\frac{{\partial }^{2}f}{\partial x^i\partial x^j}\left(x\right)-{\mathrm{\Gamma }}_{\mathit{ij}}^h\left(x\right)\frac{\partial f}{\partial x^h}\left(x\right)-{\sigma }_{\mathit{ij}}\left(x\right)\right).$$

Here we cannot plug in the point $x_0$ because we get $\frac{0}{0}$, an indeterminate form.

To contradict, we fix an auto-parallel $\gamma \left(t\right),t\in \left[0,\mathrm{ϵ}\right)$, starting from minimum point $x_0=\gamma \left(0\right)$, tangent to $\dot{\gamma }\left(0\right)=v$ and we compute (via l’Hôpital rule)

$$b_{\mathit{ij}}\left(x_0;v\right)=\underset{t\to 0}{lim}{b}_{\mathit{ij}}\left(\gamma \left(t\right)\right)=\frac{\left(\frac{{\partial }^{3}f}{\partial x^i\partial x^j\partial x^k}\left(x_0\right)-{\mathrm{\Gamma }}_{\mathit{ij}}^h\left(x_0\right)\frac{{\partial }^{2}f}{\partial x^h\partial x^k}\left(x_0\right)-\frac{\partial {\sigma }_{\mathit{ij}}}{\partial x^k}\left(x_0\right)\right)v^k}{a^h\left(x_0\right)\frac{{\partial }^{2}f}{\partial x^h\partial x^k}\left(x_0\right)v^k}.$$

But this result depends on the direction $v$ (different values along two different auto-parallels).

In some particular cases, we can eliminate the dependence on the vector $v$. For example, the conditions

$$\frac{{\partial }^{3}f}{\partial x^i\partial x^j\partial x^l}\left(x_0\right)-{\mathrm{\Gamma }}_{\mathit{ij}}^h\left(x_0\right)\frac{{\partial }^{2}f}{\partial x^h\partial x^l}\left(x_0\right)-\frac{\partial {\sigma }_{\mathit{ij}}}{\partial x^l}\left(x_0\right)$$

$$=\rho \left(\frac{{\partial }^{3}f}{\partial x^i\partial x^j\partial x^k}\left(x_0\right)-{\mathrm{\Gamma }}_{\mathit{ij}}^h\left(x_0\right)\frac{{\partial }^{2}f}{\partial x^h\partial x^k}\left(x_0\right)-\frac{\partial {\sigma }_{\mathit{ij}}}{\partial x^k}\left(x_0\right)\right),$$

$$a^h\left(x_0\right)\frac{{\partial }^{2}f}{\partial x^h\partial x^l}\left(x_0\right)=\rho \left(a^h\left(x_0\right)\frac{{\partial }^{2}f}{\partial x^h\partial x^k}\left(x_0\right)\right)$$

are sufficient to do this.

A particular condition for independence on $v$ is

$$\frac{{\partial }^{3}f}{\partial x^i\partial x^j\partial x^k}\left(x_0\right)-{\mathrm{\Gamma }}_{\mathit{ij}}^h\left(x_0\right)\frac{{\partial }^{2}f}{\partial x^h\partial x^k}\left(x_0\right)-\frac{\partial {\sigma }_{\mathit{ij}}}{\partial x^k}\left(x_0\right)=0.$$

In this particular condition, we can show that we can build connections of previous type good everywhere.

1.1. Lightning through examples

Let us lightning our previous statements by the following examples.

Example 1.1 (for the first part of the theorem) Let us consider the function $f:{\mathbf{R}}^2\to \mathbf{R},f\left(x,y\right)=x^3+y^3+3x+3y$ and ${\mathrm{\Gamma }}_{\mathit{ij}}^h=0,i,j,h=1,2$. Then $\frac{\partial f}{\partial x}=3x^2+3,\frac{\partial f}{\partial y}=3y^2+3$ and $f$ has no critical point. Moreover, the Euclidean Hessian of $f$ is not positive semi-definite overall. Let us make the above construction for ${\sigma }_{\mathit{ij}}\left(x,y\right)={\delta }_{\mathit{ij}}$. Taking $a^1=a^2=1$, we obtain the connection

$${\overline{\mathrm{\Gamma }}}_{11}^h=\frac{6x-1}{3x^2+3y^2+2},{\overline{\mathrm{\Gamma }}}_{22}^h=\frac{6y-1}{3x^2+3y^2+2},{\overline{\mathrm{\Gamma }}}_{12}^h={\overline{\mathrm{\Gamma }}}_{21}^h=0,h=1,2,$$

that is not unique.

Example 1.2 (for one minimum point) Let us consider the function $f:{\mathbf{R}}^2\to \mathbf{R},f\left(x,y\right)=1-e^{-\left(x^2+y^2\right)}$ and ${\mathrm{\Gamma }}_{\mathit{ij}}^h=0,i,j,h=1,2$. Then $\frac{\partial f}{\partial x}=2{\mathit{xe}}^{-\left(x^2+y^2\right)},\frac{\partial f}{\partial y}=2{\mathit{ye}}^{-\left(x^2+y^2\right)}$ and $f$ has a unique critical minimum point $\left(0,0\right)$. However, the Euclidean Hessian of $f$ is not positive semi-definite overall. We make previous reason for ${\sigma }_{\mathit{ij}}=2e^{-\left(x^2+y^2\right)}{\delta }_{\mathit{ij}},a^1=\frac{\partial f}{\partial x},a^2=\frac{\partial f}{\partial y}$. Hence we obtain ${\overline{\mathrm{\Gamma }}}_{\mathit{ij}}^h=T_{\mathit{ij}}^h$,

$${\overline{\mathrm{\Gamma }}}_{11}^1=-\frac{2x^3}{x^2+y^2},{\overline{\mathrm{\Gamma }}}_{12}^1={\overline{\mathrm{\Gamma }}}_{21}^1=-\frac{2x^{2}y}{x^2+y^2},{\overline{\mathrm{\Gamma }}}_{22}^1=-\frac{2{\mathit{xy}}^2}{x^2+y^2},$$

$${\overline{\mathrm{\Gamma }}}_{11}^2=-\frac{2x^{2}y}{x^2+y^2},{\overline{\mathrm{\Gamma }}}_{12}^2={\overline{\mathrm{\Gamma }}}_{21}^2=-\frac{2{\mathit{xy}}^2}{x^2+y^2},{\overline{\mathrm{\Gamma }}}_{22}^2=-\frac{2y^3}{x^2+y^2}.$$

Observe that ${lim}_{\left(x,y\right)\to \left(0,0\right)}{T}_{\mathit{ij}}^h\left(x,y\right)=0$. Hence take ${\overline{\mathrm{\Gamma }}}_{\mathit{ij}}^h\left(0,0\right)=0$.

The next example shows what happens if we come out of the conditions of the previous theorem.

Example 1.3 Let us take the function $f:\mathbb{R}\to \mathbb{R},f\left(x\right)=x^3$, where the critical point $x=0$ is an inflection point. We take $\mathrm{\Gamma }\left(x\right)=-1-\frac{2}{x^2}$, which is not defined at the critical point $x=0$, but the relation of convexity is realized by prolongation,

$$\sigma \left(x\right)=f^{\prime }\left(x\right)-\mathrm{\Gamma }\left(x\right)f^{\prime }\left(x\right)=3\left(x^2+2x+2\right)>0,\forall x\in \mathbb{R}.$$

Let us consider the ODE of auto-parallels

$$x^{\prime }\left(t\right)-\left(1+\frac{2}{t^2}\right)x^{\prime }{\left(t\right)}^2=0,t\ne 0.$$

The solutions

$$x\left(t\right)=-\frac{1}{2}ln\mid -2+t^2-\mathit{ct}\mid +\frac{c}{\sqrt{8+c^2}}\mathit{arctanh}\frac{2t-c}{\sqrt{8+c^2}}+c_1$$

are auto-parallels on $\left(\mathbb{R}\backslash \left\{0,t_1,t_2\right\},\mathrm{\Gamma }\right)$, where $t_1,t_2$ are real solutions of $-2+t^2-\mathit{ct}=0$. These curves are extended at $t=0$ by continuity. The manifold $\left(\mathbb{R},\mathrm{\Gamma }\right)$ is not auto-parallely complete. Since the image $x\left(\mathbb{R}\right)$ is not a “segment”, the function $f:\mathbb{R}\to \mathbb{R},f\left(x\right)=x^3$ is not globally convex.

Remark 1.3 For $n\ge 2$, there exists $C^1$ functions $\phi :{\mathbb{R}}^n\to \mathbb{R}$ which have two minimum points without having another extremum point. As example,

$$\phi \left(x^1{x}^2\right)={\left(x^{1^2}-1\right)}^2+{\left(x^{1^2}{x}^2-x^1-1\right)}^2$$

has two (global) minimum points $p=\left(-1,0\right),q=\left(1,2\right)$.

The restriction

$$\phi \left(x^1{x}^2\right)=\left(x^{1^4}+x^{1^4}{x}^{2^2}+2x^1+2\right)-\left(x^{1^2}+2x^{1^3}{x}^2+2x^{1^2}{x}^2\right),x^1>0,x^2>0$$

is difference of two affine convex functions (see Section 2).

Our chapter is based also on some ideas in: [3] (convex mappings between Riemannian manifolds), [7] (geometric modeling in probability and statistics), [13] (arc length in metric and Finsler manifolds), [14] (applications of Hahn-Banach principle to moment and optimization problems), [21] (geodesic connectedness of semi-Riemannian manifolds), and [28] (tangent and cotangent bundles). For algorithms, we recommend the paper [20] (sequential and parallel algorithms).

2. Optimizations with autoparallel restrictions

2.1. Direct theory

The auto-parallel curves $x\left(t\right)$ on the affine manifold $\left(M,\mathrm{\Gamma }\right)$ are solutions of the second order ODE system

$${\ddot{x}}^h\left(t\right)+{\mathrm{\Gamma }}_{\mathit{ij}}^h\left(x\left(t\right)\right){\dot{x}}^i\left(t\right){\dot{x}}^j\left(t\right)=0,x\left(t_0\right)=x_0,\dot{x}\left(t_0\right)={\xi }_0.$$

Obviously, the complete notation is $x\left(t,x_0,{\xi }_0\right)$, with

$$x\left(t_0,x_0,{\xi }_0\right)=x_0,\dot{x}\left(t_0,x_0,{\xi }_0\right)={\xi }_0.$$

Definition 2.1 Let $D\subset M$ be open and connected and $f:D\to \mathbb{R}$ a $C^2$ function. The point $x_0\in D$ is called minimum (maximum) point of $f$ conditioned by the auto-parallel system, together with initial conditions, if for the maximal solution $x\left(t,x_0,{\xi }_0\right):I\to D$, there exists a neighborhood $I_{t_0}$ of $t_0$ such that

$$f\left(x\left(t,x_0,{\xi }_0\right)\right)\ge \left(\le \right)f\left(x_0\right),\forall t\in I_{t_0}\subset I.$$

Theorem 2.1 If $x_0\in D$ is an extremum point of $f$ conditioned by the previous second order system, then $\mathit{df}\left(x_0\right)\left({\xi }_0\right)=0$.

Definition 2.2 The points $x\in D$ which are solutions of the equation $\mathit{df}\left(x\right)\left(\xi \right)=0$ are called critical points of $f$ conditioned by the previous spray.

Theorem 2.2 If $x_0\in D$ is a conditioned critical point of the function $f:D\to \mathbb{R}$ of class $C^2$ constrained by the previous auto-parallel system and if the number

$${\left(\mathit{\text{Hess}}f\right)}_{\mathit{ij}}{\xi }_0^i{\xi }_0^j=\left(\frac{{\partial }^{2}f}{\partial x^i\partial x^j}-\frac{\partial f}{\partial x^h}{\mathrm{\Gamma }}_{\mathit{ij}}^h\right)\left(x_0\right){\xi }_0^i{\xi }_0^j$$

is strictly positive (negative), then $x_0$ is a minimum (maximum) point of $f$ constrained by the auto-parallel system.

Example 2.1 We compute the Christoffel symbols on the unit sphere $S^2$, using spherical coordinates $\left(\theta ,\phi \right)$ and the Riemannian metric

$$g_{\mathit{\theta \theta }}=1,g_{\mathit{\theta \phi }}=g_{\mathit{\phi \theta }}=0,g_{\mathit{\phi \phi }}={sin}^2\theta .$$

When $\theta \ne 0,\pi$, we find

$${\mathrm{\Gamma }}_{\mathit{\phi \phi }}^{\theta }=-\frac{1}{2}sin2\theta ,{\mathrm{\Gamma }}_{\mathit{\phi \theta }}^{\phi }={\mathrm{\Gamma }}_{\mathit{\theta \phi }}^{\phi }=cot\theta ,$$

and all the other $\mathrm{\Gamma }$s are equal to zero. We can show that the apparent singularity at $\theta =0,\pi$ can be removed by a better choice of coordinates at the poles of the sphere. Thus, the above affine connection extends to the whole sphere.

The second order system defining auto-parallel curves (geodesics) on $S^2$ are

$$\ddot{\theta }\left(t\right)-\frac{1}{2}sin2\theta \left(t\right)\dot{\phi }\left(t\right)\dot{\phi }\left(t\right)=0,\ddot{\phi }\left(t\right)-2cot\theta \left(t\right)\dot{\phi }\left(t\right)\dot{\theta }\left(t\right)=0.$$

The solutions are great circles on the sphere. For example, $\theta =\alpha t+\beta$ and $\phi$ = const.

We compute the curvature tensor $R$ of the unit sphere $S^2$. Since there are only two independent coordinates, all the non-zero components of curvature tensor $R$ are given by $R_j^i=R_{\mathit{j\theta \phi }}^i=-R_{\mathit{j\phi \theta }}^i$, where $i,j=\theta ,\phi$. We get $R_{\phi }^{\theta }={sin}^2\theta ,R_{\theta }^{\phi }=-1$ and the other components are $0$.

Let $(\theta \left(t,\left({\theta }_0,{\phi }_0\right),\xi \right),\phi \left(t,\left({\theta }_0,{\phi }_0\right),\xi \right),t\in R$ be the maximal auto-parallel which satisfies $\theta \left(t_0,\left({\theta }_0,{\phi }_0\right),\xi \right)={\theta }_0$, $\dot{\theta }\left(t_0,\left({\theta }_0,{\phi }_0\right),\xi \right)={\xi }^1$; $\phi \left(t_0,\left({\theta }_0,{\phi }_0\right),\xi \right)={\phi }_0$, $\dot{\phi }\left(t_0,\left({\theta }_0,{\phi }_0\right),\xi \right)={\xi }^2$. We wish to compute $minf\left(\theta ,\phi \right)=R_{\phi }^{\theta }={sin}^2\theta$ with the restriction $\left(\theta \left(t,\left({\theta }_0,{\phi }_0\right),\xi \right),\phi \left(t,\left({\theta }_0,{\phi }_0\right)\xi \right)\right),t\in R$.

Since $\mathit{df}=\left(2sin\theta cos\theta ,0\right)$, the critical point condition $\mathit{df}\left(\theta ,\phi \right)\left(\xi \right)=0$ becomes $sin\theta cos\theta {\xi }^1=0$. Consequently, the critical points are either $\left({\theta }_0=\mathit{k\pi },k\in \mathrm{\mathbb{Z}};\phi \right),\left({\xi }^1,{\xi }^2\right)\ne \left(0,0\right)$, or $\left({\theta }_1=\left(2k+1\right)\frac{\pi }{2};k\in \mathrm{\mathbb{Z}};\phi \right),\left({\xi }^1,{\xi }^2\right)\ne \left(0,0\right)$, or $\left(\theta ;\phi \right),\left({\xi }^1=0;{\xi }^2\ne 0\right)$.

The components of the Hessian of $f$ are

$${\left(\mathit{\text{Hess}}f\right)}_{\mathit{\theta \theta }}=\frac{{\partial }^{2}f}{\partial \theta \partial \theta }=2cos2\theta ,{\left(\mathit{\text{Hess}}f\right)}_{\mathit{\theta \phi }}=0,{\left(\mathit{\text{Hess}}f\right)}_{\mathit{\phi \phi }}=\frac{1}{2}{sin}^{2}2\theta .$$

At the critical points $\left({\theta }_0,\phi \right)$ or $\left({\theta }_1,\phi \right)$, the Hessian of $f$ is positive or negative semi-definite. On the other hand, along $\left({\xi }^1=0,{\xi }^2\ne 0\right)$, we find ${\left(\mathit{\text{Hess}}f\right)}_{\mathit{ij}}{\xi }^i{\xi }^j=\frac{1}{2}{sin}^{2}2\theta {\left({\xi }^2\right)}^2>0,{\xi }^2\ne 0.$ Consequently, each point $\left(\theta \ne \frac{\mathit{k\pi }}{2},\phi \right)$, is a minimum point of $f$ along each auto-parallel, starting from given point and tangent to $\left({\xi }^1=0,{\xi }^2\ne 0\right)$.

2.2. Theory via the associated spray

This point of view regarding extrema comes from paper [22].

The second order system of auto-parallels induces a spray (special vector field) $Y\left(x,y\right)=\left(y^h,{\mathrm{\Gamma }}_{\mathit{ij}}^h\left(x\right)y^i{y}^j\right)$ on the tangent bundle $\mathit{TM}$, that is,

$${\dot{x}}^h\left(t\right)=y^h\left(t\right),{\dot{y}}^h\left(t\right)+{\mathrm{\Gamma }}_{\mathit{ij}}^h\left(x\left(t\right)\right)y^i\left(t\right)y^j\left(t\right)=0.$$

The solutions $\gamma \left(t\right)=\left(x\left(t\right),y\left(t\right)\right):I\to D$ of class $C^2$ are called field lines of $Y$. They depend on the initial condition ${\left.\gamma \left(t\right)\right|}_{t=t_0}=\left(x_0,y_0\right)$, and therefore the notation $\gamma \left(t,x_0,y_0\right)$ is more suggestive.

Definition 2.3 Let $D\subset \mathit{TM}$ be open and connected and $f:D\to \mathbb{R}$ a $C^2$ function. The point $\left(x_0,y_0\right)\in D$ is called minimum (maximum) point of $f$ conditioned by the previous spray, if for the maximal field line $\gamma \left(t,x_0,y_0\right),t\in I$, there exists a neighborhood $I_{t_0}$ of $t_0$ such that

$$f\left(\gamma \left(t,x_0,y_0\right)\right)\ge \left(\le \right)f\left(x_0,y_0\right),\forall t\in I_{t_0}\subset I.$$

Theorem 2.3 If $\left(x_0,y_0\right)\in D$ is an extremum point of $f$ conditioned by the previous spray, then $\left(x_0,y_0\right)$ is a point where $Y$ is in $\mathit{Ker}\mathit{df}$.

Definition 2.4 The points $\left(x,y\right)\in D$ which are solutions of the equation

$$D_{Y}f\left(x,y\right)=\mathit{df}\left(Y\right)\left(x,y\right)=0$$

are called critical points of $f$ conditioned by the previous spray.

Theorem 2.4 If $\left(x_0,y_0\right)\in D$ is a conditioned critical point of the function $f:D\to \mathbb{R}$ of class $C^2$ constrained by the previous spray and if the number

$$\left(d^{2}f\left(Y,Y\right)+\mathit{df}\left(D_{Y}Y\right)\right)\left(x_0,y_0\right)$$

is strictly positive (negative), then $\left(x_0,y_0\right)$ is a minimum (maximum) point of $f$ constrained by the spray.

Example 2.2 We consider the Volterra-Hamilton ODE system [2].

$$\frac{{\mathit{dx}}^1}{\mathit{dt}}\left(t\right)=y^1\left(t\right),\frac{{\mathit{dx}}^2}{\mathit{dt}}\left(t\right)=y^2\left(t\right),$$

$$\frac{{\mathit{dy}}^1}{\mathit{dt}}\left(t\right)=\lambda y^1\left(t\right)-{\alpha }_1{y}^{1^2}\left(t\right)-2{\alpha }_2{y}^1\left(t\right)y^2\left(t\right),$$

$$\frac{{\mathit{dy}}^2}{\mathit{dt}}\left(t\right)=\lambda y^1\left(t\right)-{\beta }_1{y}^{2^2}\left(t\right)-2{\beta }_2{y}^1\left(t\right)y^2\left(t\right),$$

which models production in a Gause-Witt $2$-species evolving in ${\mathbb{R}}^4$: (1) competition if ${\alpha }_1>0$, ${\alpha }_2>0$, ${\beta }_1>0$, ${\beta }_2>0$ and (2) parasitism if ${\alpha }_1>0$, ${\alpha }_2<0$, ${\beta }_1>0$, ${\beta }_2>0$.

Changing the real parameter $t$ into an affine parameter $s$, we find the connection with constant coefficients

$${\mathrm{\Gamma }}_{11}^1=\frac{1}{3}\left({\alpha }_1-2{\beta }_2\right),{\mathrm{\Gamma }}_{22}^2=\frac{1}{3}\left({\beta }_1-2{\alpha }_2\right),$$

$${\mathrm{\Gamma }}_{12}^1=\frac{1}{3}\left(2{\alpha }_2-{\beta }_1\right),{\mathrm{\Gamma }}_{12}^2=\frac{1}{3}\left(2{\beta }_2-{\alpha }_1\right).$$

Let $x\left(t,x_0,y_0\right),t\in I$ be the maximal field line which satisfies $x\left(t_0,x_0,y_0\right)=\left(x_0,y_0\right)$. We wish to compute $maxf\left(x^1,x^2,y^1,y^2\right)=y^2$ with the restriction $x=x\left(t,x_0,y_0\right)$.

We apply the previous theory. Introduce the vector field

$$Y=\left(y^1,y^2,\lambda y^1-{\alpha }_1{y}^{1^2}-2{\alpha }_2{y}^1{y}^2,\lambda y^1-{\beta }_1{y}^{2^2}-2{\beta }_2{y}^1{y}^2\right).$$

We set the critical point condition $\mathit{df}\left(Y\right)=0$. Since $\mathit{df}=\left(\mathrm{0,0,0,1}\right)$, it follows the relation $\lambda y^1-{\beta }_1{y}^{2^2}-2{\beta }_2{y}^1{y}^2=0$, that is, the critical point set is a conic in $y^1{\mathit{Oy}}^2$.

Since $d^{2}f=0$, the sufficiency condition is reduced to $\mathit{df}\left(D_{Y}Y\right)\left(x_0,y_0\right)<0$, that is,

$$\left(\lambda -\frac{{\alpha }_1{\beta }_1{y}^{22}}{\lambda -2{\beta }_2{y}^2}-2{\alpha }_2{y}^2\right)\left(y_0\right)<0.$$

This last relation is equivalent either to

$$\left(\lambda -2{\alpha }_2{y}_0^2\right)\left(\lambda -2{\beta }_2{y}_0^2\right)-{\alpha }_1{\beta }_1{y_0^2}^2<0,\lambda -2{\beta }_2{y}_0^2>0$$

or to

$$\left(\lambda -2{\alpha }_2{y}_0^2\right)\left(\lambda -2{\beta }_2{y}_0^2\right)-{\alpha }_1{\beta }_1{y_0^2}^2>0,\lambda -2{\beta }_2{y}_0^2<0.$$

Each critical point satisfying one of the last two conditions is a maximum point.

3. Affine convexity of posynomial functions

For the general theory regarding geometric programming (based on posynomial, signomial functions, etc.), see [11].

Theorem 3.1 Each posynomial function is affine convex, with respect to some affine connection.

Proof. A posynomial function has the form

$$f:{\mathbb{R}}_{++}^n\to \mathbb{R},f\left(x\right)=\sum _{k=1}^K{c}_k\prod _{i=1}^n{\left(x^i\right)}^{a_{\mathit{ik}}},$$

where all the coefficients $c_k$ are positive real numbers, and the exponents $a_{\mathit{ik}}$ are real numbers. Let us consider the auto-parallel curves of the form

$$\gamma \left(t\right)=\left({\left(a^1\right)}^{1-t}{\left(b^1\right)}^t,{\left(a^2\right)}^{1-t}{\left(b^2\right)}^t,\dots ,{\left(a^n\right)}^{1-t}{\left(b^n\right)}^t\right),t\in \left[0,1\right],$$

joining the points $a=\left(a^1,\dots ,a^n\right)$ and $b=\left(b^1,\dots ,b^n\right)$, which fix, as example, the affine connection

$${\mathrm{\Gamma }}_{\mathit{hj}}^h={\mathrm{\Gamma }}_{\mathit{jh}}^h=-\frac{1}{2}\frac{{\mu }^h}{{\mu }^j{x}^j},\text{and}\text{otherwise}{\mathrm{\Gamma }}_{\mathit{ij}}^h=0.$$

It follows

$$f\left(\gamma \left(t\right)\right)=\sum _{k=1}^K{c}_k\prod _{i=1}^n{\left({\left(a^i\right)}^{a_{\mathit{ik}}}\right)}^{1-t}{\left({\left(b^i\right)}^{a_{\mathit{ik}}}\right)}^t$$

$$=\sum _{k=1}^K{c}_k{\left(\prod _{i=1}^n{\left(a^i\right)}^{a_{\mathit{ik}}}\right)}^{1-t}{\left(\prod _{i=1}^n{\left(b^i\right)}^{a_{\mathit{ik}}}\right)}^t.$$

One term in this sum is of the form ${\psi }_k\left(t\right)=A_k^{1-t}{B}_k^t$, and hence ${\ddot{\psi }}_k\left(t\right)=A_k^{1-t}{B}_k^t{\left(ln{A}_k-ln{B}_k\right)}^2>0.$

Remark 3.1 Posynomial functions belong to the class of functions satisfying the statement “product of two convex function is convex”.

Corollary 3.1 Each signomial function is difference of two affine convex posynomials, with respect to some affine connection.

Proof. A signomial function has the form

$$f:{\mathbb{R}}_{++}^n\to \mathbb{R},f\left(x\right)=\sum _{k=1}^K{c}_k\prod _{i=1}^n{\left(x^i\right)}^{a_{\mathit{ik}}},$$

where all the exponents $a_{\mathit{ik}}$ are real numbers and the coefficients $c_k$ are either positive or negative. Without loss of generality, suppose that for $k=1,\dots ,k_0$ we have $c_k>0$ and for $k=k_0+1,\dots ,K$ we have $c_k<0$. We use the decomposition

$$f\left(x\right)=\sum _{k=1}^{k_0}{c}_k\prod _{i=1}^n{\left(x^i\right)}^{a_{\mathit{ik}}}-\sum _{k=k_0+1}^K\mid c_k\mid \prod _{i=1}^n{\left(x^i\right)}^{a_{\mathit{ik}}},$$

we apply the Theorem and the implication $u^{″}\left(t\right)\ge v^{″}\left(t\right)$ $\Rightarrow$ $u-v$ convex.□

Corollary 3.2 (1) The polynomial functions with positive coefficients, restricted to ${\mathbb{R}}_{++}^n$, are affine convex functions.

(2) The polynomial functions with positive and negative terms, restricted to ${\mathbb{R}}_{++}^n$, are differences of two affine convex functions.

Proudnikov [18] gives the necessary and sufficient conditions for representing Lipschitz multivariable function as a difference of two convex functions. An algorithm and a geometric interpretation of this representation are also given. The outcome of this algorithm is a sequence of pairs of convex functions that converge uniformly to a pair of convex functions if the conditions of the formulated theorems are satisfied.

4. Bilevel disjunctive problem

Let $\left(M_1{,}^1\mathrm{\Gamma }\right)$, the leader decision affine manifold, and $\left(M_2{,}^2\mathrm{\Gamma }\right)$, the follower decision affine manifold, be two connected affine manifolds of dimension $n_1$ and $n_2$, respectively. Moreover, $\left(M_2{,}^2\mathrm{\Gamma }\right)$ is supposed to be complete. Let also $f:M_1\times M_2\to \mathbb{R}$ be the leader objective function, and let $F=\left(F_1,\dots ,F_r\right):M_1\times M_2\to {\mathbb{R}}^r$ be the follower multiobjective function.

The components $F_i:M_1\times M_2\to \mathbb{R}$ are (possibly) conflicting objective functions.

A bilevel optimization problem means a decision of leader with regard to a multi-objective optimum of the follower (in fact, a constrained optimization problem whose constraints are obtained from optimization problems). For details, see [5, 10, 12].

Let $x\in M_1$, $y\in M_2$ be the generic points. In this chapter, the disjunctive solution set of a follower multiobjective optimization problem is defined by

(1) the set-valued function

$$\psi :M_1\rightrightarrows M_2,\psi \left(x\right)={\text{Argmin}}_{y\in M_2}F\left(x,y\right),$$

where

$${\text{Argmin}}_{y\in M_2}F\left(x,y\right)≔{\cup }_{i=1}^r{\text{Argmin}}_{y\in M_2}{F}_i\left(x,y\right)$$

or

(2) the set-valued function

$$\psi :M_1\rightrightarrows M_2,\psi \left(x\right)={\text{Argmax}}_{y\in M_2}F\left(x,y\right),$$

where

$${\text{Argmax}}_{y\in M_2}F\left(x,y\right)≔{\cup }_{i=1}^r{\text{Argmax}}_{y\in M_2}{F}_i\left(x,y\right).$$

We deal with two bilevel problems:

(1) The optimistic bilevel disjunctive problem

$$\left(\mathit{\text{OBDP}}\right)\underset{x\in M_1}{min}\underset{y\in \psi \left(x\right)}{min}f\left(x,y\right).$$

In this case, the follower cooperates with the leader; that is, for each $x\in M_1$, the follower chooses among all its disjunctive solutions (his best responses) one which is the best for the leader (assuming that such a solution exists).

(2) The pessimistic bilevel disjunctive problem

$$\left(\mathit{\text{PBDP}}\right)\underset{x\in M_1}{min}\underset{y\in \psi \left(x\right)}{max}f\left(x,y\right).$$

In this case, there is no cooperation between the leader and the follower, and the leader expects the worst scenario; that is, for each $x\in M_1$, the follower may choose among all its disjunctive solutions (his best responses) one which is unfavorable for the leader.

So, a general optimization problem becomes a pessimistic bilevel problem.

Theorem 4.1 The value

$$\underset{x}{min}\left[f\left(x,y\right):y\in \psi \left(x\right)\right]$$

exists if and only if, for an index $i$, the minimum ${min}_x\left[f\left(x,y\right):y\in {\psi }_i\left(x\right)\right]$ exists and, for each $j\ne i$, either ${min}_x\left[f\left(x,y\right):y\in {\psi }_j\left(x\right)\right]$ exists or ${\psi }_j=\mathrm{Ø}$. In this case,

$$\underset{x}{min}\left[f\left(x,y\right):y\in \psi \left(x\right)\right]$$

coincides to the minimum of minima that exist.

Proof. Let us consider the multi-functions ${\varphi }_i\left(x\right)=f\left(x,{\psi }_i\left(x\right)\right)$ and $\varphi \left(x\right)=f\left(x,\psi \left(x\right)\right)$. Then $\varphi \left(x\right)={\cup }_{i=1}^k{\varphi }_i\left(x\right)$. It follows that ${min}_x\varphi \left(x\right)$ exists if and only if either ${min}_x{\varphi }_i\left(x\right)$ exists or ${\psi }_i=\varnothing$, and at least one minimum exists.

Taking minimum of minima that exist, we find

$$\underset{x}{min}\left[f\left(x,y\right):y\in \psi \left(x\right)\right].\square$$

Theorem 4.2 Suppose $M_1$ is a compact manifold. If for each $x\in M_1$, at least one partial function $y\to F_i\left(x,y\right)$ is affine convex and has a critical point, then the problem $\left(\mathit{\text{OBDP}}\right)$ has a solution.

Proof. In our hypothesis, the set $\psi \left(x\right)$ is nonvoid, for any $x$, and the compacity assures the existence of ${min}_{x}f\left(x,\psi \left(x\right)\right)$.

In the next Theorem, we shall use the Value Function Method or Utility Function Method.□

Theorem 4.3 If a $C^1$ increasing scalarization partial function

$$y\to L\left(x,y\right)=u\left(F_1\left(x,y\right),\dots ,F_k\left(x,y\right)\right)$$

has a minimum, then there exists an index $i$ such that ${\psi }_i\left(x\right)\ne \varnothing$. Moreover, if $f\left(x,y\right)$ is bounded, then the bilevel problem

$$\underset{x}{min}\left[f\left(x,y\right):y\in \psi \left(x\right)\right]$$

has solution.

Proof. Let ${min}_{y}L\left(x,y\right)=L\left(x,y^{\ast }\right)$. Suppose that for each $i=1,\dots ,k,$ ${min}_y{F}_i\left(x,y\right)<F_i\left(x,y^{\ast }\right)$. Then $y^{\ast }$ would not be minimum point for the partial function $y\to L\left(x,y\right)$. Hence, there exists an index $i$ such that $y^{\ast }\in {\psi }_i\left(x\right)$.□

Boundedness of $f$ implies that the bilevel problem has solution once it is well-posed, but the fact that the problem is well-posed is shown in the first part of the proof.

4.1. Bilevel disjunctive programming algorithm

An important concept for making wise tradeoffs among competing objectives is bilevel disjunctive programming optimality, on affine manifolds, introduced in this chapter.

We present an exact algorithm for obtaining the bilevel disjunctive solutions to the multi-objective optimization in the following section.

Step 1: Solve

$${\psi }_i\left(x\right)={\text{Argmin}}_{y\in M_2}{F}_i\left(x,y\right),i=1,\dots ,m.$$

Let $\psi \left(x\right)={\cup }_{i=1}^r{\psi }_i\left(x\right)$ be a subset in $M_2$ representing the mapping of optimal solutions for the follower multi-objective function.

Step 2: Build the mapping $f(x,\psi \left(x\right)$.

Step 3: Solve the leader’s following program

$$\underset{x}{min}\left[f\left(x,y\right),y\in \psi \left(x\right)\right].$$

From numerical point of view, we can use the Newton algorithm for optimization on affine manifolds, which is given in [19].

5. Models of bilevel disjunctive programming problems

The manifold $M$ is understood from the context. The connection ${\mathrm{\Gamma }}_{\mathit{ij}}^h$ can be realized in each case, imposing convexity conditions.

Example 5.1 Let us solve the problem (cite [7], p. 7; [9]):

$$\underset{\left(x_1,x_2\right)}{min}F\left(x_1,x_2,y\right)=\left(x_1-y,x_2\right)$$

subject to

$$\left(x_1,x_2\right)\in {\mathit{\text{Argmin}}}_{\left(x_1,x_2\right)}\left\{\left(x_1,x_2\right)|y^2-x_1^2-x_2^2\ge 0\right\},$$

$$1+x_1+x_2\ge 0,-1\le x_1,x_2\le 1,0\le y\le 1.$$

Both the lower and the upper level optimization tasks have two objectives each. For a fixed $y$ value, the feasible region of the lower-level problem is the area inside a circle with center at origin $\left(x_1=x_2=0\right)$ and radius equal to $y$. The Pareto-optimal set for the lower-level optimization task, preserving a fixed $y$, is the bottom-left quarter of the circle,

$$\left\{\left(x_1,x_2\right)\in {\mathbb{R}}^2|x_1^2+x_2^2=y^2,x_1\le 0,x_2\le 0\right\}.$$

The linear constraint in the upper level optimization task does not allow the entire quarter circle to be feasible for some $y$. Thus, at most a couple of points from the quarter circle belongs to the Pareto-optimal set of the overall problem. Eichfelder [8] reported the following Pareto-optimal set of solutions

$$A=\left\{\left(x_1,x_2,y\right)\in {\mathbb{R}}^3|x_1=-1-x_2,x_2=-\frac{1}{2}\pm \frac{1}{2}\sqrt{2y^2-1},y\in \left[\frac{1}{\sqrt{2}},1\right]\right\}.$$

The Pareto-optimal front in $F_1-F_2$ space can be written in parametric form

$$\left\{\left(F_1,F_2\right)\in {\mathbb{R}}^2|F_1=-1-F_2-t,F_2=-\frac{1}{2}\pm \frac{1}{2}\sqrt{2t^2-1},t\in \left[\frac{1}{\sqrt{2}},1\right]\right\}.$$

Example 5.2 Consider the bilevel programming problem

$$\underset{x}{min}\left[{\left(x-y\right)}^2+x^2:-20\le x\le 20,y\in \psi \left(x\right)\right],$$

where the set-valued function is

$$\psi \left(x\right)={\mathit{\text{Argmin}}}_y\left[\mathit{xy}:-x-1⩽y⩽-x+1\right].$$

Explicitly,

$$\psi \left(x\right)=\left\{\begin{array}{ccc}\left[-1,1\right]& \mathit{\text{if}}x=0& \\ -x-1& \mathit{\text{if}}x>0& \\ -x+1& \mathit{\text{if}}x<0.& \end{array}\right.$$

Since $F\left(x,y\right)={\left(x-y\right)}^2+x^2$, we get

$$F\left(x,\psi \left(x\right)\right)=\left\{\begin{array}{ccc}\left[0,1\right]& \mathit{\text{if}}x=0& \\ {\left(-2x-1\right)}^2+x^2& \mathit{\text{if}}x>0& \\ {\left(-2x+1\right)}^2+x^2& \mathit{\text{if}}x<0.& \end{array}\right.$$

on the regions where the functions are defined.

Taking into account ${\left(-2x-1\right)}^2+x^2>0$ and ${\left(-2x+1\right)}^2+x^2>0$, it follows that $\left(x^{\circ }{y}^{\circ }\right)=\left(0,0\right)$ is the unique optimistic optimal solution of the problem. Now, if the leader is not exactly enough in choosing his solution, then the real outcome of the problem has an objective function value above $1$ which is far away from the optimistic optimal value zero.

Example 5.3 Let $F\left(x,y\right)=\left(F_1\left(x,y\right),F_2\left(x,y\right)\right)$ and a Pareto disjunctive problem

$$\psi \left(x\right)={\mathit{\text{Argmin}}}_{y}F\left(x,y\right)={\mathit{\text{Argmin}}}_y{F}_1\left(x,y\right)\cup {\mathit{\text{Argmin}}}_y{F}_2\left(x,y\right).$$

Then it appears a bilevel disjunctive programming problem of the form

$$\underset{x}{min}\left[f\left(x,y\right),y\in \psi \left(x\right)\right].$$

This problem is interesting excepting the case $\psi \left(x\right)=Ø,\forall x$. If $y\to F_1\left(x,y\right)$ and $y\to F_2\left(x,y\right)$ are convex functions, then $\psi \left(x\right)\ne Ø$.

To write an example, we use

$$F_1\left(x,y\right)=\left[\mathit{xy}:-x-1⩽y⩽-x+1\right],F_2\left(x,y\right)=\left[x^2+y^2:y⩾-x+1\right]$$

and we consider a bilevel disjunctive programming problem of the form

$$\underset{x}{min}\left[{\left(x-y\right)}^2+x^2:-20\le x\le 20,y\in \psi \left(x\right)\right],$$

with

$$\psi \left(x\right)={\psi }_1\left(x\right)\cup {\psi }_2\left(x\right),$$

where

$${\psi }_1\left(x\right)={\mathit{\text{Argmin}}}_y\left[\mathit{xy}:-x-1⩽y⩽-x+1\right]=\left\{\begin{array}{ccc}\left[-1,1\right]& \mathit{\text{if}}& x=0\\ -x-1& \mathit{\text{if}}& x>0\\ -x+1& \mathit{\text{if}}& x<0,\end{array}\right.$$

$${\psi }_2\left(x\right)={\mathit{\text{Argmin}}}_y\left[x^2+y^2:y⩾-x+1\right]=\left\{\begin{array}{ccc}-x+1& \mathit{\text{if}}& x\le 1\\ 0& \mathit{\text{if}}& x>1,\end{array}\right.$$

$$\psi \left(x\right)=\left\{\begin{array}{ccc}\left[-1,1\right]& \mathit{\text{if}}& x=0\\ \left\{-x-1,-x+1\right\}& \mathit{\text{if}}& 0<x\le 1\\ \left\{-x-1,0\right\}& \mathit{\text{if}}& x>1\\ -x+1& \mathit{\text{if}}& x<0.\end{array}\right.$$

The objective $f\left(x,y\right)={\left(x-y\right)}^2+x^2$ and the multi-function $\psi \left(x\right)$ produce a multi-function

$$f\left(x,\psi \left(x\right)\right)=\left\{\begin{array}{ccc}\left[0,1\right]& \mathit{\text{if}}& x=0\\ \left\{{\left(2x+1\right)}^2+x^2,{\left(2x-1\right)}^2+x^2\right\}& \mathit{\text{if}}& 0<x\le 1\\ \left\{{\left(2x+1\right)}^2+x^2,2x^2\right\}& \mathit{\text{if}}& x>1\\ {\left(2x-1\right)}^2+x^2& \mathit{\text{if}}& x<0.\end{array}\right.$$

In context, we find the inferior envelope

$$y\left(x\right)=\left\{\begin{array}{ccc}0& \mathit{\text{if}}& x=0\\ -x+1& \mathit{\text{if}}& 0<x\le 1\\ 0& \mathit{\text{if}}& x>1\\ -x+1& \mathit{\text{if}}& x<0\end{array}\right.$$

and then

$$f\left(x,y\left(x\right)\right)=\left\{\begin{array}{ccc}0& \mathit{\text{if}}& x=0\\ {\left(2x-1\right)}^2+x^2& \mathit{\text{if}}& x\in \left(-\infty ,0\right)\cup \left(0,1\right]\\ 2x^2& \mathit{\text{if}}& x>1.\end{array}\right.$$

Since ${\left(2x-1\right)}^2+x^2>0$, the unique optimal solution is $\left(x^{\circ }{y}^{\circ }\right)=\left(0,0\right)$.

If we consider only ${\psi }_1\left(x\right)$ as active, then the unique optimal solution $\left(0,0\right)$ is maintained. If ${\psi }_2\left(x\right)$ is active, then the optimal solution is $\left(0,1\right)$.

6. Properties of minimum functions

Let $\left(M_1{,}^1\mathrm{\Gamma }\right)$, the leader decision affine manifold, and $\left(M_2{,}^2\mathrm{\Gamma }\right)$, the follower decision affine manifold, be two connected affine manifolds of dimension $n_1$ and $n_2$, respectively. Starting from a function with two vector variables

$$\phi :M_1\times M_2\to \mathbb{R},\left(x,y\right)\to \phi \left(x,y\right),$$

and taking the infimum after one variable, let say $y$, we build a function

$$f\left(x\right)=\underset{y}{inf}\left\{\phi \left(x,y\right):y\in a\left(x\right)\right\},$$

which is called minimum function.

A minimum function is usually specified by a pointwise mapping $a$ of the manifold $M_1$ in the subsets of a manifold $M_2$ and by a functional $\phi \left(x,y\right)$ on $M_1\times M_2$. In this context, some differential properties of such functions were previously examined in [4]. Now we add new properties related to increase and convexity ideas.

First we give a new proof to Brian White Theorem (see Mean Curvature Flow, p. 7, Internet 2017).

Theorem 6.1 Suppose that $M_1$ is compact, $M_2=\left[0,T\right]$ and $f:M_1\times \left[0,T\right]\to \mathbb{R}$. Let $\varphi \left(t\right)={min}_{x}f\left(x,t\right)$. If, for each $x$ with $\varphi \left(t\right)=f\left(x,t\right)$, we have $\frac{\partial f}{\partial t}\left(x,t\right)\ge 0$, then $\varphi$ is an increasing function.

Proof. We shall prove the statement in three steps.

(1) If $f$ is continuous, then $\varphi$ is (uniformly) continuous.

Indeed, $f$ is continuous on the compact $M_1\times \left[0,1\right]$, hence uniformly continuous. So, for $\epsilon >0$ it exists $\delta >0$ such that if $\mid t_1-t_2\mid <\delta$, then $\mid f\left(x,t_1\right)-f\left(x,t_2\right)\mid <\epsilon$, for any $x\in M_1$, or

$$-\epsilon <f\left(x,t_1\right)-f\left(x,t_2\right)<\epsilon$$

On one hand, if we put $\varphi \left(t_1\right)=f\left(x_1,t_1\right)$ and $\varphi \left(t_2\right)=f\left(x_2,t_2\right)$, then we have

$$f\left(x,t_1\right)>f\left(x,t_2\right)-\epsilon \ge f\left(x_2,t_2\right)-\epsilon .$$

Hence ${min}_{x}f\left(x,t_1\right)\ge f\left(x_2,t_2\right)-\epsilon$, so is $\varphi \left(t_1\right)-\varphi \left(t_2\right)\ge -\epsilon$.

On the other hand,

$$f\left(x,t_2\right)+\epsilon >f\left(x,t_1\right)\ge f\left(x_1,t_1\right).$$

Hence ${min}_{x}f\left(x,t_2\right)+\epsilon \ge f\left(x_1,t_1\right)$, so is $\varphi \left(t_1\right)-\varphi \left(t_2\right)\le \epsilon$.

Finally, $\mid \varphi \left(t_1\right)-\varphi \left(t_2\right)\mid \le \epsilon$, for $\mid t_1-t_2\mid <\delta$, that is, $\varphi$ is (uniformly) continuous.

(2) Let us fix $t_0\in \left(0;T\right]$. If $\varphi \left(t_0\right)=f\left(x_0,t_0\right)$ and $\frac{\partial f}{\partial t}\left(x_0,t_0\right)\ge 0$, then it exists $\delta >0$ such that $\varphi \left(t\right)\le \varphi \left(t_0\right)$, for any $t\in \left(t_0-\delta ;t_0\right)$.

Suppose $\frac{\partial f}{\partial t}\left(x_0,t_0\right)>0$, it exists $\delta >0$ such that $f\left(x_0,t\right)\le f\left(x_0,t_0\right)$, for each $t\in \left(t_0-\delta ;t_0\right)$. It follows ${min}_{x}f\left(x,t\right)\le f\left(x_0,t\right)\le f\left(x_0,t_0\right)$, and so is $\varphi \left(t\right)\le \varphi \left(t_0\right)$.

If $\frac{\partial f}{\partial t}\left(x_0,t_0\right)=0$, then we use $\overline{f}\left(x,t\right)=f\left(x,t\right)+\mathit{\epsilon t},$ $\epsilon >0$. For $\overline{f}$, the above proof holds, and we take $\epsilon \to 0$.

(3) $\varphi$ is an increasing function.

Let $0\le a<b\le T$ and note $A=\left\{t\in \left[a,b\right]|\varphi \left(t\right)\le \varphi \left(b\right)\right\}$. $A$ is not empty. If $\alpha =infA$, then, by the step (2), $\alpha <b$ and, by the step (1), $\alpha \in A$. If $\alpha >a$, we can use the step (2) for $t_0=\alpha$ and it would result that $\alpha$ was not the lower bound of $A$. Hence $\alpha =a$ and $\varphi \left(a\right)\le \varphi \left(b\right)$.

Remark The third step shows that a function having the properties (1) and (2) is increasing. For this the continuity is essential. Only property (2) is not enough. For example, the function defined by $\varphi \left(t\right)=t$ on $\left[0,1\right]$ and $\varphi \left(t\right)=1-t$ on $\left(1,2\right]$ has only the property (2), but it is not increasing on $\left[0,2\right]$.

Remark Suppose that $f$ is a $C^2$ function and ${min}_{x}f\left(x,t\right)=f\left(x_0\left(t\right),t\right)$, where $x_0\left(t\right)$ is an interior point of $M$. Since $x_0\left(t\right)$ is a critical point, we have

$${\varphi }^{\text{'}}\left(t\right)=\frac{\partial f}{\partial t}\left(x_0\left(t\right),t\right)+<\frac{\partial f}{\partial x}\left(x_0\left(t\right),t\right),x_0^{\text{'}}\left(t\right)>=\frac{\partial f}{\partial t}\left(x_0\left(t\right),t\right)\ge 0.$$

Consequently, $\varphi \left(t\right)$ is an increasing function. If $M_1$ has a nonvoid boundary, then the monotony extends by continuity (see also the evolution of an extremum problem).

□

Example 6.1 The single-time perspective of a function $f:{\mathbb{R}}^n\to \mathbb{R}$ is the function $g:{\mathbb{R}}^n\times {\mathbb{R}}_{+}\to \mathbb{R}$, $g\left(x,t\right)=\mathit{tf}\left(x/t\right)$, $\mathit{dom}g=\left\{\left(x,t\right)|x/t\in \mathit{dom}f,t>0\right\}$. The single-time perspective $g$ is convex if $f$ is convex.

The single-time perspective is an example verifying Theorem 7.1. Indeed, the critical point condition for $g$, in $x$, $\frac{\partial g}{\partial x}=0$, gives $x={\mathit{tx}}_0$, where $x_0$ is a critical point of $f$. Consequently, $\varphi \left(t\right)={min}_{x}g\left(x,t\right)=\mathit{tf}\left(x_0\right)$. On the other hand, in the minimum point, we have $\frac{\partial g}{\partial t}\left(x,t\right)=f\left(x_0\right)$. Then $\varphi \left(t\right)$ is increasing if $f\left(x_0\right)\ge 0$, as in Theorem 4.1.

Theorem 6.2 Suppose that $M_1$ is compact and $f:M_1\times M_2\to \mathbb{R}$. Let $\varphi \left(y\right)={min}_{x}f\left(x,y\right)$. If, for each $x$ with $\varphi \left(y\right)=f\left(x,y\right)$, we have $\frac{\partial f}{\partial y^{\alpha }}\left(x,y\right)\ge 0$, then $\varphi \left(y\right)$ is a partially increasing function.

Proof. Suppose that $f$ is a $C^2$ function and ${min}_{x}f\left(x,y\right)=f\left(x_0\left(y\right),y\right)$, where $x_0\left(y\right)$ is an interior point of $M_1$. Since $x_0\left(y\right)$ is a critical point, we have

$$\frac{\partial \varphi }{\partial y^{\alpha }}=\frac{\partial f}{\partial y^{\alpha }}\left(x_0\left(y\right),y\right)+<\frac{\partial f}{\partial x}\left(x_0\left(y\right),y\right),\frac{\partial x_0}{\partial y^{\alpha }}>=\frac{\partial f}{\partial y^{\alpha }}\left(x_0\left(y\right),y\right)\ge 0.$$

Consequently, $\varphi \left(y\right)$ is a partially increasing function. If $M$ has a non-void boundary, then the monotony extends by continuity.□

Theorem 6.3 Suppose that $M_1$ is compact and $f:M_1\times M_2\to \mathbb{R}$. Let $\varphi \left(y\right)={min}_{x}f\left(x,y\right)$. If, for each $x$ with $\varphi \left(y\right)=f\left(x,y\right)$, we have $d_y^{2}f\left(x,y\right)\le 0$, then $\varphi \left(y\right)$ is an affine concave function.

Proof. Without loss of generality, we work on Euclidean case. Suppose that $f$ is a $C^2$ function and ${min}_{x}f\left(x,y\right)=f\left(x\left(y\right),y\right)$, where $x\left(y\right)$ is an interior point of $M_1$. Since $x\left(y\right)$ is a critical point, we must have

$$\frac{\partial f}{\partial x^i}\left(x\left(y\right),y\right)=0.$$

Taking the partial derivative with respect to $y^{\alpha }$ and the scalar product with $\frac{\partial x^i}{\partial y^{\beta }}$ it follows

$$\frac{{\partial }^{2}f}{\partial x^i\partial x^j}\frac{\partial x^j}{\partial y^{\alpha }}\frac{\partial x^i}{\partial y^{\beta }}+\frac{{\partial }^{2}f}{\partial y^{\alpha }\partial x^i}\frac{\partial x^i}{\partial y^{\beta }}=0.$$

On the other hand

$$d_y\varphi \left(y\right)=d_{y}f\left(x\left(y\right),y\right)=\left(\frac{\partial f}{\partial x^i}\frac{\partial x^i}{\partial y^{\alpha }}+\frac{\partial f}{\partial y^{\alpha }}\right){\mathit{dy}}^{\alpha }=\frac{\partial f}{\partial y^{\alpha }}{\mathit{dy}}^{\alpha }$$

$$d_y^2\varphi \left(y\right)=\left(\frac{{\partial }^{2}f}{\partial y^{\alpha }\partial x^i}\frac{\partial x^i}{\partial y^{\beta }}+\frac{{\partial }^{2}f}{\partial y^{\alpha }\partial y^{\beta }}\right){\mathit{dy}}^{\alpha }{\mathit{dy}}^{\beta }$$

$$=\left(-\frac{{\partial }^{2}f}{\partial x^j\partial x^i}\frac{\partial x^i}{\partial y^{\beta }}\frac{\partial x^j}{\partial y^{\alpha }}+\frac{{\partial }^{2}f}{\partial y^{\alpha }\partial y^{\beta }}\right){\mathit{dy}}^{\alpha }{\mathit{dy}}^{\beta }\le 0.$$

□

Theorem 6.4 Let $f:M_1\times M_2\to \mathbb{R}$ be a $C^2$ function and

$$\varphi \left(y\right)=\underset{x}{min}f\left(x,y\right)=f\left(x\left(y\right),y\right).$$

If the set $A=\left\{\left(x\left(y\right),y\right):y\in M_2\right\}$ is affine convex and ${\left.f\right|}_A$ is affine convex, then $\varphi \left(y\right)$ is affine convex.

Proof. Suppose $f$ is a $C^2$ function. At points $\left(x\left(y\right),y\right)$, we have

$$0\le d^{2}f\left(x\left(y\right),y\right)=\left(\frac{{\partial }^{2}f}{\partial x^i\partial x^j}\frac{\partial x^i}{\partial y^{\alpha }}\frac{\partial x^j}{\partial y^{\beta }}+2\frac{{\partial }^{2}f}{\partial x^i\partial y^{\alpha }}\frac{\partial x^i}{\partial y^{\beta }}+\frac{{\partial }^{2}f}{\partial y^{\alpha }\partial y^{\beta }}\right){\mathit{dy}}^{\alpha }{\mathit{dy}}^{\beta }$$

$$\hspace{1em}\hspace{1em}\hspace{1em}=\left(\frac{{\partial }^{2}f}{\partial x^i\partial y^{\alpha }}\frac{\partial x^i}{\partial y^{\beta }}+\frac{{\partial }^{2}f}{\partial y^{\alpha }\partial y^{\beta }}\right){\mathit{dy}}^{\alpha }{\mathit{dy}}^{\beta }=d^2\varphi \left(y\right).$$