Search

The aim of this paper is to approximate a Finite-State Markov (FSM) process by another process defined on a lower dimensional state space, called the approximating process, with respect to a total variation distance fidelity criterion. The approximation problem is formulated as an optimization problem using two different approaches. The first approach is based on approximating the transition probability matrix of the FSM process by a lower-dimensional transition probability matrix, resulting in an approximating process which is a Finite-State Hidden Markov (FSHM) process. The second approach is based on approximating the invariant probability vector of the original FSM process by another invariant probability vector defined on a lower-dimensional state space. Going a step further, a method is proposed based on optimizing a Kullback-Leibler divergence to approximate the FSHM processes by FSM processes. The solutions of these optimization problems are described by optimal partition functions which aggregate the states of the FSM process via a corresponding water-filling solution, resulting in lower-dimensional approximating processes which are FSHM or FSM processes. Throughout the paper, the theoretical results are justified by illustrative examples that demonstrate our proposed methodology. [ABSTRACT FROM AUTHOR]

In this paper, we study a class of robust design problems with polynomial dependence on the uncertainty. One of the main motivations for considering these problems comes from robust controller design, where one often encounters systems that depend polynomially on the uncertain parameters. This paper can be seen as integrated in the emerging area of probabilistic robustness, where a probabilistic relaxation of the original robust problem is adopted, thus requiring the satisfaction of the constraints not for all possible values of the uncertainty, but for most of them. Different from the randomized approach for tackling probabilistic relaxations, which is only guaranteed to provide soft bounds on the probability of satisfaction, we present a deterministic approach based on the novel concept of kinship function introduced in this paper. This allows the development of an original framework, which leads to easily computable deterministic convex relaxations of the probabilistic problem. In particular, optimal polynomial kinship functions are introduced, which can be computed a priori and once for all and provide the “best convex bound” on the probability of constraint violation. More importantly, it is proven that the solution of the relaxed problem converges to that of the original robust optimization problem as the degree of the optimal polynomial kinship function increases. Furthermore, by relying on quadrature formulas for computation of integrals of polynomials, it is shown that the computational complexity of the proposed approach is polynomial in the number of uncertain parameters. Finally, unlike other deterministic approaches to robust polynomial optimization, the number of variables in the ensuing optimization problem is not increased by the proposed approximation. An important feature of this approach is that a significant amount of the computational burden is shifted to a one-time offline computation whose results can be stored and provided to the end-user. [ABSTRACT FROM PUBLISHER]

The identification of nonlinear dynamic systems using radial basis function (RBF) neural models is studied in this paper. Given a model selection criterion, the main objective is to effectively and efficiently build a parsimonious compact neural model that generalizes well over unseen data. This is achieved by simultaneous model structure selection and optimization of the parameters over the continuous parameter space. It is a mixed-integer hard problem, and a unified analytic framework is proposed to enable an effective and efficient two-stage mixed discrete-continuous identification procedure. This novel framework combines the advantages of an iterative discrete two-stage subset selection technique for model structure determination and the calculus-based continuous optimization of the model parameters. Computational complexity analysis and simulation studies confirm the efficacy of the proposed algorithm. [ABSTRACT FROM AUTHOR]

In this paper, a new method for the design of optimal finite-impulse response frequency-response masking (FRM) filters with reduced passband group delays is proposed. To meet the prescribed magnitude response and group delay, the proposed design method takes into account both the magnitude error and the group delay error. The key step is the derivation of the group delay and its gradient with respect to the filter coefficients, based on which an explicit group delay constraint is formulated. By incorporating the group delay constraint into the overall optimization, FRM filters with better approximation to the prescribed reduced group delay can be obtained in comparison with a recent method by Lu and Hinamoto in 2003, as illustrated by two design examples. [ABSTRACT FROM AUTHOR]

