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

They are used for defining the convexity of subsets in

** Theorem 1.1** [1]

Let

be a (Hausdorff, connected, smooth) compact

-manifold endowed with an affine connection

and let

. If the holonomy group

(regarded as a subgroup of the group

of all the linear automorphisms of the tangent space

) has compact closure, then

is autoparallely complete.

Let

The function

* Proof.* For given

as a PDEs system (a particular case of a Frobenius-Mayer system of PDEs) with

Since,

it follows

Of course this only means the curvature tensor is zero on the topologically trivial region we used to set up our co-vector fields

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

* Proof.* For the Hessian

The first central idea for the proof is to use the catastrophe theory, since almost all families

We eliminate the case with maximum point, that is., Morse

At any critical point

** A direct proof based on decomposition of a tensor:** Let

Suppose

where

and the tensor

Suppose

Here we cannot plug in the point

To contradict, we fix an auto-parallel

But this result depends on the direction

In some particular cases, we can eliminate the dependence on the vector

are sufficient to do this.

A particular condition for independence on

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.

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

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

Obviously, the complete notation is

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

The solutions

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

## 3. Affine convexity of posynomial functions

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

* Proof.* A posynomial function has the form

where all the coefficients

joining the points

It follows

One term in this sum is of the form

* Proof.* A signomial function has the form

where all the exponents

we apply the Theorem and the implication

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 * leader decision affine manifold*, and

*, be two connected affine manifolds of dimension*follower decision affine manifold

*, and let*leader objective function

*.*follower multiobjective function

The components

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 * disjunctive solution set of a follower multiobjective optimization problem* is defined by

(1) the set-valued function

where

or

(2) the set-valued function

where

We deal with two bilevel problems:

(1) The

In this case, the follower cooperates with the leader; that is, for each

(2) The

In this case, there is no cooperation between the leader and the follower, and the leader expects the worst scenario; that is, for each

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

* Proof.* Let us consider the multi-functions

Taking minimum of minima that exist, we find

* Proof.* In our hypothesis, the set

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

* Proof.* Let

Boundedness of

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

Let

** Step 2**: Build the mapping

** Step 3**: Solve the leader’s following program

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

* Let us solve the problem (cite* [7]

*[9]*, p. 7;

):

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

## 6. Properties of minimum functions

Let * leader decision affine manifold*, and

*, be two connected affine manifolds of dimension*follower decision affine manifold

and taking the infimum after one variable, let say

which is called * minimum function*.

A * minimum function* is usually specified by a pointwise mapping

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

* Proof.* We shall prove the statement in three steps.

(1)

Indeed,

On one hand, if we put

Hence

On the other hand,

Hence

Finally,

(2)

Suppose

If

(3)

Let

** 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

** Remark** Suppose that

Consequently,

□

* Theorem 4.1*.

* Proof.* Suppose that

Consequently,

* Proof.* Without loss of generality, we work on Euclidean case. Suppose that

Taking the partial derivative with respect to

On the other hand

□

* Proof.* Suppose

## References

- 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.
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.
Arsinte V, Bejenaru A. Convex mappings between Riemannian manifolds. Balkan Journal of Geometry and Its Applications. 2016; 21 (1):1-14 - 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.
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.
Boyd S, Vandenberghe L. Convex Optimization. United Kingdom: Cambridge University Press; 2009. 716p - 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.
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.
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.
Deb K, Sinha A. Solving bilevel multi-objective optimization problems using evolutionary algorithms: KanGAL Report Number 2008005; 2017 - 11.
Duffin RJ, Peterson EL, Zener C. Geometric Programming. New Jersey: John Wiley and Sons; 1967 - 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.
Myers B. Arc length in metric and Finsler manifolds. Annals of Mathematics. 1938; 39 (2):463-471. DOI: 10.2307/1968797 - 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.
Poston T, Stewart I. Catastrophe Theory and Its Applications. Pitman; 1977. 491p - 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.
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.
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.
Rasheed AS, Udrişte C, Ţevy I. Barrier algorithm for optimization on affine manifolds. BSG Proceedings. 2017; 24 :47-63 - 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.
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.
Udrişte C, Dogaru O. Extrema conditioned by orbits. (in Romanian). Buletinul Institutului Politehnic Bucureşti, Seria Mecanică. 1989; 51 :3-9 - 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.
Udrişte C. Sufficient decreasing on Riemannian manifolds. Balkan Journal of Geometry and Its Applications. 1996; 1 :111-123 - 25.
Udrişte C. Riemannian convexity in programming (II). Balkan Journal of Geometry and Its Applications. 1996; 1 (1):99-109 - 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.
Udrişte C, Bercu G. Riemannian Hessian metrics. Analele Universitatii din Bucuresti. 2005; 55 :189-204 - 28.
Yano K, Ishihara S. Tangent and Cotangent Bundles: Differential Geometry. New York: Dekker; 1973. 423p