Globally solving a nonlinear UAV task assignment problem by stochastic and deterministic optimization approaches

In this paper, we consider a task allocation model that consists of assigning a set of m unmanned aerial vehicles (UAVs) to a set of n tasks in an optimal way. The optimality is quantified by target scores. The mission is to maximize the target score while satisfying capacity constraints of both the UAVs and the tasks. This problem is known to be NP-hard. Existing algorithms are not suitable for the large scale setting. Scalability and robustness are recognized as two main issues. We deal with these issues by two optimization approaches. The first approach is the Cross-Entropy (CE) method, a generic and practical tool of stochastic optimization for solving NP-hard problem. The second one is Branch and Bound algorithm, an efficient classical tool of global deterministic optimization. The numerical results show the efficiency of our approaches, in particular the CE method for very large scale setting.     

Continuous-time mean-variance portfolios: a comparison

In this article, we present and compare three mean-variance optimal portfolio approaches in a continuous-time market setting. These methods are the L ²-projection as presented in Schweizer [M. Schweizer, Approximation of random variables by stochastic integrals, Ann. Prob. 22 (1995), pp. 1536–1575], the Lagrangian function approach of Korn and Trautmann [R. Korn and S. Trautmann, Continuous-time portfolio optimization under terminal wealth constraints, ZOR-Math. Methods Oper. Res. 42 (1995), pp. 69–92] and the direct deterministic approach of Lindberg [C. Lindberg, Portfolio optimization when expected stock returns are determined by exposure to risk, Bernoulli 15 (2009), pp. 464–474]. As the underlying model, we choose the recent innovative market parameterization introduced by Lindberg (2009) that has the particular aim to overcome the estimation problems of the stock price drift parameters. We derive some new results for the Lagrangian function approach, in particular explicit representations for the optimal portfolio process. Further, we compare the different optimization frameworks in detail and highlight their attractive and not so attractive features by numerical examples.     

Book Review of Introduction to the theory of toeplitz operators with infinite index,Vladimir Dybin and Sergei M. Grudsky (Translated from Russian by Andrei Jacob), operator theory: advances and applications,Birkhäuser Verlag,Basel-Boston-Berlin, 2002, volume 137, 299 pages. ISBN 3-7643-6728-8.

We consider a special class of optimization problems that we call a Mathematical Programme with Vanishing Constraints. It has a number of important applications in structural and topology optimization, but typically does not satisfy standard constraint qualifications like the linear independence and the Mangasarian–Fromovitz constraint qualification. We therefore investigate the Abadie and Guignard constraint qualifications in more detail. In particular, it follows from our results that also the Abadie constraint qualification is typically not satisfied, whereas the Guignard constraint qualification holds under fairly mild assumptions for our particular class of optimization problems.     

$${{\mathcal {D}(\mathcal {C})}}$$-optimization and robust global optimization

For solving global optimization problems with nonconvex feasible sets existing methods compute an approximate optimal solution which is not guaranteed to be close, within a given tolerance, to the actual optimal solution, nor even to be feasible. To overcome these limitations, a robust solution approach is proposed that can be applied to a wide class of problems called D(C){{\mathcal {D}(\mathcal {C})}}-optimization problems. DC optimization and monotonic optimization are particular cases of D(C){{\mathcal {D}(\mathcal {C})}}-optimization, so this class includes virtually every nonconvex global optimization problem of interest. The approach is a refinement and extension of an earlier version proposed for dc and monotonic optimization.     

Connectedness of efficient points in convex and convex transformable vector optimization

Given a convex vector optimization problem with respect to a closed ordering cone, we show the connectedness of the efficient and properly efficient sets. The Arrow–Barankin–Blackwell theorem is generalized to nonconvex vector optimization problems, and the connectedness results are extended to convex transformable vector optimization problems. In particular, we show the connectedness of the efficient set if the target function f is continuously transformable, and of the properly efficient set if f is differentiably transformable. Moreover, we show the connectedness of the efficient and properly efficient sets for quadratic quasiconvex multicriteria optimization problems.     