This paper considers optimization of time averages in systems with variable length renewal frames. Applications include power-aware and profit-aware scheduling in wireless networks, peer-to-peer networks, and transportation systems. Every frame, a new policy is implemented that affects the frame size and that creates a vector of attributes. The policy can be a single decision in response to a random event observed on the frame, or a sequence of such decisions. The goal is to choose policies on each frame in order to maximize a time average of one attribute, subject to additional time average constraints on the others. Two algorithms are developed, both based on Lyapunov optimization concepts. The first makes decisions to minimize a “drift-plus-penalty” ratio over each frame. The second is similar but does not involve a ratio. For systems that make only a single decision on each frame, both algorithms are shown to learn efficient behavior without a-priori statistical knowledge. The framework is also applicable to large classes of constrained Markov decision problems. Such problems are reduced to finding an approximate solution to a simpler unconstrained stochastic shortest path problem on each frame. Approximations for the simpler problem may still suffer from a curse of dimensionality for systems with large state space. However, our results are compatible with any approximation method, and demonstrate an explicit tradeoff between performance and convergence time. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new tractable framework for dealing with linear dynamical systems affected by uncertainty, applicable to multistage robust optimization and stochastic programming. We introduce a hierarchy of near-optimal polynomial disturbance-feedback control policies, and show how these can be computed by solving a single semidefinite programming problem. The approach yields a hierarchy parameterized by a single variable (the degree of the polynomial policies), which controls the trade-off between the optimality gap and the computational requirements. We evaluate our framework in the context of three classical applications—two in inventory management, and one in robust regulation of an active suspension system—in which very strong numerical performance is exhibited, at relatively modest computational expense. [ABSTRACT FROM AUTHOR]

This paper deals with a method for the approximation of a spectral density function among the solutions of a generalized moment problem à la Byrnes/Georgiou/Lindquist. The approximation is pursued with respect to the Kullback–Leibler pseudo-distance, which gives rise to a convex optimization problem. After developing the variational analysis, we discuss the properties of an efficient algorithm for the solution of the corresponding dual problem, based on the iteration of a nonlinear map in a bounded subset of the dual space. Our main result is the proof of local convergence of the latter, established as a consequence of the central manifold theorem. Supported by numerical evidence, we conjecture that, in the mentioned bounded set, the convergence is actually global. [ABSTRACT FROM AUTHOR]

This paper presents a constructive method for (sub)optimal finite-impulse response (FIR) approximation of infinite-impulse response (IIR) models. The method minimizes the Hankel norm of the approximation error by using an explicit solution to the norm-preserved dilation problem. It has advantages over the existing methods in that it is a unified method for both single-input single-output and multiple-input multiple-output systems which allows direct tradeoff between .the least-squares and Chebyshev error criteria by using a single tuning parameter, and that the approximation algorithm is constructive and only involves algebraic manipulations rather than iteration and convex optimization procedures. The lower and upper bounds on the l² and Chebyshev norms of the approximation error are derived and are related to the tuning parameter. The problem of approximating noncausal IIR models by causal FIR models is also formulated and solved. The effectiveness and properties of the proposed algorithms are demonstrated by examples. [ABSTRACT FROM AUTHOR]

This paper describes an efficient algorithm for designing lattice wave digital (LWD) filters (parallel connections of two all-pass filters) with short-coefficient wordlength. The coefficient optimization is performed using the following three steps. First, an initial infinite-precision filter is designed such that it exceeds the given criteria in order to provide some tolerance for co-efficient quantization. Second, a nonlinear optimization algorithm is used for determining a parameter space of the infinite-precision coefficients including the feasible space where the filter meets the given criteria. The third step involves finding the filter parameters in this space so that the resulting filter meets the given criteria with the simplest coefficient representation forms. The proposed algorithm guarantees that the optimum finite-precision solution can be found for both the fixed-point binary and multiplierless coefficient representation forms. In addition, this algorithm is applicable for producing the desired finite-precision solutions for both conventional and approximately linear-phase LWD filters. Comparisons with some other existing quantization schemes show that the proposed algorithm gives the best finite-precision solutions in all examples taken from the literature. [ABSTRACT FROM AUTHOR]

Many iterative algorithms employ operators which are difficult to evaluate exactly, but for which a graduated range of approximations exist. In such cases, “coarse-to-fine” algorithms are often used, in which a crude initial operator approximation is gradually refined with new iterations. In such algorithms, because the computational complexity increases over iterations, the algorithm's convergence rate is properly calculated with respect to cumulative computation time. This suggests the problem of determining an optimal rate of refinement for the operator approximation. This paper shows that, for linearly convergent algorithm, the optimal rate of refinement approaches the rate of convergence of the exact algorithm itself, regardless of the tolerance-complexity relationship. We illustrate this result with an analysis of “coarse-to-fine” grid algorithms for Markov decision processes with continuous state spaces. Using the methods proposed here we deduce an algorithm that presents optimal complexity results and consists solely of a non-adaptive schedule for the gradual decrease of grid size. [ABSTRACT FROM AUTHOR]

