Search

In this expository article, we present a number of classic theorems that serve to identify the closure in the sup-norm of various sets of Blaschke products, inner functions and their quotients, as well as the closure of the convex hulls of these sets. The results presented include theorems of Caratheodory, Fisher, Helson–Sarason, Frostman, Adamjan–Arov–Krein, Douglas–Rudin and Marshall. As an application of some of these ideas, we obtain a simple proof of the Berger–Stampfli spectral mapping theorem for the numerical range of an operator.

The Blaschke Santalo inequality and the L p affine isoperimetric inequalities are major inequalities in convex geometry and they have a wide range of applications. Functional versions of the Blaschke Santalo inequality have been established over the years through many contributions. More recently and ongoing, such functional versions have been established for the L p affine isoperimetric inequalities as well. These functional versions involve notions from information theory, like entropy and divergence.We list stability versions for the geometric inequalities as well as for their functional counterparts. Both are known for the Blaschke Santalo inequality. Stability versions for the L p affine isoperimetric inequalities in the case of convex bodies have only been known in all dimensions for p = 1 and for p > 1 only for convex bodies in the plane. Here, we prove almost optimal stability results for the L p affine isoperimetric inequalities, for all p, for all convex bodies, for all dimensions. Moreover, we give stability versions for the corresponding functional versions of the L p affine isoperimetric inequalities, namely the reverse log Sobolev inequality, the L p affine isoperimetric inequalities for log concave functions, and certain divergence inequalities.

We discuss isoperimetric inequalities for convex sets. These include the classical isoperimetric inequality and that of Brunn-Minkowski, Blaschke-Santalo, Busemann-Petty and their various extensions. We show that many such inequalities admit stronger randomized forms in the following sense: for natural families of associated random convex sets one has stochastic dominance for various functionals such as volume, surface area, mean width and others. By laws of large numbers, these randomized versions recover the classical inequalities. We give an overview of when such stochastic dominance arises and its applications in convex geometry and probability.

This article is a survey of recent results on slicing inequalities for convex bodies. The focus is on the setting of arbitrary measures in place of volume.

The first problems belonging properly to mathematical analysis arose during fifth century bce, when Greek mathematicians became interested in the properties of various curved shapes and surfaces. The problem of squaring a circle (that is, constructing a square of the same area as a given circle with only a compass and straightedge) was well known by the second half of the century, and Hippias had already discovered a curve called the quadratix during an attempt at a solution. Hippocrates was also active during the second half of the fifth century bce, and he defined the areas of several regions bound by curves (“Hippocratic lunes”).

Kellerer’s theorem asserts the existence of a Markov martingale with given marginals, assumed to increase in the convex order. It is revisited here, in the light of previous papers by Hirsch-Roynette and by G. Lowther.

This chapter provides an overview of stochastic approximation (SA) methods in the context of simulation optimization. SA is an iterative search algorithm that can be viewed as the stochastic counterpart to steepest descent in deterministic optimization. We begin with the classical methods of Robbins–Monro (RM) and Kiefer–Wolfowitz (KW). We discuss the challenges in implementing SA algorithms and present some of the most well-known variants such as Kesten’s rule, iterate averaging, varying bounds, and simultaneous perturbation stochastic approximation (SPSA), as well as recently proposed versions including scaled-and-shifted Kiefer–Wolfowitz (SSKW), robust stochastic approximation (RSA), accelerated stochastic approximation (AC-SA) for convex and strongly convex functions, and Secant-Tangents AveRaged stochastic approximation (STAR-SA). We investigate the empirical performance of several of the recent algorithms by comparing them on a set of numerical examples.

Chapter 9 is devoted to set-valued mappings. We study approximate fixed points of such mappings, existence of fixed points, and the convergence and stability of iterates of set-valued mappings. In particular, we consider a complete metric space of nonexpansive set-valued mappings acting on a closed and convex subset of a Banach space with a nonempty interior, and show that a generic mapping in this space has a fixed point. We then prove analogous results for two complete metric spaces of set-valued mappings with convex graphs. We also introduce the notion of a contractive set-valued mapping and study the asymptotic behavior of its iterates.

