Skip to main content

Über dieses Buch

Optimization, simulation and control play an increasingly important role in science and industry. Because of their numerous applications in various disciplines, research in these areas is accelerating at a rapid pace.

This volume brings together the latest developments in these areas of research as well as presents applications of these results to a wide range of real-world problems. The book is composed of invited contributions by experts from around the world who work to develop and apply new optimization, simulation and control techniques either at a theoretical level or in practice. Some key topics presented include: equilibrium problems, multi-objective optimization, variational inequalities, stochastic processes, numerical analysis, optimization in signal processing, and various other interdisciplinary applications.

This volume can serve as a useful resource for researchers, practitioners, and advanced graduate students of mathematics and engineering working in research areas where results in optimization, simulation and control can be applied.



On the Composition of Convex Envelopes for Quadrilinear Terms

Within the framework of the spatial Branch-and-Bound algorithm for solving mixed-integer nonlinear programs, different convex relaxations can be obtained for multilinear terms by applying associativity in different ways. The two groupings \((({x}_{1}{x}_{2}){x}_{3}){x}_{4}\) and \(({x}_{1}{x}_{2}{x}_{3}){x}_{4}\) of a quadrilinear term, for example, give rise to two different convex relaxations. In Cafieri et al. (J Global Optim 47:661–685, 2010) we prove that having fewer groupings of longer terms yields tighter convex relaxations. In this chapter we give an alternative proof of the same fact and perform a computational study to assess the impact of the tightened convex relaxation in a spatial Branch-and-Bound setting.
Pietro Belotti, Sonia Cafieri, Jon Lee, Leo Liberti, Andrew J. Miller

An Oriented Distance Function Application to Gap Functions for Vector Variational Inequalities

This paper aims to extend some results dealing with gap functions for vector variational inequalities from the literature by using the so-called oriented distance function.
Lkhamsuren Altangerel, Gert Wanka, Oleg Wilfer

Optimal Inscribing of Two Balls into Polyhedral Set

In this chapter, we consider the problem for optimal inscribing of two balls into bounded polyhedral set, so that sum of their radiuses is maximized. We formulate this problem as a bilevel programming problem and investigated its some properties. The gradient-based method for solving it has been proposed. We illustrate our approach on some test problems.
Rentsen Enkhbat, Bazarragchaa Barsbold

Mathematical Programs with Equilibrium Constraints: A Brief Survey of Methods and Optimality Conditions

This chapter provides a short survey of the research for an important class of constrained optimization problems for which their constraints are defined in part by a variational inequality. Such problems are known as mathematical programs with equilibrium constraints (MPEC). MPEC arise naturally in different areas and play an important role, for example, in the pricing of telecommunication and transportation networks, in economic modeling, in computational mechanics in many other fields of modern optimization, and have been the subject of a number of recent studies. We present a general formulation of MPEC, describe the main characteristics of MPEC, and review the main properties and theoretical results for these problems. The short survey mainly concentrates on the review of the available solution methodology.
Ider Tseveendorj

Linear Programming with Interval Data: A Two-Level Programming Approach

Linear programming has been widely applied to solving real world problems. The conventional linear programming model requires the parameters to be known constants. In the real world, however, the parameters are seldom known exactly and have to be estimated. This chapter discusses the general interval linear programming problems where all the parameters, including the cost coefficients, requirement coefficients, and technological coefficients, are represented by interval data. Since the parameters are interval-valued, the objective value is interval-valued as well. A pair of two-level mathematical programs is formulated to calculate the lower bound and upper bound of the objective values of the interval linear program. The two-level mathematical programs are then transformed into one-level nonlinear programs. Solving the pair of nonlinear programs produces the interval of the objective values of the problem. An example illustrates the whole idea and sheds some light on interval linear programming.
Chiang Kao, Shiang-Tai Liu

Quantifying Retardation in Simulation Based Optimization

In many applications one wishes to optimize designs on the basis of an established simulation tool. We consider the situation where “simulation” means solving a system of state equations by a fixed point iteration. “Optimization” may then be performed by appending an adjoint solver and an iteration step on the design variables. The main mathematical goal of this chapter is to quantify and estimate the retardation factor, i.e., the complexity of an optimization run compared to that of a single simulation, measured in terms of contraction rates. It is generally believed that the retardation factor should be bounded by a reasonably small number irrespective of discretization widths and other incidental quantities. We show that this is indeed the case for a simple elliptic control problem, when the state equations are solved by Jacobi or a multigrid V-cycle. Moreover, there is strong dependence on a regularization term. This is also shown to be true when the state equation is solved by Newton’s method and the projected Hessian is explicitly available
Andreas Griewank, Adel Hamdi, Emre Özkaya

Evolutionary Algorithm for Generalized Nash Equilibrium Problems

This paper considers a method for finding multiple, hopefully all, solutions of the generalized Nash equilibrium problem (GNEP). Based on a merit function of the quasi-variational inequality (QVI) problem to GNEP, we reformulated GNEP as an unconstrained global optimization problem. To deal with the latter problem, we employ the evolutionary algorithm with adaptive fitness functions which help to search multiple global solutions. Numerical experiments for some test problems show the practical effectiveness of the method.
Mend-Amar Majig, Rentsen Enkhbat, Masao Fukushima