This paper considers semi-global stability of an observer-based extremum-seeking (ES) scheme acting on a Hammerstein plant. Unlike previous semi-global analyses, no restriction is placed on the speed of the ES dynamics relative to the plant dynamics. For any set of frequencies of a probing sinusoidal “dither,” it is shown how the plant output can be made to converge to an arbitrarily small neighborhood of its minimum from an arbitrarily large set of initial conditions. Furthermore, in the absence of noise, it is shown how increasing the dither frequency can allow arbitrarily fast convergence of the plant input to a small neighborhood of its optimum. Practical application of the results requires no a priori knowledge of the plant nonlinearity; however, in order to design the ES scheme to operate over a wide range of dither frequencies, some knowledge of the plant dynamics is required. Simulation examples are used to demonstrate these results and to highlight practical considerations when using a high-frequency dither. [ABSTRACT FROM PUBLISHER]

When approximating dynamic systems with Laguerre basis functions (LBFs) it is important to tune the Laguerre pole such that the expansion can be both parsimonious and accurate. Expressing the sum of squared errors (SSE) as a function of the Laguerre pole leads to an objective function that has many local minima and therefore cannot be optimized directly. Two alternative methods have been proposed in the literature: an asymptotically optimal method, and the enforced convergence criterion (ECC). In this paper, a generalization of the ECC will be investigated such that in the limit minimizing this generalized ECC and computing the asymptotically optimal solution lead to the same Laguerre pole. Moreover, it will be proved that these generalized ECCs are quasiconvex functions which means they can be efficiently minimized using numerical optimization techniques. The concept of operator quasiconvexity is investigated and used to prove quasiconvexity of the ECC. [ABSTRACT FROM PUBLISHER]

In this paper, we first describe a ,natricial Newton-type algorithm designed to solve the multivariable spectrum approximation problem. We then prove its global convergence. Finally, we apply this approximation procedure to multivariate spectral estimation, and test its effectiveness through simulation. Simulation shows that, in the case of short observation records, this method may provide a valid alternative to standard multivariable identification techniques such as MATLAB's PEM and MATLAB's N4SID. [ABSTRACT FROM AUTHOR]

Abstract-Stochastic approximation methods have been extensively studied in the literature for solving systems of stochastic equations and stochastic optimization problems where function values and first order derivatives are not observable but can be approximated through simulation. In this paper, we investigate stochastic approximation methods for solving stochastic variational inequality problems (SVIP) where the underlying functions are the expected value of stochastic functions. Two types of methods are proposed: stochastic approximation methods based on projections and stochastic approximation methods based on reformulations of SVIP. Global convergence results of the proposed methods are obtained under appropriate conditions. [ABSTRACT FROM AUTHOR]

We formulate a convex optimization problem for approximating any given spectral density with a rational one having a prescribed number of poles and zeros (n poles and in zeros inside the unit disc and their conjugates). The approximation utilizes the Kuilback-Leibler divergence as a distance measure. The stationarity condition for optimality requires that the approximant matches n + 1 covariance moments of the given power spectrum and in cepstral moments of the corresponding logarithm, although the latter with possible slack. The solution coincides with one derived by Byrnes, Enqvist, and Lindquist who addressed directly the question of covariance and cepstral matching. Thus, the present paper provides an approximation theoretic justification of such a problem. Since the approximation requires only moments of spectral densities and of their logarithms, it can also be used for system identification. [ABSTRACT FROM AUTHOR]

In this paper, we study a matricial version of a generalized moment problem with degree constraint. We introduce a new metric on multivariable spectral densities induced by the family of their spectral factors, which, in the scalar case, reduces to the Hellinger distance. We solve the corresponding constrained optimization problem via duality theory. A highly nontrivial existence theorem for the dual problem is established in the Byrnes-Lindquist spirit. A matricial Newton-type algorithm is finally provided for the numerical solution of the dual problem. Simulation indicates that the algorithm performs effectively and reliably. [ABSTRACT FROM AUTHOR]