This paper investigates the effectiveness of a variance-based clustering criterion whose construct is similar to the popular minimum sum-of-squares or k-means criterion, except for two distinguishing characteristics: its ability to discriminate clusters by means of quadratic boundaries and its functional form, for which convexity does not hold. Using a recently proposed iterative local search heuristic that is suitable for general variance-based criteria—convex or not, the first to our knowledge that offers such broad support—the alternative criterion has performed remarkably well. In our experimental results, it is shown to be better suited for the majority of the heterogeneous real-world data sets selected. In conclusion, we offer strong reasons to believe that this criterion can be used by practitioners as an alternative to k-means clustering.

Applications that require the optimization of nonlinear functions involving nonconvex terms include reactor network synthesis, separations design and synthesis, robust process control, batch process design, protein folding, and molecular structure prediction. The global optimization method α-branch-and-bound (αBB; Adjiman and Floudas, J. Glob. Optim. 9(1):23–40, 1996; Adjiman et al., Comput. Chem. Eng. 22(9):1137–1158, 1998; Adjiman et al., Comput. Chem. Eng. 22(9):1159–1179, 1998; Androulakis et al., J. Glob. Optim. 7(4):337–363, 1995; Floudas, Deterministic Global Optimization: Theory, Methods and Applications, vol. 37. Springer, New York, 2000; Maranas and Floudas, J. Glob. Optim. 4(2):135–170, 1994), guarantees the global optimum with e-convergence for any \(\mathcal{C}^{2}\)-continuous function within a finite number of iterations via fathoming nodes of a branch-and-bound tree through assignment of lower and upper bounds. Lower bounds are generated through convexification over a node’s subdomain to yield a convex nonlinear program at each node. This chapter explores the performance of the αBB method as well as number of competing methods designed to provide tight, convex underestimators, including the piecewise (Meyer and Floudas, J. Glob. Optim. 32(2):221–258, 2005), generalized (Akrotirianakis and Floudas, J. Glob. Optim. 30(4):367–390, 2004; Akrotirianakis and Floudas, J. Glob. Optim. 29(3):249–264, 2004), and nondiagonal (Skjal et al., J. Optim. Theory Appl. 154(2):462–490, 2012) αBB methods, the Brauer and Rohn+E (Skjal and Westerlund, J. Glob. Optim. 1–17, 2013) αBB methods, and the moment approach (Lasserre and Thanh, J. Glob. Optim. 56(1):1–25, 2013). Their performance is gauged through a test suite of 20 multivariate, box-constrained, nonconvex functions.

It is well known that open dynamical systems can admit an uncountable number of (absolutely continuous) conditionally invariant measures (ACCIMs) for each prescribed escape rate. We propose and illustrate a convex optimisation-based selection scheme (essentially maximum entropy) for gaining numerical access to some of these measures. The work is similar to the maximum entropy (MAXENT) approach for calculating absolutely continuous invariant measures of nonsingular dynamical systems but contains some interesting new twists, including the following: (i) the natural escape rate is not known in advance, which can destroy convex structure in the problem; (ii) exploitation of convex duality to solve each approximation step induces important (but dynamically relevant and not at first apparent) localisation of support; and (iii) significant potential for application to the approximation of other dynamically interesting objects (e.g. invariant manifolds).

This chapter contains an English translation of Alfred Tarski’s [1932] 2014e article Teorja dlugości okregu w szkole średniej, which appeared in the October–December 1932 issue of the journal Parametr. The journal’s target audience consisted of gimnazjum teachers and their most serious students. For further information about that publication, consult section 9.7 of the present book.

This chapter gives an overview of an extension of Benders decomposition (BD) and generalized Benders decomposition (GBD) to deterministic global optimization of nonconvex mixed-integer nonlinear programs (MINLPs) in which the complicating variables are binary. The new decomposition method, called nonconvex generalized Benders decomposition (NGBD), is developed based on convex relaxations of nonconvex functions and continuous relaxations of non-complicating binary variables in the problem. NGBD guarantees finding an e-optimal solution or indicates the infeasibility of the problem in a finite number of steps. A typical application of NGBD is to solve large-scale stochastic MINLPs that cannot be solved via the decomposition procedures of BD and GBD. Case studies of several industrial problems demonstrate the dramatic computational advantage of NGBD over state-of-the-art commercial solvers.

