Strengthened semidefinite programming bounds for codes

We give a hierarchy of semidefinite upper bounds for the maximum size A(n,d) of a binary code of word length n and minimum distance at least d. At any fixed stage in the hierarchy, the bound can be computed (to an arbitrary precision) in time polynomial in n; this is based on a result of de Klerk et al. (Math Program, 2006) about the regular ∗-representation for matrix ∗-algebras. The Delsarte bound for A(n,d) is the first bound in the hierarchy, and the new bound of Schrijver (IEEE Trans. Inform. Theory 51:2859–2866, 2005) is located between the first and second bounds in the hierarchy. While computing the second bound involves a semidefinite program with O(n ⁷) variables and thus seems out of reach for interesting values of n, Schrijver’s bound can be computed via a semidefinite program of size O(n ³), a result which uses the explicit block-diagonalization of the Terwilliger algebra. We propose two strengthenings of Schrijver’s bound with the same computational complexity. Supported by the Netherlands Organisation for Scientific Research grant NWO 639.032.203.     

New upper bounds for nonbinary codes based on the Terwilliger algebra and semidefinite programming

We give a new upper bound on the maximum size Aq(n,d) of a code of word length n and minimum Hamming distance at least d over the alphabet of q?3 letters. By block-diagonalizing the Terwilliger algebra of the nonbinary Hamming scheme, the bound can be calculated in time polynomial in n using semidefinite programming. For q=3,4,5 this gives several improved upper bounds for concrete values of n and d. This work builds upon previous results of Schrijver [A. Schrijver, New code upper bounds from the Terwilliger algebra and semidefinite programming, IEEE Trans. Inform. Theory 51 (2005) 2859-2866] on the Terwilliger algebra of the binary Hamming scheme.     

Limiting behavior of weighted central paths in linear programming

We study the limiting behavior of the weighted central paths{(x(), s())} > 0 in linear programming at both = 0 and = . We establish the existence of a partition (B ,N ) of the index set { 1, ,n } such thatx _i() ands _j () as fori B , andj N , andx _N (),s _B () converge to weighted analytic centers of certain polytopes. For allk 1, we show that thekth order derivativesx ^(k) () ands ^(k) () converge when 0 and . Consequently, the derivatives of each order are bounded in the interval (0, ). We calculate the limiting derivatives explicitly, and establish the surprising result that all higher order derivatives (k 2) converge to zero when .     

Stochastic semidefinite programming: a new paradigm for stochastic optimization

Semidefinite programs are a class of optimization problems that have been studied extensively during the past 15 years. Semidefinite programs are naturally related to linear programs, and both are defined using deterministic data. Stochastic programs were introduced in the 1950s as a paradigm for dealing with uncertainty in data defining linear programs. In this paper, we introduce stochastic semidefinite programs as a paradigm for dealing with uncertainty in data defining semidefinite programs.The work of this author was supported in part by the U.S. Army Research Office under Grant DAAD 19-00-1-0465. The material in this paper is part of the doctoral dissertation of this author in preparation at Washington State University.     

Block-diagonal semidefinite programming hierarchies for 0/1 programming

Lovász and Schrijver, and later Lasserre, proposed hierarchies of semidefinite programming relaxations for 0/1 linear programming problems. We revisit these two constructions and propose two new, block-diagonal hierarchies, which are at least as strong as the Lovász-Schrijver hierarchy, but less costly to compute. We report experimental results for the stable set problem of Paley graphs.     

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     

Exploiting sparsity in primal-dual interior-point methods for semidefinite programming

The Helmberg-Rendl-Vanderbei-Wolkowicz/Kojima-Shindoh-Hara/Monteiro and Nesterov-Todd search directions have been used in many primal-dual interior-point methods for semidefinite programs. This paper proposes an efficient method for computing the two directions when the semidefinite program to be solved is large scale and sparse.     