We study a class of linear-quadratic-Gaussian (LQG) control problems with N decision makers, where the basic objective is to minimize a social cost as the sum of N individual costs containing mean field coupling. The exact socially optimal solution (determining a particular Pareto optimum) requires centralized information for each agent and has high implementational complexity. As an alternative we subsequently exploit a mean field structure in the centralized optimal control problem to develop decentralized cooperative optimization so that each agent only uses its own state and a function which may be computed offline; the resulting set of strategies asymptotically achieves the social optimum as N\rightarrow \infty . A key feature in this scheme is to let each agent optimize a new cost as the sum of its own cost and another component capturing its social impact on all other agents. We also discuss the relationship between the decentralized cooperative solution and the so-called Nash Certainty Equivalence based solution presented in previous work on mean field LQG games. [ABSTRACT FROM PUBLISHER]

Consider an agent who seeks to traverse the shortest path in a graph having random edge weights. If the agent has no side information about the realizations of the edge weights, it should simply take the path of least average length. We consider a generalization of this framework whereby the agent has access to a limited amount of side information about the edge weights ahead of choosing a path. We define a measure for information quantity, provide bounds on the agent's performance relative to the amount of side information it receives, and present algorithms for optimizing side information. The results are based on a new graph characterization tied to shortest path optimization. [ABSTRACT FROM AUTHOR]

In this study, we aim to recover the interval hull of the set of feasible cost functions that can make uncertain observations optimal for a class of nonlinear constrained parametric optimization problems when all uncertainty and disturbances acting on observations or modeling are taken bounded but otherwise unknown. Fostering on inverse Karush–Kuhn–Tucker optimality conditions, we first state the solving equations as a constraint satisfaction problem, then show how to derive a safe overapproximation of the feasible solution set combining standard numerical tools and a posteriori validation with guaranteed methods based on interval analysis. The approach is evaluated on two well-tuned numerical examples: A discrete unicycle robot model and a planar elastica model, respectively. [ABSTRACT FROM PUBLISHER]

Given a family of real or complex monic polynomials of fixed degree with one affine constraint on their coefficients, consider the problem of minimizing the root radius (largest modulus of the roots) or root abscissa (largest real part of the roots). We give constructive methods for efficiently computing the globally optimal value as well as an optimal polynomial when the optimal value is attained and an approximation when it is not. An optimal polynomial can always be chosen to have at most two distinct roots in the real case and just one distinct root in the complex case. Examples are presented illustrating the results, including several fixed-order controller optimal design problems. [ABSTRACT FROM AUTHOR]

This technical note proposes a method for low order H-infinity synthesis where the constraint on the order of the controller is formulated as a rational equation. The resulting nonconvex optimization problem is then solved by applying a partially augmented Lagrangian method. The proposed method is evaluated together with two well-known methods from the literature. The results indicate that the proposed method has comparable performance and speed. [ABSTRACT FROM AUTHOR]

Following a polynomial approach, many robust fixed-order controller design problems can be formulated as optimization problems whose set of feasible solutions is modeled by parametrized polynomial matrix inequalities (PMIs). These feasibility sets are typically nonconvex. Given a parametrized PMI set, we provide a hierarchy of linear matrix inequality (LMI) problems whose optimal solutions generate inner approximations modeled by a single polynomial superlevel set. Those inner approximations converge in a well-defined analytic sense to the nonconvex original feasible set, with asymptotically vanishing conservatism. One may also impose the hierarchy of inner approximations to be nested or convex. In the latter case, they do not converge any more to the feasible set, but they can be used in a convex optimization framework at the price of some conservatism. Finally, we show that the specific geometry of nonconvex polynomial stability regions can be exploited to improve convergence of the hierarchy of inner approximations. [ABSTRACT FROM AUTHOR]