A (geometric) regular polygon {p} in a euclidean space can be specified by a fine Schlafli symbol {p}, where $$\displaystyle{p = \frac{r} {s_{1},\ldots,s_{k}}}$$ is a generalized fraction; here, \(0 \leq s_{1} < \cdots < s_{k} \leq \frac{1} {2}r\). This means that {p} projects onto planar polygons \(\{ \frac{r} {s_{j}}\}\) (reduced to lowest terms) in orthogonal planes, with \(\infty = \frac{1} {0}\) giving the linear apeirogon and 2 the digon (line segment). More generally, it may be possible to specify the shape or similarity class of a geometric regular polytope by means of a fine Schlafli symbol, whose data contain information about certain regular polygons occurring among its vertices in terms of generalized fractions. If so, then the fine Schlafli symbol is called rigid. This paper gives various criteria for rigidity; for instance, the classical regular polytopes are rigid. The theory is also illustrated by several examples. It is noteworthy, though, that a combinatorial description of a regular polytope – a presentation of its symmetry group – can differ considerably from its fine Schlafli symbol.

This chapter presents the new approach to time-domain modeling of UWB channels containing multiple convex obstacles. Vector fitting (VF) algorithm (rational approximation) was used for deriving the closed form impulse response of multiple diffraction ray creeping on a cascade of convex obstacles. VF algorithm was performed with respect to new generalized variables proportional to frequency but including geometrical parameters of the obstacles also. The limits of approximation domain for vector fitting algorithm follow the range of ultra-wideband (UWB) channel parameters that can be met in practical UWB channel scenarios. Finally, the closed form impulse response of a creeping UTD ray was obtained. As the result we obtained impulse response of the channel as a function of normalized, with respect to geometrical parameters of the obstacles, time. It permits for calculation of channel responses for various objects without changing the body of a rational function. In that way the presented approach is general, simple, and effective.

In order to further improve the performance of the existing incremental extreme learning machines (I-ELMs), this chapter proposes an improved convex incremental extreme learning machine based on enhanced random search (ECI-ELM). In ECI-ELM, an enhanced random search method is incorporated into ELM where a convex incremental method is used to add hidden nodes. It is proved that such ECI-ELM can still approximate any continuous target function for the widespread-type piecewise continuous hidden nodes. Simulation results show that ECI-ELM can produce better generalization performance at a faster convergence speed and obtain more compact network architecture than convex incremental extreme learning machine (CI-ELM) and enhances the incremental extreme learning machine (EI-ELM).

This is a somewhat expanded form of a 4h course given, with small variations, first at the educational workshop Probabilistic methods in geometry, Bedlewo, Poland, July 6–12, 2008 and a few weeks later at the Summer school on Fourier analytic and probabilistic methods in geometric functional analysis and convexity, Kent, Ohio, August 13–20, 2008. The main part of these notes gives yet another exposition of Dvoretzky’s theorem on Euclidean sections of convex bodies with a proof based on Milman’s. This material is by now quite standard. Towards the end of these notes we discuss issues related to fine estimates in Dvoretzky’s theorem and there are some results that didn’t appear in print before. In particular there is an exposition of an unpublished result of Figiel (Claim1) which gives an upper bound on the possible dependence on \(\epsilon \)in Milman’s theorem. We would like to thank Tadek Figiel for allowing us to include it here. There is also a better version of the proof of one of the results from Schechtman (Adv. Math. 200(1), 125–135, 2006) giving a lower bound on the dependence on \(\epsilon \)in Dvoretzky’s theorem. The improvement is in the statement and proof of Proposition 2 here which is a stronger version of the corresponding Corollary 1 in Schechtman (Adv. Math. 200(1), 125–135, 2006).

In the 1930s, A.Tarski introduced his plank problem at a time when the field discrete geometry was about to born. It is quite remarkable that Tarski’s question and its variants continue to generate interest in the geometric and analytic aspects of coverings by cylinders in the present time as well. This chapter surveys plank theorems, covering convex bodies by cylinders, Kadets–Ohmann-type theorems and investigates partial coverings of balls by planks.

