Solving linear-quadratic conditional Gaussian influence diagrams

This paper considers the problem of solving Bayesian decision problems with a mixture of continuous and discrete variables. We focus on exact evaluation of linear-quadratic conditional Gaussian influence diagrams (LQCG influence diagrams) with additively decomposing utility functions. Based on new and existing representations of probability and utility potentials, we derive a method for solving LQCG influence diagrams based on variable elimination. We show how the computations performed during evaluation of a LQCG influence diagram can be organized in message passing schemes based on Shenoy–Shafer and Lazy propagation. The proposed architectures are the first architectures for efficient exact solution of LQCG influence diagrams exploiting an additively decomposing utility function.     

Stable separation and super-resolution of mixture models

We consider simultaneously identifying the membership and locations of point sources that are convolved with different band-limited point spread functions, from the observation of their superpositions. This problem arises in three-dimensional super-resolution single-molecule imaging, neural spike sorting, multi-user channel identification, among other applications. We propose a novel algorithm, based on convex programming, and establish its near-optimal performance guarantee for exact recovery in the noise-free setting by exploiting the spectral sparsity of the point source models as well as the incoherence between point spread functions. Furthermore, robustness of the recovery algorithm in the presence of bounded noise is also established. Numerical examples are provided to demonstrate the effectiveness of the proposed approach.     

Message‐Passing Algorithms for Synchronization Problems over Compact Groups

Various alignment problems arising in cryo‐electron microscopy, community detection, time synchronization, computer vision, and other fields fall into a common framework of synchronization problems over compact groups such as ℤ/L, U(1), or SO(3). The goal in such problems is to estimate an unknown vector of group elements given noisy relative observations. We present an efficient iterative algorithm to solve a large class of these problems, allowing for any compact group, with measurements on multiple “frequency channels” (Fourier modes, or more generally, irreducible representations of the group). Our algorithm is a highly efficient iterative method following the blueprint of approximate message passing (AMP), which has recently arisen as a central technique for inference problems such as structured low‐rank estimation and compressed sensing. We augment the standard ideas of AMP with ideas from representation theory so that the algorithm can work with distributions over general compact groups. Using standard but nonrigorous methods from statistical physics, we analyze the behavior of our algorithm on a Gaussian noise model, identifying phases where we believe the problem is easy, (computationally) hard, and (statistically) impossible. In particular, such evidence predicts that our algorithm is information‐theoretically optimal in many cases, and that the remaining cases exhibit statistical‐to‐computational gaps. © 2018 Wiley Periodicals, Inc.     

Progressive Decoupling of Linkages in Optimization and Variational Inequalities with Elicitable Convexity or Monotonicity

Algorithms for problem decomposition and splitting in optimization and the solving of variational inequalities have largely depended on assumptions of convexity or monotonicity. Here, a way of “eliciting” convexity or monotonicity is developed which can get around that limitation. It supports a procedure called the progressive decoupling algorithm, which is derived from the proximal point algorithm through passing to a partial inverse, localizing and rescaling. In the optimization setting, elicitability of convexity corresponds to a new and very general kind of second-order sufficient condition for a local minimum. Applications are thereby opened up to problem decomposition and splitting even in nonconvex optimization, moreover with augmented Lagrangians for subproblems assisting in the implementation.

     

Adaptive dynamic cost updating procedure for solving fixed charge network flow problems

We approximate the objective function of the fixed charge network flow problem (FCNF) by a piecewise linear one, and construct a concave piecewise linear network flow problem (CPLNF). A proper choice of parameters in the CPLNF problem guarantees the equivalence between those two problems. We propose a heuristic algorithm for solving the FCNF problem, which requires solving a sequence of CPLNF problems. The algorithm employs the dynamic cost updating procedure (DCUP) to find a solution to the CPLNF problems. Preliminary numerical experiments show the effectiveness of the proposed algorithm. In particular, it provides a better solution than the dynamic slope scaling procedure in less CPU time. Research was partially supported by NSF and Air Force grants.     

Uniform recovery from subgaussian multi-sensor measurements

Parallel acquisition systems are employed successfully in a variety of different sensing applications when a single sensor cannot provide enough measurements for a high-quality reconstruction. In this paper, we consider compressed sensing (CS) for parallel acquisition systems when the individual sensors use subgaussian random sampling. Our main results are a series of uniform recovery guarantees which relate the number of measurements required to the basis in which the solution is sparse and certain characteristics of the multi-sensor system, known as sensor profile matrices. In particular, we derive sufficient conditions for optimal recovery, in the sense that the number of measurements required per sensor decreases linearly with the total number of sensors, and demonstrate explicit examples of multi-sensor systems for which this holds. We establish these results by proving the so-called Asymmetric Restricted Isometry Property (ARIP) for the sensing system and use this to derive both nonuniversal and universal recovery guarantees. Compared to existing work, our results not only lead to better stability and robustness estimates but also provide simpler and sharper constants in the measurement conditions. Finally, we show how the problem of CS with block-diagonal sensing matrices can be viewed as a particular case of our multi-sensor framework. Specializing our results to this setting leads to a recovery guarantee that is at least as good as existing results.     

