On Intrinsic Complexity of Nash Equilibrium Problems and Bilevel Optimization

In this article we study generalized Nash equilibrium problems (GNEP) and bilevel optimization side by side. This perspective comes from the crucial fact that both problems heavily depend on parametric issues. Observing the intrinsic complexity of GNEP and bilevel optimization, we emphasize that it originates from unavoidable degeneracies occurring in parametric optimization. Under intrinsic complexity, we understand the involved geometrical complexity of Nash equilibria and bilevel feasible sets, such as the appearance of kinks and boundary points, non-closedness, discontinuity and bifurcation effects. The main goal is to illustrate the complexity of those problems originating from parametric optimization and singularity theory. By taking the study of singularities in parametric optimization into account, the structural analysis of Nash equilibria and bilevel feasible sets is performed. For GNEPs, the number of players’ common constraints becomes crucial. In fact, for GNEPs without common constraints and for classical NEPs we show that—generically—all Nash equilibria are jointly nondegenerate Karush–Kuhn–Tucker points. Consequently, they are isolated. However, in presence of common constraints Nash equilibria will constitute a higher dimensional set. In bilevel optimization, we describe the global structure of the bilevel feasible set in case of a one-dimensional leader’s variable. We point out that the typical discontinuities of the leader’s objective function will be caused by follower’s singularities. The latter phenomenon occurs independently of the viewpoint of the optimistic or pessimistic approach. In case of higher dimensions, optimistic and pessimistic approaches are discussed with respect to possible bifurcation of the follower’s solutions.     

Necessary and Sufficient Conditions for Qualitative Properties of Infinite Dimensional Linear Programming Problems

Necessary and sufficient conditions for qualitative properties of infinite dimensional linear programing problems such as solvability, duality, and complementary slackness conditions are studied in this article. As illustrations for the results, we investigate the parametric version of Gale’s example.     

Dynamics of nonlinear transversely vibrating beams: Parametric and closed-form solutions

Nonlinear transversely vibrating beams, including a uniform beam carrying a lumped mass and a transversely vibrating quintic nonlinear beam, are considered in this paper. Firstly, using trigonometric function, analytical solutions to their Cauchy initial problems are constructed in parametric and closed-form. Secondly, it is found that one has the freedom to choose any periodic function to simulate the periodic vibration theoretically. As an example, we also construct parametric and closed-form solution expressed by Jacobi elliptic function. Thirdly, by comparing the two kinds of derived solutions, it is shown that the Jacobi elliptic function solution can degenerate to the corresponding trigonometric function solution when the modulus tends to zero. Comparison are also made between our derived Jacobi elliptic function solution and other’s exact solution, which indicates that the presented parametric solution method is more general.     

Diophantine approximation and parametric geometry of numbers

Dirichlet’s Theorem on simultaneous approximation involves a parameter Q. It can be derived from Minkowski’s geometry of numbers involving a symmetric convex body depending on Q. Therefore it is natural to study parametric Geometry of Numbers. In turn, this will shed new light on diophantine approximation.     

High-Dimensional Adaptive Sparse Polynomial Interpolation and Applications to Parametric PDEs

We consider the problem of Lagrange polynomial interpolation in high or countably infinite dimension, motivated by the fast computation of solutions to partial differential equations (PDEs) depending on a possibly large number of parameters which result from the application of generalised polynomial chaos discretisations to random and stochastic PDEs. In such applications there is a substantial advantage in considering polynomial spaces that are sparse and anisotropic with respect to the different parametric variables. In an adaptive context, the polynomial space is enriched at different stages of the computation. In this paper, we study an interpolation technique in which the sample set is incremented as the polynomial dimension increases, leading therefore to a minimal amount of PDE solving. This construction is based on the standard principle of tensorisation of a one-dimensional interpolation scheme and sparsification. We derive bounds on the Lebesgue constants for this interpolation process in terms of their univariate counterpart. For a class of model elliptic parametric PDE’s, we have shown in Chkifa et al. (Modél. Math. Anal. Numér. 47(1):253–280, 2013) that certain polynomial approximations based on Taylor expansions converge in terms of the polynomial dimension with an algebraic rate that is robust with respect to the parametric dimension. We show that this rate is preserved when using our interpolation algorithm. We also propose a greedy algorithm for the adaptive selection of the polynomial spaces based on our interpolation scheme, and illustrate its performance both on scalar valued functions and on parametric elliptic PDE’s.     

The parametric nature of two students’ covariational reasoning

Researchers have argued that covariational reasoning is foundational for learning a variety of mathematics topics. We extend prior research by examining two students’ covariational reasoning with attention to the extent they became consciously aware of the parametric nature of their reasoning. We first describe our theoretical background including different conceptions of covariation researchers have found useful when characterizing student reasoning. We then present two students’ activities during a teaching experiment in which they constructed and reasoned about covarying quantities. We highlight aspects of the students’ reasoning that we conjectured created an intellectual need that resulted in their constructing a parameter quantity or attribute, a need we explored in closing teaching episodes. We discuss implications of these results for perspectives on covariational reasoning, students’ understandings of graphs and parametric functions, and areas of future research.     

