Algorithms for computing shape preserving spline approximations to data

Summary We treat the problem of approximating data that are sampled with error from a function known to be convex and increasing. The approximating function is a polynomial spline with knots at the data points. This paper presents results (analogous to those in [7] and [9]) that describe some approximation properties of polynomial splines and algorithms for determining the existence of a shape-preserving approximant for given data.Formerly of the Graduate Program in Operations Research, NC State University. Author nowResearch supported in part by NASA Grant NAG1-103     

Polynomial convergence of primal-dual algorithms for the second-order cone program based on the MZ-family of directions

In this paper we study primal-dual path-following algorithms for the second-order cone programming (SOCP) based on a family of directions that is a natural extension of the Monteiro-Zhang (MZ) family for semidefinite programming. We show that the polynomial iteration-complexity bounds of two well-known algorithms for linear programming, namely the short-step path-following algorithm of Kojima et al. and Monteiro and Adler, and the predictor-corrector algorithm of Mizuno et al., carry over to the context of SOCP, that is they have an O( logε^-1) iteration-complexity to reduce the duality gap by a factor of ε, where n is the number of second-order cones. Since the MZ-type family studied in this paper includes an analogue of the Alizadeh, Haeberly and Overton pure Newton direction, we establish for the first time the polynomial convergence of primal-dual algorithms for SOCP based on this search direction. Received: June 5, 1998 / Accepted: September 8, 1999?Published online April 20, 2000     

Self-concordant functions for optimization on smooth manifolds

This paper discusses self-concordant functions on smooth manifolds. In Euclidean space, such functions are utilized extensively as barrier functions in interior-point methods for polynomial time optimization algorithms. Here, the self-concordant function is carefully defined on a differential manifold in such a way that the properties of self-concordant functions in Euclidean space are preserved. A Newton decrement is defined and analyzed for this class of functions. Based on this, a damped Newton algorithm is proposed for the optimization of self-concordant functions. Under reasonable technical assumptions such as geodesic completeness of the manifold, this algorithm is guaranteed to fall in any given small neighborhood of the optimal solution in a finite number of steps. The existence and uniqueness of the optimal solution is also proved in this paper. Hence, the optimal solution is a global one. Furthermore, it ensures a quadratic convergence within a neighborhood of the minimal point. This neighborhood can be specified in terms of the Newton decrement. The computational complexity bound of the proposed approach is also given explicitly. This complexity bound is shown to be of the order where is the desired precision. Some interesting optimization problems are given to illustrate the proposed concept and algorithm. A part of the materials has been presented at 2004 Conference on Decision and Control     

A generalized Newton algorithm for quantile regression models

This paper formulates the quadratic penalty function for the dual problem of the linear programming associated with the \(L_1\) constrained linear quantile regression model. We prove that the solution of the original linear programming can be obtained by minimizing the quadratic penalty function, with the formulas derived. The obtained quadratic penalty function has no constraint, thus could be minimized efficiently by a generalized Newton algorithm with Armijo step size. The resulting algorithm is easy to implement, without requiring any sophisticated optimization package other than a linear equation solver. The proposed approach can be generalized to the quantile regression model in reproducing kernel Hilbert space with slight modification. Extensive experiments on simulated data and real-world data show that, the proposed Newton quantile regression algorithms can achieve performance comparable to state-of-the-art.     

Quadratic convergence of potential-reduction methods for degenerate problems

Global and local convergence properties of a primal-dual interior-point pure potential-reduction algorithm for linear programming problems is analyzed. This algorithm is a primal-dual variant of the Iri-Imai method and uses modified Newton search directions to minimize the Tanabe-Todd-Ye (TTY) potential function. A polynomial time complexity for the method is demonstrated. Furthermore, this method is shown to have a unique accumulation point even for degenerate problems and to have Q-quadratic convergence to this point by an appropriate choice of the step-sizes. This is, to the best of our knowledge, the first superlinear convergence result on degenerate linear programs for primal-dual interior-point algorithms that do not follow the central path. Received: February 12, 1998 / Accepted: March 3, 2000?Published online January 17, 2001     

On the Convergence of the Generalized Linear Least Squares Algorithm

This paper considers the issue of parameter estimation for biomedical applications using nonuniformly sampled data. The generalized linear least squares (GLLS) algorithm, first introduced by Feng and Ho (1993), is used in the medical imaging community for removal of bias when the data defining the model are correlated. GLLS provides an efficient iterative linear algorithm for the solution of the non linear parameter estimation problem. This paper presents a theoretical discussion of GLLS and introduces use of both Gauss Newton and an alternating Gauss Newton for solution of the parameter estimation problem in nonlinear form. Numerical examples are presented to contrast the algorithms and emphasize aspects of the theoretical discussion. AMS subject classification (2000) 65F10.R. A. Renaut: This work was partially supported by the Arizona Center for Alzheimer’s Disease Research, by NIH grant EB 2553301 and for the second author by NSF CMG-02223.Received December 2003. Revised November 2004. Communicated by Lars Eldén.     