We present several sharp inequalities for the SL(n) invariant Ω 2, n (K) introduced in our earlier work on centro-affine invariants for smooth convex bodies containing the origin. A connection arose with the Paouris-Werner invariant Ω K defined for convex bodies K whose centroid is at the origin. We offer two alternative definitions for Ω K when K ∈ C + 2. The technique employed prompts us to conjecture that any SL(n) invariant of convex bodies with continuous and positive centro-affine curvature function can be obtained as a limit of normalized p-affine surface areas of the convex body.

In this paper, we propose an algorithm of an interior point method to solve a linear complementarity problem (LCP). The study is based on the transformation of a LCP into a convex quadratic problem; then we use the linearization approach to obtain the simplified problem of Karmarkar. Theoretical results deduct of those are established later, we show that this algorithm enjoys the best theoretical polynomial complexity, namely, \(O(n + m + 1)L,\ \) iteration bound. The numerical tests confirm that the algorithm is robust.

Here we present integral inequalities for convex and increasing functions applied to products of functions. As applications we derive a wide range of fractional inequalities of Hardy type. They involve the left and right Riemann-Liouville fractional integrals and their generalizations, in particular the Hadamard fractional integrals. Also inequalities for left and right Riemann-Liouville, Caputo, Canavati and their generalizations fractional derivatives. These application inequalities are of L p type, \(p \geq 1\), and exponential type, as well as their mixture.

First, we prove that any of the shortest generalized billiard trajectories in an arbitrary convex body of Euclidean d-space is of period of at most d + 1. Second, we prove an analogue of Stoker’s rigidity theorem for standard ball-polyhedra. Third, we give a proof of the global rigidity analogue of Alexandrov’s theorem for normal ball-polyhedra. Next, we show that every simple and standard ball-polyhedron of Euclidean 3-space is locally rigid with respect to its inner dihedral angles (resp., face angles). Then we prove some basic separation and support properties for spindle convex bodies as well as give a proof of a Charatheodory-type theorem for spindle convex hulls. Furthermore, we prove an Euler-Poincare-type formula for standard ball-polyhedra in Euclidean d-space. Finally, we give a proof of the long-standing Boltyanski-Hadwiger illumination conjecture for fat spindle convex bodies in Euclidean dimensions greater than or equal to 15.

First, we give a proof of the long-standing affine plank conjecture of Bang for successive hyperplane cuts and then for inductive partitions. Second, we prove a lower estimate for the sum of the cross-sectional volumes of cylinders covering a convex body in Euclidean d-space. Then we prove a Kadets–Ohmann-type theorem in spherical d-space for coverings of balls by convex bodies via volume maximizing lunes. Finally, we give estimates for partial coverings of balls by planks in Euclidean d-space.

We prove, via a new projection algorithm, the existence of solutions for differential inclusion generated by sweeping process with closed convex sets depending on state.

The concept of a visible point of a convex set relative to a given point is introduced. A number of basic properties of such visible point sets are developed. In particular, it is shown that this concept is useful in the study of best approximation, and it also seems to have potential value in the study of robotics.

One of Paul Erdős’s many continuing interests is distances between points in finite sets. We focus here on conjectures and results on intervertex distances in convex polygons in the Euclidean plane. Two conjectures are highlighted. Let t(x) be the number of different distances from vertex x to the other vertices of a convex polygon C, let \(T(C) = \Sigma t(x)\), and take \(T_{n} =\min \{ T(C) : C\mbox{ has $n$ vertices}\}\). The first conjecture is \(T_{n} = \left ({ n \atop 2} \right )\). The second says that if \(T(C) = \left ({ n \atop 2} \right )\) for a convex n-gon, then the n-gon is regular if n is odd, and is what we refer to as bi-regular if n is even. The conjectures are confirmed for small n.

We give an affirmative answer to a question asked by Gardner and Mauldin (Geom. Dedicata 26, 323–332, 1988) about bijections of the plane taking each polygon with n sides onto a polygon with n sides. We also state and prove more general results in this spirit. For example, we show that an injective mapping taking each convex n-gon onto a non-degenerate n-gon (not necessarily convex or even simple) must be affine.

