Optimum designs for clinical trials in personalized medicine when response variance depends on treatment.

We study optimal designs for clinical trials when the value of the response and its variance depend on treatment and covariates are included in the response model. Such designs are generalizations of Neyman allocation, commonly used in personalized medicine when external factors may have differing effects on the response depending on subgroups of patients. We develop theoretical results for D-, A-, E- and D A-optimal designs and construct semidefinite programming (SDP) formulations that support their numerical computation. D-, A-, and E-optimal designs are appropriate for efficient estimation of distinct properties of the parameters of the response models. Our formulation allows finding optimal allocation schemes for a general number of treatments and of covariates. Finally, we study frequentist sequential clinical trial allocation within contexts where response parameters and their respective variances remain unknown. We illustrate, with a simulated example and with a redesigned clinical trial on the treatment of neuro-degenerative disease, that both theoretical and SDP results, derived under the assumption of known variances, converge asymptotically to allocations obtained through the sequential scheme. Procedures to use static and sequential allocation are proposed.

Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs.

We consider both facial reduction, FR, and symmetry reduction, SR, techniques for semidefinite programming, SDP. We show that the two together fit surprisingly well in an alternating direction method of multipliers, ADMM, approach. In fact, this approach allows for simply adding on nonnegativity constraints, and solving the doubly nonnegative, DNN , relaxation of many classes of hard combinatorial problems. We also show that the singularity degree remains the same after SR, and that the DNN relaxations considered here have singularity degree one, that is reduced to zero after FR. The combination of FR and SR leads to a significant improvement in both numerical stability and running time for both the ADMM and interior point approaches. We test our method on various DNN relaxations of hard combinatorial problems including quadratic assignment problems with sizes of more than n=500. This translates to a semidefinite constraint of order 250, 000 and 625×108 nonnegative constrained variables, before applying the reduction techniques.

Square Root Convexity of Fisher Information along Heat Flow in Dimension Two.

Recently, Ledoux, Nair, and Wang proved that the Fisher information along the heat flow is log-convex in dimension one, that is d2dt2log(I(Xt))≥0 for n=1, where Xt is a random variable with density function satisfying the heat equation. In this paper, we consider the high dimensional case and prove that the Fisher information is square root convex in dimension two, that is d2dt2IX≥0 for n=2. The proof is based on the semidefinite programming approach.

The background method: theory and computations.

The background method is a widely used technique to bound mean properties of turbulent flows rigorously. This work reviews recent advances in the theoretical formulation and numerical implementation of the method. First, we describe how the background method can be formulated systematically within a broader 'auxiliary function' framework for bounding mean quantities, and explain how symmetries of the flow and constraints such as maximum principles can be exploited. All ideas are presented in a general setting and are illustrated on Rayleigh-Bénard convection between stress-free isothermal plates. Second, we review a semidefinite programming approach and a timestepping approach to optimizing bounds computationally, revealing that they are related to each other through convex duality and low-rank matrix factorization. Open questions and promising directions for further numerical analysis of the background method are also outlined. This article is part of the theme issue 'Mathematical problems in physical fluid dynamics (part 1)'.

A smoothing gradient-based neural network strategy for solving semidefinite programming problems.

Linear semidefinite programming problems have received a lot of attentions because of large variety of applications. This paper deals with a smooth gradient neural network scheme for solving semidefinite programming problems. According to some properties of convex analysis and using a merit function in matrix form, a neural network model is constructed. It is shown that the proposed neural network is asymptotically stable and converges to an exact optimal solution of the semidefinite programming problem. Numerical simulations are given to show that the numerical behaviours are in good agreement with the theoretical results.

Noisy tensor completion via the sum-of-squares hierarchy.

In the noisy tensor completion problem we observe m entries (whose location is chosen uniformly at random) from an unknown n 1 × n 2 × n 3 tensor T. We assume that T is entry-wise close to being rank r. Our goal is to fill in its missing entries using as few observations as possible. Let n = max ( n 1 , n 2 , n 3 ) . We show that if m ≳ n 3 / 2 r then there is a polynomial time algorithm based on the sixth level of the sum-of-squares hierarchy for completing it. Our estimate agrees with almost all of T's entries almost exactly and works even when our observations are corrupted by noise. This is also the first algorithm for tensor completion that works in the overcomplete case when r > n , and in fact it works all the way up to r = n 3 / 2 - ϵ . Our proofs are short and simple and are based on establishing a new connection between noisy tensor completion (through the language of Rademacher complexity) and the task of refuting random constraint satisfaction problems. This connection seems to have gone unnoticed even in the context of matrix completion. Furthermore, we use this connection to show matching lower bounds. Our main technical result is in characterizing the Rademacher complexity of the sequence of norms that arise in the sum-of-squares relaxations to the tensor nuclear norm. These results point to an interesting new direction: Can we explore computational vs. sample complexity tradeoffs through the sum-of-squares hierarchy?

