Search

To date, no systematic study has assessed the effect of random experimental errors on the predictive power of QSAR models. To address this shortage, we have benchmarked the noise sensitivity of 12 learning algorithms on 12 data sets (15,840 models in total), namely the following: Support Vector Machines (SVM) with radial and polynomial (Poly) kernels, Gaussian Process (GP) with radial and polynomial kernels, Relevant Vector Machines (radial kernel), Random Forest (RF), Gradient Boosting Machines (GBM), Bagged Regression Trees, Partial Least Squares, and k-Nearest Neighbors. Model performance on the test set was used as a proxy to monitor the relative noise sensitivity of these algorithms as a function of the level of simulated noise added to the bioactivities from the training set. The noise was simulated by sampling from Gaussian distributions with increasingly larger variances, which ranged from zero to the range of pIC50 values comprised in a given data set. General trends were identified by designing a full-factorial experiment, which was analyzed with a normal linear model. Overall, GBM displayed low noise tolerance, although its performance was comparable to RF, SVM Radial, SVM Poly, GP Poly, and GP Radial at low noise levels. Of practical relevance, we show that the bag fraction parameter has a marked influence on the noise sensitivity of GBM, suggesting that low values (e.g., 0.1-0.2) for this parameter should be set when modeling noisy data. The remaining 11 algorithms display a comparable noise tolerance, as a smooth and linear degradation of model performance is observed with the level of noise. However, SVM Poly and GP Poly display significant noise sensitivity at high noise levels in some cases. Overall, these results provide a practical guide to make informed decisions about which algorithm and parameter values to use according to the noise level present in the data.

We consider a homogeneous self-dual interior-point algorithm for solving multistage stochastic linear programs. The algorithm is particularly suitable for the so-called “scenario formulation” of the problem, whose constraint system consists of a large block-diagonal matrix together with a set of sparse nonanticipativity constraints. Due to this structure, the major computational work required by the homogeneous self-dual interior-point method can be split into three steps, each of which is highly decomposable. Numerical results on some randomly generated problems and a multistage production-planning problem are reported.

Using the idea of quasi-coincidence of a fuzzy point with a fuzzy set, the concept of an (@a,@b)-fuzzy interior ideal, which is a generalization of a fuzzy interior ideal, in a semigroup is introduced, and related properties are investigated.

An interior point approach for medium and large non-negative linear least-squares problems is proposed. Global and locally quadratic convergence is shown even if a degenerate solution is approached. Viable approaches for implementation are discussed and numerical results are provided. Copyright © 2006 John Wiley & Sons, Ltd.

Based on the min-max principle, the standard centering equation in the interior point method is replaced by the optimality condition of a new proximity measure function. Thus, a self-adjusting mechanism is constructed in the new perturbed system. The Newton direction can be adjusted self-adaptively according to the information of last iterates. A self-adjusting interior point method is given based on the new perturbed system. Numerical comparison is made between this algorithm and a primal-dual interior point algorithm using “standard” perturbed system. Results demonstrate the efficiency and some advantages of the proposed algorithm.

A primal-dual interior point method for optimal control problems is considered. The algorithm is directly applied to the infinite-dimensional problem. Existence and convergence of the central path are analyzed, and linear convergence of a short-step path-following method is established.

A primal-dual interior point method for optimal control problems with PDE constraints is considered. The algorithm is directly applied to the infinite dimensional problem. Existence and convergence of the central path are analyzed. Numerical results from an inexact continuation method applied to a model problem are shown. (© 2004 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)

We study trace inequalities of the type ∥T k f∥ L q (dμ) ≤ C∥f∥ L p (dσ) , f ∈ L p (dσ), in the upper triangle case 1 ≤ q < p for integral operators T k with positive kernels, where dσ and dp are positive Borel measures on R n . Our main tool is a generalization of Th. Wolff's inequality which gives two-sided estimates of the energy E k,σ [μ] = R n(T k [μ]) p' dσ through the L 1 (dμ)-norm of an appropriate nonlinear potential W k,σ [μ] associated with the kernel k and measures dp, dσ. We initially work with a dyadic integral operator with kernel K D (x,y) = Σ Q ∈ D K(Q)X Q (x)X Q (y), where D = {Q} is the family of all dyadic cubes in R n , and K: D → R + . The corresponding continuous versions of Wolff's inequality and trace inequalities are derived from their dyadic counterparts.

