An improved semidefinite programming relaxation for the satisfiability problem

The satisfiability (SAT) problem is a central problem in mathematical logic, computing theory, and artificial intelligence. An instance of SAT is specified by a set of boolean variables and a propositional formula in conjunctive normal form. Given such an instance, the SAT problem asks whether there is a truth assignment to the variables such that the formula is satisfied. It is well known that SAT is in general NP-complete, although several important special cases can be solved in polynomial time. Semidefinite programming (SDP) refers to the class of optimization problems where a linear function of a matrix variable X is maximized (or minimized) subject to linear constraints on the elements of X and the additional constraint that X be positive semidefinite. We are interested in the application of SDP to satisfiability problems, and in particular in how SDP can be used to detect unsatisfiability. In this paper we introduce a new SDP relaxation for the satisfiability problem. This SDP relaxation arises from the recently introduced paradigm of higher liftings for constructing semidefinite programming relaxations of discrete optimization problems. To derive the SDP relaxation, we first formulate SAT as an optimization problem involving matrices. Relaxing this formulation yields an SDP which significantly improves on the previous relaxations in the literature. The important characteristics of the SDP relaxation are its ability to prove that a given SAT formula is unsatisfiable independently of the lengths of the clauses in the formula, its potential to yield truth assignments satisfying the SAT instance if a feasible matrix of sufficiently low rank is computed, and the fact that it is more amenable to practical computation than previous SDPs arising from higher liftings. We present theoretical and computational results that support these claims.Mathematics Subject Classification (2000): 20E28, 20G40, 20C20     

On semidefinite programming relaxations of maximum k-section

We derive a new semidefinite programming bound for the maximum $k$ -section problem. For $k=2$ (i.e. for maximum bisection), the new bound is at least as strong as a well-known bound by Poljak and Rendl (SIAM J Optim 5(3):467?C487, 1995). For $k \ge 3$ the new bound dominates a bound of Karisch and Rendl (Topics in semidefinite and interior-point methods, 1998). The new bound is derived from a recent semidefinite programming bound by De Klerk and Sotirov for the more general quadratic assignment problem, but only requires the solution of a much smaller semidefinite program.     

Donsker-type theorems for nonparametric maximum likelihood estimators

Let ${\mathcal{P}}$ be a nonparametric probability model consisting of smooth probability densities and let ${\hat{p}_{n}}$ be the corresponding maximum likelihood estimator based on n independent observations each distributed according to the law ${\mathbb{P}}$ . With $\hat{\mathbb{P}}_{n}$ denoting the measure induced by the density ${\hat{p}_{n}}$ , define the stochastic process ${\hat{\nu}}_{n}: f\longmapsto \sqrt{n} \int fd({\hat{\mathbb{P}}}_{n} -\mathbb{P})$ where f ranges over some function class ${\mathcal{F}}$ . We give a general condition for Donsker classes ${\mathcal{F}}$ implying that the stochastic process $\hat{\nu}_{n}$ is asymptotically equivalent to the empirical process in the space ${\ell ^{\infty }(\mathcal{F})}$ of bounded functions on ${ \mathcal{F}}$ . This implies in particular that $\hat{\nu}_{n}$ converges in law in ${\ell ^{\infty }(\mathcal{F})}$ to a mean zero Gaussian process. We verify the general condition for a large family of Donsker classes ${\mathcal{ F}}$ . We give a number of applications: convergence of the probability measure ${\hat{\mathbb{P}}_{n}}$ to ${\mathbb{P}}$ at rate ${\sqrt{n}}$ in certain metrics metrizing the topology of weak(-star) convergence; a unified treatment of convergence rates of the MLE in a continuous scale of Sobolev-norms; ${\sqrt{n}}$ -efficient estimation of nonlinear functionals defined on ${\mathcal{P}}$ ; limit theorems at rate ${\sqrt{n}}$ for the maximum likelihood estimator of the convolution product ${\mathbb{P\ast P}}$ .     

Monotone maximum likelihood estimate for hazard function

A wide class of reliability theory models or lifetime data can be described as follows. Assume that the lifetime distribution function is F(t, θ)=F₀(λ(θ)t), where θ is the parameter characterizing some inner properties of a product and λ(θ) is an unknown increasing function. The paper deals with methods of estimation of λ(θ) from the sample (t _i ,θ _i ),i = 1, ...,n, for the case of exponentialF ₀. Translated fromStatisticheskie Metody Otsenivaniya i Proverki Gipotez, pp. 46–51, Perm, 1991.     

Finding maximum likelihood estimators for the three-parameter Weibull distribution

Much work has been devoted to the problem of finding maximum likelihood estimators for the three-parameter Weibull distribution. This problem has not been clearly recognized as a global optimization one and most methods from the literature occasionally fail to find a global optimum. We develop a global optimization algorithm which uses first order conditions and projection to reduce the problem to a univariate optimization one. Bounds on the resulting function and its first order derivative are obtained and used in a branch-and-bound scheme. Computational experience is reported. It is also shown that the solution method we propose can be extended to the case of right censored samples.     