A new proof of the strong duality theorem for semidefinite programming

Semidefinite programs are convex optimization problems arising in a wide variety of applications and are the extension of linear programming. Most methods for linear programming have been generalized to semidefinite programs. Just as in linear programming, duality theorem plays a basic and an important role in theory as well as in algorithmics. Based on the discretization method and convergence property, this paper proposes a new proof of the strong duality theorem for semidefinite programming, which is different from other common proofs and is more simple.     

Affine scaling algorithm fails for semidefinite programming

In this paper, we introduce an affine scaling algorithm for semidefinite programming (SDP), and give an example of a semidefinite program such that the affine scaling algorithm converges to a non-optimal point. Both our program and its dual have interior feasible solutions and unique optimal solutions which satisfy strict complementarity, and they are non-degenerate everywhere.     

Sufficient conditions for error bounds and linear regularity in Banach spaces

In this paper, we study error bounds for lower semicontinuous functions defined on Banach space and linear regularity for finitely many closed subset in Banach spaces. By using Clarke＇s subd- ifferentials and Ekeland variational principle, we establish several sufficient conditions ensuring error bounds and linear regularity in Banach spaces.     

A study of mixed discrete bilevel programs using semidefinite and semi-infinite programming

In this paper, we study the bilevel programming problem with discrete polynomial lower level problem. We start by transforming the problem into a bilevel problem comprising a semidefinite program (SDP for short) in the lower level problem. Then, we are able to deduce some conditions of existence of solutions for the original problem. After that, we again change the bilevel problem with SDP in the lower level problem into a semi-infinite program. With the aid of the exchange technique, for simple bilevel programs, an algorithm for computing a global optimal solution is suggested, the convergence is shown, and a numerical example is given.     

A semidefinite programming approach to the generalized problem of moments

We consider the generalized problem of moments (GPM) from a computational point of view and provide a hierarchy of semidefinite programming relaxations whose sequence of optimal values converges to the optimal value of the GPM. We then investigate in detail various examples of applications in optimization, probability, financial economics and optimal control, which all can be viewed as particular instances of the GPM. This work was supported by french ANR-grant NT05-3-41612, and part of it was completed in January 2006 while the author was a member of IMS, the Institute for Mathematical Sciences of NUS (The National University of Singapore).     

Approximation algorithms from inexact solutions to semidefinite programming relaxations of combinatorial optimization problems

Semidefinite relaxations of certain combinatorial optimization problems lead to approximation algorithms with performance guarantees. For large-scale problems, it may not be computationally feasible to solve the semidefinite relaxations to optimality. In this paper, we investigate the effect on the performance guarantees of an approximate solution to the semidefinite relaxation for MaxCut, Max2Sat, and Max3Sat. We show that it is possible to make simple modifications to the approximate solutions and obtain performance guarantees that depend linearly on the most negative eigenvalue of the approximate solution, the size of the problem, and the duality gap. In every case, we recover the original performance guarantees in the limit as the solution approaches the optimal solution to the semidefinite relaxation.     

Stable zero duality gaps in convex programming: Complete dual characterisations with applications to semidefinite programs

The zero duality gap that underpins the duality theory is one of the central ingredients in optimisation. In convex programming, it means that the optimal values of a given convex program and its associated dual program are equal. It allows, in particular, the development of efficient numerical schemes. However, the zero duality gap property does not always hold even for finite-dimensional problems and it frequently fails for problems with non-polyhedral constraints such as the ones in semidefinite programming problems. Over the years, various criteria have been developed ensuring zero duality gaps for convex programming problems. In the present work, we take a broader view of the zero duality gap property by allowing it to hold for each choice of linear perturbation of the objective function of the given problem. Globalising the property in this way permits us to obtain complete geometric dual characterisations of a stable zero duality gap in terms of epigraphs and conjugate functions. For convex semidefinite programs, we establish necessary and sufficient dual conditions for stable zero duality gaps, as well as for a universal zero duality gap in the sense that the zero duality gap property holds for each choice of constraint right-hand side and convex objective function. Zero duality gap results for second-order cone programming problems are also given. Our approach makes use of elegant conjugate analysis and Fenchel's duality.     