We are interested in the average behavior of interior-point methods (IPMs) for linear programming problems (LPs). We use the rotation-symmetry-model as the probabilistic model for the average case analysis. This model had been used by Borgwardt in his average case analysis of the simplex-method. IPMs solve LPs in three phases. First, one has to find an appropriate starting point, then a sequence of interior points is generated, which converges to the optimal face. Finally, the optimum has to be calculated, as it is not an interior point. We present upper bounds on the average number of iterations in the first and the third phase by looking at random figures of the underlying polyhedron. These bounds show, that IPMs solve LPs in strongly polynomial time in the average case, so only the dimension parameters and not the encoding length of the problem determine the average behavior of IPMs.

In this paper the sampling method for the shape reconstruction of a penetrable scatterer in three-dimensional linear elasticity is examined. We formulate the governing differential equations of the problem in dyadic form in order to acquire a symmetric and uniform representation for the underlying elastic fields. The corresponding far-field operator is defined in the appropriate space setting. We establish the interior transmission problem in the weak sense and consider the case where the nonhomogeneous boundary data are generated by a dyadic source point located in the interior domain. Assuming that the inclusion has absorbing behaviour, we prove the existence and uniqueness of the weak solution of the interior transmission problem. In this framework the main theorem for the shape reconstruction for the transmission case is established. As for the cases of the rigid body and the cavity an approximate far-field equation is derived with the known dyadic Green function term with the source point an interior point of the inclusion. The inversion scheme which is proposed is based on the unboundedness for the solution of an equation of the first kind. More precisely, the support of the body can be found by noting that the solution of the integral equation is not bounded as the point of the location of the fundamental solution approaches the boundary of the scatterer from interior points.

In this article we present a generic primal-dual interior-point algorithm for linear optimization in which the search direction depends on a univariate kernel function which is also used as proximity measure in the analysis of the algorithm. We present some powerful tools for the analysis of the algorithm under the assumption that the kernel function satisfies three easy to check and mild conditions (i.e., exponential convexity, superconvexity and monotonicity of the second derivative). The approach is demonstrated by introducing a new kernel function and showing that the corresponding large-update algorithm improves the iteration complexity with a factor n 1/4 when compared with the classical method, which is based on the use of the logarithmic barrier function.

We investigate the use of interior-point methods for solving quadratic programming problems with a small number of linear constraints, where the quadratic term consists of a low-rank update to a positive semidefinite matrix. Several formulations of the support vector machine fit into this category. An interesting feature of these particular problems is the volume of data, which can lead to quadratic programs with between 10 and 100 million variables and, if written explicitly, a dense Q matrix. Our code is based on OOQP, an object-oriented interior-point code, with the linear algebra specialized for the support vector machine application. For the targeted massive problems, all of the data is stored out of core and we overlap computation and input/output to reduce overhead. Results are reported for several linear support vector machine formulations demonstrating that the method is reliable and scalable.

By geometric viewpoint in search directions of linear programming problems (LP), there are two major approaches: the simplex method and the interior-point algorithm originated from Karmarkar's approach. Many of their variants developed both in theory and applications are still in progress. Roughly speaking, the main difference among them is that the simplex method is devoted for each the exact optimal solution while Karmarkar-based method is computationally fast in approaching to the neighborhood of the optimal solution, but it becomes slow near the optimal point. By the separating hyperplane theorem, we know that the optimal solution of a linear programming problem would locate at the boundary point. However, Karmarkar's algorithm is claimed as an interior-point approach which takes a solution trajectory path through the interior of the feasible region. On the other hand, these algorithms will coincide the zig-zag situation following the trajectory path before attaining the optimal point meanwhi...

We are concerned with the problem of recovering the radial kernel $k$, depending also on time, in the parabolic integro-differential equation $$D_{t}u(t,x)={\cal A}u(t,x)+\int_0^t k(t-s,|x|){\cal B}u(s,x)ds +\int_0^t D_{|x|}k(t-s,|x|){\cal C}u(s,x)ds+f(t,x),$$ ${\cal A}$ being a uniformly elliptic second-order linear operator in divergence form. We single out a special class of operators ${\cal A}$ and two pieces of suitable additional information for which the problem of identifying $k$ can be uniquely solved locally in time when the domain under consideration is a ball or a disk., 18 pages

In 1994, S. Hu conjectured in his paper (1994, Trans. Amer. Math. Soc. 342 , 753–772) that Axiom A systems are dense in the interior of Kupka–Smale systems. We will show that if X is in the interior of Kupka–Smale systems, then X satisfies Axiom A.

An interior point of a finite point set is a point of the set that is not on the boundary of the convex hull of the set. For any integer k⩾1, let g(k) be the smallest integer such that every set of points in the plane, no three collinear, containing at least g(k) interior points has a subset of points containing exactly k interior points. We prove that g(1)=1, g(2)=4, g(3)⩾8 , and g(k)⩾k+2, k⩾4 . We also give some related results.

