It is well known that by adding integrality constraints to the semidefinite programming (SDP) relaxation of the max -cut problem, the resulting integer semidefinite program is an exact formulation of the problem. In t...
详细信息
It is well known that by adding integrality constraints to the semidefinite programming (SDP) relaxation of the max -cut problem, the resulting integer semidefinite program is an exact formulation of the problem. In this paper we show similar results for a wide variety of discrete optimization problems for which SDP relaxations have been derived. Based on a comprehensive study on discrete positive semidefinite matrices, we introduce a generic approach to derive mixed -integer SDP (MISDP) formulations of binary quadratically constrained quadratic programs and binary quadraticmatrix programs. Applying a problem -specific approach, we derive more compact MISDP formulations of several problems, such as the quadratic assignment problem, the graph partition problem, and the integer matrix completion problem. We also show that several structured problems allow for novel compact MISDP formulations through the notion of association schemes. Complementary to the recent advances on algorithmic aspects related to MISDP, this work opens new perspectives on solution approaches for the here considered problems.
We consider the problem of maximizing the ratio of two generalized quadraticmatrix form functions over the Stiefel manifold, i.e., maxXTX=Itr(GXTAX)tr(GXTBX)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepack...
详细信息
We consider the problem of maximizing the ratio of two generalized quadraticmatrix form functions over the Stiefel manifold, i.e., maxXTX=Itr(GXTAX)tr(GXTBX)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\max \limits _{X<^>{T}X=I} \frac{\text {tr}(GX<^>{T}AX)}{\text {tr}(GX<^>{T}BX)}$$\end{document} (RQMP). We utilize the Dinkelbach algorithm to globally solve RQMP, where each subproblem is evaluated by the closed-form solution. For a special case of RQMP with AB=BA\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$AB=BA$$\end{document}, we propose an equivalent linear programming problem. Numerical experiments demonstrate that it is more efficient than the recent SDP-based algorithm.
作者：
Yong XiaKey Laboratory of Mathematics
Informatics and Behavioral Semantics of the Ministry of EducationSchool of Mathematics and System SciencesBeihang UniversityBeijing 100191China
Motivated by the fact that not all nonconvex optimization problems are difficult to solve,we survey in this paper three widely used ways to reveal the hidden convex structure for different classes of nonconvex optimiz...
详细信息
Motivated by the fact that not all nonconvex optimization problems are difficult to solve,we survey in this paper three widely used ways to reveal the hidden convex structure for different classes of nonconvex optimization ***,ten open problems are raised.
In this paper, we investigate a unified linear transceiver design with mean-square-error (MSE) as the objective function for a wide range of wireless systems. The unified design is based on an elegant mathematical pro...
详细信息
ISBN:
(纸本)9781467358293;9781467358309
In this paper, we investigate a unified linear transceiver design with mean-square-error (MSE) as the objective function for a wide range of wireless systems. The unified design is based on an elegant mathematical programming technology namely quadratic matrix programming (QMP). It is revealed that for different wireless systems such as multi-cell coordination systems, multi-user MIMO systems, MIMO cognitive radio systems, amplify-and-forward MIMO relaying systems, the MSE minimization beamforming design problems can always be solved by solving a number of QMP problems. A comprehensive framework on how to solve QMP problems is also given.
We analyze two popular semidefinite programming relaxations for quadratically constrained quadratic programs with matrix variables. These relaxations are based on vector lifting and on matrix lifting;they are of diffe...
详细信息
We analyze two popular semidefinite programming relaxations for quadratically constrained quadratic programs with matrix variables. These relaxations are based on vector lifting and on matrix lifting;they are of different size and expense. We prove, under mild assumptions, that these two relaxations provide equivalent bounds. Thus, our results provide a theoretical guideline for how to choose a less expensive semidefinite programming relaxation and still obtain a strong bound. The main technique used to show the equivalence and that allows for the simplified constraints is the recognition of a class of nonchordal sparse patterns that admit a smaller representation of the positive semidefinite constraint.
We introduce and study a special class of nonconvex quadratic problems in which the objective and constraint functions have the form f(X) = Tr(X(T)AX) + 2Tr(B(T)X) + c, X is an element of RR(nxr). The latter formulati...
详细信息
We introduce and study a special class of nonconvex quadratic problems in which the objective and constraint functions have the form f(X) = Tr(X(T)AX) + 2Tr(B(T)X) + c, X is an element of RR(nxr). The latter formulation is termed quadratic matrix programming (QMP) of order r. We construct a specially devised semidefinite relaxation (SDR) and dual for the QMP problem and show that under some mild conditions strong duality holds for QMP problems with at most r constraints. Using a result on the equivalence of two characterizations of the nonnegativity property of quadratic functions of the above form, we are able to compare the constructed SDR and dual problems to other known SDRs and dual formulations of the problem. An application to robust least squares problems is discussed.
暂无评论