Computing A-optimal and E-optimal designs for regression models via semidefinite programming

In semidefinite programming (SDP), we minimize a linear objective function subject to a linear matrix being positive semidefinite. A powerful program, SeDuMi, has been developed in MATLAB to solve SDP problems. In this article, we show in detail how to formulate A-optimal and E-optimal design problems as SDP problems and solve them by SeDuMi. This technique can be used to construct approximate A-optimal and E-optimal designs for all linear and nonlinear regression models with discrete design spaces. In addition, the results on discrete design spaces provide useful guidance for finding optimal designs on any continuous design space, and a convergence result is derived. Moreover, restrictions in the designs can be easily incorporated in the SDP problems and solved by SeDuMi. Several representative examples and one MATLAB program are given.     

Semidefinite Programming Relaxations for the Quadratic Assignment Problem

Semidefinite programming (SDP) relaxations for the quadratic assignment problem (QAP) are derived using the dual of the (homogenized) Lagrangian dual of appropriate equivalent representations of QAP. These relaxations result in the interesting, special, case where only the dual problem of the SDP relaxation has strict interior, i.e., the Slater constraint qualification always fails for the primal problem. Although there is no duality gap in theory, this indicates that the relaxation cannot be solved in a numerically stable way. By exploring the geometrical structure of the relaxation, we are able to find projected SDP relaxations. These new relaxations, and their duals, satisfy the Slater constraint qualification, and so can be solved numerically using primal-dual interior-point methods.For one of our models, a preconditioned conjugate gradient method is used for solving the large linear systems which arise when finding the Newton direction. The preconditioner is found by exploiting the special structure of the relaxation. See e.g., Vandenverghe and Boyd (1995) for a similar approach for solving SDP problems arising from control applications.Numerical results are presented which indicate that the described methods yield at least competitive lower bounds.     

A semidefinite programming study of the Elfving theorem

The theorem of Elfving is one of the most important and earliest results which have led to the theory of optimal design of experiments. This paper presents a fresh study of it from the viewpoint of modern semidefinite programming. There is one-to-one correspondence between solutions of the derived semidefinite programming problem (SDP) and c-optimal designs. We also derive a uniqueness theorem which ensures a unique optimal design without assuming the linear independence property over the largest set of supporting points. The SDP can also be cast as an ?₁‐convex program which has recently been extensively studied and often yields sparse solutions. Our numerical experiments on the trigonometric regression model confirm that the SDP does produce a sparse optimal design.     

Novel Approaches for Analyzing Biological Networks

This paper proposes clique relaxations to identify clusters in biological networks. In particular, the maximum n-clique and maximum n-club problems on an arbitrary graph are introduced and their recognition versions are shown to be NP-complete. In addition, integer programming formulations are proposed and the results of sample numerical experiments performed on biological networks are reported.     

SDP vs. LP Relaxations for the Moment Approach in Some Performance Evaluation Problems

Abstract

Given a Markov process, we are interested in the numerical computation of the moments of the exit time from a bounded domain. We use a moment approach which, together with appropriate semidefinite positivity moment conditions, yields a sequence of semidefinite programs (or SDP relaxations), depending on the number of moments considered, that provide a sequence of nonincreasing (resp. nondecreasing) upper (resp. lower) bounds. The results are compared to the linear Hausdorff moment conditions approach considered for the LP relaxations in Helmes et al. [Helmes, K., Röhl, S., Stockbridge, R.H. Computing moments of the exit time distribution for Markov processes by linear programming. Oper. Res. 2001, 49, 516–530]. The SDP relaxations are shown to be more general and more precise than the LP relaxations.     

Detecting large cohesive subgroups with high clustering coefficients in social networks

Clique relaxations are used in classical models of cohesive subgroups in social network analysis. Clustering coefficient was introduced more recently as a structural feature characterizing small-world networks. Noting that cohesive subgroups tend to have high clustering coefficients, this paper introduces a new clique relaxation, α-cluster, defined by enforcing a lower bound α on the clustering coefficient in the corresponding induced subgraph. Two variations of the clustering coefficient are considered, namely, the local and global clustering coefficient. Certain structural properties of α-clusters are analyzed and mathematical optimization models for determining α-clusters of the largest size in a network are developed and validated using several real-life social networks. In addition, a network clustering algorithm based on local α-clusters is proposed and successfully tested.     

A Semidefinite Programming Approach to the Quadratic Knapsack Problem

In order to gain insight into the quality of semidefinite relaxations of constrained quadratic 0/1 programming problems we study the quadratic knapsack problem. We investigate several basic semidefinite relaxations of this problem and compare their strength in theory and in practice. Various possibilities to improve these basic relaxations by cutting planes are discussed. The cutting planes either arise from quadratic representations of linear inequalities or from linear inequalities in the quadratic model. In particular, a large family of combinatorial cuts is introduced for the linear formulation of the knapsack problem in quadratic space. Computational results on a small class of practical problems illustrate the quality of these relaxations and cutting planes.     

Improved Bounds on Relaxations of a Parallel Machine Scheduling Problem

We consider the problem of scheduling n jobs withrelease dates on m identical parallel machines to minimize the average completion time of the jobs. We prove that the ratio of the average completion time of the optimal nonpreemptive schedule to that of the optimal preemptive schedule is at most 7/3, improving a bound of Shmoys and Wein.