We describe a major update of our Matlab freeware GloptiPoly for parsing generalized problems of moments and solving them numerically with semidefinite programming.
We describe a major update of our Matlab freeware GloptiPoly for parsing generalized problems of moments and solving them numerically with semidefinite programming.
Let G = (V, E) be a graph. In matrix completion theory, it is known that the following two conditions are equivalent: (i) G is a chordal graph;(ii) Every G-partial positive semidefinite matrix has a positive semidefin...
详细信息
Let G = (V, E) be a graph. In matrix completion theory, it is known that the following two conditions are equivalent: (i) G is a chordal graph;(ii) Every G-partial positive semidefinite matrix has a positive semidefinite matrix completion. In this paper, we relate these two conditions to constraint nondegeneracy condition in semidefinite programming and prove that they are each equivalent to;(iii) For any G-partial positive definite matrix that has a positive semidefinite completion, constraint nondegeneracy is satisfied at each of its positive semidefinite matrix completions. (c) 2008 Elsevier Inc. All rights reserved.
In this paper, we propose an array pattern synthesis scheme using semidefinite programming (SDP) under array excitation power constraints. When an array pattern synthesis problem is formulated as an SDP problem, it is...
详细信息
In this paper, we propose an array pattern synthesis scheme using semidefinite programming (SDP) under array excitation power constraints. When an array pattern synthesis problem is formulated as an SDP problem, it is known that an additional rank-one constraint is generated inevitably and relaxed via semidefinite relaxation. If the solution to the relaxed SDP problem is not of rank one, then conventional SDP-based array pattern synthesis approaches fail to obtain optimal solutions because the additional rank-one constraint is not handled appropriately. To overcome this drawback, we adopted a bisection technique combined with a penalty function method. Numerical applications are presented to demonstrate the validity of the proposed scheme.
We consider beamformer design for multiuser multiple-input multiple-output (MIMO) interference channels where each transmitter communicates to its intended receivers while sharing the same spectro-temporal resources w...
详细信息
We consider beamformer design for multiuser multiple-input multiple-output (MIMO) interference channels where each transmitter communicates to its intended receivers while sharing the same spectro-temporal resources with some other unintended receivers. This scenario is often referred to as MIMO interference broadcast channel (IBC) where by using interference alignment (IA), it is possible to cancel out inter and intracell interferences so that the achievable degrees of freedom could be linearly scaled up with the number of users. In this paper, we propose two distinct and novel IA algorithms, one of which is IA via signal matching (SIGMA) that revolves around interference leakage minimization and further takes the desired signal subspaces into account to output higher sum rates. The second algorithm is called bipartite rank fitting, which is founded on the prior knowledge of the rank of receive beamformers and interference matrices. Therefore, this algorithm is quite a unique approach towards interference alignment in MIMO IBCs since it performs the optimization over only receive beamformers. Furthermore, we propose a robust design of SIGMA algorithm to achieve better performance in the presence of imperfect channel state information (CSI). The key tenet of our design is that we formulate the optimization problems involved in these two algorithms as plain semidefinite programs. It is shown that the proposed algorithms are able to outperform state-of-the-art IA techniques under perfect and imperfect CSI, and the suitability of each algorithm for different network configurations is further discussed.
Given a data matrix, we find its nearest symmetric positive-semidefinite Toeplitz matrix. In this paper, we formulate the problem as an optimization problem with a quadratic objective function and semidefinite constra...
详细信息
Given a data matrix, we find its nearest symmetric positive-semidefinite Toeplitz matrix. In this paper, we formulate the problem as an optimization problem with a quadratic objective function and semidefinite constraints. In particular, instead of solving the so-called normal equations, our algorithm eliminates the linear feasibility equations from the start to maintain exact primal and dual feasibility during the course of the algorithm. Subsequently, the search direction is found using an inexact Gauss-Newton method rather than a Newton method on a symmetrized system and is computed using a diagonal preconditioned conjugate-gradient-type method. Computational results illustrate the robustness of the algorithm.
The quantum many-body problem can be rephrased as a variational determination of the two-body reduced density matrix, subject to a set of N-representability constraints. The mathematical problem has the form of a semi...
详细信息
The quantum many-body problem can be rephrased as a variational determination of the two-body reduced density matrix, subject to a set of N-representability constraints. The mathematical problem has the form of a semidefinite program. We adapt a standard primal-dual interior point algorithm in order to exploit the specific structure of the physical problem. In particular the matrix-vector product can be calculated very efficiently. We have applied the proposed algorithm to a pairing-type Hamiltonian and studied the computational aspects of the method. The standard N-representability conditions perform very well for this problem. (C) 2011 Elsevier B.V. All rights reserved.
In this paper we present an extension to SDP of the well known infeasible Interior Point method for linear programming of Kojima, Megiddo and Mizuno (A primal-dual infeasible-interior-point algorithm for Linear Progra...
详细信息
In this paper we present an extension to SDP of the well known infeasible Interior Point method for linear programming of Kojima, Megiddo and Mizuno (A primal-dual infeasible-interior-point algorithm for Linear programming, Math. Progr., 1993). The extension developed here allows the use of inexact search directions;i.e., the linear systems defining the search directions can be solved with an accuracy that increases as the solution is approached. A convergence analysis is carried out and the global convergence of the method is proved.
Recent results in compressed sensing show that, under certain conditions, the sparsest solution to an underdetermined set of linear equations can be recovered by solving a linear program. These results either rely on ...
详细信息
Recent results in compressed sensing show that, under certain conditions, the sparsest solution to an underdetermined set of linear equations can be recovered by solving a linear program. These results either rely on computing sparse eigenvalues of the design matrix or on properties of its nullspace. So far, no tractable algorithm is known to test these conditions and most current results rely on asymptotic properties of random matrices. Given a matrix A, we use semidefinite relaxation techniques to test the nullspace property on A and show on some numerical examples that these relaxation bounds can prove perfect recovery of sparse solutions with relatively high cardinality.
This paper considers a multiuser transmit beamforming problem under uncertain channel state information (CSI) subject to SINR constraints in a downlink multiuser MISO system. A robust transmit beamforming formulation ...
详细信息
This paper considers a multiuser transmit beamforming problem under uncertain channel state information (CSI) subject to SINR constraints in a downlink multiuser MISO system. A robust transmit beamforming formulation is proposed. This robust formulation is to minimize the transmission power subject to worst-case signal-to-interference-plus-noise ratio (SINR) constraints on the receivers. The challenging problem is that the worst-case SINR constraints correspond to an infinite number of nonconvex quadratic constraints. In this paper, a natural semidifinite programming (SDP) relaxation problem is proposed to solve the robust beamforming problem. The main contribution of this paper is to establish the tightness of the SDP relaxation problem under proper assumption, which means that the SDP relaxation problem definitely yields rank-one solutions under the assumption. Then the SDP relaxation problem provides globally optimum solutions of the primal robust transmit beamforming problem under proper assumption and norm-constrained CSI errors. Simulation results show the correctness of the proposed theoretical results and also provide a counterexample whose solutions are not rank one. The existence of counterexample shows that the guess that the solutions of the SDP relaxation problem must be rank one is wrong, except that some assumptions (such as the one proposed in this paper) hold.
We provide new tools for worst-case performance analysis of the gradient (or steepest descent) method of Cauchy for smooth strongly convex functions, and Newton's method for self-concordant functions, including th...
详细信息
We provide new tools for worst-case performance analysis of the gradient (or steepest descent) method of Cauchy for smooth strongly convex functions, and Newton's method for self-concordant functions, including the case of inexact search directions. The analysis uses semidefinite programming performance estimation, as pioneered by Drori and Teboulle [it Math. Program., 145 (2014), pp. 451-482], and extends recent performance estimation results for the method of Cauchy by the authors [it Optim. Lett., 11 (2017), pp. 1185-1199]. To illustrate the applicability of the tools, we demonstrate a novel complexity analysis of short step interior point methods using inexact search directions. As an example in this framework, we sketch how to give a rigorous worst-case complexity analysis of a recent interior point method by Abernethy and Hazan [it PMLR, 48 (2016), pp. 2520-2528].
暂无评论