A tight bound for the boolean quadratic optimization problem and its use in a branch and bound algorithm 1

Known duality statements are used to find tight bounds for the branch and bound process in solving Boolean quadratic optimization problems. To solve the corresponding continuous partial problem, a NEWTON-like procedure is indicated. Superlinear convergence, however, is only obtained in partial cases.     

AnL 1 smoothing spline algorithm with cross validation

We propose an algorithm for the computation ofL ₁ (LAD) smoothing splines in the spacesW _M (D), with . We assume one is given data of the formy _i =(f(t _i ) + _i , i=1,...,N with {itt_i} _i=1 ^{N D} , the _i are errors withE( _i )=0, andf is assumed to be inW _M . The LAD smoothing spline, for fixed smoothing parameter0, is defined as the solution,s , of the optimization problem (1/N) _i=1 ^N ¦y _i –g(t _i ¦+J _M (g), whereJ _M (g) is the seminorm consisting of the sum of the squaredL ₂ norms of theMth partial derivatives ofg. Such an LAD smoothing spline,s , would be expected to give robust smoothed estimates off in situations where the _i are from a distribution with heavy tails. The solution to such a problem is a thin plate spline of known form. An algorithm for computings is given which is based on considering a sequence of quadratic programming problems whose structure is guided by the optimality conditions for the above convex minimization problem, and which are solved readily, if a good initial point is available. The data driven selection of the smoothing parameter is achieved by minimizing aCV() score of the form .The combined LAD-CV smoothing spline algorithm is a continuation scheme in 0 taken on the above SQPs parametrized in, with the optimal smoothing parameter taken to be that value of at which theCV() score first begins to increase. The feasibility of constructing the LAD-CV smoothing spline is illustrated by an application to a problem in environment data interpretation.     

LOWLAD: a locally weightedL 1 smoothing spline algorithm with cross validated choice of smoothing parameters

The computation ofL ₁ smoothing splines on large data sets is often desirable, but computationally infeasible. A locally weighted, LAD smoothing spline based smoother is suggested, and preliminary results will be discussed. Specifically, one can seek smoothing splines in the spacesW _m (D), with [0, 1] ⁿ D. We assume data of the formy _i =f(t _i )+ _i ,i=1,..., N with {t _i } _i=1 ^N D, the _i are errors withE( _i )=0, andf is assumed to be inW _m . An LAD smoothing spline is the solution,s , of the following optimization problem

New five-step DTZD algorithm for future nonlinear minimization with quartic steady-state error pattern

Numerical Algorithms - In this paper, a new five-step discrete-time zeroing dynamics (DTZD) algorithm, discretized from a continuous-time zeroing dynamics (CTZD) model, is proposed and investigated...     

Branch and bound algorithm with applications to robust stability

We discuss a branch and bound algorithm for global optimization of NP-hard problems related to robust stability. This includes computing the distance to instability of a system with uncertain parameters, computing the minimum stability degree of a system over a given set of uncertain parameters, and computing the worst case \(H_\infty \) norm over a given parameter range. The success of our method hinges (1) on the use of an efficient local optimization technique to compute lower bounds fast and reliably, (2) a method with reduced conservatism to compute upper bounds, and (3) the way these elements are favorably combined in the algorithm.     

New analysis of linear convergence of gradient-type methods via unifying error bound conditions

Mathematical Programming - This paper reveals that a common and central role, played in many error bound (EB) conditions and a variety of gradient-type methods, is a residual measure operator. On...     

On the algorithm of smoothing by a spline with bilateral constraints

In this paper, the problem of constructing a spline σ in the Hilbert space, which satisfies the bilateral constraints z ^? ≤ Aσ ≤ z ⁺ with a linear operator A and minimizes the squared Hilbert seminorm is studied. A solution to this problem can be obtained with convex programming iterative methods, in particular, with the gradient projection method. A modification of the gradient projection method is proposed, which allows one to find a set of active constraints with a smaller number of iterations. The efficiency of the modification proposed is demonstrated in the problem of approximation with a pseudolinear bivariate spline.     

Branch and bound algorithm for multidimensional scaling with city-block metric

A two level global optimization algorithm for multidimensional scaling (MDS) with city-block metric is proposed. The piecewise quadratic structure of the objective function is employed. At the upper level a combinatorial global optimization problem is solved by means of branch and bound method, where an objective function is defined as the minimum of a quadratic programming problem. The later is solved at the lower level by a standard quadratic programming algorithm. The proposed algorithm has been applied for auxiliary and practical problems whose global optimization counterpart was of dimensionality up to 24.     

New efficient numerical procedures for solving stochastic variational problems with a priori maximum pointwise error estimates

In a previous paper we gave a new formulation and derived the Euler equations and other necessary conditions to solve strong, pathwise, stochastic variational problems with trajectories driven by Brownian motion. Thus, unlike current methods which minimize the control over deterministic functionals (the expected value), we find the control which gives the critical point solution of random functionals of a Brownian path and then, if we choose, find the expected value.This increase in information is balanced by the fact that our methods are anticipative while current methods are not. However, our methods are more directly connected to the theory and meaningful examples of deterministic variational theory and provide better means of solution for free and constrained problems. In addition, examples indicate that there are methods to obtain nonanticipative solutions from our equations although the anticipative optimal cost function has smaller expected value.In this paper we give new, efficient numerical methods to find the solution of these problems in the quadratic case. Of interest is that our numerical solution has a maximal, a priori, pointwise error of O(h3/2) where h is the node size. We believe our results are unique for any theory of stochastic control and that our methods of proof involve new and sophisticated ideas for strong solutions which extend previous deterministic results by the first author where the error was O(h²).We note that, although our solutions are given in terms of stochastic differential equations, we are not using the now standard numerical methods for stochastic differential equations. Instead we find an approximation to the critical point solution of the variational problem using relations derived from setting to zero the directional derivative of the cost functional in the direction of simple test functions.Our results are even more significant than they first appear because we can reformulate stochastic control problems or constrained calculus of variations problems in the unconstrained, stochastic calculus of variations formulation of this paper. This will allow us to find efficient and accurate numerical solutions for general constrained, stochastic optimization problems. This is not yet being done, even in the deterministic case, except by the first author.     

An interval branch and bound algorithm for bound constrained optimization problems

In this paper, we propose modifications to a prototypical branch and bound algorithm for nonlinear optimization so that the algorithm efficiently handles constrained problems with constant bound constraints. The modifications involve treating subregions of the boundary identically to interior regions during the branch and bound process, but using reduced gradients for the interval Newton method. The modifications also involve preconditioners for the interval Gauss-Seidel method which are optimal in the sense that their application selectively gives a coordinate bound of minimum width, a coordinate bound whose left endpoint is as large as possible, or a coordinate bound whose right endpoint is as small as possible. We give experimental results on a selection of problems with different properties.     

Oracally efficient spline smoothing of nonlinear additive autoregression models with simultaneous confidence band

Under weak conditions of smoothness and mixing, we propose spline-backfitted spline (SBS) estimators of the component functions for a nonlinear additive autoregression model that is both computationally expedient for analyzing high dimensional large time series data, and theoretically reliable as the estimator is oracally efficient and comes with asymptotically simultaneous confidence band. Simulation evidence strongly corroborates with the asymptotic theory.     

Hyperbolic smoothing and penalty techniques applied to molecular structure determination

This work considers the problem of estimating the relative positions of all atoms of a protein, given a subset of all the pair-wise distances between the atoms. This problem is NP-hard, and the usual formulations are nonsmoothed and nonconvex, having a high number of local minima. Our contribution is an efficient method that combines the hyperbolic smoothing and the penalty techniques that are useful in obtaining differentiability and reducing the number of local minima.     

Fuzzy data approximation using smoothing cubic splines: Similarity and error analysis

In this paper, a new methodology is developed for defining error and similarity measure indexes, in order to establish a criterion adequate for comparison function approximation using fuzzy data. The proposed similarity measures and error indexes are applied for smoothing with cubic splines, showing a good performance for defining the accuracy of approximation obtained with fuzzy numbers. Examples are given to compare the behavior of the new indexes proposed for different configurations of the smooth cubic splines. A statistical analysis was carried out to verify the homogeneity of the indexes proposed as criteria to determine the correctness or accuracy of such approximation of fuzzy numbers.     

A branch and bound algorithm for bound constrained optimization problems without derivatives

In this paper, we give a new branch and bound algorithm for the global optimization problem with bound constraints. The algorithm is based on the use of inclusion functions. The bounds calculated for the global minimum value are proved to be correct, all rounding errors are rigorously estimated. Our scheme attempts to exclude most uninteresting parts of the search domain and concentrates on its promising subsets. This is done as fast as possible (by involving local descent methods), and uses little information as possible (no derivatives are required). Numerical results for many well-known problems as well as some comparisons with other methods are given.     

Asymptotic theory of the global error and some techniques of error estimation

Summary The error of the approximate solution obtained by discretising a functional equation can be shown under certain conditions to possess an asymptotic expansion in terms of some parameter which is usually a representative step-length. We consider the case of two-parameter expansions, which is particularly relevant to parabolic equations. We derive results for the existence of the expansion and for the application of the classical difference correction and of defect correction. The theory is illustrated by the discussion of a simple parabolic problem     

Some branch and bound techniques for nonlinear optimization

The range of nonlinear optimization problems which can be solved by Linear Programming and the Branch and Bound algorithm is extended by introducing Chains of Linked Ordered Sets and by allowing automatic interpolation of new variables. However this approach involves solving a succession of linear subproblems, whose solutions in general violate the logical requirements of the nonlinear formulation and may lie far from any local or global optimum. The paper describes techniques which are designed to improve the performance of the Branch and Bound algorithm on problems containing chains, and which also yield benefits in integer programming.Each linear subproblem is tightened towards the corresponding nonlinear problem by removing variables which must logically be nonbasic in any feasible solution. This is achieved by a presolve procedure, and also by post-optimal Lagrangian relaxation which tightens the bound on the objective function by assessing the cheapest way to satisfy any violated chain constraints. Frequently fewer subsequent branches are required to find a feasible solution or to prove infeasibility.Formerly of Scicon Ltd.