Search

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.

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

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.

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.

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.

We have seen in Chap. 4 that necessary conditions for optimality follow from separation results using convex approximations for the reachable set from a point. If the reachable sets are known exactly, not only necessary conditions, but complete solutions can be obtained for related optimal control problems (e.g., the time-optimal control problem). In general, determining these sets is as difficult a problem as solving an optimal control problem.

In this paper we survey recent work on the perspective reformulation approach that generates tight, tractable relaxations for convex mixed integer nonlin- ear programs (MINLP)s. This preprocessing technique is applicable to cases where the MINLP contains binary indicator variables that force continuous decision variables to take the value 0, or to belong to a convex set. We derive from first principles the perspective reformulation, and we discuss a variety of practical MINLPs whose relaxation can be strengthened via the perspective reformulation. The survey concludes with comments and computations comparing various algorithmic techniques for solving perspective reformulations.

In this chapter, we provide a non-exhaustive account of decomposition algorithms for solving structured large scale convex and non-convex optimization problemswith major emphasis on several splitting approaches based on the classical or modified augmented Lagrangian functions. This study covers last 40 years of research on theoretical properties of augmented Lagrangians.

In this chapter we carry the paper-folding procedures and the mathematics of paper-folding further than we did in [2]. However, in order to make this account as self-contained as possible, we will recall, in Section 2, the systematic folding procedures from Chapter 4 of [2] that enabled us to approximate, to any degree of accuracy desired, any regular convex N-gon.1

From this chapter on, our journey through discrete geometry leads us to the high-dimensional world. Up until now, although we have often been considering geometric objects in arbitrary dimension, we could mostly rely on the intuition from the familiar dimensions 2 and 3. In the present chapter we can still use dimensions 2 and 3 to picture examples, but these tend to be rather trivial. For instance, in the first section we are going to prove things about graphs via convex polytopes, and for an n-vertex graph we need to consider an n-dimensional polytope. It is clear that graphs with 2 or 3 vertices cannot serve as very illuminating examples. In order to underline this shift to high dimensions, from now on we mostly denote the dimension by n instead of d as before, in agreement with the habits prevailing in the literature on high-dimensional topics.

The present chapter concludes my discussion of the early modern tradition of geometrical problem solving before Descartes. Problem solving constituted the primary context of Descartes’ geometrical studies to which Part II is devoted. His contributions, however, changed the theory and practice of geometrical problem solving in so fundamental a manner that they eclipsed many of the techniques, concepts, and concerns of the earlier tradition. It is therefore appropriate to conclude Part I by a sketch of the state of the art of geometrical problem solving around 1635, that is, just before Descartes published his innovations (and also before Fermat’s new techniques began to circulate among cognoscenti).

In this chapter we create a common experience by reading portions of Euclid’s Elements. We discuss the nature of proof in geometry. We introduce a particular way of recording ruler and compass constructions so that we can measure their complexity. We discuss what are presumably familiar notions from high school geometry as it is taught today. And then we present Euclid’s construction of the regular pentagon and discuss its proof.

In this chapter, we describe how to work with polylines and polygons. A polyline is a set of points that is connected by straight edges in a given order. Polygons are closed polylines. Polygons can be convex or non-convex (in the latter case they can also consist of several “loops”). They can be filled with constant color, shaded according to certain illumination models, “textured” etc. Finally, we will also introduce conics (conic intersections).

We begin this story with the Greeks and their fascination with the challeng of constructing regular convex polygons–that is, polygons with all sides of the same length and all interior angles equal. We refer to such N-sided polygons as regular convex N-gons, and we may suppress the word “regular” or the word “convex” if no confusion would result. The Greeks wanted to construct these polygons using what we call Euclidean tools, namely, an unmarked straight edge and a compass.

In this chapter we will provide applications of the syntactic rules established in Chapter III for the generation and evolution of geometric forms. Most of these two-dimensional and three-dimensional forms are either taken directly from classical geometry or derived from geometric shapes, but some of the models have been inspired by more abstract geometries, such as topology, differential geometry, and projective geometry.

Decomposing complex shapes into simpler components has always been a focus of attention in computational geometry. The reason is obvious: most geometric algorithms perform more efficiently and are easier to implement and debug if the objects have simple shapes. For example, mesh-generation is a standard staple of the finite-element method; partitioning polygons or polyhedra into convex pieces or simplices is a typical preprocessing step in automated design, robotics, and pattern recognition. In computer graphics, decompositions of two-dimensional scenes are used in contour filling, hit detection, clipping and windowing; polyhedra are decomposed into smaller parts to perform hidden surface removal and ray-tracing.

Most of the problems encountered so far have involved convex sets, or other sets with considerable intrinsic geometric structure. Nevertheless, one can study the geometry of much more general objects, for example, sets that are just closed or Lebesgue measurable, or even completely arbitrary. This chapter contains a selection of problems which, at least at first glance, are of such a general nature.

Colors are very important to me because I have a gift—it’s not my fault, it’s just how I am—whenever I hear music, or even if I read music, I see colors (Hume, 1979).

This chapter has two objectives. The first is the discussion of variants and special cases of the convex hull problem, as well as the average-case performance analysis of convex hull algorithms. The second objective is the discussion of applications that use the convex hull. New problems will be formulated and treated as they arise in these applications. Their variety should convince the reader that the hull problem is important both in practice and as a fundamental tool in computational geometry.

In this chapter we begin to develop an abstract theory of joining which is suggested by the operation of joining two points to form a segment in Euclidean geometry. The first section gives a brief treatment of the join operation in Euclidean geometry, defining it precisely and presenting its basic properties.1 This “Euclidean join unit” motivates—becomes a model for—the abstract theory of join. The postulates for the operation join are given, and their elementary consequences deduced. The notion of convex set is then defined in terms of join and quickly takes on a central role in the theory. With each convex set A there are associated two important subsidiary sets which are themselves convex: the interior of A and the closure of A. These ideas receive a major share of our attention.

The problem of computing a convex hull is not only central to practical applications, but is also a vehicle for the solution of a number of apparently unrelated questions arising in computational geometry. The computation of the convex hull of a finite set of points, particularly in the plane, has been studied extensively and has applications, for example, in pattern recognition [Akl–CToussaint (1978); Duda–CHart (1973)], image processing [Rosenfeld (1969)] and stock cutting and allocation [Freeman (1974);Sklansky (1972); Freeman–CShapira (1975)].

The methods developed earlier to intersect planar convex polygons are certainly applicable to a collection of rectangles. Similarly, a collection of segments, each of which is either parallel or orthogonal to any other member of the collection, can be handled by the general segment intersection technique described in the preceding chapter. However, the very special nature of segments having just two orthogonal directions, or of rectangles whose sides are such segments, suggests that perhaps more efficientad hoctechniques can be developed to treat such highly structured cases. And in the process of studying this class of problems one may acquire more insight into the geometric properties possessed by the objects mentioned above—rectangles and orthogonal segments—and may succeed in characterizing the wider class to which the techniques are still applicable.

Our definition of segment and ray will be motivated by Figure 8.1. It seems reasonable to say that a segment with endpoints A and B should contain all the points between A and B. Should A and B be included? This is initially a matter of choice! The reader of a textbook is sometimes unaware that the author has made several rather arbitrary decisions about his definitions. The author can decide whether he wants the endpoints included in a segment or not; he makes the decision for himself and his reader. Once that decision is made, the defined word must be used consistently. We are stuck with the choice.