The Euclidean distance matrix completion problem (EDMCP) is the problem of determining whether or not a given partial matrix can be completed into a Euclidean distance matrix (EDM). In this paper, we investigate the n...
详细信息
The Euclidean distance matrix completion problem (EDMCP) is the problem of determining whether or not a given partial matrix can be completed into a Euclidean distance matrix (EDM). In this paper, we investigate the necessary and sufficient conditions for the uniqueness of a given EDM completion in the case where this EDM completion is generated by points in general position. We also show that the problem of checking the validity of these conditions can be formulated as a semidefinite programming problem. (C) 2004 Elsevier Inc. All rights reserved.
In continuation to an earlier work, we further consider the problem of robust estimation of a random vector (or signal), with an uncertain covariance matrix, that is observed through a known linear transformation and ...
详细信息
In continuation to an earlier work, we further consider the problem of robust estimation of a random vector (or signal), with an uncertain covariance matrix, that is observed through a known linear transformation and corrupted by additive noise with a known covariance matrix. While, in the earlier work, we developed and proposed a competitive minimax approach of minimizing the worst-case mean-squared error (MSE) difference regret criterion, here, we study, in the same spirit, the minimum worst-case MSE ratio regret criterion, namely, the worst-case ratio (rather than difference) between the MSE attainable using a linear estimator, ignorant of the exact signal covariance, and the minimum MSE (MMSE) attainable by optimum linear estimation with a known signal covariance. We present the optimal linear estimator, under this criterion, in two ways: The first is as a solution to a certain semidefinite programming (SDP) problem, and the second is as an expression that is of closed form up to a single parameter whose value can be found by a simple line search procedure. We then show that the linear minimax ratio regret estimator can also be interpreted as the MMSE estimator that minimizes the MSE for a certain choice of signal covariance that depends on the uncertainty region. We demonstrate that in applications, the proposed minimax MSE ratio regret approach may outperform the well-known minimax MSE approach, the minimax MSE difference regret approach, and the "plug-in" approach, where in the latter, one uses the MMSE estimator with an estimated covariance matrix replacing the true unknown covariance.
A basic closed semialgebraic subset S of R-n is defined by simultaneous polynomial inequalities g(1) >= 0,..., g(m) >= 0. We give a short introduction to Lasserre's method for minimizing a polynomial f on a ...
详细信息
A basic closed semialgebraic subset S of R-n is defined by simultaneous polynomial inequalities g(1) >= 0,..., g(m) >= 0. We give a short introduction to Lasserre's method for minimizing a polynomial f on a compact set S of this kind. It consists of successively solving tighter and tighter convex relaxations of this problem which can be formulated as semidefinite programs. We give a new short proof for the convergence of the optimal values of these relaxations to the in. mum f* of f on S which is constructive and elementary. In the case where f possesses a unique minimizer x*, we prove that every sequence of "nearly" optimal solutions of the successive relaxations gives rise to a sequence of points in R-n converging to x*.
Symmetricity of an optimal solution of Semi-Definite programming (SDP) is discussed based on the symmetry property of the central path that is traced by a primal-dual interior-point method. A symmetric SDP is defined ...
详细信息
Symmetricity of an optimal solution of Semi-Definite programming (SDP) is discussed based on the symmetry property of the central path that is traced by a primal-dual interior-point method. A symmetric SDP is defined by operators for rearranging elements of matrices and vectors, and the solution on the central path is proved to be symmetric. Therefore, it is theoretically guaranteed that a symmetric optimal solution is always obtained by using a primal-dual interior-point method even if there exist other asymmetric optimal solutions. The optimization problem of symmetric trusses under eigenvalue constraints is shown to be formulated as a symmetric SDP. Numerical experiments illustrate convergence to strictly symmetric optimal solutions.
作者：
Lasserre, JBCNRS
LAAS F-31077 Toulouse 4 France LAAS
Inst Math F-31077 Toulouse 4 France
Wih every real polynomial f, we associate a family {f is an element of r} is an element of, r of real polynomials, in explicit form in terms of f and the parameters is an element of > 0, r is an element of N, and s...
详细信息
Wih every real polynomial f, we associate a family {f is an element of r} is an element of, r of real polynomials, in explicit form in terms of f and the parameters is an element of > 0, r is an element of N, and such that parallel to f - f is an element of r parallel to 1 -> 0 as is an element of -> 0. Let V subset of R-n be a real algebraic set described by. nitely many polynomials equations g(j) (x) = 0, j is an element of J, and let f be a real polynomial, nonnegative on V. We show that for every is an element of > 0, there exist nonnegative scalars {lambda(j) (is an element of)} (j is an element of J) such that, for all r sufficiently large, [Graphics] This representation is an obvious certificate of nonnegativity of f (is an element of r) on V, and very specific in terms of the g(j) that de. ne the set V. In particular, it is valid with no assumption on V. In addition, this representation is also useful from a computation point of view, as we can define semidefinite programming relaxations to approximate the global minimum of f on a real algebraic set V, or a semialgebraic set K, and again, with no assumption on V or K.
This paper considers the distribution of values Q(x), x is an element of {- 1, 1}(n), where Q is a quadratic form in n variables with real coefficients. Error estimates are established for approximations of the maximu...
详细信息
This paper considers the distribution of values Q(x), x is an element of {- 1, 1}(n), where Q is a quadratic form in n variables with real coefficients. Error estimates are established for approximations of the maximum and minimum values of Q on {- 1, 1}(n) which can be obtained by semidefinite programming. Bounds are given involving the sum of the absolute values of the off-diagonal entries. Other bounds are given which are useful in the case of extreme skewness. Used in conjunction with earlier bounds of Nesterov in [Optim. Methods Softw., 9 ( 1998), pp. 141 - 160], these new bounds lead to improvements on the bound given by the trace. The trigonometric description of the maximum and minimum given in [ Optim. Methods Softw., 9 ( 1998), pp. 141 - 160], which is based on the rounding argument introduced by Goemans and Williamson in [J. Assoc. Comput. Mach., 6 ( 1995), pp. 1115 1145], is a major tool in obtaining these bounds.
The purpose of this paper is threefold. First we propose splitting schemes for reformulating non-separable problems as block-separable problems. Second we show that the Lagrangian dual of a block-separable mixed-integ...
详细信息
The purpose of this paper is threefold. First we propose splitting schemes for reformulating non-separable problems as block-separable problems. Second we show that the Lagrangian dual of a block-separable mixed-integer all-quadratic program (MIQQP) can be formulated as an eigenvalue optimization problem keeping the block-separable structure. Finally we report numerical results on solving the eigenvalue optimization problem by a proximal bundle algorithm applying Lagrangian decomposition. The results indicate that appropriate block-separable reformulations of MIQQPs could accelerate the running time of dual solution algorithms considerably.
This note points out an error in the local quadratic convergence proof of the predictor-corrector interior-point algorithm for solving the semidefinite linear complementarity problem based on the Alizadeh-Haeberly-Ove...
详细信息
This note points out an error in the local quadratic convergence proof of the predictor-corrector interior-point algorithm for solving the semidefinite linear complementarity problem based on the Alizadeh-Haeberly-Overton search direction presented in [M. Kojima, M. Shida, and S. Shindoh, SIAM J. Optim., 9 (1999), pp. 444-465]. Their algorithm is slightly modified and the local quadratic convergence of the resulting method is established.
We present algorithms for the optimization of two-dimensional (2-D) infinite impulse response (IIR) filters with separable or nonseparable denominator, for least squares or Chebyshev criteria. The algorithms are itera...
详细信息
We present algorithms for the optimization of two-dimensional (2-D) infinite impulse response (IIR) filters with separable or nonseparable denominator, for least squares or Chebyshev criteria. The algorithms are iterative, and each iteration consists of solving a semidefinite programming problem. For least squares designs, we adapt the Gauss-Newton idea, which outcomes to a convex approximation of the optimization criterion. For Chebyshev designs, we adapt the iterative reweighted least squares (IRLS) algorithm;in each iteration, a least squares Gauss-Newton step is performed, while the weights are changed as in the basic IRLS algorithm. The stability of the 2-D IIR filters is ensured by keeping the denominator inside convex stability domains, which aredefined by linear matrix inequalities. For the 2-D (nonseparable) case, this is a new contribution, based on the parameterization of 2-D polynomials that are positive on the unit bicircle. In the experimental section, 2-D IIR filters with separable and nonseparable denominators are designed and compared. We show that each type may be better than the other, depending on the design specification. We also give an example of filter that is clearly better than a recent very good design.
This paper studies the asymptotic behavior of the central path (X(nu), S(nu), y(nu)) as nu down arrow 0 for a class of degenerate semidefinite programming (SDP) problems, namely those that do not have strictly complem...
详细信息
This paper studies the asymptotic behavior of the central path (X(nu), S(nu), y(nu)) as nu down arrow 0 for a class of degenerate semidefinite programming (SDP) problems, namely those that do not have strictly complementary primal-dual optimal solutions and whose "degenerate diagonal blocks" X-T(nu) and S-T(nu) of the central path are assumed to satisfy max{||X-T(nu)||, ||S-T(nu)||} = O(root nu). We establish the convergence of the central path towards a primal-dual optimal solution, which is characterized as being the unique optimal solution of a certain log-barrier problem. A characterization of the class of SDP problems which satisfy our assumptions are also provided. It is shown that the re-parametrization t > 0 -> (X(t(4)), S(t(4)), y(t(4))) of the central path is analytic at t = 0. The limiting behavior of the derivative of the central path is also investigated and it is shown that the order of convergence of the central path towards its limit point is O(root nu). Finally, we apply our results to the convex quadratically constrained convex programming (CQCCP) problem and characterize the class of CQCCP problems which can be formulated as SDPs satisfying the assumptions of this paper. In particular, we show that CQCCP problems with either a strictly convex objective function or at least one strictly convex constraint function lie in this class.
暂无评论