The Neumann problem on ellipsoids

The Neumann problem on an ellipsoid in \(\mathbf {R}^n\) asks for a function harmonic inside the ellipsoid whose normal derivative is some specified function on the ellipsoid. We solve this problem when the specified function on the ellipsoid is a normalized polynomial (a polynomial divided by the norm of the normal vector arising from the definition of the ellipsoid). Specifically, we give a necessary and sufficient condition for a solution to exist, and we show that if a solution exists then it is a polynomial whose degree is at most the degree of the polynomial giving the specified function. Furthermore, we give an algorithm for computing this solution. We also solve the corresponding generalized Neumann problem and give an algorithm for computing its solution.     

A Two-Echelon Inventory Optimization Model with Demand Time Window Considerations

This paper studies a two-echelon dynamic lot-sizing model with demand time windows and early and late delivery penalties. The problem is motivated by third-party logistics and vendor managed inventory applications in the computer industry where delivery time windows are typically specified under a time definite delivery contract. Studying the optimality properties of the problem, the paper provides polynomial time algorithms that require O(T ³) computational complexity if backlogging is not allowed and O(T ⁵) computational complexity if backlogging is allowed.     

Unconstrained and constrained global optimization of polynomial functions in one variable

In Floudas and Visweswaran (1990), a new global optimization algorithm (GOP) was proposed for solving constrained nonconvex problems involving quadratic and polynomial functions in the objective function and/or constraints. In this paper, the application of this algorithm to the special case of polynomial functions of one variable is discussed. The special nature of polynomial functions enables considerable simplification of the GOP algorithm. The primal problem is shown to reduce to a simple function evaluation, while the relaxed dual problem is equivalent to the simultaneous solution of two linear equations in two variables. In addition, the one-to-one correspondence between the x and y variables in the problem enables the iterative improvement of the bounds used in the relaxed dual problem. The simplified approach is illustrated through a simple example that shows the significant improvement in the underestimating function obtained from the application of the modified algorithm. The application of the algorithm to several unconstrained and constrained polynomial function problems is demonstrated.     

Solution of dual fuzzy polynomial equations by modified Adomian decomposition method

In this paper, we present some efficient numerical algorithm for solving dual fuzzy polynomial equations based on Newton’s method. The modified Adomian decomposition method is applied to construct the numerical algorithms. Some numerical illustrations are given to show the efficiency of the algorithms.     

A global optimization algorithm for polynomial programming problems using a Reformulation-Linearization Technique

This paper is concerned with the development of an algorithm to solve continuous polynomial programming problems for which the objective function and the constraints are specified polynomials. A linear programming relaxation is derived for the problem based on a Reformulation Linearization Technique (RLT), which generates nonlinear (polynomial) implied constraints to be included in the original problem, and subsequently linearizes the resulting problem by defining new variables, one for each distinct polynomial term. This construct is then used to obtain lower bounds in the context of a proposed branch and bound scheme, which is proven to converge to a global optimal solution. A numerical example is presented to illustrate the proposed algorithm.     

Newton basis for multivariate Birkhoff interpolation

Multivariate Birkhoff interpolation is the most complex polynomial interpolation problem and people know little about it so far. In this paper, we introduce a special new type of multivariate Birkhoff interpolation and present a Newton paradigm for it. Using the algorithms proposed in this paper, we can construct a Hermite system for any interpolation problem of this type and then obtain a Newton basis for the problem w.r.t. the Hermite system.     

An Integral Simplex Algorithm for Solving Combinatorial Optimization Problems

In this paper a local integral simplex algorithm will be described which, starting with the initial tableau of a set partitioning problem, makes pivots using the pivot on one rule until no more such pivots are possible because a local optimum has been found. If the local optimum is also a global optimum the process stops. Otherwise, a global integral simplex algorithm creates and solves the problems in a search tree consisting of a polynomial number of subproblems, subproblems of subproblems, etc. The solution to at least one of these subproblems is guaranteed to be an optimal solution to the original problem. If that solution has a bounded objective then it is an optimal set partitioning solution of the original problem, but if it has an unbounded objective then the original problem has no feasible solution. It will be shown that the total number of pivots required for the global integral simplex method to solve a set partitioning problem having m rows, where m is an arbitrary but fixed positive integer, is bounded by a polynomial function of n.A method for programming the algorithms in this paper to run on parallel computers is discussed briefly.     