Stability Analysis for Composite Optimization Problems and Parametric Variational Systems

This paper aims to provide various applications for second-order variational analysis of extended-real-valued piecewise linear functions recently obtained by the authors. We mainly focus here on establishing relationships between full stability of local minimizers in composite optimization and Robinson’s strong regularity of associated (linearized and nonlinearized) KKT systems. Finally, we address Lipschitzian stability of parametric variational systems with convex piecewise linear potentials.     

Students’ reasoning about relationships between variables in a real-world problem

This paper reports on part of an investigation of fifteen second-semester calculus students’ understanding of the concept of parametric function. Employing APOS theory as our guiding theoretical perspective, we offer a genetic decomposition for the concept of parametric function, and we explore students’ reasoning about an invariant relationship between two quantities varying simultaneously with respect to a third quantity when described in a real-world problem, as such reasoning is important for the study of parametric functions. In particular, we investigate students’ reasoning about an adaptation of the popular bottle problem in which they were asked to graph relationships between (a) time and volume of the water, (b) time and height of the water, and (c) volume and height of the water. Our results illustrate that several issues make reasoning about relationships between variables a complex task. Furthermore, our findings indicate that conceiving an invariant relationship, as it relates to the concept of parametric function, is nontrivial, and various complimentary ways of reasoning are favorable for developing such a conception. We conclude by making connections between our results and our genetic decomposition.     

Parametrization of extremals of Grötzsch’s problem

We give parametric expressions for extremals of the Grötzsch’s problem.     

Reduced basis approximation and a posteriori error estimation for Stokes flows in parametrized geometries: roles of the inf-sup stability constants

In this paper we review and we extend the reduced basis approximation and a posteriori error estimation for steady Stokes flows in affinely parametrized geometries, focusing on the role played by the Brezzi’s and Babu?ka’s stability constants. The crucial ingredients of the methodology are a Galerkin projection onto a low-dimensional space of basis functions properly selected, an affine parametric dependence enabling to perform competitive Offline-Online splitting in the computational procedure and a rigorous a posteriori error estimation on field variables. The combinatiofn of these three factors yields substantial computational savings which are at the basis of an efficient model order reduction, ideally suited for real-time simulation and many-query contexts (e.g. optimization, control or parameter identification). In particular, in this work we focus on (i) the stability of the reduced basis approximation based on the Brezzi’s saddle point theory and the introduction of a supremizer operator on the pressure terms, (ii) a rigorous a posteriori error estimation procedure for velocity and pressure fields based on the Babu?ka’s inf-sup constant (including residuals calculations), (iii) the computation of a lower bound of the stability constant, and (iv) different options for the reduced basis spaces construction. We present some illustrative results for both interior and external steady Stokes flows in parametrized geometries representing two parametrized classical Poiseuille and Couette flows, a channel contraction and a simple flow control problem around a curved obstacle.     

Statistical estimation in a randomly structured branching population

We consider a binary branching process structured by a stochastic trait that evolves according to a diffusion process that triggers the branching events, in the spirit of Kimmel’s model of cell division with parasite infection. Based on the observation of the trait at birth of the first $n$ generations of the process, we construct nonparametric estimator of the transition of the associated bifurcating chain and study the parametric estimation of the branching rate. In the limit $n\to \infty$, we obtain asymptotic efficiency in the parametric case and minimax optimality in the nonparametric case.     

2D shape optimization under proximity constraints by CFD and response surface methodology

In this paper we consider two-dimensional CFD-based shape optimization in the presence of obstacles, which introduce nontrivial proximity constraints to the optimization problem. Built on Gregory’s piecewise rational cubic splines, the main contribution of this paper is the introduction of such parametric deformations to a nominal shape that are guaranteed to satisfy the proximity constraints. These deformed shape candidates are then used in the identification of a multivariate polynomial response surface; proximity-constrained shape optimization thus reduces to parametric optimization on this polynomial model, with simple interval bounds on the design variables. We illustrate the proposed approach by carrying out lift and/or drag optimization for the NACA 0012 airfoil containing a rectangular fuel tank: By identifying polynomial response surfaces using a large batch of 1800 design candidates, we conclude that the lift coefficient can be optimized by a linear model, whereas the drag coefficient can be optimized by using a quadratic model. Higher order polynomial models yield no improvement in the optimization.     

A linearized finite-difference scheme for the numerical solution of the nonlinear cubic Schrödinger equation