We present optimality conditions for bilevel optimal control problems where the upper level is a scalar optimal control problem to be solved by a leader and the lower level is a multiobjective convex optimal control problem to be solved by several followers acting in a cooperative way inside the greatest coalition and choosing amongst efficient optimal controls. We deal with the so-called optimistic case, when the followers are assumed to choose the best choice for the leader amongst their best responses, as well with the so-called pessimistic case, when the best response chosen by the followers can be the worst choice for the leader. This paper continues the research initiated in Bonnel (SIAM J. Control Optim. 50(6), 3224–3241, 2012) where existence results for these problems have been obtained.

First, we give a proof of the long-standing Kneser–Poulsen conjecture in the Euclidean plane. Although that result is 2-dimensional its proof is higher dimensional. Second, we prove an analogue of the Kneser–Poulsen conjecture for hemispheres in spherical d-space. Third, we give a proof of a Kneser–Poulsen-type theorem for convex polyhedra in hyperbolic 3-space.

In this chapter we study the structure of approximate solutions of autonomous variational problems with convex integrands. The main goal is to study the structure of approximate solutions of the problems in the regions close to the endpoints of the domains. The results of this chapter provide the full description of the structure of solutions of the convex autonomous problems.

Measures on flag manifolds have been recently used to describe local properties of convex bodies and more general sets in \({\mathbb{R}}^{d}\). Here, we provide a systematic account of flag measures for convex bodies, we collect various properties of flag measures and we prove some new results. In particular, we discuss mixed flag measures for several bodies and we present formulas for (mixed) flag measures of generalized zonoids.

In this chapter we study nonoccurrence of the Lavrentiev phenomenon for a large class of nonconvex nonautonomous constrained variational problems. A state variable belongs to a convex subset H of a Banach space X with nonempty interior. Integrands belong to a complete metric space of functions \(\mathcal{M}_{B}\) which satisfy a growth condition common in the literature and are Lipschitzian on bounded sets. This space will be described below. In [97] we considered a class of nonconstrained variational problems with integrands belonging to a subset \(\mathcal{L}_{B} \subset \mathcal{M}_{B}\) and showed that for \(f \in \mathcal{L}_{B}\) the following property holds

In this chapter, we introduce an extension of the theory of convex polyhedral sets (resp., convex bodies) to the family of intersections of finitely many congruent balls, called ball-polyhedra (resp., to the family of intersections of not necessarily finitely many congruent balls, called spindle convex bodies). The basic properties of ball-polyhedra (resp., spindle convex bodies) that are discussed here include separation and support properties for spindle convex bodies, a Caratheodory-type theorem for spindle convex hulls, and an Euler–Poincare-type formula for ball-polyhedra in d-dimensional Euclidean space. In addition, we discuss (generalized) billiard trajectories in disk-polygons and an analogue of Blaschke–Lebesgue theorem for disk-polygons. Furthermore, we investigate the problem of characterizing the edge-graphs of ball-polyhedra in Euclidean 3-space. Another topic, discussed in more details, is on global and local rigidity of ball-polyhedra in Euclidean 3-space. Finally, we investigate the status of the long-standing illumination conjecture of V. G. Boltyanski and H. Hadwiger from 1960 for ball-polyhedra (resp., spindle convex bodies) in Euclidean d-space.

In this paper it will be demonstrated how functional analytic tools from duality theory can be used to give interesting characterizations of stochastic order relations for discrete distributions in terms of mass transfer principles. A general result for a large class of integral stochastic orders will be derived, and it will be shown that this applies to many important examples like usual stochastic order, convex order, supermodular order, directional convex order, and orthant orders.

Considering the fact that polyhedra have been studied for so long, it is rather surprising that there has been no exhaustive study of their history. But we are very lucky that the authors of four modern classics on the theory of polyhedra—Bruckner, Coxeter, Fejes-Toth and Grunbaum—were interested in historical information and provided detailed historical notes in their books. I propose to present an outline of the milestones in the history of the subject, putting together the thread of what happened as the theory developed. I will pay special attention to regularity concepts.

This chapter includes six “recipes” for making polyhedra, devised by famous polyhedra31.3pc]Please provide affiliation for “Arthur Vi Hart”. chefs. Some recipes are for beginners, others are intermediate or advanced. You can use these recipes, or devise your own. Building models is fun, and will give you a deeper understanding of the chapters that follow.

