Search

We provide a complete classification of the extreme rays of the $$6 \times 6$$ copositive cone $$\mathcal {COP}^{6}$$ . We proceed via a coarse intermediate classification of the possible minimal zero support set of an exceptional extremal matrix $$A \in \mathcal {COP}^{6}$$ . To each such minimal zero support set we construct a stratified semi-algebraic manifold in the space of real symmetric $$6 \times 6$$ matrices $${\mathcal {S}}^{6}$$ , parameterized in a semi-trigonometric way, which consists of all exceptional extremal matrices $$A \in \mathcal {COP}^{6}$$ having this minimal zero support set. Each semi-algebraic stratum is characterized by the supports of the minimal zeros u as well as the supports of the corresponding matrix-vector products Au. The analysis uses recently and newly developed methods that are applicable to copositive matrices of arbitrary order.

We decompose the copositive cone $$\mathcal {COP}^{n}$$ into a disjoint union of a finite number of open subsets $$S_{{\mathcal {E}}}$$ of algebraic sets $$Z_{{\mathcal {E}}}$$ . Each set $$S_{{\mathcal {E}}}$$ consists of interiors of faces of $$\mathcal {COP}^{n}$$ . On each irreducible component of $$Z_{{\mathcal {E}}}$$ these faces generically have the same dimension. Each algebraic set $$Z_{{\mathcal {E}}}$$ is characterized by a finite collection $${{\mathcal {E}}} = \{(I_{\alpha },J_{\alpha })\}_{\alpha = 1,\dots ,|\mathcal{E}|}$$ of pairs of index sets. Namely, $$Z_{{\mathcal {E}}}$$ is the set of symmetric matrices A such that the submatrices $$A_{J_{\alpha } \times I_{\alpha }}$$ are rank-deficient for all $$\alpha $$ . For every copositive matrix $$A \in S_{{\mathcal {E}}}$$ , the index sets $$I_{\alpha }$$ are the minimal zero supports of A. If $$u^{\alpha }$$ is a corresponding minimal zero, then $$J_{\alpha }$$ is the set of indices j such that $$(Au^{\alpha })_j = 0$$ . We call the pair $$(I_{\alpha },J_{\alpha })$$ the extended support of the zero $$u^{\alpha }$$ , and $${{\mathcal {E}}}$$ the extended minimal zero support set of A. We provide some necessary conditions on $${{\mathcal {E}}}$$ for $$S_{{\mathcal {E}}}$$ to be non-empty, and for a subset $$S_{{{\mathcal {E}}}'}$$ to intersect the boundary of another subset $$S_{{\mathcal {E}}}$$ .

6 figures; International audience; The theoretical foundation of path-following methods is the performance analysis of the (damped) Newton step on the class of self-concordant functions. However, the bounds available in the literature and used in the design of path-following methods are not optimal. In this contribution we use methods of optimal control theory to compute the optimal step length of the Newton method on the class of self-concordant functions, as a function of the initial Newton decrement, and the resulting worst-case decrease of the decrement. The exact bounds are expressed in terms of solutions of ordinary differential equations which cannot be integrated explicitly. We provide approximate numerical and analytic expressions which are accurate enough for use in optimization methods. Consequently, the neighbourhood of the central path in which the iterates of path-following methods are required to stay can be enlarged, enabling faster progress along the central path during each iteration and hence fewer iterations to achieve a given accuracy.

International audience; The optimal stopping problem arising in the pricing of American options can be tackled by the so called dual martingale approach. In this approach, a dual problem is formulated over the space of adapted martingales. A feasible solution of the dual problem yields an upper bound for the solution of the original primal problem. In practice, the optimization is performed over a finite-dimensional subspace of martingales. A sample of paths of the underlying stochastic process is produced by a Monte-Carlo simulation, and the expectation is replaced by the empirical mean. As a rule the resulting optimization problem, which can be written as a linear program, yields a martingale such that the variance of the obtained estimator can be large. In order to decrease this variance, a penalizing term can be added to the objective function of the pathwise optimization problem. In this paper, we provide a rigorous analysis of the optimization problems obtained by adding different penalty functions. In particular, a convergence analysis implies that it is better to minimize the empirical maximum instead of the empirical mean. Numerical simulations confirm the variance reduction effect of the new approach.

International audience; Let $A \in {\cal C}^n$ be an exceptional extremal copositive $n \times n$ matrix with positive diagonal. A zero $u$ of $A$ is a non-zero nonnegative vector such that $u^TAu = 0$. The support of a zero $u$ is the index set of the positive elements of $u$. A zero $u$ is minimal if there is no other zero $v$ such that ${\rm supp} v \subset {\rm supp} u$ strictly. Let $G$ be the graph on $n$ vertices which has an edge $(i,j)$ if and only if $A$ has a zero with support $\{1,\dots,n\} \setminus \{i,j\}$. In this paper, it is shown that $G$ cannot contain a cycle of length strictly smaller than $n$. As a consequence, if all minimal zeros of $A$ have support of cardinality $n - 2$, then $G$ must be the cycle graph $C_n$.

Let $A$ be an element of the copositive cone $coposn$. A zero $vu$ of $A$ is a nonnegative vector whose elements sum up to one and such that $vu^TAvu = 0$. The support of $vu$ is the index set $Suppvu subset 1,dots,n$ corresponding to the nonzero entries of $vu$. A zero $vu$ of $A$ is called minimal if there does not exist another zero $vv$ of $A$ such that its support $Suppvv$ is a strict subset of $Suppvu$. Our main result is a characterization of the cone of feasible directions at $A$, i.e., the convex cone $VarKA$ of real symmetric $n times n$ matrices $B$ such that there exists $delta > 0$ satisfying $A + delta B in coposn$. This cone is described by a set of linear inequalities on the elements of $B$ constructed from the set of zeros of $A$ and their supports. This characterization furnishes descriptions of the minimal face of $A$ in $coposn$, and of the minimal exposed face of $A$ in $coposn$, by sets of linear equalities and inequalities constructed from the set of minimal zeros of $A$ and their supports. In particular, we can check whether $A$ lies on an extreme ray of $coposn$ by examining the solution set of a system of linear equations. In addition, we deduce a simple necessary and sufficient condition on the irreducibility of $A$ with respect to a copositive matrix $C$. Here $A$ is called irreducible with respect to $C$ if for all $delta > 0$ we have $A - delta C notin coposn$.

Let ${\cal S}_+^n \subset {\cal S}^n$ be the cone of positive semi-definite matrices as a subset of the vector space of real symmetric $n \times n$ matrices. The intersection of ${\cal S}_+^n$ with a linear subspace of ${\cal S}^n$ is called a spectrahedral cone. We consider spectrahedral cones $K$ such that every element of $K$ can be represented as a sum of rank 1 matrices in $K$. We shall call such spectrahedral cones rank one generated (ROG). We show that ROG cones which are linearly isomorphic as convex cones are also isomorphic as linear sections of the positive semi-definite matrix cone, which is not the case for general spectrahedral cones. We give many examples of ROG cones and show how to construct new ROG cones from given ones by different procedures. We provide classifications of some subclasses of ROG cones, in particular, we classify all ROG cones for matrix sizes not exceeding 4. Further we prove some results on the structure of ROG cones. We also briefly consider the case of complex or quaternionic matrices. ROG cones are in close relation with the exactness of semi-definite relaxations of quadratically constrained quadratic optimization problems or of relaxations approximating the cone of nonnegative functions in squared functional systems., Version 2: section on complex and quaternionic case added, many sections completely rewritten

Special Issue Dedicated to Brian Anderson on the Occasion of His 70th Birthday: Part II; International audience; This article reviews the development of experiment design in the field of identification of dynamical systems, from the early work of the seventies on input design for open loop identification to the developments of the last decade that were spurred by the research on identification for control. While the early work focused entirely on criteria based on the asymptotic parameter covariance, the results of the last decade aim at minimizing a wide range of possible criteria, including measures of the estimated transfer function, or of functions of this estimated transfer function. Two important recent developments are the solution of the experiment design problem for closed loop identification, and the formulation and solution of the dual optimal design problem in which the cost of identification is minimized subject to a quality constraint on the estimated model. We shall conclude this survey with new results on the optimal closed loop experiment design problem, where the optimization is performed jointly with respect to the controller and the spectrum of the external excitation.

International audience; All approaches to optimal experiment design for control have so far focused on deriving an input signal (or input signal spectrum) that minimizes some control-oriented measure of plant/model mismatch between the nominal closed-loop system and the actual closed-loop system, typically under a constraint on the total input power. In practical terms, this amounts to finding the (constrained) input signal that minimizes a measure of a control-oriented model uncertainty set. Here we address the experiment design problem from a “dual” point of view and in a closed-loop setting: given a maximum allowable control-oriented model uncertainty measure compatible with our robust control specifications, what is the cheapest identification experiment that will give us an uncertainty set that is within the required bounds? The identification cost can be measured by either the experiment time, the performance degradation during experimentation due to the added excitation signal, or a combination of both. Our results are presented for the situation where the control objective is disturbance rejection only.

We study the effect of undermodeling on the parameter variance for prediction error time-domain identification with linear model structures. We restrict our consideration to linear time-invariant discrete time single input single output systems. We examine the asymptotic expression for the variance as the number of data tends to infinity. This quantity is known to depend in general on the fourth order statistical properties of the applied input. However, we establish a sufficient condition under which the asymptotic variance is a function of the input power spectrum only. For this case we deliver exact expressions. We show that for a stochastic input the undermodeling contributes to the parameter variance due to the correlation between the prediction errors and its gradients. As an additional contribution we investigate the parameter variance under the assumptions of the stochastic embedding procedure. We show by means of a counterexample that in the framework of stochastic embedding the parameter variance is not necessarily monotonous with respect to the input power spectrum.

We consider a linear-quadratic deterministic optimal control problem where the control takes values in a two-dimensional simplex. The phase portrait of the optimal synthesis contains second-order singular extremals and exhibits modes of infinite accumulations of switchings in finite time, so-called chattering. We prove the presence of an entirely new phenomenon, namely the chaotic behaviour of bounded pieces of optimal trajectories. We find the hyperbolic domains in the neighbourhood of a homoclinic point and estimate the corresponding contraction-extension coefficients. This gives us the possibility to calculate the entropy and the Hausdorff dimension of the non-wandering set which appears to have a Cantor-like structure as in Smale's Horseshoe. The dynamics of the system is described by a topological Markov chain. In the second part it is shown that this behaviour is generic for piece-wise smooth Hamiltonian systems in the vicinity of a junction of three discontinuity hyper-surface strata., Comment: 113 pages, 22 figures

International audience; Parameter identification experiments deliver an identified model together with an ellipsoidal uncertainty region in parameter space. The objective of robust controller design is thus to stabilize all plants in the identified uncertainty region. The subject of the present contribution is to design an identification experiment such that the worst-case $\nu$-gap over all plants in the resulting uncertainty region between the identified plant and plants in this region is as small as possible. The experiment design is performed via input power spectrum optimization. Two cost functions are investigated, which represent different levels of trade-off between accuracy and computational complexity. It is shown that the input optimization problem with respect to these cost functions is amenable to standard numerical algorithms used in convex analysis.

We investigate the relation between the cone \({\mathcal{C}^{n}}\) of n × n copositive matrices and the approximating cone \({\mathcal{K}_{n}^{1}}\) introduced by Parrilo. While these cones are known to be equal for n ≤ 4, we show that for n ≥ 5 they are not equal. This result is based on the fact that \({\mathcal{K}_{n}^{1}}\) is not invariant under diagonal scaling. We show that for any copositive matrix which is not the sum of a nonnegative and a positive semidefinite matrix we can find a scaling which is not in \({\mathcal{K}_{n}^{1}}\). In fact, we show that if all scaled versions of a matrix are contained in \({\mathcal{K}_{n}^{r}}\) for some fixed r, then the matrix must be in \({\mathcal{K}_{n}^{0}}\). For the 5 × 5 case, we show the more surprising result that we can scale any copositive matrix X into \({\mathcal{K}_{5}^{1}}\) and in fact that any scaling D such that \({(DXD)_{ii} \in \{0,1\}}\) for all i yields \({DXD \in \mathcal{K}_{5}^{1}}\). From this we are able to use the cone \({\mathcal{K}_{5}^{1}}\) to check if any order 5 matrix is copositive. Another consequence of this is a complete characterisation of \({\mathcal{C}^{5}}\) in terms of \({\mathcal{K}_{5}^{1}}\). We end the paper by formulating several conjectures.

Let \({K \subset \mathbb R^n}\) be a regular convex cone, let \({e_1,\ldots,e_n \in \partial K}\) be linearly independent points on the boundary of a compact affine section of the cone, and let \({x^* \in K^{0}}\) be a point in the relative interior of this section. For k = 1, . . . , n, let lk be the line through the points ek and x*, let yk be the intersection point of lk with \({\partial K}\) opposite to ek, and let zk be the intersection point of lk with the linear subspace spanned by all points el, l = 1, . . . , n except ek. We give a lower bound on the barrier parameter ν of logarithmically homogeneous self-concordant barriers \({F: K^{0}\to \mathbb R}\) on K in terms of the projective cross-ratios \({q_k = (e_k,x^*;y_k,z_k)}\). Previously known lower bounds by Nesterov and Nemirovski can be obtained from our result as a special case. As an application, we construct an optimal barrier for the epigraph of the \({||\cdot||_{\infty}}\) -norm in \({\mathbb R^n}\) and compute lower bounds on the barrier parameter for the power cone and the epigraph of the \({||\cdot||_p}\) -norm in \({\mathbb R^2}\).

International audience; We consider a linear-quadratic deterministic optimal control problem where the control takes values in a two-dimensional simplex. The phase portrait of the optimal synthesis contains second-order singular extremals and exhibits modes of infinite accumulations of switchings in finite time, so-called chattering. We prove the presence of an entirely new phenomenon, namely a chaotic behaviour of the set of optimal trajectories. The set of optimal non-wandering trajectories has the structure of a Cantor set, and the dynamics of the system is described by a topological Markov chain. We compute the entropy and the Hausdorff dimension of the non-wandering set. This behaviour is generic for piece-wise smooth Hamiltonian systems in the vicinity of a junction of three discontinuity hypersurface strata.

International audience; Piecewise smooth Hamiltonian systems with tangent discontinuity are studied. A new phenomenon is discovered, namely, the generic chaotic behavior of finite parts of trajectories. The approach is to consider the evolution of Poisson brackets for smooth parts of the initial Hamiltonian system. It turns out that, near second-order singular points lying on a discontinuity stratum of codimension two, the system of Poisson brackets is reduced to the Hamiltonian system of the Pontryagin Maximum Principle. The corresponding optimization problem is studied and the topological structure of its optimal trajectories is constructed (optimal synthesis). The synthesis contains countably many periodic solutions on the quotient space by the scale group and a Cantor-like set of nonwandering points (NW) having fractal Hausdorff dimension. The dynamics of the system is described by a topological Markov chain. The entropy is evaluated, together with bounds for the Hausdorff and box dimension of (NW).

International audience; The purpose of the software GASIP is to simulate the gravitational interaction of a large number of point masses. This problem is known as the n-body problem in physics and astronomy. The specificity of the software is that it detects and uses hierarchical structure present in the concrete distribution of the point masses to speed up the computation. The structure is represented as a dynamical tree, with the leaves being the individual point masses. The integration is performed using symplectic methods.

International audience; It is shown that the order of a singular trajectory in problems with multidimensional control is described by a flag of linear subspaces in the control space. In terms of this flag, we construct necessary conditions for the junction of a nonsingular trajectory with a singular one in affine control systems. We also give examples of multidimensional problems in which the optimal control has the form of an irrational winding of a torus that is passed in finite time.

International audience; We consider optimal experiment design for parametric prediction error system identification of linear time-invariant systems in closed loop. The optimisation is performed jointly over the controller and the external input. We use a partial correlation approach, i.e. we parameterize the set of "admissible controller"-"external input" pairs by a finite set of matrix-valued trigonometric moments. Our main contribution is twofold. First we derive a description of the set of admissible finite-dimensional moments by a linear matrix inequality. Optimal input design problems with semi-definite constraints and criteria which are linear in these moments can then be cast as semi-definite programs and solved by standard semi-definite programming packages. Secondly, we develop algorithms to recover the controller and the power spectrum of the external input from the optimal moment vector. This furnishes the user a complete and very general procedure to solve the input design problems of the considered class. Our results can be applied to multi-input multi-output systems, but for pedagogical reasons we present here the single-input single-output case. We also assume that the true system is in the model set.

International audience; In this paper we investigate the problem of designing an input signal for a multi-input multi-output plant to minimize a control-oriented criterion. By employing Ljung's asymptotic (in model order and sample size) covariance formulas, we determine closed form expressions for the optimal input, which provide direct insight into the effect of the principal directions and gains of the open- and closed-loop transfer functions on the kind of experiment to be applied.

International audience; In this paper we consider the problem of input design for open loop identification of linear single input single output finite impulse response systems, under the assumption of full-order modeling. We provide analytic formulas for the information matrix of the optimal input when the design is intended to identify a scalar function of the impulse response coefficients. In particular, we characterize the cases when the optimal information matrix is singular and the optimal input is necessarily a multisine signal. Our results have surprising consequences for the robustness properties of optimal input designs. We show that, contrary to intuition, the choice of an optimal regular information matrix might pose robustness problems if there exist also singular solutions.

International audience; Let $L_n$ be the $n$-dimensional second order cone. A linear map from $\mathbb R^m$ to $\mathbb R^n$ is called positive if the image of $L_m$ under this map is contained in $L_n$. For any pair $(n,m)$ of dimensions, the set of positive maps forms a convex cone. We construct a linear matrix inequality (LMI) that describes this cone. Namely, we show that its dual cone, the cone of Lorentz-Lorentz separable elements, is a section of some cone of positive semidefinite complex hermitian matrices. Therefore the cone of positive maps is a projection of a positive semidefinite matrix cone. The construction of the LMI is based on the spinor representations of the groups $\Spin_{1,n-1}(\mathbb R)$, $\Spin_{1,m-1}(\mathbb R)$. We also show that the positive cone is not hyperbolic for $\min(n,m) \geq 3$.

International audience; It is well known that the quality of the parameters identified during an identification experiment depends on the applied excitation signal. Prediction error identification using full order parametric models delivers an ellipsoidal region in which the true parameters lie with some prescribed probability level. This ellipsoidal region is determined by the covariance matrix of the parameters. Input design strategies aim at the minimization of some measure of this covariance matrix. We show that it is possible to optimize the input in an identification experiment with respect to a performance cost function of a closed-loop system involving explicitly the dependence of the designed controller on the identified model. In the present contribution we focus on finding the optimal input for the estimation of the parameters of a minimum variance controller, without the intermediate step of first minimizing some measure of the model parameter accuracy. We do this in conjunction with using covariance formulas which are not asymptotic in the model order, which is rather new in the domain of optimal input design. The identification procedure is performed in closed-loop. Besides optimizing the input power spectrum for the identification experiment, we also address the question of optimality of the controller. It is a wide belief that the minimum variance controller should be the optimal choice, since we perform an experiment for designing a minimum variance controller. However, we show that this may not always be the case, but rather depends on the model structure.

International audience; Iterative feedback tuning (IFT) is a widely used procedure for controller tuning. It is a sequence of iteratively performed special experiments on the plant interlaced with periods of data collection under normal operating conditions. In this note, we derive the asymptotic convergence rate of IFT for disturbance rejection, which is one of the main fields of application.

International audience; Iterative feedback tuning (IFT) is a data-based method for the iterative tuning of restricted complexity controllers. A "special experiment" in which a batch of previously collected output data is fed back at the reference input allows one to compute an unbiased estimate of the gradient of the control performance criterion. We show that, by performing an optimal filtering of the data that are fed back, one can minimize the asymptotic variability of the control performance cost and, hence, minimize the average performance degradation that results from the randomness of the data. The expression of the optimal filter is derived, and a simulation illustrates the benefits that result from using this optimal filter as compared to the use of the classical constant filter.

This paper presents a new method of identification experiment design for control. Our objective is to design the open-loop identification experiment with minimal excitation such that the controller designed with the identified model stabilizes and achieves a prescribed level of H/sub /spl infin// performance with the unknown true system G/sub 0/.