An arbitrary subset (n-m) of the (n) closed loop eigenvalues of an n^th order continuous time single input linear time invariant system is to be placed using full state feedback, at pre-specified locations in the complex plane. The remaining m closed loop eigenvalues can be placed anywhere inside a pre-defined region in the complex plane. This region constraint on the unspecified poles is translated into a linear matrix inequality constraint on the feedback gains through a convex inner approximation of the polynomial stability region. The closed loop locations for these m eigenvalues are optimized to obtain a minimum norm feedback gain vector. This reduces the controller effort leading to less expensive actuators required to be installed in the control system. The proposed algorithm is illustrated on a linearized model of a 4-machine, 2-area power system example. [ABSTRACT FROM PUBLISHER]

We consider three \cal H\infty optimization problems: system inversion, model matching with probably unstable plant, and full information control. A common theme in numerical solution of these problems is that the infimal \cal H\infty performance among solutions has to be approximated before a suboptimal solution can be found. Recently, a sequence of lower bounds that converges monotonously towards the exact infimum has been established for the system inversion problem. The goal of this technical note is twofold. First, we show that except for some rare cases these lower bounds converge at least root-exponentially fast, i.e., we establish the good-naturedness of this approximation method. Second, we show how the approximation method can be extended such that also arbitrarily good lower bounds on the infima in the model matching problem and the full information control problem can be obtained. [ABSTRACT FROM AUTHOR]

We consider the problem of monitoring spatial phenomena, such as road speeds on a highway, using wireless sensors with limited battery life. A central question is to decide where to locate these sensors to best predict the phenomenon at the unsensed locations. However, given the power constraints, we also need to determine when to activate these sensors in order to maximize the performance while satisfying lifetime requirements. Traditionally, these two problems of sensor placement and scheduling have been considered separately; one first decides where to place the sensors, and then when to activate them. [ABSTRACT FROM AUTHOR]

We analyze how to allocate the budget for data collection effectively when data envelopment analysis (DEA) is used for predicting the efficiency. We formulate this problem under a Bayesian framework and propose two heuristics algorithms, i.e., a gradient-based algorithm and a hybrid GA algorithm to solve this optimization problem. Our results indicate that effective allocation of budget for data collection can greatly reduce the overall data collection effort in comparison with a uniform budget allocation. [ABSTRACT FROM AUTHOR]

The problem of controlling a linear time invariant system in open loop for the maximal time period is considered. The system is subjected to bounded parametric uncertainties and time varying disturbances. The open-loop operation is continued as long as the L2 norm of the states is bounded by a pre-specified threshold, for every possible value of the uncertainty and disturbance. It is shown that an optimal open-loop input that achieves the maximal open-loop operation, and a worst disturbance input exist. Moreover, both can be approximated for computational purposes by bang-bang functions with finite number of switches. [ABSTRACT FROM AUTHOR]

We examine the theoretical and numerical global convergence properties of a certain "gradient free" stochastic approximation algorithm called the "simultaneous perturbation stochastic approximation (SPSA)" that has performed well in complex optimization problems. We establish two theorems on the global convergence of SPSA, the first involving the well-known method of injected noise. The second theorem establishes conditions under which "basic" SPSA without injected noise can achieve convergence in probability to a global optimum, a result with important practical benefits. [ABSTRACT FROM AUTHOR]

We consider control, planning, and resource allocation problems involving several independent subsystems that are coupled through a control/decision constraint. We discuss one-step look ahead methods that use an approximate cost-to-go function derived from the solution of single subsystem problems. We propose a new method for constructing such approximations, and derive bounds on the performance of the associated suboptimal policies. We then specialize this method to problems of reachability of target tubes that have the form of a box (a Cartesian product of subsystem tubes). We thus obtain inner approximating tubes, which are the union of a finite number of boxes, each involving single subsystem calculations. [ABSTRACT FROM AUTHOR]

In this note, we study the rational covariance extension problem with degree bound when the chosen pseudopolynomial of degree at most n has zeros on the boundary of the unit circle and derive some new theoretical results for this special case. In particular, a necessary and sufficient condition for a solution to be bounded (i.e., has no poles on the unit circle) is established. Our approach is based on convex optimization, similar in spirit to the recent development of a theory of generalized interpolation with a complexity constraint. However, the two treatments do not proceed in the same way and there are important differences between them which we discuss herein. An implication of our results is that bounded solutions can be computed via methods that have been developed for pseudopolynomials which are free of zeros on the boundary, extending the utility of those methods. Numerical examples are provided for illustration. [ABSTRACT FROM AUTHOR]