Constrained Global Optimization of Expensive Black Box Functions Using Radial Basis Functions

We present a new strategy for the constrained global optimization of expensive black box functions using response surface models. A response surface model is simply a multivariate approximation of a continuous black box function which is used as a surrogate model for optimization in situations where function evaluations are computationally expensive. Prior global optimization methods that utilize response surface models were limited to box-constrained problems, but the new method can easily incorporate general nonlinear constraints. In the proposed method, which we refer to as the Constrained Optimization using Response Surfaces (CORS) Method, the next point for costly function evaluation is chosen to be the one that minimizes the current response surface model subject to the given constraints and to additional constraints that the point be of some distance from previously evaluated points. The distance requirement is allowed to cycle, starting from a high value (global search) and ending with a low value (local search). The purpose of the constraint is to drive the method towards unexplored regions of the domain and to prevent the premature convergence of the method to some point which may not even be a local minimizer of the black box function. The new method can be shown to converge to the global minimizer of any continuous function on a compact set regardless of the response surface model that is used. Finally, we considered two particular implementations of the CORS method which utilize a radial basis function model (CORS-RBF) and applied it on the box-constrained Dixon–Szegö test functions and on a simple nonlinearly constrained test function. The results indicate that the CORS-RBF algorithms are competitive with existing global optimization algorithms for costly functions on the box-constrained test problems. The results also show that the CORS-RBF algorithms are better than other algorithms for constrained global optimization on the nonlinearly constrained test problem.     

Cross-entropic learning of a machine for the decision in a partially observable universe

In this paper, we are interested in optimal decisions in a partially observable universe. Our approach is to directly approximate an optimal strategic tree depending on the observation. This approximation is made by means of a parameterized probabilistic law. A particular family of Hidden Markov Models (HMM), with input and output, is considered as a model of policy. A method for optimizing the parameters of these HMMs is proposed and applied. This optimization is based on the cross-entropic (CE) principle for rare events simulation developed by Rubinstein.     

A Structured Reduced Sequential Quadratic Programming and Its Application to a Shape Design Problem

The objective of this work is to solve a model one dimensional duct design problem using a particular optimization method. The design problem is formulated as an equality constrained optimization, called all at once method, so that the analysis problem is not solved until the optimal design is reached. Furthermore, the sparsity structure in the Jacobian of the linearized constraints is exploited by decomposing the variables into the design and flow parts. To achieve this, sequential quadratic programming with BFGS update for the reduced Hessian of the Lagrangian function is used with the variable reduction method which preserves the structure of the Jacobian in representing the null space basis matrix. By updating the reduced Hessians of which the dimension is the number of design variables, the storage requirement for the Hessians is reduced by a large amount. In addition, the flow part of the Jacobian can be computed analytically.The algorithm with a line search globalization is described. A global and local analysis is provided with a modification of the paper by Byrd and Nocedal [Mathematical Programming 49(1991) pp 285-323] in which they analyzed a similar algorithm with the orthogonal factorization method which assumes the orthogonality of the null space basis matrix. Numerical results are obtained and compared favorably with results from the black box method, unconstrained optimization formulation.     

An M/G/1 queue with cyclic service times

In this paper we consider a single server queue with Poisson arrivals and general service distributions in which the service distributions are changed cyclically according to customer sequence number. This model extends a previous study that used cyclic exponential service times to the treatment of general service distributions. First, the stationary probability generating function and the average number of customers in the system are found. Then, a single vacation queueing system with aN-limited service policy, in which the server goes on vacation after servingN consecutive customers is analyzed as a particular case of our model. Also, to increase the flexibility of using theM/G/1 model with cyclic service times in optimization problems, an approximation approach is introduced in order to obtain the average number of customers in the system. Finally, using this approximation, the optimalN-limited service policy for a single vacation queueing system is obtained.On leave from the Department of Industrial Engineering, Iran University of Science and Technology, Narmak, Tehran 16844, Iran.     

A general approach for studying duality in multiobjective optimization