A family of rules for parameter choice in Tikhonov regularization of ill-posed problems with inexact noise level

We consider Tikhonov regularization of linear ill-posed problems with noisy data. The choice of the regularization parameter by classical rules, such as discrepancy principle, needs exact noise level information: these rules fail in the case of an underestimated noise level and give large error of the regularized solution in the case of very moderate overestimation of the noise level. We propose a general family of parameter choice rules, which includes many known rules and guarantees convergence of approximations. Quasi-optimality is proved for a sub-family of rules. Many rules from this family work well also in the case of many times under- or overestimated noise level. In the case of exact or overestimated noise level we propose to take the regularization parameter as the minimum of parameters from the post-estimated monotone error rule and a certain new rule from the proposed family. The advantages of the new rules are demonstrated in extensive numerical experiments.     

Error bound of critical points and KL property of exponent 1/2 for squared F-norm regularized factorization

This paper is concerned with the squared F(robenius)-norm regularized factorization form for noisy low-rank matrix recovery problems. Under a suitable assumption on the restricted condition number of the Hessian matrix of the loss function, we establish an error bound to the true matrix for the non-strict critical points with rank not more than that of the true matrix. Then, for the squared F-norm regularized factorized least squares loss function, we establish its KL property of exponent 1/2 on the global optimal solution set under the noisy and full sample setting, and achieve this property at its certain class of critical points under the noisy and partial sample setting. These theoretical findings are also confirmed by solving the squared F-norm regularized factorization problem with an accelerated alternating minimization method.

     

Worst case tractability of linear problems in the presence of noise: Linear information

We study the worst case tractability of multivariate linear problems defined on separable Hilbert spaces. Information about a problem instance consists of noisy evaluations of arbitrary bounded linear functionals, where the noise is either deterministic or random. The cost of a single evaluation depends on its precision and is controlled by a cost function. We establish mutual interactions between tractability of a problem with noisy information, the cost function, and tractability of the same problem, but with exact information.     

An exact algorithm for solving the bilevel facility interdiction and fortification problem

We present an exact approach for solving the $r$-interdiction median problem with fortification. Our approach consists of solving a greedy heuristic and a set cover problem iteratively that guarantees to find an optimal solution upon termination. The greedy heuristic obtains a feasible solution to the problem, and the set cover problem is solved to verify optimality of the solution and to provide a direction for improvement if not optimal. We demonstrate the performance of the algorithm in a computational study.     

An enumeration procedure for the assembly line balancing problem based on branching by non-decreasing idle time

In this article, we present a new exact algorithm for solving the simple assembly line balancing problem given a determined cycle time (SALBP-1). The algorithm is a station-oriented bidirectional branch-and-bound procedure based on a new enumeration strategy that explores the feasible solutions tree in a non-decreasing idle time order. The procedure uses several well-known lower bounds, dominance rules and a new logical test based on the assimilation of the feasibility problem for a given cycle time and number of stations (SALBP-F) to a maximum-flow problem.     

基于同步模型的查办群体性腐败案件策略研究

为了更有效地查办群体性腐败案件,首先论述了引入同步理论进行研究的可行性.其次对腐败群体各节点的决策同步过程进行了定量分析,阐释了腐败群体规避调查的决策机理.最后提出了查办群体性腐败案件的相关策略,为腐败问题的研究提供了新的视角.     

A multiple criteria decision analytic approach for evaluating acid rain policy choices

Multi-Attribute Utility Theoretic Approach is adopted to analyze the problem of acid rain policy choices for multiple impacted groups (agents) under two conditions: exact and imprecise preference information. The analysis involves the setting up of attributes and feasible policy alternatives. Estimates of acid rain impacts are obtained from secondary data. The emphasis is more on framework which allows explorations of compromises and the identification of acceptable impact areas than on exact results. The strongest message of this paper is that even without specifying exact cardinal preferences some dominance relationships can be established between policies in a real-world setting.     

Angular Synchronization by Eigenvectors and Semidefinite Programming

