-
作者：Grosso, Andrea; Locatelli, Marco; Schoen, Fabio
作者单位：University of Florence; University of Turin
摘要：When dealing with extremely hard global optimization problems, i.e. problems with a large number of variables and a huge number of local optima, heuristic procedures are the only possible choice. In this situation, lacking any possibility of guaranteeing global optimality for most problem instances, it is quite difficult to establish rules for discriminating among different algorithms. We think that in order to judge the quality of new global optimization methods, different criteria might be a...
-
作者：Rendl, Franz; Sotirov, Renata
作者单位：University of Klagenfurt; University of Melbourne
摘要：Semidefinite programming (SDP) has recently turned out to be a very powerful tool for approximating some NP-hard problems. The nature of the quadratic assignment problem (QAP) suggests SDP as a way to derive tractable relaxations. We recall some SDP relaxations of QAP and solve them approximately using a dynamic version of the bundle method. The computational results demonstrate the efficiency of the approach. Our bounds are currently among the strongest ones available for QAP. We investigate ...
-
作者：Munson, Todd
作者单位：United States Department of Energy (DOE); Argonne National Laboratory
摘要：Meshes containing elements with bad quality can result in poorly conditioned systems of equations that must be solved when using a discretization method, such as the finite-element method, for solving a partial differential equation. Moreover, such meshes can lead to poor accuracy in the approximate solution computed. In this paper, we present a nonlinear fractional program that relocates the vertex coordinates of a given mesh to optimize the average element shape quality as measured by the in...
-
作者：So, Anthony Man-Cho; Zhang, Jiawei; Ye, Yinyu
作者单位：Stanford University; New York University; Stanford University
摘要：In this paper we study semidefinite programming (SDP) models for a class of discrete and continuous quadratic optimization problems in the complex Hermitian form. These problems capture a class of well-known combinatorial optimization problems, as well as problems in control theory. For instance, they include the MAX-3-CUT problem where the Laplacian matrix is positive semidefinite ( in particular, some of the edge weights can be negative). We present a generic algorithm and a unified analysis...
-
作者：de Klerk, Etienne; Pasechnik, Dmitrii V.; Schrijver, Alexander
作者单位：Centrum Wiskunde & Informatica (CWI); University of Amsterdam; Tilburg University
摘要：We consider semidefinite programming problems on which a permutation group is acting. We describe a general technique to reduce the size of such problems, exploiting the symmetry. The technique is based on a low-order matrix *-representation of the commutant (centralizer ring) of the matrix algebra generated by the permutation matrices. We apply it to extending a method of de Klerk et al. that gives a semidefinite programming lower bound to the crossing number of complete bipartite graphs. It ...
-
作者：Yaman, H.; Karasan, O. E.; Pinar, M. C.
作者单位：Ihsan Dogramaci Bilkent University
摘要：For the problem of selecting p items with interval objective function coefficients so as to maximize total profit, we introduce the r-restricted robust deviation criterion and seek solutions that minimize the r-restricted robust deviation. This new criterion increases the modeling power of the robust deviation (minmax regret) criterion by reducing the level of conservatism of the robust solution. It is shown that r-restricted robust deviation solutions can be computed efficiently. Results of e...
-
作者：Nayakkankuppam, Madhu V.
作者单位：Bloomberg L.P.
摘要：We describe an approach to the parallel and distributed solution of large-scale, block structured semidefinite programs using the spectral bundle method. Various elements of this approach (such as data distribution, an implicitly restarted Lanczos method tailored to handle block diagonal structure, a mixed polyhedral-semidefinite subdifferential model, and other aspects related to parallelism) are combined in an implementation called LAMBDA, which delivers faster solution times than previously...
-
作者：Laurent, Monique
摘要：We consider the problem of minimizing a polynomial over a set defined by polynomial equations and inequalities. When the polynomial equations have a finite set of complex solutions, we can reformulate this problem as a semidefinite programming problem. Our semidefinite representation involves combinatorial moment matrices, which are matrices indexed by a basis of the quotient vector space R[x(1), . . . ,x(n) ]/I, where I is the ideal generated by the polynomial equations in the problem. Moreov...
-
作者：Fukuda, Mituhiro; Braams, Bastiaan J.; Nakata, Maho; Overton, Michael L.; Percus, Jerome K.; Yamashita, Makoto; Zhao, Zhengji
作者单位：Institute of Science Tokyo; Tokyo Institute of Technology; Emory University; University of Tokyo; New York University
摘要：It has been a long-time dream in electronic structure theory in physical chemistry/chemical physics to compute ground state energies of atomic and molecular systems by employing a variational approach in which the two-body reduced density matrix (RDM) is the unknown variable. Realization of the RDM approach has benefited greatly from recent developments in semidefinite programming (SDP). We present the actual state of this new application of SDP as well as the formulation of these SDPs, which ...