Scalar and Vector Optimization with Composed Objective Functions and Constraints

In this chapter we consider scalar and vector optimization problems with objective functions being the composition of a convex function and a linear mapping and cone and geometric constraints. By means of duality theory we derive dual problems and formulate weak, strong, and converse duality theorems for the scalar and vector optimization problems with the help of some generalized interior point regularity conditions and consider optimality conditions for a certain scalar problem.
Nicole Lorenz, Gert Wanka

A PTAS for Weak Minimum Routing Cost Connected Dominating Set of Unit Disk Graph

Considering the virtual backbone problem of wireless sensor networks with the shortest path constraint, the problem can be modeled as finding a minimum routing cost connected dominating set (MOC-CDS) in the graph. In this chapter, we study a variation of the MOC-CDS problem. Let k be a fixed positive integer. For any two vertices u, v of G and a vertex subset \(S \subseteq V (G)\), denote S (u, v) the length of the shortest (u, v)-path in G all whose intermediate vertices are in S and define
$$g(u,v) = \left \{\begin{array}{@{}l@{\quad }l@{}} d(u,v) + 4, \quad &\mbox{ if }d(u,v) \leq k + 1; \\ (1 + \frac{4} {k})d(u,v) + 6,\quad &\mbox{ if }d(u,v) > k + 1. \end{array} \right.$$
The g-MOC-CDS problem asks for a subset S with the minimum cardinality such that S is a connected dominating set of G and \({\mathcal{l}}_{S}(u,v) \leq g(u,v)\) for any pair of vertices (u, v) of G. Clearly, g-MOC-CDS can serve as a virtual backbone of the network such that the routing cost is not increased too much. In this chapter, we give a PTAS for the g-MOC-CDS problem on unit disk graphs.
Qinghai Liu, Zhao Zhang, Yanmei Hong, Weili Wu, Ding-Zhu Du

Power Control in Wireless Ad Hoc Networks: Stability and Convergence Under Uncertainties

A successful distributed power control algorithm requires only local measurements for updating the power level of a transmitting node, so that eventually all transmitters meet their QoS requirements, i.e. the solution converges to the global optimum. There are numerous algorithm which claim to work under ideal conditions in which there exist no uncertainties and the model is identical to the real-world implementation. Nevertheless, the problem arises when real-world phenomena are introduced into the problem, such as uncertainties (such as changing environment and time delays) or the QoS requirements cannot be achieved for all the users in the network. In this chapter, we study some distributed power control algorithms for wireless ad hoc networks and discuss their robustness to real-world phenomena. Simulations illustrate the validity of the existing results and suggest directions for future research.
Themistoklis Charalambous

The Changing Role of Optimization in Urban Planning

Most world cities are now planned in one way or another. Through the deliberate positioning of activity and transportation facilities, urban authorities hope to ensure the success of their cities in economic, social and environmental terms. Urban planning models are an important tool to help them in this task, and in this chapter, we examine the use of optimization techniques in urban planning modelling. Through a broad review of the field, we highlight the distinction between single-goal urban-environment models and multi-objective land use and transportation models. While it is shown that optimization no longer plays a stand-alone role in land use and transportation modelling, it does contribute to the overall modelling workflow. Furthermore, optimization forms the basis of two niche applications: excess commuting and sketch modelling. This last field holds the most promise for the future, enabling planners to establish minimum resource consumption benchmarks for their city as a means of comparison with other cities and to evaluate the ambition and feasibility of new plans.
James Keirstead, Nilay Shah

Parametric Optimization Approach to the Solow Growth Theory

We extend the classical growth theory model assuming that production function is an arbitrary continuously differentiable function on its domain and the saving rate and depreciation rate of capital depend on time. Then the per capita consumption maximization problem reduces to one dimensional parametric maximization problem. We propose a new finite method for solving the problem using Lipschitz condition. Some test problems have been solved numerically.
Rentsen Enkhbat, Darkhijav Bayanjargal

Cyclical Fluctuations in Continuous Time Dynamic Optimization Models: Survey of General Theory and an Application to Dynamic Limit Pricing

In this chapter, we reconsider the analytical results on the existence of cyclical fluctuations in continuous time dynamic optimization models with two state variables and their applications to dynamic economic theory. In the first part, we survey the useful analytical results which were obtained by Dockner and Feichtinger (J Econom 53–1:31–50, 1991), Liu (J Math Anal Appl 182:250–256, 1994) and Asada and Yoshida (Chaos, Solitons and Fractals 18:525–536, 2003) on the general theory of cyclical fluctuations in continuous time dynamic optimizing and non-optimizing models. In the second part, we provide an application of these analytical results to a particular continuous time dynamic optimizing economic model, that is, a model of dynamic limit pricing with two state variables, which is an extension of Gaskins (J Econom Theor 3:306–322, 1971) prototype model.
Toichiro Asada

Controlling of Processes by Optimized Expertsystems

Expertsystems are characterised by storing knowledge, normally in if-then-rules. The human Intelligence implies the ability to comprehend, reason, memorise, learn, adapt and create. The attribute of certainty or precision does not exist in human perception and cognition. Perception and cognition through biological sensors, pain reception and other similar biological events are characterised by many uncertainties. A person can linguistically express perceptions experienced through the senses, but these perceptions cannot be described using conventional statistic theory. The perception and cognition activity of the brain is based on relative grades of information acquired by the human sensory systems. These are the reasons that fuzzy logic has been applied very successfully in many areas where conventional model–based approaches are difficult or not cost-effective to implement. Therefore fuzzy-rule based Expertsystems have many advantages over classical expertsystems. Hybrid neuro-fuzzy-Expertsystems combine the advantages of fuzzy systems, which deal with explicit knowledge which can be explained and understood, and neural networks which deal with implicit knowledge which can be acquired by learning. Different methods are known for combining fuzzy-rule-based-systems with neural networks. But all these methods have some disadvantages and restrictions. We suggest a new model enabling the user to represent a given fuzzy-rule-base by a neural network and to adapt its components as desired.
Wolfram-M. Lippe

Using Homotopy Method to Solve Bang–Bang Optimal Control Problems

According to the Pontryagin maximum principle, some optimal control problem can result in a bang-bang control law. In despite of what method is used in the optimization procedure for the bang-bang control, fixing switching points of the bang-bang control is very intractable. In this chapter, the smoothing technique presented by Bertrand et al. for solving bang-bang optimal control problems is introduced, but its convergence is quite slow. To overcome this flaw, based upon a method termed homotopy method, this chapter presents an integration switching method which can converge very fast. Finally, two numerical examples are solved illustrating the interest of our method, and the simulation results are provided to demonstrate the effectiveness of our method.
Zhijie Gao, Hexi Baoyin

A Collection of Test Multiextremal Optimal Control Problems

This chapter considers a collection of test optimal control problems that have been applied to test the efficiency of algorithms for many years. The techniques of comparative testing, statistical testing, and stress testing are used for creating problems of this set. The tests are designed in the same format: there is information about the known local extrema, optimal control and trajectory, attainable set approximation, and the number of Cauchy problems required to obtain the optimal value of an objective functional in each test. Currently the implemented collection includes about 100 test cases.
Alexander Yu. Gornov, Tatiana S. Zarodnyuk, Taras I. Madzhara, Anna V. Daneeva, Irina A. Veyalko

A Multimethod Technique for Solving Optimal Control Problem

A multimethod algorithm for solving optimal control problems is implemented in the form of parallel optimization processes with the choice of the best approximation. The multimethod algorithm based on a sequence of different methods is to provide fast convergence to an optimal solution. Such a technology allows one to take into account some particularities of the problem at all stages of its solving and improve the efficiency of optimal control search.
Alexander I. Tyatyushkin

Tunneling Algorithm for Solving Nonconvex Optimal Control Problems

This chapter considers a new method of search for the global extremum in a nonlinear nonconvex optimal control problem. The method employs a curvilinear search technique to implement the tunneling phase of the algorithm. Local search in the minimization phase is carried out with the standard algorithm that combines the methods of conjugate and reduced gradients.
The software implementation of the suggested tunneling algorithm was tested on a collection of nonconvex optimal control problems and demonstrated efficiency of the this approach.
Alexander Yurievich Gornov, Tatiana Sergeevna Zarodnyuk

Solving Linear Systems with Polynomial Parameter Dependency with Application to the Verified Solution of Problems in Structural Mechanics

We give a short survey on methods for the enclosure of the solution set of a system of linear equations where the coefficients of the matrix and the right hand side depend on parameters varying within given intervals. Then we present a hybrid method for finding such an enclosure in the case that the dependency is polynomial or rational. A general-purpose parametric fixed-point iteration is combined with efficient tools for range enclosure based on the Bernstein expansion of multivariate polynomials. We discuss applications of the general-purpose parametric method to linear systems obtained by standard finite element analysis of mechanical structures and illustrate the efficiency of the new parametric solver.
Jürgen Garloff, Evgenija D. Popova, Andrew P. Smith

A Fast Block Krylov Implicit Runge–Kutta Method for Solving Large-Scale Ordinary Differential Equations

In this chapter, we describe a new based block Krylov–Runge–Kutta method for solving stiff ordinary differential equations. We transform the linear system arising in the application of Newton’s method to a nonsymmetric matrix Stein equation that will be solved by a block Krylov iterative method. Numerical examples are given to illustrate the performance of our proposed method.
A. Bouhamidi, K. Jbilou

Semilocal Convergence with R-Order Three Theorems for the Chebyshev Method and Its Modifications

In this chapter we consider some modifications of the Chebyshev method that are free from second derivative and prove semilocal convergence theorems for these modifications as well as for the Chebyshev method. These two modifications can be considered as a generalization of some well-known iterative methods.
Zhanlav Tugal, Khongorzul Dorjgotov
Weitere Informationen

Premium Partner