The angular synchronization problem is to obtain an accurate estimation (up to a constant additive phase) for a set of unknown angles θ(1), …, θ(n) from m noisy measurements of their offsets θ(i) - θ(j) mod 2π. Of particular interest is angle recovery in the presence of many outlier measurements that are uniformly distributed in [0, 2π) and carry no information on the true offsets. We introduce an efficient recovery algorithm for the unknown angles from the top eigenvector of a specially designed Hermitian matrix. The eigenvector method is extremely stable and succeeds even when the number of outliers is exceedingly large. For example, we successfully estimate n = 400 angles from a full set of m=(4002) offset measurements of which 90% are outliers in less than a second on a commercial laptop. The performance of the method is analyzed using random matrix theory and information theory. We discuss the relation of the synchronization problem to the combinatorial optimization problem Max-2-Lin mod L and present a semidefinite relaxation for angle recovery, drawing similarities with the Goemans-Williamson algorithm for finding the maximum cut in a weighted graph. We present extensions of the eigenvector method to other synchronization problems that involve different group structures and their applications, such as the time synchronization problem in distributed networks and the surface reconstruction problems in computer vision and optics.     

Aircraft deconfliction with speed regulation: new models from mixed-integer optimization

Detecting and solving aircraft conflicts, which occur when aircraft sharing the same airspace are too close to each other according to their predicted trajectories, is a crucial problem in Air Traffic Management. We focus on mixed-integer optimization models based on speed regulation. We first solve the problem to global optimality by means of an exact solver. Since the problem is very difficult to solve, we also propose a heuristic procedure where the problem is decomposed and it is locally exactly solved. Computational results show that the proposed approach provides satisfactory results.     

Projective synchronization of Chua’s chaotic system with dead-zone in the control input

This paper investigates the chaos synchronization problem for drive-response Chua’s systems coupled with dead-zone nonlinear input. An estimator of unknown nonlinear term is proposed. Using the sliding mode control technique and the estimate of unknown nonlinear term, a novel variable structure controller which guarantees projective synchronization even when the dead-zone nonlinearity is present. Computer simulations are provided to demonstrate the effectiveness of the proposed synchronization scheme.     

An algorithm for solving linearly constrained minimax problems

In this study, we propose an algorithm for solving a minimax problem over a polyhedral set defined in terms of a system of linear inequalities. At each iteration a direction is found by solving a quadratic programming problem and then a suitable step size along that direction is taken through an extension of Armijo's approximate line search technique. We show that each accumulation point is a Kuhn-Tucker solution and give a condition that guarantees convergence of the whole sequence of iterations. Through the use of an exact penalty function, the algorithm can be used for solving constrained nonlinear programming. In this case, our algorithm resembles that of Han, but differs from it both in the direction-finding and the line search steps.     

An exact penalty approach for solving a class of minimization problems with boolean variables

An exact penalty approach for solving minimization problems with a concave objective function, linear constraints and Boolean variables is proposed. The penalty problems have continuous variables. An estimation of the penalty parameter which guarantees the exactness can be calculated on the base of an auxiliary problem. The results are applied to problems with an arbitrary quadratic objective function, linear constraints and Boolean variables. This leads to a modified Lagrangean approach for the latter problems. In the general case, the penalty approach is compared with a direct application of results of global optimization to a modification of the initial problem.     

Fast synchronization of non-identical chaotic modulation-based secure systems using a modified sliding mode controller

In this paper, a secure communication scheme based on chaotic modulation is proposed using a reversible process and a robust controller with efficient cost and complexity to synchronize two different chaotic systems. In the controller design, a sliding mode control with an adaptive rule is used for non-linear inputs. The adaptive rule is applied to ensure the synchronization when uncertainties, non-modeled dynamics or external distortions are at work. The message signal is recovered at the receiver using a recursive process at the end. The effectiveness of the proposed algorithm is confirmed via the simulation results for the synchronization of the transmitted signal modulated by Chen chaotic system at the transmitter and Genesio chaotic system at the receiver, and those for the information recovery process.     

Exact Worst-Case Convergence Rates of the Proximal Gradient Method for Composite Convex Minimization

We study the worst-case convergence rates of the proximal gradient method for minimizing the sum of a smooth strongly convex function and a non-smooth convex function, whose proximal operator is available. We establish the exact worst-case convergence rates of the proximal gradient method in this setting for any step size and for different standard performance measures: objective function accuracy, distance to optimality and residual gradient norm. The proof methodology relies on recent developments in performance estimation of first-order methods, based on semidefinite programming. In the case of the proximal gradient method, this methodology allows obtaining exact and non-asymptotic worst-case guarantees that are conceptually very simple, although apparently new. On the way, we discuss how strong convexity can be replaced by weaker assumptions, while preserving the corresponding convergence rates. We also establish that the same fixed step size policy is optimal for all three performance measures. Finally, we extend recent results on the worst-case behavior of gradient descent with exact line search to the proximal case.