Factorization of moving-average spectral densities by state-space representations and stacking

To factorize a spectral density matrix of a vector moving average process, we propose a state space representation. Although this state space is not necessarily of minimal dimension, its associated system matrices are simple and most matrix multiplications involved are nothing but index shifting. This greatly reduces the complexity of computation. Moreover, in this article we stack every q consecutive observations of the original process MA(q) and generate a vector MA(1) process. We consider a similar state space representation for the stacked process. Consequently, the solution hinges on a surprisingly compact discrete algebraic Riccati equation (DARE), which involves only one Toeplitz and one Hankel block matrix composed of autocovariance functions. One solution to this equation is given by the so-called iterative projection algorithm. Each iteration of the stacked version is equivalent to q iterations of the unstacked one. We show that the convergence behavior of the iterative projection algorithm is characterized by the decreasing rate of the partial correlation coefficients for the stacked process. In fact, the calculation of the partial correlation coefficients via the Whittle algorithm, which takes a very simple form in this case, offers another solution to the problem. To achieve computational efficiency, we apply the general Newton procedure given by Lancaster and Rodman to the DARE and obtain an algorithm of quadratic convergence rate. One immediate application of the new algorithms is polynomial stabilization. We also discuss various issues such as check of positivity and numerical implementation.     

A primal-dual interior-point method for linear programming based on a weighted barrier function

One motivation for the standard primal-dual direction used in interior-point methods is that it can be obtained by solving a least-squares problem. In this paper, we propose a primal-dual interior-point method derived through a modified least-squares problem. The direction used is equivalent to the Newton direction for a weighted barrier function method with the weights determined by the current primal-dual iterate. We demonstrate that the Newton direction for the usual, unweighted barrier function method can be derived through a weighted modified least-squares problem. The algorithm requires a polynomial number of iterations. It enjoys quadratic convergence if the optimal vertex is nondegenerate.The research of the second author was supported in part by ONR Grants N00014-90-J-1714 and N00014-94-1-0391.     

Milnor number at infinity, topology and Newton boundary of a polynomial function

Abstract. In this paper we show that the Euler characteristic of the generic fibre of a complex polynomial function can be easily computed using the Newton number of f. We apply this result to study polynomials with a finite number of critical points. Received May 25, 1998; in final form January 28, 1999     

Level structure of Zhegalkin polynomials,properties of test sets,and an annihilator search algorithm

Properties of the Boolean functions specified by the Zhegalkin polynomials in n variables of degree not greater than k are investigated from the viewpoint of placing their unit (zero) points on a unit cube. Properties of test sets for the Zhegalkin polynomials are considered, where the key role is played by the irredundant test sets. A deterministic algorithm for finding all the annihilators for a given polynomial is described including minimal-degree annihilators that have applications in cryptology. In the available algorithms for finding annihilators, the problem is reduced to solving systems of linear Boolean equations. Reducing the dimension of these systems decreases the algorithmic complexity of solving the problem. The proposed algorithm makes it possible to decrease the complexity of finding annihilators by reducing the dimension of such systems but it does not reduce the asymptotic complexity of solving systems of linear Boolean equations.     

Polynomial complexity algorithms for computational problems in the theory of algebraic curves

It is proved that the classical algorithm for constructing Newton-Puiseux expansions for the roots of polynomials using the method of Newton polygons is of polynomial complexity in the notation length of the expansion coefficients. This result is used, in the case of a ground field of characteristic O, to construct polynomial-time algorithms for factoring polynomials over fields of formal power series, and for fundamental computational problems in the theory of algebraic curves, such as curve normalization.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova Akademii Nauk SSSR, Vol. 176, pp. 127–150, 1989.     

An application of simultaneous diophantine approximation in combinatorial optimization

We present a preprocessing algorithm to make certain polynomial time algorithms strongly polynomial time. The running time of some of the known combinatorial optimization algorithms depends on the size of the objective functionw. Our preprocessing algorithm replacesw by an integral valued-w whose size is polynomially bounded in the size of the combinatorial structure and which yields the same set of optimal solutions asw. As applications we show how existing polynomial time algorithms for finding the maximum weight clique in a perfect graph and for the minimum cost submodular flow problem can be made strongly polynomial. Further we apply the preprocessing technique to make H. W. Lenstra’s and R. Kannan’s Integer Linear Programming algorithms run in polynomial space. This also reduces the number of arithmetic operations used. The method relies on simultaneous Diophantine approximation. This research was done while the authors were visiting the Institute for Operations Research, University of Bonn, West Germany (1984–85), and while the second author was visiting MSRI, Berkeley. Her research was supported in part by NSF Grant 8120790.