A linearized finite-difference scheme is used to transform the initial/boundary-value problem associated with the nonlinear Schrödinger equation into a linear algebraic system. This method is developed by re placing the time and the space partial derivatives by parametric finite-difference re placements and the nonlinear term by an appropriate parametric linearized scheme based on Taylor’s expansion. The resulting finite-difference method is analysed for stability and convergence. The results of a number of numerical experiments for the single-soliton wave are given.     

On a problem of nonoverlapping domains

We solve the problem of finding the range E of some functional on the class of pairs of functions univalent in the system of the disk and the interior of the disk for the arbitrary parameters characterizing the functional. We prove that E is connected and bounded. Using the method of internal variations and the parametric method, we find the equation of the boundary of E. The obtained results extend Lebedev’s study [1].     

Parametric Resonance in Adiabatic Oscillators

We use the averaging method and Levinson’s fundamental theorem to study phenomenon of parametric resonance in some new equations from the class of adiabatic oscillators.     

Is bilevel programming a special case of a mathematical program with complementarity constraints?

Bilevel programming problems are often reformulated using the Karush–Kuhn–Tucker conditions for the lower level problem resulting in a mathematical program with complementarity constraints(MPCC). Clearly, both problems are closely related. But the answer to the question posed is “No” even in the case when the lower level programming problem is a parametric convex optimization problem. This is not obvious and concerns local optimal solutions. We show that global optimal solutions of the MPCC correspond to global optimal solutions of the bilevel problem provided the lower-level problem satisfies the Slater’s constraint qualification. We also show by examples that this correspondence can fail if the Slater’s constraint qualification fails to hold at lower-level. When we consider the local solutions, the relationship between the bilevel problem and its corresponding MPCC is more complicated. We also demonstrate the issues relating to a local minimum through examples.     

Robust optimization in spline regression models for multi-model regulatory networks under polyhedral uncertainty

In our study, we integrate the data uncertainty of real-world models into our regulatory systems and robustify them. We newly introduce and analyse robust time-discrete target–environment regulatory systems under polyhedral uncertainty through robust optimization. Robust optimization has reached a great importance as a modelling framework for immunizing against parametric uncertainties and the integration of uncertain data is of considerable importance for the model’s reliability of a highly interconnected system. Then, we present a numerical example to demonstrate the efficiency of our new robust regression method for regulatory networks. The results indicate that our approach can successfully approximate the target–environment interaction, based on the expression values of all targets and environmental factors.     

Posterior consistency for partially observed Markov models

We establish the posterior consistency for parametric, partially observed, fully dominated Markov models. The prior is assumed to assign positive probability to all neighborhoods of the true parameter, for a distance induced by the expected Kullback–Leibler divergence between the parametric family members’ Markov transition densities. This assumption is easily checked in general. In addition, we show that the posterior consistency is implied by the consistency of the maximum likelihood estimator. The result is extended to possibly improper priors and non-stationary observations. Finally, we check our assumptions on a linear Gaussian model and a well-known stochastic volatility model.     

The fuzzy decision problem: An approach to the point estimation problem with fuzzy information

This paper is devoted to the extension of the Bayesian method for the point estimation, when the available information is ‘vague’.In the nonfuzzy case, the parametric estimation can be approached as a particularization in the statistical decision problem. This motivates us to accomplish the mentioned extension by looking at the parametric estimation in the fuzzy case as a special situation in the fuzzy decision problem (defined by Tanaka, Okuda and Asia).In this way, concepts in the fuzzy decision problem are first ‘expressed’ in the estimation terminology. Then, on the basis of these concepts, we shall introduce some notions and state some interesting results. Finally, several illustrative examples will be exposed.     

Heterogeneous surface-to-air missile defense battery location: a game theoretic approach

In the context of an air defense missile-and-interceptor engagement, a challenge for the defender is that surface-to-air missile batteries often must be located to protect high-value targets dispersed over a vast area, subject to which an attacker may observe the disposition of batteries and subsequently develop and implement an attack plan. To model this scenario, we formulate a two-player, extensive form, three-stage, perfect information, zero-sum game that accounts for, respectively, a defender’s location of batteries, an attacker’s launch of missiles against targets, and a defender’s assignment of interceptor missiles from batteries to incoming attacker missiles. The resulting trilevel math programming formulation cannot be solved via direct optimization, and it is not suitable to solve via full enumeration for realistically-sized instances. We instead adapt the game tree search technique Double Oracle, within which we embed either of two alternative heuristics to solve an important subproblem for the attacker. We test and compare these solution methods to solve a designed set of 52 instances having parametric variations, from which we derive insights regarding the nature of the underlying problem. Enhancing the solution methods with alternative initialization strategies, our superlative methodology attains the optimal solution for over 75% of the instances tested and solutions within 3% of optimal, on average, for the remaining 25% of the instances, and it is promising for realistically-sized instances, scaling well with regard to computational effort.