A simple interior point method is proposed for solving a system of linear equations subject to nonnegativity constraints. The direction of update is defined by projection of the current solution on a linear manifold defined by the equations. Infeasibility is discussed and extension for free and bounded variables is presented. As an application, we consider linear programming problems and a comparison with a state-of-the-art primal-dual infeasible interior point code is presented.

For hydraulic computations that take flow and pressure regulators into account, a little-known variant of the Newton method is used. Successive approximations belong to the interior of a set R specified by linear inequalities. In contrast to the base variant of the method of interior points, the Jacobian matrix is square. The solution of the problem of flow distribution is found on the boundary of R. The local convergence of the method considered is analyzed.

This paper addresses the local convergence properties of the affine-scaling interior-point algorithm for nonlinear programming. The analysis of local convergence is developed in terms of parameters that control the interior-point scheme and the size of the residual of the linear system that provides the step direction. The analysis follows the classical theory for quasi-Newton methods and addresses q-linear, q-superlinear, and q-quadratic rates of convergence.

The aim of this paper is to present an algorithm for finding a saddle point to the constrained minimax problem. The initial problem is transformed into an equivalent equality constrained problem, and then the interior point approach is used. To satisfy the original inequality constraints a logarithmic barrier function is used and special care is given to step size parameter to keep the variables within permitted boundaries. Numerical results illustrating the method are given.

1. INTRODUCTIONWe define interior algebras, which are natural generalizations of Booleanrings equipped with an interior operator and of equality algebras. We char-acterize interior algebras in terms of a distinguished subsemilattice. Fullyinterior algebras, in which the subsemilattice consists of all idempotents,are generalizations of Boolean rings and semilattices. Our main theoremsdescribe all ring and semigroup varieties consisting of fully interior algebras.2. INTERIOR ALGEBRASThe notion of a Boolean ring with an interior operation has been aroundfor some time: they are Boolean rings with identity on which an interioroperation is defined, satisfying the usual Kuratowski sorts of conditions

We describe the code PCx, a primal-dual interior-point code for linear programming. Information is given about problem formulation and the underlying algorithm, along with instructions for installing, invoking, and using the code. Computational results on standard test problems are reported.

We use Dirichlet form methods to construct and analyze a general class of reversible Markov precesses with totally disconnected state space. We study in detail the special case of bipartite Markov chains. The latter processes have a state space consisting of an “interior” with a countable number of isolated points and a, typically uncountable, “boundary.” The equilibrium measure assigns all of its mass to the interior. When the chain is started at a state in the interior, it holds for an exponentially distributed amount of time and then jumps to the boundary. It then instantaneously re-enters the interior. There is a “local time on the boundary.” That is, the set of times the process is on the boundary is uncountable and coincides with the points of increase of a continuous additive functional. Certain processes with values in the space of trees and the space of vertices of a fixed tree provide natural examples of bipartite chains. Moreover, time-changing a bipartite chain by its local time on the boundary leads to interesting processes, including particular Levy processes on local fields (for example, the p-adic numbers) that have been considered elsewhere in the literature.

Interior point methods, especially the algorithms for linear programming problems are sensitive if there are unconstrained (free) variables in the problem. While replacing a free variable by two nonnegative ones may cause numerical instabilities, the implicit handling results in a semidefinite scaling matrix at each interior point iteration. In the paper we investigate the effects if the scaling matrix is regularized. Our analysis will prove that the effect of the regularization can be easily monitored and corrected if necessary. We describe the regularization scheme mainly for the efficient handling of free variables, but a similar analysis can be made for the case, when the small scaling factors are raised to larger values to improve the numerical stability of the systems that define the searcn direction. We will show the superiority of our approach over the variable replacement method on a set of test problems arising from water management application

There exists an equilibrium potential, an element of a Dirichlet space, for any compact subset, with non-emtpy interior, of Rm. This potential is constant on the interior of the set. There is a corresponding measure that is 0 outside the set. We prove that the restriction of this equilibrium measure to the interior of the set is absolutely continuous, and we derive an explicit formula for its density.

Resource allocation problems are usually solved with specialized methods exploiting their general sparsity and problem-specific algebraic structure. We show that the sparsity structure alone yields a closed-form Newton search direction for the generic primal-dual interior point method. Computational tests show that the interior point method consistently outperforms the best specialized methods when no additional algebraic structure is available., Comment: 1 figure

