An algorithm for moving average (MA) parameter estimation was recently proposed by Stoica et al. Its key step (covariance fitting) is a semidefinite programming (SDP) problem with two convex constraints: one reflectin...
详细信息
An algorithm for moving average (MA) parameter estimation was recently proposed by Stoica et al. Its key step (covariance fitting) is a semidefinite programming (SDP) problem with two convex constraints: one reflecting the real positiveness of the desired covariance sequence and the other having a second-order cone form. In this paper, we analyze two parameterizations of a positive real sequence and show that there is a one-to-one correspondence between them. We also show that the dual of the covariance fitting problem has a significantly smaller number of variables and, thus, a much reduced computational complexity. We discuss in detail the formulations that are best suited for the currently available semidefinite quadratic programming packages. Experimental results show that the execution times of the newly proposed algorithms scale well with the MA order, which are therefore convenient for large-order MA signals.
The optimization problem with the Bilinear Matrix Inequality (BMI) is one of the problems which have greatly interested researchers of system and control theory in the last few years. This inequality permits to reduce...
详细信息
The optimization problem with the Bilinear Matrix Inequality (BMI) is one of the problems which have greatly interested researchers of system and control theory in the last few years. This inequality permits to reduce in an elegant way various problems of robust control into its form. However, in contrast to the Linear Matrix Inequality (LMI), which can be solved by interior-point-methods, the BMI is a computationally difficult object in theory and in practice. This article improves the branch-and-bound algorithm of Goh, Safonov and Papavassilopoulos (Journal of Global Optimization, vol. 7, pp. 365-380, 1995) by applying a better convex relaxation of the BMI Eigenvalue Problem (BMIEP), and proposes new Branch-and-Bound and Branch-and-Cut Algorithms. Numerical experiments were conducted in a systematic way over randomly generated problems, and they show the robustness and the efficiency of the proposed algorithms.
Recently, a new characterization of rigid graphs was introduced using Euclidean distance matrices (EDMs) [A.Y. Alfakih, Linear Algebra Appl. 310 (2000) 149]. In this paper, we address the computational aspects of this...
详细信息
Recently, a new characterization of rigid graphs was introduced using Euclidean distance matrices (EDMs) [A.Y. Alfakih, Linear Algebra Appl. 310 (2000) 149]. In this paper, we address the computational aspects of this characterization. Also we present a characterization of graphs which are realizable in R-r For some 1 less than or equal to r less than or equal to n - 2 but not realizable in R(n-1), where n is the number of nodes, (C) 2001 Elsevier Science Inc. All rights reserved. AMS classification: 94C15;52A20;05C50: 15A57.
We study the lift-and-project procedures of Lovasz and Schrijver for 0-1 integer programming problems. We prove that the procedure using the positive semidefiniteness constraint is not better than the one without it, ...
详细信息
We study the lift-and-project procedures of Lovasz and Schrijver for 0-1 integer programming problems. We prove that the procedure using the positive semidefiniteness constraint is not better than the one without it, in the worst case. Various examples are considered. We also provide geometric conditions characterizing when the positive semidefiniteness constraint does not help,
In this communication, we propose a new approach to the problem of finding the signal-adapted optimal compaction filter. This approach is based on a transformation to eigenvalue minimization, a typical application in ...
详细信息
In this communication, we propose a new approach to the problem of finding the signal-adapted optimal compaction filter. This approach is based on a transformation to eigenvalue minimization, a typical application in semidefinite programming. Interior-point methods may be used to offer a reliable optimal solution. The resulting algorithm compares favorable with other known methods. (C) 2001 Elsevier Science B.V. All rights reserved.
The necessary and sufficient conditions for global optimality are derived for an eigenvalue optimization problem. We consider the generalized eigenvalue problem where real symmetric matrices on both sides are linear f...
详细信息
The necessary and sufficient conditions for global optimality are derived for an eigenvalue optimization problem. We consider the generalized eigenvalue problem where real symmetric matrices on both sides are linear functions of design variables. In this case, a minimization problem with eigenvalue constraints can be formulated as Semi-Definite programming (SDP). From the Karush-Kuhn-Tucker conditions of SDP, the necessary and sufficient conditions are derived for arbitrary multiplicity of the lowest eigenvalues for the case where important lower bound constraints are considered for the design variables.
作者：
Nunez, MAFreund, RMChapman Univ
Argyros Sch Business & Econ Orange CA 92866 USA MIT
Alfred P Sloan Sch Management Cambridge MA 02139 USA
We present bounds on various quantities of interest regarding the central trajectory of a semidefinite program, where the bounds are functions of Renegar's condition number C(d) and other naturally occurring quant...
详细信息
We present bounds on various quantities of interest regarding the central trajectory of a semidefinite program, where the bounds are functions of Renegar's condition number C(d) and other naturally occurring quantities such as the dimensions n and m. The condition number C ( d) is defined in terms of the data instance d = (A,b,C) for a semidefinite program;it is the inverse of a relative measure of the distance of the data instance to the set of ill-posed data instances, that is, data instances for which arbitrary perturbations would make the corresponding semidefinite program either feasible or infeasible. We provide upper and lower bounds on the solutions along the central trajectory, and upper bounds on changes in solutions and objective function values along the central trajectory when the data instance is perturbed and/or when the path parameter defining the central trajectory is changed. Based on these bounds, we prove that the solutions along the central trajectory grow at most linearly and at a rate proportional to the inverse of the distance to ill-posedness, and grow at least linearly and at a rate proportional to the inverse of C(d)(2), as the trajectory approaches an optimal solution to the semidefinite program. Furthermore, the change in solutions and in objective function values along the central trajectory is at most linear in the size of the changes in the data. All such bounds involve polynomial functions of C (d), the size of the data, the distance to ill-posedness of the data, and the dimensions n and m of the semidefinite program.
We consider the problem of finding the unconstrained global minimum of a real-valued polynomial p(x) : R-n-->R, as well as the global minimum of p (x), in a compact set K defined by polynomial inequalities. It is s...
详细信息
We consider the problem of finding the unconstrained global minimum of a real-valued polynomial p(x) : R-n-->R, as well as the global minimum of p (x), in a compact set K defined by polynomial inequalities. It is shown that this problem reduces to solving an (often finite) sequence of convex linear matrix inequality( LMI) problems. A notion of Karush-Kuhn-Tucker polynomials is introduced in a global optimality condition. Some illustrative examples are provided.
作者：
Ye, YYUniv Iowa
Dept Management Sci Henry B Tippie Coll Business Iowa City IA 52242 USA
We present a .699-approximation algorithm fur Max-Bisection, i.e., partitioning the nodes of a weighted graph into two blocks of equal cardinality so as to maximize the weights of crossing edges. This is an improved r...
详细信息
We present a .699-approximation algorithm fur Max-Bisection, i.e., partitioning the nodes of a weighted graph into two blocks of equal cardinality so as to maximize the weights of crossing edges. This is an improved result from the .651-approximation algorithm of Frieze and Jerrum and the semidefinite programming relaxation of Goemans and Williamson.
This paper proposes a receding horizon control scheme for a set of uncertain discrete-time linear systems with randomly jumping parameters described by a finite-state Markov process whose jumping transition probabilit...
详细信息
This paper proposes a receding horizon control scheme for a set of uncertain discrete-time linear systems with randomly jumping parameters described by a finite-state Markov process whose jumping transition probabilities are assumed to belong to some convex sets. The control scheme for the underlying systems is based on the minimization of an upper bound on the worst-case infinite horizon cost function at each time instant. It is shown that the mean square stability of the proposed control system is guaranteed under some matrix inequality conditions on the terminal weighting matrices. The proposed controller is obtained using semidefinite programming.
暂无评论