A recipe for semidefinite relaxation for (0,1)-quadratic programming

We review various relaxations of (0,1)-quadratic programming problems. These include semidefinite programs, parametric trust region problems and concave quadratic maximization. All relaxations that we consider lead to efficiently solvable problems. The main contributions of the paper are the following. Using Lagrangian duality, we prove equivalence of the relaxations in a unified and simple way. Some of these equivalences have been known previously, but our approach leads to short and transparent proofs. Moreover we extend the approach to the case of equality constrained problems by taking the squared linear constraints into the objective function. We show how this technique can be applied to the Quadratic Assignment Problem, the Graph Partition Problem and the Max-Clique Problem. Finally we show our relaxation to be best possible among all quadratic majorants with zero trace.The research was partially supported by GAR 201/93/0519.Research support by Christian Doppler Laboratorium für Diskrete Optimierung.Research support by the National Science and Engineering Research Council Canada.     

A matrix formula for the skewness of maximum likelihood estimators

We give a general matrix formula for computing the second-order skewness of maximum likelihood estimators. The formula was firstly presented in a tensorial version by Bowman and Shenton (1998). Our matrix formulation has numerical advantages, since it requires only simple operations on matrices and vectors. We apply the second-order skewness formula to a normal model with a generalized parametrization and to an ARMA model.     

On the maximum likelihood estimator for the Generalized Extreme-Value distribution

The vanilla method in univariate extreme-value theory consists of fitting the three-parameter Generalized Extreme-Value (GEV) distribution to a sample of block maxima. Despite claims to the contrary, the asymptotic normality of the maximum likelihood estimator has never been established. In this paper, a formal proof is given using a general result on the maximum likelihood estimator for parametric families that are differentiable in quadratic mean but whose supports depend on the parameter. An interesting side result concerns the (lack of) differentiability in quadratic mean of the GEV family.     

An improved rounding method and semidefinite programming relaxation for graph partition

Given an undirected graph G=(V,E) with |V|=n and an integer k between 0 and n, the maximization graph partition (MAX-GP) problem is to determine a subset S⊂V of k nodes such that an objective function w(S) is maximized. The MAX-GP problem can be formulated as a binary quadratic program and it is NP-hard. Semidefinite programming (SDP) relaxations of such quadratic programs have been used to design approximation algorithms with guaranteed performance ratios for various MAX-GP problems. Based on several earlier results, we present an improved rounding method using an SDP relaxation, and establish improved approximation ratios for several MAX-GP problems, including Dense-Subgraph, Max-Cut, Max-Not-Cut, and Max-Vertex-Cover. Received: March 10, 2000 / Accepted: July 13, 2001?Published online February 14, 2002     

Local polynomial maximum likelihood estimation for Pareto-type distributions

We discuss the estimation of the tail index of a heavy-tailed distribution when covariate information is available. The approach followed here is based on the technique of local polynomial maximum likelihood estimation. The generalized Pareto distribution is fitted locally to exceedances over a high specified threshold. The method provides nonparametric estimates of the parameter functions and their derivatives up to the degree of the chosen polynomial. Consistency and asymptotic normality of the proposed estimators will be proven under suitable regularity conditions. This approach is motivated by the fact that in some applications the threshold should be allowed to change with the covariates due to significant effects on scale and location of the conditional distributions. Using the asymptotic results we are able to derive an expression for the asymptotic mean squared error, which can be used to guide the selection of the bandwidth and the threshold. The applicability of the method will be demonstrated with a few practical examples.     

Limit theorems for maximum likelihood estimators in the Curie-Weiss-Potts model

The Curie-Weiss-Potts model, a model in statistical mechanics, is parametrized by the inverse temperature β and the external magnetic field h. This paper studies the asymptotic behavior of the maximum likelihood estimator of the parameter β when h = 0 and the asymptotic behavior of the maximum likelihood estimator of the parameter h when β is known and the true value of h is 0. The limits of these maximum likelihood estimators reflect the phase transition in the model; i.e., different limits depending on whether β < β_c, β = β_c or β > β_c, where β_c ε (0, ∞) is the critical inverse temperature of the model.     

极大似然估计算法研究

将解一元方程的二分法推广至求解多元非线性方程组.以第K个变元Xk为参数,则κ元方程组就可以看作曲线s(前κ-1个方程)和κ-1维曲面C(第κ个方程),于是κ元方程组的解就可以看作寻找曲线s和曲面C的交点.对参数Xk作二分法,重复迭代,直到找到满足误差要求的方程组的解.最后给出了用多元二分法的算法求解极大似然估计的数值解.     

On the consistency of conditional maximum likelihood estimators

Let {P _, : , H} be a family of probability measures admitting a sufficient statistic for the nuisance parameter . The paper presents conditions for consistency of (asymptotic) conditional maximum likelihood estimators for . An application to the Rasch-model (a stochastic model for psychological tests) yields a condition on the sequence of nuisance parameters which is sufficient for strong consistency of conditional maximum likelihood estimators, and necessary for the existence of any weakly consistent estimator-sequence.