A continuation algorithm for the solution of Max-Bisection problems is proposed in this paper. Unlike available relaxation algorithms for Max-Bisection problems, the Max-Bisection problems are converted to an equivale...
详细信息
A continuation algorithm for the solution of Max-Bisection problems is proposed in this paper. Unlike available relaxation algorithms for Max-Bisection problems, the Max-Bisection problems are converted to an equivalent continuous nonlinear programming by employing NCP functions, and the resulting nonlinear programming problem is then solved using the augmented Lagrange penalty function method. The convergence property and finite termination property of the proposed algorithm are studied, and numerical experiments and comparisons on the simple circuit partitioning problems are made. Results reported in section "Numerical experiments" show the algorithm generates satisfactory solutions to test problems. (c) 2005 Elsevier Inc. All rights reserved.
We propose a stability test for discrete-time systems whose coefficients depend polynomially on some bounded parameters. The test is a particular form of Positivstellensatz, appeals to sum-of-squares polynomials and c...
详细信息
We propose a stability test for discrete-time systems whose coefficients depend polynomially on some bounded parameters. The test is a particular form of Positivstellensatz, appeals to sum-of-squares polynomials and can be implemented as a semidefinite programming problem. Although implementable only in relaxed form, due to the necessity of limiting the degrees of the polynomial variables involved, the experiments show a good accuracy with degrees smaller than for other tests.
Industrial implementation of model-based control methods, such as model predictive control, is often complicated by the lack of knowledge about the disturbances entering the system. In this paper, we present a new met...
详细信息
Industrial implementation of model-based control methods, such as model predictive control, is often complicated by the lack of knowledge about the disturbances entering the system. In this paper, we present a new method (constrained ALS) to estimate the variances of the disturbances entering the process using routine operating data. A variety of methods have been proposed to solve this problem. Of note, we compare ALS to the classic approach presented in Mehra [(1970). On the identification of variances and adaptive Kalman filtering. IEEE Transactions on Automatic Control, 15(12), 175-184]. This classic method, and those based on it, use a three-step procedure to compute the covariances. The method presented in this paper is a one-step procedure, which yields covariance, estimates with lower variance on all examples tested. The for-mutation used in this paper provides necessary and sufficient conditions for uniqueness of the estimated covariances, previously not available in the literature. We show that the estimated covariances are unbiased and converge to the true values with increasing sample size. The proposed method also guarantees positive semidefinite covariance estimates by adding constraints to the ALS problem. The resulting convex program can be solved efficiently. (c) 2005 Elsevier Ltd. All rights reserved.
An important question in discrete optimization under uncertainty is to understand the persistency of a decision variable, i.e., the probability that it is part of an optimal solution. For instance, in project manageme...
详细信息
An important question in discrete optimization under uncertainty is to understand the persistency of a decision variable, i.e., the probability that it is part of an optimal solution. For instance, in project management, when the task activity times are random, the challenge is to determine a set of critical activities that will potentially lie on the longest path. In the spanning tree and shortest path network problems, when the arc lengths are random, the challenge is to pre-process the network and determine a smaller set of arcs that will most probably be a part of the optimal solution under different realizations of the arc lengths. Building on a characterization of moment cones for single variate problems, and its associated semidefinite constraint representation, we develop a limited marginal moment model to compute the persistency of a decision variable. Under this model, we show that finding the persistency is tractable for zero-one optimization problems with a polynomial sized representation of the convex hull of the feasible region. Through extensive experiments, we show that the persistency computed under the limited marginal moment model is often close to the simulated persistency value under various distributions that satisfy the prescribed marginal moments and are generated independently.
We consider a protocol to perform the optimal quantum state discrimination of N linearly independent non-orthogonal pure quantum states and present a computational code. Through the extension of the original Hilbert s...
详细信息
We consider a protocol to perform the optimal quantum state discrimination of N linearly independent non-orthogonal pure quantum states and present a computational code. Through the extension of the original Hilbert space, it is possible to perform an unitary operation yielding a final configuration, which gives the best discrimination without ambiguity by means of von Neumann measurements. Our goal is to introduce a detailed general mathematical procedure to realize this task by means of semidefinite programming and norm minimization. The former is used to fix which is the best detection probability amplitude for each state of the ensemble. The latter determines the matrix which leads the states to the final configuration. In a final step, we decompose the unitary transformation in a sequence of two-level rotation matrices.
We present a convex programming approach to the problem of matching subgraphs which represent object views against larger graphs which represent scenes. Starting from a linear programming formulation for computing opt...
详细信息
作者：
Lasserre, JBCNRS
LAAS F-31077 Toulouse 4 France LAAS
Inst Math F-31077 Toulouse 4 France
We consider the optimization problems max (z is an element of Omega) min (x is an element of K) p(z, x) and min (x is an element of K) max (z is an element of Omega) p(z, x) where the criterion p is a polynomial, line...
详细信息
We consider the optimization problems max (z is an element of Omega) min (x is an element of K) p(z, x) and min (x is an element of K) max (z is an element of Omega) p(z, x) where the criterion p is a polynomial, linear in the variables z, the set Omega can be described by LMIs, and K is a basic closed semi-algebraic set. The first problem is a robust analogue of the generic SDP problem max (z is an element of Omega) p(z), whereas the second problem is a robust analogue of the generic problem min (x is an element of K) p(x) of minimizing a polynomial over a semi-algebraic set. We show that the optimal values of both robust optimization problems can be approximated as closely as desired, by solving a hierarchy of SDP relaxations. We also relate and compare the SDP relaxations associated with the max-min and the min-max robust optimization problems.
We build upon the work of Fukuda et al. [SIAM J. Optim., 11 (2001), pp. 647-674] and Nakata et al. [Math. Program., 95 (2003), pp. 303-327], in which the theory of partial positive semidefinite matrices was applied to...
详细信息
We build upon the work of Fukuda et al. [SIAM J. Optim., 11 (2001), pp. 647-674] and Nakata et al. [Math. Program., 95 (2003), pp. 303-327], in which the theory of partial positive semidefinite matrices was applied to the semidefinite programming (SDP) problem as a technique for exploiting sparsity in the data. In contrast to their work, which improved an existing algorithm based on a standard search direction, we present a primal-dual path-following algorithm that is based on a new search direction, which, roughly speaking, is defined completely within the space of partial symmetric matrices. We show that the proposed algorithm computes a primal-dual solution to the SDP problem having duality gap less than a fraction epsilon > 0 of the initial duality gap in O(n log(epsilon(-1))) iterations, where n is the size of the matrices involved. Moreover, we present computational results showing that the algorithm possesses several advantages over other existing implementations.
We show that every real nonnegative polynomial f can be approximated as closely as desired (in the l(1)-norm of its coefficient vector) by a sequence of polynomials {f(epsilon)} that are sums of squares. The novelty i...
详细信息
We show that every real nonnegative polynomial f can be approximated as closely as desired (in the l(1)-norm of its coefficient vector) by a sequence of polynomials {f(epsilon)} that are sums of squares. The novelty is that each f(epsilon) has a simple and explicit form in terms of f and epsilon.
We consider the 2-Catalog Segmentation problem (2-CatSP) introduced by Kleinberg et al. [J. Kleinberg, C. Papadimitriou and P. Raghavan (1998). Segmentation problems. In Proceedings of the 30th Symposium on Theory of ...
详细信息
We consider the 2-Catalog Segmentation problem (2-CatSP) introduced by Kleinberg et al. [J. Kleinberg, C. Papadimitriou and P. Raghavan (1998). Segmentation problems. In Proceedings of the 30th Symposium on Theory of Computation , pp. 473-482.], where we are given a ground set I of n items, a family {S-1, S-2,...,S-m } of subsets of I and an integer 1 less than or equal to k less than or equal to n . The objective is to find subsets A(1), A(2) subset of I such that \A(1)\ = \A(2)\ = k and Sigma(i=1)(m) max {\S-i boolean AND A(1)\, \S-i boolean AND A(2)\} is maximized. It is known that a simple and elegant greedy algorithm has a performance guarantee 1/2. Furthermore, using a semidefinite programming (SDP) relaxation Doids et al. [Y. Doids, V. Guruswami and S. Khanna (1999). The 2-catalog segmentation problem. In Proceedings of SODA , pp. 378-380.] showed that 2-CatSP can be approximated by a factor of 0.56 when k = n/2. Motivated by these results, we develop improved approximation algorithms for 2-CatSP on a range of k in this paper. The performance guarantee of our algorithm is 1/2 for general k , and is strictly greater than 1/2 when k greater than or equal to n /3. In particular, we obtain a ratio of 0.67 for 2-CatSP when k = n/2. Unlike the relaxation used by Doids et al. , our extended and direct SDP relaxation deals with general k , which enables us to obtain better approximation for 2-CatSP. Another contribution of this paper is a new variation of the random hyperplane rounding technique, which allows us to explore the structure of 2-CatSP. This rounding technique might be of independent interest. It can be also used to obtain improved approximation for several other graph partitioning problems considered in Feige and Langberg [U. Fiege and M. Langberg (2002). Approximation algorithms for maximization problems arising in graph partitioning. Journal of Algorithm .], Ye and Zhang [Y. Ye and J. Zhang (2003). Approximation for dense-n/2-subgraph and the complemen
暂无评论