Complete positivity and distance-avoiding sets.

We introduce the cone of completely positive functions, a subset of the cone of positive-type functions, and use it to fully characterize maximum-density distance-avoiding sets as the optimal solutions of a convex optimization problem. As a consequence of this characterization, it is possible to reprove and improve many results concerning distance-avoiding sets on the sphere and in Euclidean space.

Joint Design of Colocated MIMO Radar Constant Envelope Waveform and Receive Filter to Reduce SINR Loss.

In this paper, we aim at the problem that MIMO radar's target detection performance is greatly reduced in the complex multi-signal-dependent interferences environment. We propose a joint design method based on semidefinite relaxation (SDR), fractional programming and randomization technique (JD-SFR) and a joint design method based on coordinate descent (JD-CD) to solve the actual transmit waveform and receive filter bank directly to reduce the loss of strong interference to the output signal-to-interference-plus-noise ratio (SINR) of the radar system. Therefore, the maximization of output SINR is taken as the criterion of the optimization problem. The designed waveforms take into account the radar transmitter's hardware requirements for constant envelope waveforms and impose similarity constraints on the waveforms. JD-SFR uses SDR, fractional programming and randomization technique to deal with the non-convex optimization problems encountered in the solution process. JD-CD transforms the optimization problem into a function of the phase of the waveform and then solves the transmit waveform based on CD. Compared with other methods, the proposed method has lower output SINR loss under strong power interference and forms deep nulls on the direction beampattern of multiple interference sources, which indicates that it has better anti-interference performance.

Habitat amount and connectivity in forest planning models: Consequences for profitability and compensation schemes.

Adjacency relationships are pervasive in forest planning problems, especially the ones related to the selection of habitat networks for biodiversity conservation. Two main approaches are applied in the planning of these conservation actions: i) selection grounded on the island biogeography theory, where connected habitats are preferred and ii) selection grounded in the habitat amount hypothesis, where the amount of habitat is enforced in local landscapes, regardless of their spatial distribution. Because the presence of connectivity requirements in the creation of habitat networks impose more stringent limitations on the search for optimal solutions, they are expected to cascade to the total benefit from harvesting revenues and, consequently, to the costs of the habitat networks. The ecological implications of these approaches have been investigated, whereas the economic consequences of imposing connectivity remain unclear. Here, I address this issue and investigate the costs of selecting habitat networks in multiple forest landscapes in central Europe, applying these two approaches. To this end, a conic optimization model is proposed, to find minimum cost allocations of forest reserves. Furthermore, a sensitivity analysis on the optimal allocation is conducted, regarding the size of the habitat network required and the level of heterogeneity in forest profitability within the landscapes. The results show that habitat networks amounting to 10% of the forest area may be created with up to 5.5% reduction in the total Net Present Value (NPV), with a higher cost when connectivity is imposed (6.5%). The cost of connectivity, however, may increase in landscapes with high heterogeneity in forest profitability and with the minimum amount of habitat required. In conclusion, habitat selection must be tailored to local conditions and weight the additional costs of imposing connectivity against the requirements of the target species and the expected ecological benefits.

Enforcing necessary non-negativity constraints for common diffusion MRI models using sum of squares programming.

In this work we investigate the use of sum of squares constraints for various diffusion-weighted MRI models, with a goal of enforcing strict, global non-negativity of the diffusion propagator. We formulate such constraints for the mean apparent propagator model and for spherical deconvolution, guaranteeing strict non-negativity of the corresponding diffusion propagators. For the cumulant expansion similar constraints cannot exist, and we instead derive a set of auxiliary constraints that are necessary but not sufficient to guarantee non-negativity. These constraints can all be verified and enforced at reasonable computational costs using semidefinite programming. By verifying our constraints on standard reconstructions of the different models, we show that currently used weak constraints are largely ineffective at ensuring non-negativity. We further show that if strict non-negativity is not enforced then estimated model parameters may suffer from significant errors, leading to serious inaccuracies in important derived quantities such as the main fiber orientations, mean kurtosis, etc. Finally, our experiments confirm that the observed constraint violations are mostly due to measurement noise, which is difficult to mitigate and suggests that properly constrained optimization should currently be considered the norm in many cases.

