Open access peer-reviewed chapter

# Bilevel Disjunctive Optimization on Affine Manifolds

Written By

Constantin Udriste, Henri Bonnel, Ionel Tevy and Ali Sapeeh Rasheed

Submitted: October 24th, 2017 Reviewed: February 19th, 2018 Published: September 5th, 2018

DOI: 10.5772/intechopen.75643

From the Edited Volume

## Optimization Algorithms

Edited by Jan Valdman

Chapter metrics overview

View Full Metrics

## 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.

### Keywords

• convex programming
• affine manifolds
• optimization along curves
• bilevel disjunctive optimization
• minimum functions
• Mathematics Subject Classification 2010: 90C25
• 90C29
• 90C30

## 1. Affine convex functions

In optimization problems [16, 17, 19, 23, 24, 25, 26, 27], one can use an affine manifold as a pair MΓ, where M is a smooth real n-dimensional manifold, and Γ is an affine symmetric connection on M. The connection Γ produces auto-parallel curves xt via ODE system

x¨ht+Γijhxtẋitẋjt=0.

They are used for defining the convexity of subsets in M and convexity of functions f:DMR (see also [3, 6]).

Definition 1.1 An affine manifold MΓ is called autoparallely complete if any auto-parallel xt starting at pM is defined for all values of the parameter tR.

Theorem 1.1 [1] Let M be a (Hausdorff, connected, smooth) compact n-manifold endowed with an affine connection Γ and let pM. If the holonomy group HolpΓ (regarded as a subgroup of the group GlTpM of all the linear automorphisms of the tangent space TpM) has compact closure, then MΓ is autoparallely complete.

Let MΓ be an auto-parallely complete affine manifold. For a C2 function f:MR, we define the tensor HessΓf of components

HessΓfij=2fxixjΓijhfxh.

Definition 1.2 A C2 function f:MR is called:

(1) linear affine with respect to Γ if HessΓf=0, throughout;

(2) affine convex (convex with respect to Γ) if HessΓf0 (positive semidefinite), throughout.

The function f is: (1) linear affine if its restriction fxt on each autoparallel xt satisfies fxt=at+b, for some numbers a,b that may depend on xt; (2) affine convex if its restriction fxt is convex on each auto-parallel xt.

Theorem 1.2 If there exists a linear affine nonconstant function f on MΓ, then the curvature tensor field Rhikj is in Kerdf.

Proof. For given Γ, if we consider

2fxixj=Γijhfxh

as a PDEs system (a particular case of a Frobenius-Mayer system of PDEs) with 12nn+1 equations and the unknown function f, then we need the complete integrability conditions

3fxixjxk=3fxkxixj.

Since,

3fxixjxk=Γijhxk+ΓijlΓklhfxh,

it follows

fxhRhikj=0,Rhikj=ΓijhxkΓkihxj+ΓijlΓklhΓkilΓjlh.

Corollary 1.1 If there exists n linear affine functions fl,l=1,,n on MΓ, whose dfl are linearly independent, then Γ is flat, that is, Rhikj=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 dflx. 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 dflx to the entire manifold. If this could be done, then dflx would now be everywhere nonzero co-vector fields; but there are topologies, for example, S2, 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:MR be a C2 function.

(1) If f is regular or has only one minimum point, then there exists a connection Γ such that f is affine convex.

(2) If f has a maximum point x0, then there is no connection Γ making f affine convex throughout.

Proof. For the Hessian HessΓfij be positive semidefinite, we need n conditions like inequalities and equalities. The number of unknowns Γijh is 12n2n+1. 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 fxc, x=x1xnRn, c=c1cmRm, of real differentiable functions, with m4 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 fxc 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 fxc affine convex on M.

At any critical point x0, the affine Hessian HessΓf is reduced to Euclidean Hessian, 2fxixjx0. 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 MΓ be an affine manifold and f:MR be a C2 function.

Suppose f has no critical points (is regular). If the function f is not convex with respect to Γ, we look to find a new connection Γ¯ijh=Γijh+Tijh, with the unknown a tensor field Tijh, such that

2fxixjxΓ¯ijhxfxhx=σijx,xM,

where σijx is a positive semi-definite tensor. A very particular solution is the decomposition Tijhx=ahxbijx, where the vector field a has the property

Daf=ahxfxhx0,xM

and the tensor bij is