Plane pictures of three-dimensional convex polyhedra, plane sections of three-dimensional Dirichlet tessellations, and flat spider webs with tension in all the threads are essentially the same geometric object. At the root of this remarkable coincidence is a single geometric diagram that permits us to offer a unified image of the connections among these and other objects. Some hints of these connections are more than a century old, but others are very recent. We begin with an historical sketch.

What is a polyhedron? The question is short, the answer is long. Although you may never have heard of the Polyhedron Kingdom before, it is nearly as vast and as varied as the animal, mineral, and vegetable kingdoms (and it overlaps all three of them). There are aristocrats and workers, families and individuals, old polyhedra with long and interesting histories and young polyhedra born yesterday or the day before. In this kingdom you can take a walking tour of polyhedral architecture, visit a nature preserve and an art gallery and an artisans’ polyhedra fair. As you stroll along you may even glimpse polyhedral ghosts from four-dimensional space.

In this chapter we investigate polyhedra in Euclidean 3-space, E 3, without self-intersections and with some local and global properties related to those of the Platonic solids. A polyhedron is the geometric realization of a compact 2-manifold in E 3 such that its 2-faces are (not necessarily convex) plane polygons bounded by finitely many line segments. Adjacent faces and edges are not coplanar. A flag of a polyhedron P is any triple consisting of a vertex, an edge, and a face of P, all mutually incident.

A graph G is called generically minimally rigid in ℝ d if, for any choice of sufficiently generic edge lengths, it can be embedded in ℝ d in a finite number of distinct ways, modulo rigid transformations. Here, we deal with the problem of determining tight bounds on the number of such embeddings, as a function of the number of vertices. The study of rigid graphs is motivated by numerous applications, mostly in robotics, bioinformatics, sensor networks, and architecture. We capture embeddability by polynomial systems with suitable structure so that their mixed volume, which bounds the number of common roots, yields interesting upper bounds on the number of embeddings. We explore different polynomial formulations so as to reduce the corresponding mixed volume, namely by introducing new variables that remove certain spurious roots and by applying the theory of distance geometry. We focus on \({\mathbb{R}}^{2}\) and \({\mathbb{R}}^{3}\), where Laman graphs and 1-skeleta (or edge graphs) of convex simplicial polyhedra, respectively, admit inductive Henneberg constructions. Our implementation yields upper bounds for \(n \leq 10\) in \({\mathbb{R}}^{2}\) and \({\mathbb{R}}^{3}\), which reduce the existing gaps and lead to tight bounds for \(n \leq 7\) in both \({\mathbb{R}}^{2}\) and \({\mathbb{R}}^{3}\); in particular, we describe the recent settlement of the case of Laman graphs with seven vertices. Our approach also yields a new upper bound for Laman graphs with eight vertices, which is conjectured to be tight. We also establish the first lower bound in \({\mathbb{R}}^{3}\) of about 2. 52 n , where n denotes the number of vertices.

Let \(t(\mathcal{C})\) be the number of tangent pairs among a set \(\mathcal{C}\) of n Jordan regions in the plane. Pach et al. [Tangencies between families of disjoint regions in the plane, in Proceedings of the 26th ACM Symposium on Computational Geometry (SoCG 2010), Snowbird, June 2010, pp. 423–428] showed that if \(\mathcal{C}\) consists of convex bodies and its intersection graph is bipartite, then \(t(\mathcal{C}) \leq 4n - \Theta (1)\), and, moreover, there are such sets that admit at least \(3n - \Theta (\sqrt{n})\) tangencies. We close this gap and generalize their result by proving that the correct bound is \(3n - \Theta (1)\), even when the intersection graph of \(\mathcal{C}\) is only assumed to be triangle-free.