Low Complexity Beamspace Super Resolution for DOA Estimation of Linear Array.

Beamspace processing has become much attractive in recent radar and wireless communication applications, since the advantages of complexity reduction and of performance improvements in array signal processing. In this paper, we concentrate on the beamspace DOA estimation of linear array via atomic norm minimization (ANM). The existed generalized linear spectrum estimation based ANM approaches suffer from the high computational complexity for large scale array, since their complexity depends upon the number of sensors. To deal with this problem, we develop a low dimensional semidefinite programming (SDP) implementation of beamspace atomic norm minimization (BS-ANM) approach for DFT beamspace based on the super resolution theory on the semi-algebraic set. Then, a computational efficient iteration algorithm is proposed based on alternating direction method of multipliers (ADMM) approach. We develop the covariance based DOA estimation methods via BS-ANM and apply the BS-ANM based DOA estimation method to the channel estimation problem for massive MIMO systems. Simulation results demonstrate that the proposed methods exhibit the superior performance compared to the state-of-the-art counterparts.

An Efficient NLOS Errors Mitigation Algorithm for TOA-Based Localization.

In time-of-arrival (TOA) localization systems, errors caused by non-line-of-sight (NLOS) signal propagation could significantly degrade the location accuracy. Existing works on NLOS error mitigation commonly assume that NLOS error statistics or the TOA measurement noise variances are known. Such information is generally unavailable in practice. The goal of this paper is to develop an NLOS error mitigation scheme without requiring such information. The core of the proposed algorithm is a constrained least-squares optimization, which is converted into a semidefinite programming (SDP) problem that can be easily solved by using the CVX toolbox. This scheme is then extended for cooperative source localization. Additionally, its performance is better than existing schemes for most of the scenarios, which will be validated via extensive simulation.

A computational study of exact subgraph based SDP bounds for Max-Cut, stable set and coloring.

The "exact subgraph" approach was recently introduced as a hierarchical scheme to get increasingly tight semidefinite programming relaxations of several NP-hard graph optimization problems. Solving these relaxations is a computational challenge because of the potentially large number of violated subgraph constraints. We introduce a computational framework for these relaxations designed to cope with these difficulties. We suggest a partial Lagrangian dual, and exploit the fact that its evaluation decomposes into several independent subproblems. This opens the way to use the bundle method from non-smooth optimization to minimize the dual function. Finally computational experiments on the Max-Cut, stable set and coloring problem show the excellent quality of the bounds obtained with this approach.

Hedging crash risk in optimal portfolio selection.

When almost all underlying assets suddenly lose a certain part of their nominal value in a market crash, the diversification effect of portfolios in a normal market condition no longer works. We integrate the crash risk into portfolio management and investigate performance measures, hedging and optimization of portfolio selection involving derivatives. A suitable convex conic programming framework based on parametric approximation method is proposed to make the problem a tractable one. Simulation analysis and empirical study are performed to test the proposed approach.

Phase transitions in semidefinite relaxations.

Statistical inference problems arising within signal processing, data mining, and machine learning naturally give rise to hard combinatorial optimization problems. These problems become intractable when the dimensionality of the data is large, as is often the case for modern datasets. A popular idea is to construct convex relaxations of these combinatorial problems, which can be solved efficiently for large-scale datasets. Semidefinite programming (SDP) relaxations are among the most powerful methods in this family and are surprisingly well suited for a broad range of problems where data take the form of matrices or graphs. It has been observed several times that when the statistical noise is small enough, SDP relaxations correctly detect the underlying combinatorial structures. In this paper we develop asymptotic predictions for several detection thresholds, as well as for the estimation error above these thresholds. We study some classical SDP relaxations for statistical problems motivated by graph synchronization and community detection in networks. We map these optimization problems to statistical mechanics models with vector spins and use nonrigorous techniques from statistical mechanics to characterize the corresponding phase transitions. Our results clarify the effectiveness of SDP relaxations in solving high-dimensional statistical problems.

A Monotone Path Proof of an Extremal Result for Long Markov Chains.

We prove an extremal result for long Markov chains based on the monotone path argument, generalizing an earlier work by Courtade and Jiao.

Uniqueness of codes using semidefinite programming.

