The parameter estimation of moving-average (MA) signals from second-order statistics was deemed for a long time to be a difficult nonlinear problem for which no computationally convenient and reliable solution was pos...
详细信息
The parameter estimation of moving-average (MA) signals from second-order statistics was deemed for a long time to be a difficult nonlinear problem for which no computationally convenient and reliable solution was possible. Ln this paper, we show how the problem of MA parameter estimation from sample covariances can be formulated as a semidefinite program that can be solved in a time that is a polynomial function of the MA order. Two methods are proposed that rely on two specific (over)parametrizations of the MA covariance sequence, whose use makes the minimization of a covariance fitting criterion a convex problem. The MW estimation algorithms proposed here are computationally fast, statistically accurate, and reliable. None of the previously available algorithms for MA estimation (methods based on higher-order statistics included) shares all these desirable properties. Our methods can also be used to obtain the optimal least squares approximant of an invalid (estimated) MA spectrum (that takes on negative values at some frequencies), which was another long-standing problem in the signal processing literature awaiting a satisfactory solution.
A parameter estimation method for finite dimensional multivariate linear stochastic systems, which is guaranteed to produce valid models approximating the true underlying system in a computational time of a polynomial...
详细信息
A parameter estimation method for finite dimensional multivariate linear stochastic systems, which is guaranteed to produce valid models approximating the true underlying system in a computational time of a polynomial order in the system dimension, is presented. This is achieved by combining the main features of certain stochastic subspace identification techniques with sound matrix Schur restabilizing procedures and multivariate covariance fitting, both of which are formulated as linear matrix inequality problems. all aspects of the identification method are discussed, with an emphasis on the two issues mentioned above, and examples of the overall performance are provided for two different systems.
This paper is devoted to the computation of distance to set, called S, defined by polynomial equations. First we consider the case of quadratic systems. Then, application of results stated for quadratic systems to the...
详细信息
This paper is devoted to the computation of distance to set, called S, defined by polynomial equations. First we consider the case of quadratic systems. Then, application of results stated for quadratic systems to the quadratic equivalent of polynomial systems (see [5]), allows us to compute distance to semi-algebraic sets. Problem of computing distance can be viewed as non convex minimization problem: d(u, S) = inf(x is an element ofS) parallel tox - u parallel to (2), where u is in R-n. To have, at least, lower approximation of distance, we consider the dual bound m(u) associated with the dual problem and give sufficient conditions to guarantee m(u) = d(u, S). The second part deal with numerical computation of m(u) using an interior point method in semidefinite programming. Last, various examples, namely from chemistry and robotic, are given.
The use of piecewise quadratic cost functions is extended from stability analysis of piecewise linear systems to performance analysis and optimal control, Lower bounds on the optimal control cost are obtained by semid...
详细信息
The use of piecewise quadratic cost functions is extended from stability analysis of piecewise linear systems to performance analysis and optimal control, Lower bounds on the optimal control cost are obtained by semidefinite programming based on the Bellman inequality. This also gives an approximation to the optimal control law. An upper bound to the optimal cost is obtained by another convex optimization problem using the given control law. A compact matrix notation is introduced to support the calculations and it is proved that the framework of piecewise linear systems can be used to analyze smooth nonlinear dynamics with arbitrary accuracy.
This paper is concerned with an optimal stochastic Linear-quadratic (LQ) control problem in infinite time horizon, where the diffusion term in dynamics depends on both the state and the control variables. In contrast ...
详细信息
This paper is concerned with an optimal stochastic Linear-quadratic (LQ) control problem in infinite time horizon, where the diffusion term in dynamics depends on both the state and the control variables. In contrast to the deterministic case, we allow the control and state weighting matrices in the cost functional to be indefinite. This leads to an indefinite LQ problem, which may still be well posed due to the deep nature of uncertainty involved. The problem gives rise to a stochastic algebraic Riccati equation (SARE), which is, however, fundamentally different from the classical algebraic Riccati equation as a result of the indefinite nature of the LQ problem. To analyze the SARE, we introduce linear matrix inequalities (LMI's) whose feasibility is shown to be equivalent to the solvability of the SARE, Moreover, we develop a computational approach to the SARE via a semidefinite programming associated with the LMI's. Finally, numerical experiments are reported to illustrate the proposed approach.
We present a dual-scaling interior-point algorithm and show how it exploits the structure and sparsity of some large-scale problems. We solve the positive semidefinite relaxation of combinatorial and quadratic optimiz...
详细信息
We present a dual-scaling interior-point algorithm and show how it exploits the structure and sparsity of some large-scale problems. We solve the positive semidefinite relaxation of combinatorial and quadratic optimization problems subject to boolean constraints. We report the first computational results of interior-point algorithms for approximating maximum cut semidefinite programs with dimension up to 3,000.
This paper deals with a central question of structural optimization: design of the stiffest structure occupying some fixed domain which is capable of carrying a given set of external loads. The design variables are th...
详细信息
This paper deals with a central question of structural optimization: design of the stiffest structure occupying some fixed domain which is capable of carrying a given set of external loads. The design variables are the material properties at each point of the structure. In addition, we require that the structure can withstand small incidental forces which are not known a priori. We introduce the notion of robust design and propose a solution technique called cascading. This technique enables us to find a good approximation of the robust design with a relatively small computational effort. Examples demonstrate efficiency of this technique and importance of the robust structural design itself. (C) 2000 Elsevier Science Ltd. All rights reserved.
In this paper we present a nonsmooth algorithm to minimize the maximum eigenvalue of matrices belonging to an affine subspace of n x n symmetric matrices. We show how a simple bundle method, the approximate eigenvalue...
详细信息
In this paper we present a nonsmooth algorithm to minimize the maximum eigenvalue of matrices belonging to an affine subspace of n x n symmetric matrices. We show how a simple bundle method, the approximate eigenvalue method can be used to globalize the second-order method developed by M.L. Overton in the eighties and recently revisited in the framework of the U-Lagrangian theory. With no additional assumption, the resulting algorithm generates a minimizing sequence. A geometrical and constructive proof is given. To prove that quadratic convergence is achieved asymptotically, some strict complementarity and non-degeneracy assumptions are needed. We also introduce new variants of bundle methods for semidefinite programming.
The standard technique of reduced cost fixing from linear programming is not trivially extensible to semidefinite relaxations because the corresponding Lagrange multipliers are usually not available. We propose a gene...
详细信息
The standard technique of reduced cost fixing from linear programming is not trivially extensible to semidefinite relaxations because the corresponding Lagrange multipliers are usually not available. We propose a general technique for computing reasonable Lagrange multipliers for constraints that are not part of the problem description. Its specialization to the semidefinite {-1, 1} relaxation of quadratic 0-1 programming yields an efficient routine for fixing variables. The routine offers the possibility of exploiting problem structure. We extend the traditional bijective map between {0, 1} and {1, 1} formulations to the constraints so that the dual variables remain the same and structural properties are preserved. Consequently, the fixing routine can be applied efficiently to optimal solutions of the semidefinite {0, 1} relaxation of constrained quadratic 0-1 programming as well. We provide numerical results showing the efficacy of this approach.
In theory, the greatest lower bound (g.l.b.) to reliability is the best possible lower bound to the reliability based on single test administration. Yet the practical use of the g.l.b. has been severely hindered by sa...
详细信息
In theory, the greatest lower bound (g.l.b.) to reliability is the best possible lower bound to the reliability based on single test administration. Yet the practical use of the g.l.b. has been severely hindered by sampling bias problems. It is well known that the g.l.b. based on small samples (even a sample of one thousand subjects is not generally enough) may severely overestimate the population value, and statistical treatment of the bias has been badly missing. The only results obtained so far are concerned with the asymptotic variance of the g.l.b. and of its numerator (the maximum possible error variance of a test), based on first order derivatives and the asumption of multivariate normality. The present paper extends these results by offering explicit expressions for the second order derivatives. This yields a closed form expression For the asymptotic bias of both the g.l.b, and its numerator, under the assumptions that the rank of the reduced covariance matrix is at or above the Ledermann bound, and that the nonnegativity constraints on the diagonal elements of the matrix of unique variances are inactive. It is also shown that, when the reduced rank is at its highest possible value (i.e., the number of variables minus one), the numerator of the g.l.b. is asymptotically unbiased, and the asymptotic bias of the g.l.b, is negative. The latter results are contrary to common belief, bur apply only to cases where the number of variables is small. The asymptotic results are illustrated by numerical examples.
暂无评论