On sensitivity of central solutions in semidefinite programming

In this paper we study the properties of the analytic central path of a semidefinite programming problem under perturbation of the right hand side of the constraints, including the limiting behavior when the central optimal solution, namely the analytic center of the optimal set, is approached. Our analysis assumes the primal-dual Slater condition and the strict complementarity condition. Our findings are as follows. First, on the negative side, if we view the central optimal solution as a function of the right hand side of the constraints, then this function is not continuous in general, whereas in the linear programming case this function is known to be Lipschitz continuous. On the positive side, compared with the previous conclusion we obtain a (seemingly) paradoxical result: on the central path any directional derivative with respect to the right hand side of the constraints is bounded, and even converges as the central optimal solution is approached. This phenomenon is possible due to the lack of a uniform bound on the derivatives with respect to the right hand side parameters. All these results are based on the strict complementarity assumption. Concerning this last property we give an example. In that example the set of right hand side parameters for which the strict complementarity condition holds is neither open nor closed. This is remarkable since a similar set for which the primal-dual Slater condition holds is always open. Received: April 2, 1998 / Accepted: January 16, 2001?Published online March 22, 2001     

A note on the existence of the Alizadeh-Haeberly-Overton direction for semidefinite programming

This note establishes a new sufficient condition for the existence and uniqueness of the Alizadeh-Haeberly-Overton direction for semidefinite programming. The work of these authors was based on research supported by the National Science Foundation under grants INT-9600343 and CCR-970048 and the Office of Naval Research under grant N00014-94-1-0340.     

Theory of semidefinite programming for Sensor Network Localization

We analyze the semidefinite programming (SDP) based model and method for the position estimation problem in sensor network localization and other Euclidean distance geometry applications. We use SDP duality and interior-point algorithm theories to prove that the SDP localizes any network or graph that has unique sensor positions to fit given distance measures. Therefore, we show, for the first time, that these networks can be localized in polynomial time. We also give a simple and efficient criterion for checking whether a given instance of the localization problem has a unique realization in using graph rigidity theory. Finally, we introduce a notion called strong localizability and show that the SDP model will identify all strongly localizable sub-networks in the input network. A preliminary version of this paper has appeared in the Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2005.     

An exact duality theory for semidefinite programming and its complexity implications

In this paper, an exact dual is derived for Semidefinite Programming (SDP), for which strong duality properties hold without any regularity assumptions. Its main features are: (i) The new dual is an explicit semidefinite program with polynomially many variables and polynomial size coefficient bitlengths. (ii) If the primal is feasible, then it is bounded if and only if the dual is feasible. (iii) When the primal is feasible and bounded, then its optimum value equals that of the dual, or in other words, there is no duality gap. Further, the dual attains this common optimum value. (iv) It yields a precise theorem of the alternative for semidefinite inequality systems, i.e. a characterization of theinfeasibility of a semidefinite inequality in terms of thefeasibility of another polynomial size semidefinite inequality. The standard duality for linear programming satisfies all of the above features, but no such explicit gap-free dual program of polynomial size was previously known for SDP, without Slater-like conditions being assumed. The dual is then applied to derive certain complexity results for SDP. The decision problem of Semidefinite Feasibility (SDFP), which asks to determine if a given semidefinite inequality system is feasible, is the central problem of interest, he complexity of SDFP is unknown, but we show the following: (i) In the Turing machine model, the membership or nonmembership of SDFP in NP and Co-NP is simultaneous; hence SDFP is not NP-Complete unless NP=Co-NP. (ii) In the real number model of Blum, Shub and Smale, SDFP is in NP∩CoNP.