This contribution discusses the construction of kernel-based adaptive particle methods for numerical flow simulation, where the finite volume particle method (FVPM) is used as a prototype. In the FVPM, scattered data approximation algorithms are required in the recovery step of the WENO reconstruction. We first show how kernel-based approximation schemes can be used in the recovery step of particle methods, where we give preference to the radial polyharmonic spline kernel. Then we discuss important aspects concerning the numerical stability and approximation behaviour of polyharmonic splines. Moreover, we propose customized coarsening and refinement rules for the adaptive resampling of the particles. Supporting numerical examples and comparisons with other radial kernels are provided.

Motivated by a simple optimal control problem with state constraints, we consider an inexact implementation of the primal-dual interior point algorithm of Zhang, Tapia, and Dennis. We show how the control problem can be formulated as a linear program in an infinite dimensional space in two different ways and prove convergence results.

In this article we present a simple introduction to the notion of self-concordance and its implications for convex programming. We consider certain interior-point methods for solving convex programs Starting from a straightforward derivation of sufficient conditions that allow the formulation of a polynomial time interior-point method, we give an outline of the method of centers. Our presentation includes a complete analysis of the method as well as some improved results on ellipsoidal approximations of the feasible set

Invariant Moment is an important method for image representation for its invariant for shift, rotation, scale, and intensity distortion of an image. According to drawbacks of state-of-the-art methods, the criteria of designing radial kernels were summarized in this paper. And also a new invariant moment-Non-Uniform Cube Fourier Moment was proposed. The zeros are distributed non-uniformly, and the amplitudes of vibration are descending along the radial orientation. And also information redundancy was used to design the radial kernel, so the base functions of it are non-orthogonal. Those features make them more reasonable for image representation, especially small images. Finally image reconstruction with those new moments was experimented, to prove those new moments perform better in image representation.

In the boundary integral method, interior point values are calculated by means of an integration over the boundary. For interior points close to the boundary, some integrands will be nearly singular and standard numerical integration is highly inaccurate. In this paper, interior values are computed by means of analytical integration formulas obtained via symbolic computation. Numerical experiments for the two-dimensional Laplace equation ∇2φ = 0 demonstrate that the exact formulas accurately evaluate the potential φ arbitrarily close to the boundary. The interior potential gradient ∇φ is more difficult, and accurate results very near the boundary are obtained by suitably modifying the potential function.

The n-interior point variant of the Erdos-Szekeres problem is to show the following: For any n, n ⩾ 1 , every point set in the plane with sufficient number of interior points contains a convex polygon containing exactly n-interior points. This has been proved only for n ⩽ 3 . In this paper, we prove it for pointsets having atmost logarithmic number of convex layers. We also show that any pointset containing atleast n interior points, there exists a 2-convex polygon that contains exactly n-interior points.

We consider nonlinear function estimation using Radial Basis Function Networks. We analytically determine the optimal radial kernel minimizing the Mean Integrated Square Error (MISE) and the optimal MISE rate of convergence. The rates of convergence for various classes of nonlinear functions and input densities are also considered.

It was brought to our attention by Professor Valeria Simoncini that our proof of Theorem 2.1 [2, p. 139] is incorrect. Indeed, on page 140 we write the inequality (2.4) which is correct because we work with A which is an m× n matrix and m ≤ n and rank(A)=m hence ‖AT y‖ ‖y‖ ≥ σ1. However, on page 141 we write the inequality (2.6). We try to use a similar argument but now instead of A we have A and x ∈Rn. Hence the inequality ‖Ax‖ ‖x‖ ≥ σ1 (which we use to prove inequality (2.6)) is incorrect. In this short note we restate Theorem 2.1 of [2] and give a new proof.

We show that recently developed interior point methods for quadratic programming and linear complementarity problems can be put to use in solving discrete-time optimal control problems, with general pointwise constraints on states and controls. We describe interior point algorithms for a discrete-time linear-quadratic regulator problem with mixed state/control constraints and show how they can be efficiently-incorporated into an inexact sequential quadratic programming algorithm for nonlinear problems. The key to the efficiency of the interior-point method is the narrow-banded structure of the coefficient matrix which is factorized at each iteration.

This paper establishes basic results on the existence of interior points and interior paths in a nonlinear monotone complementarity problem in ℝn under very weak interior conditions. We show that the interior paths are bounded, continuous, and all the limit points of the paths are solutions to the complementarity problem. We prove that certain sets, including the solution set to the complementary problem, form a compact convex set. We also prove the existence of generalized interior points and interior paths. These generalized paths are also continuous and contain readily available starting points from which we can follow the paths to locate the solutions to the complementarity problem. We prove our results in the context of maximal monotone operators. The result presented here can be used to develop polynomial time interior point algorithms for general monotone complementarity problems.