In a convex n-gon, let \({d}_{1} > {d}_{2} > \cdots \) denote the set of all distances between pairs of vertices, and let m i be the number of pairs of vertices at distance d i from one another. Erdős, Lovasz, and Vesztergombi conjectured that \(\sum\nolimits_{i\leq k}{m}_{i} \leq kn\). Using a new computational approach, we prove their conjecture when k ≤ 4 and n is large; we also make some progress for arbitrary k by proving that \(\sum\nolimits_{i\leq k}{m}_{i} \leq (2k - 1)n\). Our main approach revolves around a few known facts about distances, together with a computer program that searches all distance configurations of two disjoint convex hull intervals up to some finite size. We thereby obtain other new bounds, such as m 3 ≤ 3n∕2 for large n.

Let P be a set of points in the plane in general position. Any three points \(x,y,z \in P\) determine a triangle \(\Delta (x,y,z)\) of the plane. We say that \(\Delta (x,y,z)\) is empty if its interior contains no element of P. In this chapter, we study the following problems: What is the size of the largest family of edge-disjoint triangles of a point set? How many triangulations of P are needed to cover all the empty triangles of P? We also study the following problem: What is the largest number of edge-disjoint triangles of P containing a point q of the plane in their interior? We establish upper and lower bounds for these problems.

In this chapter, we present a complete characterization of the smallest sets that block all the simple spanning trees (SSTs) in a complete geometric graph. We also show that if a subgraph is a blocker for all SSTs of diameter at most 4, then it must block all simple spanning subgraphs and, in particular, all SSTs. For convex geometric graphs, we obtain an even stronger result: Being a blocker for all SSTs of diameter at most 3 is already sufficient for blocking all simple spanning subgraphs.

This chapter provides a concrete introduction to several advanced topics in optimization theory. Specifying an interior feasible point is the first issue that must be faced in applying a barrier method. Given an exterior point, Dykstra’s algorithm [21, 70, 79] finds the closest point in the intersection \(\cap _{i=0}^{r-1}C_{i}\) of a finite number of closed convex sets. If C i is defined by the convex constraint \(h_{i}(\boldsymbol{x}) \leq 0\), then one obvious tactic for finding an interior point is to replace C i by the set \(C_{i}(\epsilon ) =\{ \boldsymbol{x} : h_{j}(\boldsymbol{x}) \leq -\epsilon \}\) for some small e > 0. Projecting onto the intersection of the C i (e) then produces an interior point.

Ellipses and ellipsoids form a well-established special class of convex surfaces, primarily due to a wide range of their applications in various mathematical disciplines. The present survey deals with a natural extension of this class to that of convex quadrics. It contains a classification of convex quadrics of the Euclidean space R n and describes, in terms of plane quadric sections, their various characteristic properties among all convex hypersurfaces of R n , possibly unbounded.

There are several instances (e.g., [2, p. 255], [3, p. 255]) in the general equilibrium theory of economics where one is interested in the following question: Given sets {X i } i = 1 n in a vector space V, how close is the vector sum $${\sum }_{i=1}^{n}{X}_{ i} = \left \{{\sum }_{i=1}^{n}{x}_{ i} : {x}_{i} \in {X}_{i}\right \}$$ (4.1) to being convex?

In this chapter, we shall present existence results for some classes of initial value problems for partial hyperbolic differential inclusions with fractional order involving the Caputo fractional derivative, when the right-hand side is convex as well as nonconvex valued. Some results rely on the nonlinear alternative of Leray–Schauder type. In other results, we shall use the fixed-point theorem for contraction multivalued maps due to Covitz and Nadler.

We investigate the optimized configuration of sensor cameras to be placed in a suitably defined three-dimensional cubic region E, in order to maximize the coverage of a completely embedded cube C⊂E. The sensing regions associated with each of the cameras are convex, but not necessarily identical. In order to handle this important practical problem, we present mixed integer linear programming (MILP) and mixed integer nonlinear programming (MINLP) model formulations and propose corresponding solution approaches. Illustrative numerical results are presented, and certain application aspects are also discussed.

In Chapter 4, we showed that when a graph is embedded in a suitably constructed Markov decision process, the associated convex domain of discounted occupational measures is a polyhedron with extreme points corresponding to all spanning subgraphs of the given graph. Furthermore, from Theorem 4.1 we learned that a simple cut of the above domain yields a polyhedron the extreme points of which correspond to only two possible types: Hamiltonian cycles and convex combinations of short and noose cycles. These properties, naturally, suggest certain algorithmic approaches to searching for Hamiltonian cycles.