bijx=1Daf2fxixjxΓijhxfxhxσijx,xM.

Remark 1.2 The connection Γ¯ijh is strongly dependent on both the function f and the tensor field σij.

Suppose f has a minimum point x0. In this case, observe that we must have the condition σijx0=2fxixjx0. Can we make the previous reason for xx0 and then extend the obtained connection by continuity? The answer is generally negative. Indeed, let us compute

bijx0=limxx01Daf2fxixjxΓijhxfxhxσijx.

Here we cannot plug in the point x0 because we get 00, an indeterminate form.

To contradict, we fix an auto-parallel γt,t0ϵ, starting from minimum point x0=γ0, tangent to γ̇0=v and we compute (via l’Hôpital rule)

bijx0v=limt0bijγt=3fxixjxkx0Γijhx02fxhxkx0σijxkx0vkahx02fxhxkx0vk.

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

3fxixjxlx0Γijhx02fxhxlx0σijxlx0
=ρ3fxixjxkx0Γijhx02fxhxkx0σijxkx0,
ahx02fxhxlx0=ρahx02fxhxkx0

are sufficient to do this.

A particular condition for independence on v is

3fxixjxkx0Γijhx02fxhxkx0σijxkx0=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:R2R,fxy=x3+y3+3x+3y and Γijh=0,i,j,h=1,2. Then fx=3x2+3,fy=3y2+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 σijxy=δij. Taking a1=a2=1, we obtain the connection

Γ¯11h=6x13x2+3y2+2,Γ¯22h=6y13x2+3y2+2,Γ¯12h=Γ¯21h=0,h=1,2,

that is not unique.

Example 1.2 (for one minimum point) Let us consider the function f:R2R,fxy=1ex2+y2 and Γijh=0,i,j,h=1,2. Then fx=2xex2+y2,fy=2yex2+y2 and f has a unique critical minimum point 00. However, the Euclidean Hessian of f is not positive semi-definite overall. We make previous reason for σij=2ex2+y2δij,a1=fx,a2=fy. Hence we obtain Γ¯ijh=Tijh,

Γ¯111=2x3x2+y2,Γ¯121=Γ¯211=2x2yx2+y2,Γ¯221=2xy2x2+y2,
Γ¯112=2x2yx2+y2,Γ¯122=Γ¯212=2xy2x2+y2,Γ¯222=2y3x2+y2.

Observe that limxy00Tijhxy=0. Hence take Γ¯ijh00=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:RR,fx=x3, where the critical point x=0 is an inflection point. We take Γx=12x2, which is not defined at the critical point x=0, but the relation of convexity is realized by prolongation,

σx=f(x)Γxfx=3x2+2x+2>0,xR.

Let us consider the ODE of auto-parallels

xt1+2t2xt2=0,t0.

The solutions

xt=12ln2+t2ct+c8+c2arctanh2tc8+c2+c1

are auto-parallels on R\0t1t2Γ, where t1,t2 are real solutions of 2+t2ct=0. These curves are extended at t=0 by continuity. The manifold RΓ is not auto-parallely complete. Since the image xR is not a “segment”, the function f:RR,fx=x3 is not globally convex.

Remark 1.3 For n2, there exists C1 functions φ:RnR which have two minimum points without having another extremum point. As example,

φx1x2=x1212+x12x2x112

has two (global) minimum points p=10,q=12.

The restriction

φx1x2=x14+x14x22+2x1+2x12+2x13x2+2x12x2,x1>0,x2>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 xt on the affine manifold MΓ are solutions of the second order ODE system

x¨ht+Γijhxtẋitẋjt=0,xt0=x0,ẋt0=ξ0.

Obviously, the complete notation is xtx0ξ0, with

xt0x0ξ0=x0,ẋt0x0ξ0=ξ0.

Definition 2.1 Let DM be open and connected and f:DR a C2 function. The point x0D is called minimum (maximum) point of f conditioned by the auto-parallel system, together with initial conditions, if for the maximal solution xtx0ξ0:ID, there exists a neighborhood It0 of t0 such that

fxtx0ξ0fx0,tIt0I.

Theorem 2.1 If x0D is an extremum point of f conditioned by the previous second order system, then dfx0ξ0=0.

Definition 2.2 The points xD which are solutions of the equation dfxξ=0 are called critical points of f conditioned by the previous spray.