In this paper, the interior point based continuous method is proposed for linear programming. The continuous method model can be viewed as the continuous realization of the existing interior point method for linear programming. Our study will be under the framework of the continuous method for optimization. As a result, we are able to study the behaviors of these continuous method models in a unified format. A key component of the continuous method is an ordinary differential equation (ODE), which is established based on the interior point method for linear programming. The properties of the ODE along with the convergence issues will be addressed.

To trace the aggregate homotopy method for constrained sequential max-min problems, a new interior point algorithm is proposed, and its global convergence is established under some conditions. The residual control criteria, which ensures that the obtained iterative points are interior points, is given by the condition that ensures the s-cone neighborhood to be included in the interior of the feasible region. Hence, the algorithm avoids judging whether the iterative points are the interior points or not in every predictor step and corrector step of the Euler-Newton method so that the computation is reduced greatly.

In this paper, we study the search directions of three important interior-point algorithms, namely, the primal-affine scaling method (with logarithmic barrier function), the dual-affine scaling method (with logarithmic barrier function), and the primal-dual interior point method. From an algebraic point of view, we show that the search directions of these three algorithms are merely Newton directions along three different “paths” that lead to a solution of the Karush-Kuhn-Tucker conditions of a given linear programming problem. From a geometric point of view, we show that these directions can be obtained by solving certain well-defined subproblems. Both views provide a general platform for studying the existing interior-point methods and deriving new interior-point algorithms. We illustrate the derivation of new interior-point algorithms by replacing the logarithmic barrier function with an entropic barrier function. The results have been generalized and discussed.

A convergence result is proved for the dual variables of a completely degenerate linear programming problem. The successive approximations are shown to converge to an interior point of the dual solution set.

The non---equational notion of abstract approximation space for roughness theory is introduced, and its relationship with the equational definition of lattice with Tarski interior and closure operations is studied. Their categorical isomorphism is proved, and the role of the Tarski interior and closure with an algebraic semantic of a S4---like model of modal logic is widely investigated. A hierarchy of three particular models of this approach to roughness based on a concrete universe is described, listed from the stronger model to the weaker one: (1) the partition spaces, (2) the topological spaces by open basis, and (3) the covering spaces.

In this paper we report on some recent results concerning Hermite quasi-interpolation on uniform grids with interesting applications to the approximation of solutions to elliptic PDE, quasi-interpolation on nonuniform grids and the cubature of convolutions with radial kernel functions based on an approximation method proposed by V. Maz’ya.

We propose an infeasible interior proximal method for solving variational inequality problems with maximal monotone operators and linear constraints. The interior proximal method proposed by Auslender, Teboulle and Ben-Tiba [3] is a proximal method using a distance-like barrier function and it has a global convergence property under mild assumptions. However, this method is applicable only to problems whose feasible region has nonempty interior. The algorithm we propose is applicable to problems whose feasible region may have empty interior. Moreover, a new kind of inexact scheme is used. We present a full convergence analysis for our algorithm.

A lattice polytope is a polytope in whose vertices are all in . The volume of a lattice polytope P containing exactly k ≥ 1 points in d in its interior is bounded above by . Any lattice polytope in of volume V can after an integral unimodular transformation be contained in a lattice cube having side length at most n˙n ! V. Thus the number of equivalence classes under integer unimodular transformations of lattice poly topes of bounded volume is finite. If S is any simplex of maximum volume inside a closed bounded convex body K in having nonempty interior, then K⊆ ( n + 2)S — (n+ l)s where mS denotes a nomothetic copy of S with scale factor m, and s is the centroid of S.

A basic characteristic of an interior point algorithm for linear programming is the search direction. Many papers on interior point algorithms only give an implicit description of the search direction. In this report we derive explicit expressions for the search directions used in many well-known algorithms. Comparing these explicit expressions gives a good insight into the similarities and differences between the various algorithms. Moreover, we give a survey of projected gradient and Newton directions for all potential and barrier functions. This is done both for the affine and projective variants.

We present an interior point approach to the zero–one integer programming feasibility problem based on the minimization of a nonconvex potential function. Given a polytope defined by a set of linear inequalities, this procedure generates a sequence of strict interior points of this polytope, such that each consecutive point reduces the value of the potential function. An integer solution (not necessarily feasible) is generated at each iteration by a rounding scheme. The direction used to determine the new iterate is computed by solving a nonconvex quadratic program on an ellipsoid. We illustrate the approach by considering a class of difficult set covering problems that arise from computing the 1-width of the incidence matrix of Steiner triple systems.