A general duality framework in convex multiobjective optimization is established using the scalarization with K-strongly increasing functions and the conjugate duality for composed convex cone-constrained optimization problems. Other scalarizations used in the literature arise as particular cases and the general duality is specialized for some of them, namely linear scalarization, maximum (-linear) scalarization, set scalarization, (semi)norm scalarization and quadratic scalarization.      

Interior variations in dynamic optimization problems

In this article, the author examines the properties of interior variations and indicates how to use them in order to formulate the necessary condition of optimality for problems of dynamic optimization, in particular, problems of variational calculus and of optimal control. For optimal control problems, an optimization technique based on interior variations and polynomial approximations is suggested and then illustrated by an explanatory example.     

An Extended Beam Theory for Smart Materials Applications Part II: Static Formation Problems

In this paper we further develop the theory of the extended Timoshenko beam model, as first introduced in Part I [5] of this work, with particular emphasis on applications of the model in formation theory [11], [12]. We begin with formal development of the equilibrium equations of static formation theory in the context of the extended Timoshenko model, giving a rigorous discussion of existence, uniqueness, and regularity of weak solutions with appropriate assumptions on the coefficients. We continue to obtain the fundamental duality relationship in the context of weak solutions and indicate its usefulness in investigations of approximate formability. Optimal formation problems and corresponding necessary conditions for optimality are discussed. We conclude with a discussion of a particular problem of joint optimization of controls and actuator densities in the context of a prismatic extended Timoshenko beam and we present the results of some computational studies. Accepted 14 November 1996     

An imputation method for dealing with missing data in regression

We develop two methods for imputing missing values in regression situations. We examine the standard fixed-effects linear-regression model Y = X β + ?, where the regressors X are fixed and ? is the error term. This research focuses on the problem of missing X values. A particular component of market-share analysis has motivated this research where the price and other promotional instruments of each brand are allowed to have their own impact on the total sales volume in a consumer-products category. When a brand is not distributed in a particular week, only a few of the many measures occurring in that observation are missing. ‘What values should be imputed for the missing measures?’ is the central question this paper addresses. This context creates a unique problem in the missing-data literature, i.e. there is no true value for the missing measure. Using influence functions, from robust statistics we develop two loss functions, each of which is a function of the missing and existing X values. These loss functions turn out to be sums of ratios of low-order polynomials. The minimization of either loss function is an unconstrained non-linear-optimization problem. The solution to this non-linear optimization leads to imputed values that have minimal influence on the estimates of the parameters of the regression model. Estimates using the method for replacing missing values are compared with estimates obtained via some conventional methods.     

On average complexity of global optimization problems

We discuss the average case complexity of global optimization problems. By the average complexity, we roughly mean the amount of work needed to solve the problem with the expected error not exceeding a preassigned error demand. The expectation is taken with respect to a probability measure on a classF of objective functions.Since the distribution of the maximum, max _x f (x), is known only for a few nontrivial probability measures, the average case complexity of optimization is still unknown. Although only preliminary results are available, they indicate that on the average, optimization is not as hard as in the worst case setting. In particular, there are instances, where global optimization is intractable in the worst case, whereas it is tractable on the average.We stress, that the power of the average case approach is proven by exhibiting upper bounds on the average complexity, since the actual complexity is not known even for relatively simple instances of global optimization problems. Thus, we do not know how much easier global optimization becomes when the average case approach is utilized.Research partially supported by the National Science Foundation under Grant CCR-89-0537.     

Computing Eigenelements of Real Symmetric Matrices via Optimization

In certain circumstances, it is advantageous to use an optimization approach in order to solve the generalized eigenproblem, Ax = Bx, where A and B are real symmetric matrices and B is positive definite. In particular, this is the case when the matrices A and B are very large the computational cost, prohibitive, of solving, with high accuracy, systems of equations involving these matrices. Usually, the optimization approach involves optimizing the Rayleigh quotient.We first propose alternative objective functions to solve the (generalized) eigenproblem via (unconstrained) optimization, and we describe the variational properties of these functions.We then introduce some optimization algorithms (based on one of these formulations) designed to compute the largest eigenpair. According to preliminary numerical experiments, this work could lead the way to practical methods for computing the largest eigenpair of a (very) large symmetric matrix (pair).     