Theorem 2.2 If x0D is a conditioned critical point of the function f:DR of class C2 constrained by the previous auto-parallel system and if the number

Hessfijξ0iξ0j=2fxixjfxhΓijhx0ξ0iξ0j

is strictly positive (negative), then x0 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 S2, using spherical coordinates θφ and the Riemannian metric

gθθ=1,gθφ=gφθ=0,gφφ=sin2θ.

When θ0,π, we find

Γφφθ=12sin2θ,Γφθφ=Γθφφ=cotθ,

and all the other Γs are equal to zero. We can show that the apparent singularity at θ=0,π 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 S2 are

θ¨t12sin2θtφ̇tφ̇t=0,φ¨t2cotθtφ̇tθ̇t=0.

The solutions are great circles on the sphere. For example, θ=αt+β and φ = const.

We compute the curvature tensor R of the unit sphere S2. Since there are only two independent coordinates, all the non-zero components of curvature tensor R are given by Rji=Rjθφi=Rjφθi, where i,j=θ,φ. We get Rφθ=sin2θ,Rθφ=1 and the other components are 0.

Let (θtθ0φ0ξ,φtθ0φ0ξ,tR be the maximal auto-parallel which satisfies θt0θ0φ0ξ=θ0, θ̇t0θ0φ0ξ=ξ1; φt0θ0φ0ξ=φ0, φ̇t0θ0φ0ξ=ξ2. We wish to compute minfθφ=Rφθ=sin2θ with the restriction θtθ0φ0ξφt,θ0φ0ξ,tR.

Since df=2sinθcosθ0, the critical point condition dfθφξ=0 becomes sinθcosθξ1=0. Consequently, the critical points are either θ0=kφ,ξ1ξ200, or θ1=2k+1π2kφ,ξ1ξ200, or θφ,ξ1=0ξ20.

The components of the Hessian of f are

Hessfθθ=2fθθ=2cos2θ,Hessfθφ=0,Hessfφφ=12sin22θ.

At the critical points θ0φ or θ1φ, the Hessian of f is positive or negative semi-definite. On the other hand, along ξ1=0ξ20, we find Hessfijξiξj=12sin22θξ22>0,ξ20. Consequently, each point θ2φ, is a minimum point of f along each auto-parallel, starting from given point and tangent to ξ1=0ξ20.

### 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) Yxy=yhΓijhxyiyj on the tangent bundle TM, that is,

ẋht=yht,ẏht+Γijhxtyityjt=0.

The solutions γt=xtyt:ID of class C2 are called field lines of Y. They depend on the initial condition γtt=t0=x0y0, and therefore the notation γtx0y0 is more suggestive.

Definition 2.3 Let DTM be open and connected and f:DR a C2 function. The point x0y0D is called minimum (maximum) point of f conditioned by the previous spray, if for the maximal field line γtx0y0,tI, there exists a neighborhood It0 of t0 such that

fγtx0y0fx0y0,tIt0I.

Theorem 2.3 If x0y0D is an extremum point of f conditioned by the previous spray, then x0y0 is a point where Y is in Kerdf.

Definition 2.4 The points xyD which are solutions of the equation

DYfxy=dfYxy=0

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

Theorem 2.4 If x0y0D is a conditioned critical point of the function f:DR of class C2 constrained by the previous spray and if the number

d2fYY+dfDYYx0y0

is strictly positive (negative), then x0y0 is a minimum (maximum) point of f constrained by the spray.

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

dx1dtt=y1t,dx2dtt=y2t,
dy1dtt=λy1tα1y12t2α2y1ty2t,
dy2dtt=λy1tβ1y22t2β2y1ty2t,

which models production in a Gause-Witt 2-species evolving in R4: (1) competition if α1>0, α2>0, β1>0, β2>0 and (2) parasitism if α1>0, α2<0, β1>0, β2>0.

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

Γ111=13α12β2,Γ222=13β12α2,
Γ121=132α2β1,Γ122=132β2α1.

Let xtx0y0,tI be the maximal field line which satisfies xt0x0y0=x0y0. We wish to compute maxfx1x2y1y2=y2 with the restriction x=xtx0y0.

We apply the previous theory. Introduce the vector field

Y=y1y2λy1α1y122α2y1y2λy1β1y222β2y1y2.

We set the critical point condition dfY=0. Since df=0,0,0,1, it follows the relation λy1β1y222β2y1y2=0, that is, the critical point set is a conic in y1Oy2.

Since d2f=0, the sufficiency condition is reduced to dfDYYx0y0<0, that is,

λα1β1y22λ2β2y22α2y2y0<0.

This last relation is equivalent either to

λ2α2y02λ2β2y02α1β1y022<0,λ2β2y02>0

or to

λ2α2y02λ2β2y02α1β1y022>0,λ2β2y02<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:R++nR,fx=k=1Kcki=1nxiaik,

where all the coefficients ck are positive real numbers, and the exponents aik are real numbers. Let us consider the auto-parallel curves of the form

γt=a11tb1ta21tb2tan1tbnt,t01,

joining the points a=a1an and b=b1bn, which fix, as example, the affine connection

Γhjh=Γjhh=12μhμjxj,andotherwiseΓijh=0.

It follows

fγt=k=1Kcki=1naiaik1tbiaikt
=k=1Kcki=1naiaik1ti=1nbiaikt.

One term in this sum is of the form ψkt=Ak1tBkt, and hence ψ¨kt=Ak1tBktlnAklnBk2>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:R++nR,fx=k=1Kcki=1nxiaik,

where all the exponents aik are real numbers and the coefficients ck are either positive or negative. Without loss of generality, suppose that for k=1,,k0 we have ck>0 and for k=k0+1,,K we have ck<0. We use the decomposition

fx=k=1k0cki=1nxiaikk=k0+1Kcki=1nxiaik,

we apply the Theorem and the implication utvt uv convex.□

Corollary 3.2 (1) The polynomial functions with positive coefficients, restricted to R++n, are affine convex functions.

(2) The polynomial functions with positive and negative terms, restricted to 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 M1,1Γ, the leader decision affine manifold, and M2,2Γ, the follower decision affine manifold, be two connected affine manifolds of dimension n1 and n2, respectively. Moreover, M2,2Γ is supposed to be complete. Let also f:M1×M2R be the leader objective function, and let F=F1Fr:M1×M2Rr be the follower multiobjective function.

The components Fi:M1×M2R 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 xM1, yM2 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

ψ:M1M2,ψx=ArgminyM2Fxy,

where

ArgminyM2Fxyi=1rArgminyM2Fixy

or

(2) the set-valued function

ψ:M1M2,ψx=ArgmaxyM2Fxy,

where

ArgmaxyM2Fxyi=1rArgmaxyM2Fixy.

We deal with two bilevel problems:

(1) The optimistic bilevel disjunctive problem

OBDPminxM1minyψxfxy.

In this case, the follower cooperates with the leader; that is, for each xM1, 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

PBDPminxM1maxyψxfxy.

In this case, there is no cooperation between the leader and the follower, and the leader expects the worst scenario; that is, for each xM1, 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

minxfxy:yψx

exists if and only if, for an index i, the minimum minxfxy:yψix exists and, for each ji, either minxfxy:yψjx exists or ψj=Ø. In this case,

minxfxy:yψx

coincides to the minimum of minima that exist.

Proof. Let us consider the multi-functions ϕix=fxψix and ϕx=fxψx. Then ϕx=i=1kϕix. It follows that minxϕx exists if and only if either minxϕix exists or ψi=, and at least one minimum exists.

Taking minimum of minima that exist, we find

minxfxy:yψx.

Theorem 4.2 Suppose M1 is a compact manifold. If for each xM1, at least one partial function yFixy is affine convex and has a critical point, then the problem OBDP has a solution.

Proof. In our hypothesis, the set ψx is nonvoid, for any x, and the compacity assures the existence of minxfxψx.

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

Theorem 4.3 If a C1 increasing scalarization partial function

yLxy=uF1xyFkxy

has a minimum, then there exists an index i such that ψix. Moreover, if fxy is bounded, then the bilevel problem

minxfxy:yψx

has solution.

Proof. Let minyLxy=Lxy. Suppose that for each i=1,,k, minyFixy<Fixy. Then y would not be minimum point for the partial function yLxy. Hence, there exists an index i such that yψix.□

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

ψix=ArgminyM2Fixy,i=1,,m.

Let ψx=i=1rψix be a subset in M2 representing the mapping of optimal solutions for the follower multi-objective function.

Step 2: Build the mapping f(x,ψx.

Step 3: Solve the leader’s following program

minxfxyyψx.

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 Γijh can be realized in each case, imposing convexity conditions.

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

minx1x2Fx1x2y=x1yx2

subject to

x1x2Argminx1x2x1x2y2x12x220,
1+x1+x20,1x1,x21,0y1.

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 x1=x2=0 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,

x1x2R2x12+x22=y2x10x20.

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=x1x2yR3x1=1x2x2=12±122y21y121.

The Pareto-optimal front in F1F2 space can be written in parametric form

F1F2R2F1=1F2tF2=12±122t21t121.

Example 5.2 Consider the bilevel programming problem

minxxy2+x2:20x20yψx,

where the set-valued function is

ψx=Argminyxy:x1yx+1.

Explicitly,

ψx=11ifx=0x1ifx>0x+1ifx<0.

Since Fxy=xy2+x2, we get

Fxψx=01ifx=02x12+x2ifx>02x+12+x2ifx<0.

on the regions where the functions are defined.

Taking into account 2x12+x2>0 and 2x+12+x2>0, it follows that xy=00 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 Fxy=F1xyF2xy and a Pareto disjunctive problem

ψx=ArgminyFxy=ArgminyF1xyArgminyF2xy.

Then it appears a bilevel disjunctive programming problem of the form

minxfxyyψx.

This problem is interesting excepting the case ψx=Ø,x. If yF1xy and yF2xy are convex functions, then ψxØ.

To write an example, we use

F1xy=xy:x1yx+1,F2xy=x2+y2:yx+1

and we consider a bilevel disjunctive programming problem of the form

minxxy2+x2:20x20yψx,

with

ψx=ψ1xψ2x,

where

ψ1x=Argminyxy:x1yx+1=11ifx=0x1ifx>0x+1ifx<0,
ψ2x=Argminyx2+y2:yx+1=x+1ifx10ifx>1,
ψx=11ifx=0x1x+1if0<x1x10ifx>1x+1ifx<0.

The objective fxy=xy2+x2 and the multi-function ψx produce a multi-function

fxψx=01ifx=02x+12+x22x12+x2if0<x12x+12+x22x2ifx>12x12+x2ifx<0.

In context, we find the inferior envelope

yx=0ifx=0x+1if0<x10ifx>1x+1ifx<0

and then

fxyx=0ifx=02x12+x2ifx0012x2ifx>1.

Since 2x12+x2>0, the unique optimal solution is xy=00.

If we consider only ψ1x as active, then the unique optimal solution 00 is maintained. If ψ2x is active, then the optimal solution is 01.

## 6. Properties of minimum functions

Let M1,1Γ, the leader decision affine manifold, and M2,2Γ, the follower decision affine manifold, be two connected affine manifolds of dimension n1 and n2, respectively. Starting from a function with two vector variables

φ:M1×M2R,xyφxy,

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

fx=infyφxy:yax,

which is called minimum function.

A minimum function is usually specified by a pointwise mapping a of the manifold M1 in the subsets of a manifold M2 and by a functional φxy on M1×M2. 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 M1 is compact, M2=0T and f:M1×0TR. Let ϕt=minxfxt. If, for each x with ϕt=fxt, we have ftxt0, then ϕ is an increasing function.

Proof. We shall prove the statement in three steps.

(1) If f is continuous, then ϕ is (uniformly) continuous.

Indeed, f is continuous on the compact M1×01, hence uniformly continuous. So, for ε>0 it exists δ>0 such that if t1t2<δ, then fxt1fxt2<ε, for any xM1, or

ε<fxt1fxt2<ε

On one hand, if we put ϕt1=fx1t1 and ϕt2=fx2t2, then we have

fxt1>fxt2εfx2t2ε.

Hence minxfxt1fx2t2ε, so is ϕt1ϕt2ε.

On the other hand,

fxt2+ε>fxt1fx1t1.

Hence minxfxt2+εfx1t1, so is ϕt1ϕt2ε.

Finally, ϕt1ϕt2ε, for t1t2<δ, that is, ϕ is (uniformly) continuous.

(2) Let us fix t00T. If ϕt0=fx0t0 and ftx0t00, then it exists δ>0 such that ϕtϕt0, for any tt0δt0.

Suppose ftx0t0>0, it exists δ>0 such that fx0tfx0t0, for each tt0δt0. It follows minxfxtfx0tfx0t0, and so is ϕtϕt0.

If ftx0t0=0, then we use f¯xt=fxt+εt, ε>0. For f¯, the above proof holds, and we take ε0.

(3) ϕ is an increasing function.

Let 0a<bT and note A=tabϕtϕb. A is not empty. If α=infA, then, by the step (2), α<b and, by the step (1), αA. If α>a, we can use the step (2) for t0=α and it would result that α was not the lower bound of A. Hence α=a and ϕaϕb.

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 ϕt=t on 01 and ϕt=1t on 12 has only the property (2), but it is not increasing on 02.

Remark Suppose that f is a C2 function and minxfxt=fx0tt, where x0t is an interior point of M. Since x0t is a critical point, we have

ϕ't=ftx0tt+<fxx0tt,x0't>=ftx0tt0.

Consequently, ϕt is an increasing function. If M1 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:RnR is the function g:Rn×R+R, gxt=tfx/t, domg=xtx/tdomft>0. 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, gx=0, gives x=tx0, where x0 is a critical point of f. Consequently, ϕt=minxgxt=tfx0. On the other hand, in the minimum point, we have gtxt=fx0. Then ϕt is increasing if fx00, as in Theorem 4.1.

Theorem 6.2 Suppose that M1 is compact and f:M1×M2R. Let ϕy=minxfxy. If, for each x with ϕy=fxy, we have fyαxy0, then ϕy is a partially increasing function.

Proof. Suppose that f is a C2 function and minxfxy=fx0yy, where x0y is an interior point of M1. Since x0y is a critical point, we have

ϕyα=fyαx0yy+<fxx0yy,x0yα>=fyαx0yy0.

Consequently, ϕy is a partially increasing function. If M has a non-void boundary, then the monotony extends by continuity.□

Theorem 6.3 Suppose that M1 is compact and f:M1×M2R. Let ϕy=minxfxy. If, for each x with ϕy=fxy, we have dy2fxy0, then ϕy is an affine concave function.

Proof. Without loss of generality, we work on Euclidean case. Suppose that f is a C2 function and minxfxy=fxyy, where xy is an interior point of M1. Since xy is a critical point, we must have

fxixyy=0.

Taking the partial derivative with respect to yα and the scalar product with xiyβ it follows

2fxixjxjyαxiyβ+2fyαxixiyβ=0.

On the other hand

dyϕy=dyfxyy=fxixiyα+fyαdyα=fyαdyα
dy2ϕy=2fyαxixiyβ+2fyαyβdyαdyβ
=2fxjxixiyβxjyα+2fyαyβdyαdyβ0.

Theorem 6.4 Let f:M1×M2R be a C2 function and

ϕy=minxfxy=fxyy.

If the set A=xyy:yM2 is affine convex and fA is affine convex, then ϕy is affine convex.

Proof. Suppose f is a C2 function. At points xyy, we have

0d2fxyy=2fxixjxiyαxjyβ+22fxiyαxiyβ+2fyαyβdyαdyβ
=2fxiyαxiyβ+2fyαyβdyαdyβ=d2ϕy.

## References

1. 1. Aké LA, Sánchez M. Compact affine manifolds with precompact holonomy are geodesically complete. Journal of Mathematical Analysis and Applications. 2016;436(2):1369-1371. DOI: 10.1016/j.jmaa.2015.12.037
2. 2. Antonelli PL, Ingarden RS, Matsumoto M. The Theory of Sparays and Finsler Spaces with Applications in Physics and Biology. Netherlands: Kluwer Academic Publishers, Springer; 1993. pp. 97-132. DOI: 10.1007/978-94-015-8194-3-4
3. 3. Arsinte V, Bejenaru A. Convex mappings between Riemannian manifolds. Balkan Journal of Geometry and Its Applications. 2016;21(1):1-14
4. 4. Beresnev VV, Pshenichnyi BN. The differential properties of minimum functions. USSR Computational Mathematics and Mathematical Physics. 1974;14(3):101-113. DOI: 10.1016/0041-5553(74)90105-0
5. 5. Bonnel H, Todjihounde L, Udrişte C. Semivectorial bilevel optimization on Riemannian manifolds. Journal of Optimization Theory and Applications. 2015;167(2):464-486. DOI: 10.1007/s10957-015-0789-6
6. 6. Boyd S, Vandenberghe L. Convex Optimization. United Kingdom: Cambridge University Press; 2009. 716p
7. 7. Calin O, Udrişte C. Geometric Modeling in Probability and Statistics. New York: Springer; 2014. DOI: 10.1007/978-3-319-07779-6
8. 8. Combettes PL. Perspective functions: Properties, constructions, and examples. Set-Valued and Variational Analysis. Dordrecht: Springer Science+Business Media; 2017:1-18. DOI: 10.1007/s11228-017-0407-x
9. 9. Das P, Roy TK. Multi-objective geometric programming and its application in gravel box problem. Journal of Global Research in Computer Science. 2014;5(7):6-11
10. 10. Deb K, Sinha A. Solving bilevel multi-objective optimization problems using evolutionary algorithms: KanGAL Report Number 2008005; 2017
11. 11. Duffin RJ, Peterson EL, Zener C. Geometric Programming. New Jersey: John Wiley and Sons; 1967
12. 12. Eichfelder G. Solving nonlinear multiobjective bilevel optimization problems with coupled upper level constraints: Technical Report Preprint No. 320, Preprint-Series of the Institut für Angewandte Mathematik, University of Erlangen-Nuremberg, Germany; 2007
13. 13. Myers B. Arc length in metric and Finsler manifolds. Annals of Mathematics. 1938;39(2):463-471. DOI: 10.2307/1968797
14. 14. Olteanu O, Udrişte C. Applications of Hahn-Banach principle to moment and optimization problems. Nonlinear Functional Analysis and its Applications. 2005;10(5):725-742
15. 15. Poston T, Stewart I. Catastrophe Theory and Its Applications. Pitman; 1977. 491p
16. 16. Pripoae CL. Affine differential invariants associated to convex functions. In: Proceedings of Conference of SSM, Cluj, 1998; Digital Data Publishing House, Cluj-Napoca; 1999. pp. 247-252
17. 17. Pripoae CL, Pripoae GT. Generalized convexity in the affine differential setting. In: The International Conference “Differential Geometry—Dynamical Systems” (DGDS); 10–13 October 2013; Bucharest-Romania: BSG Proceedings 21; 2013. pp. 156-166
18. 18. Proudnikov I. The necessary and sufficient conditions for representing Lipschitz multivariable function as a difference of two convex functions. arXiv preprint arXiv:1409.5081v4. 2014
19. 19. Rasheed AS, Udrişte C, Ţevy I. Barrier algorithm for optimization on affine manifolds. BSG Proceedings. 2017;24:47-63
20. 20. Strongin DRG, Sergeyev YD. Global Optimization with Non-Convex Constraints: Sequential and Parallel Algorithms. London: Springer; 2000. 704p. DOI: 10.1007/978-1-4615-4677-1
21. 21. Sánchez M. Geodesic connectedness of semi-Riemannian manifolds. arXiv preprint math/0005039. 2001;47:3085-3102. DOI: 10.1016/s0362-546x(01)00427-8
22. 22. Udrişte C, Dogaru O. Extrema conditioned by orbits. (in Romanian). Buletinul Institutului Politehnic Bucureşti, Seria Mecanică. 1989;51:3-9
23. 23. Udrişte C. Convex Functions and Optimization Methods on Riemannian Manifolds. Netherlands: Kluwer Academic Publishers; 1994 . 365p. DOI: 10.1007/978-94-015-8390-9
24. 24. Udrişte C. Sufficient decreasing on Riemannian manifolds. Balkan Journal of Geometry and Its Applications. 1996;1:111-123
25. 25. Udrişte C. Riemannian convexity in programming (II). Balkan Journal of Geometry and Its Applications. 1996;1(1):99-109
26. 26. Udrişte C. Optimization methods on Riemannian manifolds. In: Proceedings of (IRB) International Workshop; 8–12 August 1995; Monteroduni. Italy: Algebras, Groups and Geometries; 1997. pp. 339-359
27. 27. Udrişte C, Bercu G. Riemannian Hessian metrics. Analele Universitatii din Bucuresti. 2005;55:189-204
28. 28. Yano K, Ishihara S. Tangent and Cotangent Bundles: Differential Geometry. New York: Dekker; 1973. 423p

Written By

Constantin Udriste, Henri Bonnel, Ionel Tevy and Ali Sapeeh Rasheed

Submitted: October 24th, 2017 Reviewed: February 19th, 2018 Published: September 5th, 2018