Structure Algorithms for Partially Ordered Isotonic Regression

Abstract

An algorithm for isotonic regression is called a structure algorithm if it searches for a “solution partition”—that is, a class of sets on each of which the isotonic regression is a constant. We discuss structure algorithms for partially ordered isotonic regression. In this article we provide a new class of structure algorithms called the isotonic block class (IBC) type algorithms. One of these is called the isotonic block class with recursion method (IBCR) algorithm, which works for partially ordered isotonic regression. It is a generalization of the pooled adjacent violators algorithm and is simpler than the min-max algorithm. We also give a polynomial time algorithm—the isotonic block class with stratification (IBCS) algorithm for matrix-ordered isotonic regression. We demonstrate the efficiency of our IBCR algorithm by using simulation to estimate the relative frequencies of the numbers of level sets of isotonic regressions on certain two-dimensional grids with the matrix order.     

A simulation optimization approach for a two-echelon inventory system with service level constraints

In this paper, we present a simulation optimization algorithm for solving the two-echelon constrained inventory problem. The goal is to determine the optimal setting of stocking levels to minimize the total inventory investment costs while satisfying the expected response time targets for each field depot. The proposed algorithm is more adaptive than ordinary optimization algorithms, and can be applied to any multi-item multi-echelon inventory system, where the cost structure and service level function resemble what we assume. Empirical studies are performed to compare the efficiency of the proposed algorithms with other existing simulation algorithms.     

A Comparison of Markov Chain Methods for Reliability Estimation