Asset allocation under threshold autoregressive models

We discuss the asset allocation problem in the important class of parametric non‐linear time series models called the threshold autoregressive model in (J. Roy. Statist. Soc. Ser. A 1977; 140 :34–35; Patten Recognition and Signal Processing. Sijthoff and Noordhoff: Netherlands, 1978; and J. Roy. Statist. Soc. Ser. B 1980; 42 :245–292). We consider two specific forms, one self‐exciting (i.e. the SETAR model) and the other smooth (i.e. the STAR) model developed by Chan and Tong (J. Time Ser. Anal. 1986; 7 :179–190). The problem of maximizing the expected utility of wealth over a planning horizon is considered using a discrete‐time dynamic programming approach. This optimization approach is flexible enough to deal with the optimal asset allocation problem under a general stochastic dynamical system, which includes the SETAR model and the STAR model as particular cases. Numerical studies are conducted to demonstrate the practical implementation of the proposed model. We also investigate the impacts of non‐linearity in the SETAR and STAR models on the optimal portfolio strategies. Copyright © 2011 John Wiley & Sons, Ltd.     

How to optimize discrete-event systems from a single sample path by the score function method

We present a method for deriving theoptimal solution of a class of mathematical programming problems, associated with discrete-event systems and in particular with queueing models, while using asingle sample path (single simulation experiment) from the underlying process. Our method, called thescore function method, is based on probability measure transformation derived from the efficient score process and generating statistical counterparts to the conventional deterministic optimization procedures (e.g. Lagrange multipliers, penalty functions, etc.). Applications of our method to optimization of various discrete-event systems are presented, and numerical results are given.Research supported by the L. Edelstein Research Fund at the Technion-Israel Institute of Technology.     

Certified Nonlinear Parameter Optimization with Reduced Basis Surrogate Models

PDE-constrained parameter optimization problems suffer from the high dimensionality of the corresponding discretizations, which results in long optimization runtimes. One possible approach to solve such large scale optimization problems more rapidly is to replace the PDE constraint by a low-dimensional model constraint obtained via model reduction. We present a general technique for certification of such surrogate optimization results by a-posteriori error estimation based on Reduced Basis (RB) models. We allow arbitrary PDEs and optimization functionals, in particular cover nonlinear optimization problems. Experiments on a stationary heat-conduction problem demonstrate the applicability of the error bound. (© 2013 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Conjugaison par tranches et dualitë de toland

A level set duality scheme analoguous to Toland's one is developed. In particular, his formula on the difference of two functions finds its level-set analogue. In this way, new couples of dual optimization problems are obtained. Applications to the maximization of functions which level sets are P-closed (where Pis a not necessarily topological closure) are shown.     

Reliable gain‐scheduled control design for networked control systems

In this article, the problem of reliable gain‐scheduled H_∞ performance optimization and controller design for a class of discrete‐time networked control system (NCS) is discussed. The main aim of this work is to design a gain‐scheduled controller, which consists of not only the constant parameters but also the time‐varying parameter such that NCS is asymptotically stable. In particular, the proposed gain‐scheduled controller is not only based on fixed gains but also the measured time‐varying parameter. Further, the result is extended to obtain a robust reliable gain‐scheduled H_∞ control by considering both unknown disturbances and linear fractional transformation parametric uncertainties in the system model. By constructing a parameter‐dependent Lyapunov–Krasovskii functional, a new set of sufficient conditions are obtained in terms of linear matrix inequalities (LMIs). The existence conditions for controllers are formulated in the form of LMIs, and the controller design is cast into a convex optimization problem subject to LMI constraints. Finally, a numerical example based on a station‐keeping satellite system is given to demonstrate the effectiveness and applicability of the proposed reliable control law. © 2014 Wiley Periodicals, Inc. Complexity 21: 214–228, 2015