For  n , d , w ∈ N , let A(n, d, w) denote the maximum size of a binary code of word length n, minimum distance d and constant weight w. Schrijver recently showed using semidefinite programming that A ( 23 , 8 , 11 ) = 1288 , and the second author that  A ( 22 , 8 , 11 ) = 672 and  A ( 22 , 8 , 10 ) = 616 . Here we show uniqueness of the codes achieving these bounds. Let A(n, d) denote the maximum size of a binary code of word length n and minimum distance d. Gijswijt et al. showed that  A ( 20 , 8 ) = 256 . We show that there are several nonisomorphic codes achieving this bound, and classify all such codes with all distances divisible by 4.

Efficient Convex Optimization for Energy-Based Acoustic Sensor Self-Localization and Source Localization in Sensor Networks.

The energy reading has been an efficient and attractive measure for collaborative acoustic source localization in practical application due to its cost saving in both energy and computation capability. The maximum likelihood problems by fusing received acoustic energy readings transmitted from local sensors are derived. Aiming to efficiently solve the nonconvex objective of the optimization problem, we present an approximate estimator of the original problem. Then, a direct norm relaxation and semidefinite relaxation, respectively, are utilized to derive the second-order cone programming, semidefinite programming or mixture of them for both cases of sensor self-location and source localization. Furthermore, by taking the colored energy reading noise into account, several minimax optimization problems are formulated, which are also relaxed via the direct norm relaxation and semidefinite relaxation respectively into convex optimization problems. Performance comparison with the existing acoustic energy-based source localization methods is given, where the results show the validity of our proposed methods.

Integrating NOE and RDC using sum-of-squares relaxation for protein structure determination.

We revisit the problem of protein structure determination from geometrical restraints from NMR, using convex optimization. It is well-known that the NP-hard distance geometry problem of determining atomic positions from pairwise distance restraints can be relaxed into a convex semidefinite program (SDP). However, often the NOE distance restraints are too imprecise and sparse for accurate structure determination. Residual dipolar coupling (RDC) measurements provide additional geometric information on the angles between atom-pair directions and axes of the principal-axis-frame. The optimization problem involving RDC is highly non-convex and requires a good initialization even within the simulated annealing framework. In this paper, we model the protein backbone as an articulated structure composed of rigid units. Determining the rotation of each rigid unit gives the full protein structure. We propose solving the non-convex optimization problems using the sum-of-squares (SOS) hierarchy, a hierarchy of convex relaxations with increasing complexity and approximation power. Unlike classical global optimization approaches, SOS optimization returns a certificate of optimality if the global optimum is found. Based on the SOS method, we proposed two algorithms-RDC-SOS and RDC-NOE-SOS, that have polynomial time complexity in the number of amino-acid residues and run efficiently on a standard desktop. In many instances, the proposed methods exactly recover the solution to the original non-convex optimization problem. To the best of our knowledge this is the first time SOS relaxation is introduced to solve non-convex optimization problems in structural biology. We further introduce a statistical tool, the Cramér-Rao bound (CRB), to provide an information theoretic bound on the highest resolution one can hope to achieve when determining protein structure from noisy measurements using any unbiased estimator. Our simulation results show that when the RDC measurements are corrupted by Gaussian noise of realistic variance, both SOS based algorithms attain the CRB. We successfully apply our method in a divide-and-conquer fashion to determine the structure of ubiquitin from experimental NOE and RDC measurements obtained in two alignment media, achieving more accurate and faster reconstructions compared to the current state of the art.

Semidefinite bounds for nonbinary codes based on quadruples.

For nonnegative integers q, n, d, let A q ( n , d ) denote the maximum cardinality of a code of length n over an alphabet [q] with q letters and with minimum distance at least d. We consider the following upper bound on A q ( n , d ) . For any k, let C k be the collection of codes of cardinality at most k. Then A q ( n , d ) is at most the maximum value of ∑ v ∈ [ q ] n x ( { v } ) , where x is a function C 4 → R + such that x ( ∅ ) = 1 and x ( C ) = 0 if C has minimum distance less than d, and such that the C 2 × C 2 matrix ( x ( C ∪ C ' ) ) C , C ' ∈ C 2 is positive semidefinite. By the symmetry of the problem, we can apply representation theory to reduce the problem to a semidefinite programming problem with order bounded by a polynomial in n. It yields the new upper bounds A 4 ( 6 , 3 ) ≤ 176 , A 4 ( 7 , 3 ) ≤ 596 , A 4 ( 7 , 4 ) ≤ 155 , A 5 ( 7 , 4 ) ≤ 489 , and A 5 ( 7 , 5 ) ≤ 87 .