Two Markov chain Monte Carlo simulation methods for reliability estimation, subset simulation and the moving particles algorithm, are compared based on theoretical arguments and test cases. The differences in the efficiency between both algorithms are rather small. They seem to be well suited for off-the-shelf reliability estimations, but with a different setting for the most important parameters (proposal density and initial sample size). (© 2017 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A storm of feasibility pumps for nonconvex MINLP

One of the foremost difficulties in solving Mixed-Integer Nonlinear Programs, either with exact or heuristic methods, is to find a feasible point. We address this issue with a new feasibility pump algorithm tailored for nonconvex Mixed-Integer Nonlinear Programs. Feasibility pumps are algorithms that iterate between solving a continuous relaxation and a mixed-integer relaxation of the original problems. Such approaches currently exist in the literature for Mixed-Integer Linear Programs and convex Mixed-Integer Nonlinear Programs: both cases exhibit the distinctive property that the continuous relaxation can be solved in polynomial time. In nonconvex Mixed-Integer Nonlinear Programming such a property does not hold, and therefore special care has to be exercised in order to allow feasibility pump algorithms to rely only on local optima of the continuous relaxation. Based on a new, high level view of feasibility pump algorithms as a special case of the well-known successive projection method, we show that many possible different variants of the approach can be developed, depending on how several different (orthogonal) implementation choices are taken. A remarkable twist of feasibility pump algorithms is that, unlike most previous successive projection methods from the literature, projection is ??naturally?? taken in two different norms in the two different subproblems. To cope with this issue while retaining the local convergence properties of standard successive projection methods we propose the introduction of appropriate norm constraints in the subproblems; these actually seem to significantly improve the practical performance of the approach. We present extensive computational results on the MINLPLib, showing the effectiveness and efficiency of our algorithm.     

A Mixed Heuristic for Circuit Partitioning

As general-purpose parallel computers are increasingly being used to speed up different VLSI applications, the development of parallel algorithms for circuit testing, logic minimization and simulation, HDL-based synthesis, etc. is currently a field of increasing research activity. This paper describes a circuit partitioning algorithm which mixes Simulated Annealing (SA) and Tabu Search (TS) heuristics. The goal of such an algorithm is to obtain a balanced distribution of the target circuit among the processors of the multicomputer allowing a parallel CAD application for Test Pattern Generation to provide good efficiency. The results obtained indicate that the proposed algorithm outperforms both a pure Simulated Annealing and a Tabu Search. Moreover, the usefulness of the algorithm in providing a balanced workload distribution is demonstrated by the efficiency results obtained by a topological partitioning parallel test-pattern generator in which the proposed algorithm has been included. An extented algorithm that works with general graphs to compare our approach with other state of the art algorithms has been also included.     

Walk On Spheres Algorithm for Helmholtz and Yukawa Equations via Duffin Correspondence

We show that a constant-potential time-independent Schrödinger equation with Dirichlet boundary data can be reformulated as a Laplace equation with Dirichlet boundary data. With this reformulation, which we call the Duffin correspondence, we provide a classical Walk On Spheres (WOS) algorithm for Monte Carlo simulation of the solutions of the boundary value problem. We compare the obtained Duffin WOS algorithm with existing modified WOS algorithms.     

Subset simulation for multi-objective optimization

Subset simulation is an efficient Monte Carlo technique originally developed for structural reliability problems, and further modified to solve single-objective optimization problems based on the idea that an extreme event (optimization problem) can be considered as a rare event (reliability problem). In this paper subset simulation is extended to solve multi-objective optimization problems by taking advantages of Markov Chain Monte Carlo and a simple evolutionary strategy. In the optimization process, a non-dominated sorting algorithm is introduced to judge the priority of each sample and handle the constraints. To improve the diversification of samples, a reordering strategy is proposed. A Pareto set can be generated after limited iterations by combining the two sorting algorithms together. Eight numerical multi-objective optimization benchmark problems are solved to demonstrate the efficiency and robustness of the proposed algorithm. A parametric study on the sample size in a simulation level and the proportion of seed samples is performed to investigate the performance of the proposed algorithm. Comparisons are made with three existing algorithms. Finally, the proposed algorithm is applied to the conceptual design optimization of a civil jet.     

Backfitting neural networks

Summary  Regression and classification problems can be viewed as special cases of the problem of function estimation. It is rather well known that a two-layer perceptron with sigmoidal transformation functions can approximate any continuous function on the compact subsets ofRP if there are sufficient number of hidden nodes. In this paper, we present an algorithm for fitting perceptron models, which is quite different from the usual backpropagation or Levenberg-Marquardt algorithm. This new algorithm based on backfitting ensures a better convergence than backpropagation. We have also used resampling techniques to select an ideal number of hidden nodes automatically using the training data itself. This resampling technique helps to avoid the problem of overfitting that one faces for the usual perceptron learning algorithms without any model selection scheme. Case studies and simulation results are presented to illustrate the performance of this proposed algorithm.     

Variational Approximation for Mixtures of Linear Mixed Models

Mixtures of linear mixed models (MLMMs) are useful for clustering grouped data and can be estimated by likelihood maximization through the Expectation–Maximization algorithm. A suitable number of components is then determined conventionally by comparing different mixture models using penalized log-likelihood criteria such as Bayesian information criterion. We propose fitting MLMMs with variational methods, which can perform parameter estimation and model selection simultaneously. We describe a variational approximation for MLMMs where the variational lower bound is in closed form, allowing for fast evaluation and develop a novel variational greedy algorithm for model selection and learning of the mixture components. This approach handles algorithm initialization and returns a plausible number of mixture components automatically. In cases of weak identifiability of certain model parameters, we use hierarchical centering to reparameterize the model and show empirically that there is a gain in efficiency in variational algorithms similar to that in Markov chain Monte Carlo (MCMC) algorithms. Related to this, we prove that the approximate rate of convergence of variational algorithms by Gaussian approximation is equal to that of the corresponding Gibbs sampler, which suggests that reparameterizations can lead to improved convergence in variational algorithms just as in MCMC algorithms. Supplementary materials for the article are available online.     

On the Best Least Squares Approximation of Continuous Functions using Linear Splines with Free Knots

Approximations to continuous functions by linear splines cangenerally be greatly improved if the knot points are free variables.In this paper we address the problem of computing a best linearspline L₂-approximant to a given continuous function on a givenclosed real interval with a fixed number of free knots. We describe an algorithm that is currently available and establishthe theoretical basis for two new algorithms that we have developedand tested. We show that one of these new algorithms had goodlocal convergence properties by comparison with the other techniques,though its convergence is quite slow. The second new algorithmis not so robust but is quicker and so is used to aid efficiency.A starting procedure based on a dynamic programming approachis introduced to give more reliable global convergence properties. We thus propose a hybrid algorithm which is both robust andreasonably efficient for this problem.     

Using objective values to start multiple objective linear programming algorithms

We introduce in this paper a new starting mechanism for multiple-objective linear programming (MOLP) algorithms. This makes it possible to start an algorithm from any solution in objective space. The original problem is first augmented in such a way that a given starting solution is feasible. The augmentation is explicitly or implicitly controlled by one parameter during the search process, which verifies the feasibility (efficiency) of the final solution. This starting mechanism can be applied either to traditional algorithms, which search the exterior of the constraint polytope, or to algorithms moving through the interior of the constraints. We provide recommendations on the suitability of an algorithm for the various locations of a starting point in objective space. Numerical considerations illustrate these ideas.     

Measuring the Stability of Results From Supervised Statistical Learning

Stability is a major requirement to draw reliable conclusions when interpreting results from supervised statistical learning. In this article, we present a general framework for assessing and comparing the stability of results, which can be used in real-world statistical learning applications as well as in simulation and benchmark studies. We use the framework to show that stability is a property of both the algorithm and the data-generating process. In particular, we demonstrate that unstable algorithms (such as recursive partitioning) can produce stable results when the functional form of the relationship between the predictors and the response matches the algorithm. Typical uses of the framework in practical data analysis would be to compare the stability of results generated by different candidate algorithms for a dataset at hand or to assess the stability of algorithms in a benchmark study. Code to perform the stability analyses is provided in the form of an R package. Supplementary material for this article is available online.     

Iterative improvement methods for a multiperiod network design problem

We address an important problem in telecommunications planning: the multiperiod network expansion problem. Our aim is to show that it can be efficiently solved using a new local search approach. To achieve our goal, we first show how to adapt the problem's formulation to meet our local search program's requirements. We then describe GLIT (Generic Local Improvement Template), a new, generic auto-calibrating local search algorithm; the different neighbouring strategies that we designed specifically for this problem; as well as a Genetic algorithm for this problem. We compare and discuss the performance of these algorithms using extensive computational tests on a large range of instances with up to 7500 arcs. These experiments show that GLIT clearly outperforms competitive approaches, especially when it is coupled with Genetic algorithms. We also show that the hybrid algorithms Genetic/Tabu, Genetic/Simulated Annealing, and finally Genetic/GLIT all outperform both pure Genetic and pure local search algorithms.     

Modified particle swarm optimization algorithm with simulated annealing behavior and its numerical verification

The hybrid algorithm that combined particle swarm optimization with simulated annealing behavior (SA-PSO) is proposed in this paper. The SA-PSO algorithm takes both of the advantages of good solution quality in simulated annealing and fast searching ability in particle swarm optimization. As stochastic optimization algorithms are sensitive to their parameters, proper procedure for parameters selection is introduced in this paper to improve solution quality. To verify the usability and effectiveness of the proposed algorithm, simulations are performed using 20 different mathematical optimization functions with different dimensions. The comparative works have also been conducted among different algorithms under the criteria of quality of the solution, the efficiency of searching for the solution and the convergence characteristics. According to the results, the SA-PSO could have higher efficiency, better quality and faster convergence speed than compared algorithms.     

The classic differential evolution algorithm and its convergence properties

Differential evolution algorithms represent an up to date and efficient way of solving complicated optimization tasks. In this article we concentrate on the ability of the differential evolution algorithms to attain the global minimum of the cost function. We demonstrate that although often declared as a global optimizer the classic differential evolution algorithm does not in general guarantee the convergence to the global minimum. To improve this weakness we design a simple modification of the classic differential evolution algorithm. This modification limits the possible premature convergence to local minima and ensures the asymptotic global convergence. We also introduce concepts that are necessary for the subsequent proof of the asymptotic global convergence of the modified algorithm. We test the classic and modified algorithm by numerical experiments and compare the efficiency of finding the global minimum for both algorithms. The tests confirm that the modified algorithm is significantly more efficient with respect to the global convergence than the classic algorithm.     

Maximum lifetime coverage preserving scheduling algorithms in sensor networks

In wireless sensor networks, when each target is covered by multiple sensors, sensors can take turns to monitor the targets in order to extend the lifetime of the network. In this paper, we address how to improve network lifetime through optimal scheduling of sensor nodes. We present two algorithms to achieve the maximum lifetime while maintaining the required coverage: a linear programming-based exponential-time exact solution, and an approximation algorithm. Numerical simulation results from the approximation algorithm are compared to the exact solution and show a high degree of accuracy and efficiency.     

A multi-swarm PSO using charged particles in a partitioned search space for continuous optimization

Particle swarm optimization (PSO) is characterized by a fast convergence, which can lead the algorithms of this class to stagnate in local optima. In this paper, a variant of the standard PSO algorithm is presented, called PSO-2S, based on several initializations in different zones of the search space, using charged particles. This algorithm uses two kinds of swarms, a main one that gathers the best particles of auxiliary ones, initialized several times. The auxiliary swarms are initialized in different areas, then an electrostatic repulsion heuristic is applied in each area to increase its diversity. We analyse the performance of the proposed approach on a testbed made of unimodal and multimodal test functions with and without coordinate rotation and shift. The Lennard-Jones potential problem is also used. The proposed algorithm is compared to several other PSO algorithms on this benchmark. The obtained results show the efficiency of the proposed algorithm.     

Tree-Structured Mixed-Effects Regression Modeling for Longitudinal Data

Tree-structured models have been widely used because they function as interpretable prediction models that offer easy data visualization. A number of tree algorithms have been developed for univariate response data and can be extended to analyze multivariate response data. We propose a tree algorithm by combining the merits of a tree-based model and a mixed-effects model for longitudinal data. We alleviate variable selection bias through residual analysis, which is used to solve problems that exhaustive search approaches suffer from, such as undue preference to split variables with more possible splits, expensive computational cost, and end-cut preference. Most importantly, our tree algorithm discovers trends over time on each of the subspaces from recursive partitioning, while other tree algorithms predict responses. We investigate the performance of our algorithm with both simulation and real data studies. We also develop an R package melt that can be used conveniently and freely. Additional results are provided as online supplementary material.     

New accelerated conjugate gradient algorithms as a modification of Dai-Yuan’s computational scheme for unconstrained optimization

New accelerated nonlinear conjugate gradient algorithms which are mainly modifications of Dai and Yuan’s for unconstrained optimization are proposed. Using the exact line search, the algorithm reduces to the Dai and Yuan conjugate gradient computational scheme. For inexact line search the algorithm satisfies the sufficient descent condition. Since the step lengths in conjugate gradient algorithms may differ from 1 by two orders of magnitude and tend to vary in a very unpredictable manner, the algorithms are equipped with an acceleration scheme able to improve the efficiency of the algorithms. Computational results for a set consisting of 750 unconstrained optimization test problems show that these new conjugate gradient algorithms substantially outperform the Dai-Yuan conjugate gradient algorithm and its hybrid variants, Hestenes-Stiefel, Polak-Ribière-Polyak, CONMIN conjugate gradient algorithms, limited quasi-Newton algorithm LBFGS and compare favorably with CG_DESCENT. In the frame of this numerical study the accelerated scaled memoryless BFGS preconditioned conjugate gradient ASCALCG algorithm proved to be more robust.