Graph partition is used in the telecommunication industry to subdivide a transmission network into small clusters. We consider both linear and semidefinite relaxations for the equipartition problem and present numeric...
详细信息
Graph partition is used in the telecommunication industry to subdivide a transmission network into small clusters. We consider both linear and semidefinite relaxations for the equipartition problem and present numerical results on real data from France Telecom networks with up 900 nodes, and also on randomly generated problems.
作者：
Eldar, YCMIT
Elect Res Lab Cambridge MA 02139 USA
In this paper, we consider the problem. of unambiguous discrimination between a set of linearly independent pure quantum states. We show that the design of the optimal measurement that minimizes the probability of an ...
详细信息
In this paper, we consider the problem. of unambiguous discrimination between a set of linearly independent pure quantum states. We show that the design of the optimal measurement that minimizes the probability of an inconclusive result can be formulated as a semidefinite programming problem. Based on this formulation, we develop a set of necessary and sufficient conditions for an optimal quantum measurement. We show that the optimal measurement can be computed very efficiently in polynomial time by exploiting the many well-known algorithms for solving semidefinite programs, which are guaranteed to converge to the global optimum. Using the general conditions for optimality, we derive necessary and sufficient conditions so that the measurement that results in an equal probability of an inconclusive result for each one of the quantum states is optimal. We refer to this measurement as the equal-probability measurement (EPM). We then show that for any state set, the prior probabilities of the states can be chosen such that the EPM is optimal. Finally, we consider state sets with strong symmetry properties and equal prior probabilities for which the EPM is optimal. We first consider geometrically uniform (GU) state sets that are defined over a group of unitary matrices and are generated by a single generating vector. We then consider compound GU state sets which are generated by a group of unitary matrices using multiple generating vectors, where the generating vectors satisfy a certain (weighted) norm constraint.
We study the asymptotic behavior of the interior-point bounds arising from the work of Yildirim and Todd on sensitivity analysis in semidefinite programming in comparison with the optimal partition bounds. We introduc...
详细信息
We study the asymptotic behavior of the interior-point bounds arising from the work of Yildirim and Todd on sensitivity analysis in semidefinite programming in comparison with the optimal partition bounds. We introduce a weaker notion of nondegeneracy and discuss its implications. For perturbations of the right-hand-side vector or the cost matrix, we show that the interior-point bounds evaluated on the central path using the Monteiro-Zhang family of search directions converge (as the duality gap tends to zero) to the symmetrized version of the optimal partition bounds under mild nondegeneracy assumptions. Furthermore, our analysis does not assume strict complementarity as long as the central path converges to the analytic center in a relatively controlled manner. We also show that the same convergence results carry over to iterates lying in an appropriate (very narrow) central path neighborhood if the Nesterov-Todd direction is used to evaluate the interior-point bounds. We extend our results to the case of simultaneous perturbations of the right-hand-side vector and the cost matrix. We also provide examples illustrating that our assumptions, in general, cannot be weakened.
We present algorithms for the soluition of two problems in array pattern synthesis. The first is the design of nonuniform arrays with a desired magnitude response. The second is that of robust design, i.e., design in ...
详细信息
We present algorithms for the soluition of two problems in array pattern synthesis. The first is the design of nonuniform arrays with a desired magnitude response. The second is that of robust design, i.e., design in the presence of uncertainties. Constraints such as power limitation can be addressed with both problems. The algorithms that we present are based on semidefinite programming, for which efficient software is readily available. We present examples that illustrate the effectiveness of our approach.
This article considers feasible long-step primal-dual path-following methods for semidefinite programming based on Newton directions associated with central path equations of the form Phi ( PXPT , P-T SP-1) - nu I = 0...
详细信息
This article considers feasible long-step primal-dual path-following methods for semidefinite programming based on Newton directions associated with central path equations of the form Phi ( PXPT , P-T SP-1) - nu I = 0, where the map Phi and the nonsingular matrix P satisfy several key properties. An iteration-complexity bound for the long-step method is derived in terms of an upper bound on a certain scaled norm of the second derivative of Phi. As a consequence of our general framework, we derive polynomial iteration-complexity bounds for long-step algorithms based on the following four maps: Phi(X, S) = (XS + SX) /2 , Phi(X,S) = L-x(T) SLx , Phi(X,S) = X-1/2 S X-1/2, and Phi (X , S) = W-1/2 XSW-1/2 , where L-x is the lower Cholesky factor of X and W is the unique symmetric matrix satisfying S = WXW .
We introduce a computer program PENNON for the solution of problems of convex Nonlinear and semidefinite programming (NLP-SDP). The algorithm used in PENNON is a generalized version of the Augmented Lagrangian method,...
详细信息
We introduce a computer program PENNON for the solution of problems of convex Nonlinear and semidefinite programming (NLP-SDP). The algorithm used in PENNON is a generalized version of the Augmented Lagrangian method, originally introduced by Ben-Tal and Zibulevsky for convex NLP problems. We present generalization of this algorithm to convex NLP-SDP problems, as implemented in PENNON and details of its implementation. The code can also solve second-order conic programming (SOCP) problems, as well as problems with a mixture of SDP, SOCP and NLP constraints. Results of extensive numerical tests and comparison with other optimization codes are presented. The test examples show that PENNON is particularly suitable for large sparse problems.
Hydrothermal coordination (HTC) is a problem that has been solved using direct and decomposition solution methods. The latter has shown shorter solution times than the former. A direct solution method for the HTC prob...
详细信息
Hydrothermal coordination (HTC) is a problem that has been solved using direct and decomposition solution methods. The latter has shown shorter solution times than the former. A direct solution method for the HTC problem that is based in semidefinite programming (SDP) is presented in this paper. SDP is a convex programming method with polynomial solution time. The variables of the problem are arranged in a vector, which is used to construct a positive-definite matrix;the optimal solution is then found in the cone defined by the set of positive-definite matrices. An HTC problem can be formulated as a convex optimization problem without explicitly stating the integer value requirements for the. thermal-plants discrete variables. Thus, it is possible to replace the nonconvex integer-value constraints by convex quadratic constraints, and then use SDP. Due to its polynomial complexity, it is not necessary to use decomposition or other tools for discrete optimization, such as enumeration schemes or other exponential-time procedures. No initial relaxation is necessary when applying a SDP algorithm;the solution shows only minor mismatches in the integer variables, which are easily corrected by a heuristic method. Different size test cases are presented. The solution quality is assessed by comparing with that produced by a Lagrangian Relaxation method.
作者：
Eldar, YCMegretski, AVerghese, GCMIT
Res Lab Elect Cambridge MA 02139 USA MIT
Informat & Decis Syst Lab Cambridge MA 02139 USA MIT
Electromagnet & Elect Syst Lab Cambridge MA 02139 USA
We consider the problem of designing an optimal quantum detector to minimize the probability of a detection error when distinguishing among a collection of quantum states, represented by a set of density operators. We...
详细信息
We consider the problem of designing an optimal quantum detector to minimize the probability of a detection error when distinguishing among a collection of quantum states, represented by a set of density operators. We show that the design of the optimal detector can be formulated as a semidefinite programming problem. Based on this formulation, we derive a set of necessary Ind sufficient conditions for an optimal quantum measurement. We then show that the optimal measurement can be found by solving a standard (convex) semidefinite program. By exploiting the many well-known algorithms for solving semidefinite programs, which are guaranteed to converge to the global optimum, the optimal measurement can be computed very efficiently in polynomial time within any desired accuracy. Using the semidefinite programming formulation, we also show that the rank of each optimal measurement operator is no larger than the rank of the corresponding density operator. In particular, if the quantum state ensemble is a pure-state ensemble consisting of (not necessarily independent) rank-one density operators, then we show that the optimal measurement is a pure-state measurement consisting of rank-one measurement operators.
Since Lim's 1986 paper on the frequency-response-masking,(FRM) technique for the design of finite-impulse response digital filters with very small transition widths, the analysis and design of FRM filters has been...
详细信息
Since Lim's 1986 paper on the frequency-response-masking,(FRM) technique for the design of finite-impulse response digital filters with very small transition widths, the analysis and design of FRM filters has been a subject of study. In this paper, a new optimization technique for the design of various FRM filters is proposed. Central to the new design method is a sequence of linear updates for the design variables, with each update carried out by semidefinite programming. Algorithmic details for the design of basic and multistage FRM filters are presented to show that the proposed method offers a unified design framework for a variety of FRM filters. Design simulations are included to illustrate the proposed algorithms and to evaluate the design performance in comparison with that of several existing methods.
Recently, de Klerk, van Maaren and Warners [ 10] investigated a relaxation of 3-SAT via semidefinite programming. Thus a 3-SAT formula is relaxed to a semidefinite feasibility problem. If the feasibility problem is in...
详细信息
Recently, de Klerk, van Maaren and Warners [ 10] investigated a relaxation of 3-SAT via semidefinite programming. Thus a 3-SAT formula is relaxed to a semidefinite feasibility problem. If the feasibility problem is infeasible then a certificate of unsatisfiability of the formula is obtained. The authors proved that this approach is exact for several polynomially solvable classes of logical formulae, including 2-SAT, pigeonhole formulae and mutilated chessboard formulae. In this paper we further explore this approach, and investigate the strength of the relaxation on (2+p)-SAT formulae, i.e., formulae with a fraction p of 3-clauses and a fraction (1-p) of 2-clauses. In the first instance, we provide an empirical computational evaluation of our approach. Secondly, we establish approximation guarantees of randomized and deterministic rounding schemes when the semidefinite feasibility problem is feasible, and also present computational results for the rounding schemes. In particular, we do a numerical and theoretical comparison of this relaxation and the stronger relaxation by Karloff and Zwick [15].
暂无评论