Geometric Hermite interpolation with Tschirnhausen cubics

Explicit formulae are found that give the unique Tschirnhausen cubic that solves a geometric Hermite interpolation problem. That solution is used to create a planar G¹ spline by joining segments of Tschirnhausen cubics. If the geometric Hermite data is from a smooth function, the Tschirnhausen cubic approximates the smooth function. The error in the approximation of a short segment of length h can be expressed as a power series in h. The error is O(h⁴) and the coefficient of the leading term is found.     

A Geometric Programming Framework for Univariate Cubic L 1 Smoothing Splines

Univariate cubic L ₁ smoothing splines are capable of providing shape-preserving C ¹-smooth approximation of multi-scale data. The minimization principle for univariate cubic L ₁ smoothing splines results in a nondifferentiable convex optimization problem that, for theoretical treatment and algorithm design, can be formulated as a generalized geometric program. In this framework, a geometric dual with a linear objective function over a convex feasible domain is derived, and a linear system for dual to primal conversion is established. Numerical examples are given to illustrate this approach. Sensitivity analysis for data with uncertainty is presented. This work is supported by research grant #DAAG55-98-D-0003 of the Army Research Office, USA.     

On a Kohn-Vogelius like formulation of free boundary problems

The present paper is concerned with the solution of a Bernoulli type free boundary problem by means of shape optimization. Two state functions are introduced, namely one which satisfies the mixed boundary value problem, whereas the second one satisfies the pure Dirichlet problem. The shape problem under consideration is the minimization of the L ²-distance of the gradients of the state functions. We compute the corresponding shape gradient and Hessian. By the investigation of sufficient second order conditions we prove algebraic ill-posedness of the present formulation. Our theoretical findings are supported by numerical experiments.     

Bivariate C1 Cubic Spline Spaces Over Even Stratified Triangulations

It is well-known that the basic properties of a bivariate spline space such as dimension and approximation order depend on the geometric structure of the partition. The dependence of geometric structure results in the fact that the dimension of a C ¹ cubic spline space over an arbitrary triangulation becomes a well-known open problem. In this paper, by employing a new group of smoothness conditions and conformality conditions, we determine the dimension of bivariate C ¹ cubic spline spaces over a so-called even stratified triangulation.     

A new fourth-order cubic spline method for second-order nonlinear two-point boundary-value problems

Bickley [5] had suggested the use of cubic splines for the solution of general linear two-point boundary-value problems. It is well known since then that this method gives only order h² uniformly convergent approximations. But cubic spline interpolation itself is a fourth-order process. We present a new fourth-order cubic spline method for second-order nonlinear two-point boundary-value problems: y″ = f(x, y, y′), a < x < b, α₀y(a) − α₀y′(a) = A, β₀y(b) + β₁y′(b) = B. We generate the solution at the nodal points by a fourth-order method and then use ‘conditions of continuity’ to obtain smoothed approximations for the second derivatives of the solution needed for the construction of the cubic spline solution. We show that our method provides order h⁴ uniformly convergent approximations over [a, b]. The fourth order of the presented method is demonstrated computationally by two examples.     

Numerical solution of the inverse electrocardiography problem with the use of the Tikhonov regularization method

The inverse electrocardiography problem related to medical diagnostics is considered in terms of potentials. Within the framework of the quasi-stationary model of the electric field of the heart, the solution of the problem is reduced to the solution of the Cauchy problem for the Laplace equation in R ³. A numerical algorithm based on the Tikhonov regularization method is proposed for the solution of this problem. The Cauchy problem for the Laplace equation is reduced to an operator equation of the first kind, which is solved via minimization of the Tikhonov functional with the regularization parameter chosen according to the discrepancy principle. In addition, an algorithm based on numerical solution of the corresponding Euler equation is proposed for minimization of the Tikhonov functional. The Euler equation is solved using an iteration method that involves solution of mixed boundary value problems for the Laplace equation. An individual mixed problem is solved by means of the method of boundary integral equations of the potential theory. In the study, the inverse electrocardiography problem is solved in region Ω close to the real geometry of the torso and heart.     

Partial Geometric Regularity of Some Optimal Connected Transportation Networks

We consider a continuous optimization model of a one-dimensional connected transportation network under the assumption that the cost of transportation with the use of network is negligible in comparison with the cost of transportation without it. We investigate the connections between this problem and its important special case, the minimization of the average distance functional. For the average distance minimization problem we formulate a number of conditions for the partial geometric regularity of a solution in ℝⁿ with an arbitrary dimension n ⩾ 2. The corresponding results are applied to solutions to the general optimization problem. Bibliography: 26 titles. Illustrations: 1 Figure. __________ Translated from Problemy Matematicheskogo Analiza, No. 31, 2005, pp. 129–157.     

An energy-minimization framework for monotonic cubic spline interpolation

This paper describes the use of cubic splines for interpolating monotonic data sets. Interpolating cubic splines are popular for fitting data because they use low-order polynomials and have C² continuity, a property that permits them to satisfy a desirable smoothness constraint. Unfortunately, that same constraint often violates another desirable property: monotonicity. It is possible for a set of monotonically increasing (or decreasing) data points to yield a curve that is not monotonic, i.e., the spline may oscillate. In such cases, it is necessary to sacrifice some smoothness in order to preserve monotonicity.The goal of this work is to determine the smoothest possible curve that passes through its control points while simultaneously satisfying the monotonicity constraint. We first describe a set of conditions that form the basis of the monotonic cubic spline interpolation algorithm presented in this paper. The conditions are simplified and consolidated to yield a fast method for determining monotonicity. This result is applied within an energy minimization framework to yield linear and nonlinear optimization-based methods. We consider various energy measures for the optimization objective functions. Comparisons among the different techniques are given, and superior monotonic C² cubic spline interpolation results are presented. Extensions to shape preserving splines and data smoothing are described.     

Connected graphs with a minimal number of spanning trees

The problem studied is the following: Find a simple connected graph G with given numbers of vertices and edges which minimizes the number t_μ(G), the number of spanning trees of the multigraph obtained from G by adding μ parallel edges between every pair of distinct vertices. If G is nearly complete (the number of edges qis ≥(₂^P)?p+2 where p is the number of vertices), then the solution to the minimization problem is unique (up to isomorphism) and the same for all values of μ. The present paper investigates the case whereq<(₂^P)?p+2. In this case the solution is not always unique and there does not always exist a common solution for all values of μ. A (small) class of graphs is given such that for any μ there exists a solution to the problem which is contained in this class. For μ = 0 there is only one graph in the class which solves the problem. This graph is described and the minimum value of t₀(G) is found. In order to derive these results a representation theorem is proved for the cofactors of a special class of matrices which contains the tree matrices associated with graphs.     

Spectral element methods on unstructured meshes: which interpolation points?

In the field of spectral element approximations, the interpolation points can be chosen on the basis of different criteria, going from the minimization of the Lebesgue constant to the simplicity of the point generation procedure. In the present paper, we summarize some recent nodal distributions for a high order interpolation in the triangle. We then adopt these points as approximation points for the numerical solution of an elliptic partial differential equation on an unstructured simplicial mesh. The L ²-norm of the approximation error is then analyzed for a model problem.     

Cubic superconvergent finite volume element method for one-dimensional elliptic and parabolic equations

In this paper, a cubic superconvergent finite volume element method based on optimal stress points is presented for one-dimensional elliptic and parabolic equations. For elliptic problem, it is proved that the method has optimal third order accuracy with respect to H¹ norm and fourth order accuracy with respect to L² norm. We also obtain that the scheme has fourth order superconvergence for derivatives at optimal stress points. For parabolic problem, the scheme is given and error estimate is obtained with respect to L² norm. Finally, numerical examples are provided to show the effectiveness of the method.     

L 1 C 1 polynomial spline approximation algorithms for large data sets

In this article, we address the problem of approximating data points by C ¹-smooth polynomial spline curves or surfaces using L ₁-norm. The use of this norm helps to preserve the data shape and it reduces extraneous oscillations. In our approach, we introduce a new functional which enables to control directly the distance between the data points and the resulting spline solution. The computational complexity of the minimization algorithm is nonlinear. A local minimization method using sliding windows allows to compute approximation splines within a linear complexity. This strategy seems to be more robust than a global method when applied on large data sets. When the data are noisy, we iteratively apply this method to globally smooth the solution while preserving the data shape. This method is applied to image denoising.     

Some properties and characterizations for generalized multivariate Pareto distributions

In this paper, several distributional properties and characterization theorems of the generalized multivariate Pareto distributions are studied. It is found that the multivariate Pareto distributions have many mixture properties. They are mixed either by geometric, Weibull, or exponential variables. The multivariate Pareto, MP^(k)(I), MP^(k)(II), and MP^(k)(IV) families have closure property under finite sample minima. The MP^(k)(III) family is closed under both geometric minima and geometric maxima. Through the geometric minima procedure, one characterization theorem for MP^(k)(III) distribution is developed. Moreover, the MP^(k)(III) distribution is proved as the limit multivariate distribution under repeated geometric minimization. Also, a characterization theorem for the homogeneous MP^(k)(IV) distribution via the weighted minima among the ordered coordinates is developed. Finally, the MP^(k)(II) family is shown to have the truncation invariant property.     

A gradient method for the matrix eigenvalue problemAx=λBx

LetA andB ben×m matrices. A gradient method for the minimization of the functionalF(x)=‖Ax?(〈Ax, Bx〉/〈Bx, Bx〉)Bx‖² is developed. The minima ofF are the eigenvectors of the eigenproblemAx=λBx. The concept of a non-defective eigenvalue for this generalized eigenvalue problem is developed. It is then shown that geometric convergence is attained for non-defective eigenvalues. A convergence rate analysis is given where it is shown that the rapidity of convergence of the gradient method to an eigenvalue λ depends on the degree of non-defectiveness of λ and the singular values ofA?λB.     

On using cubic spline for the solution of problems in calculus of variations

Two different approaches based on cubic B-spline are developed to approximate the solution of problems in calculus of variations. Both direct and indirect methods will be described. It is known that, when using cubic spline for interpolating a function g∈C⁴[a,b] on a uniform partition with the step size h, the optimal order of convergence derived is O(h⁴). In Zarebnia and Birjandi (J. Appl. Math. 1–10, 2012) a non-optimal O(h²) method based on cubic B-spline has been used to solve the problems in calculus of variations. In this paper at first we will obtain an optimal O(h⁴) indirect method using cubic B-spline to approximate the solution. The convergence analysis will be discussed in details. Also a locally superconvergent O(h⁶) indirect approximation will be describe. Finally the direct method based on cubic spline will be developed. Some test problems are given to demonstrate the efficiency and applicability of the numerical methods.     

Single machine scheduling to minimize total weighted earliness subject to minimal number of tardy jobs

Motivated by just-in-time manufacturing, we consider a single machine scheduling problem with dual criteria, i.e., the minimization of the total weighted earliness subject to minimum number of tardy jobs. We discuss several dominance properties of optimal solutions. We then develop a heuristic algorithm with time complexity O(n³) and a branch and bound algorithm to solve the problem. The computational experiments show that the heuristic algorithm is effective in terms of solution quality in many instances while the branch and bound algorithm is efficient for medium-size problems.     

Dimensionality reduction and volume minimization—generalization of the determinant minimization criterion for reduced rank regression problems

In this article we propose a generalization of the determinant minimization criterion. The problem of minimizing the determinant of a matrix expression has implicit assumptions that the objective matrix is always nonsingular. In case of singular objective matrix the determinant would be zero and the minimization problem would be meaningless. To be able to handle all possible cases we generalize the determinant criterion to rank reduction and volume minimization of the objective matrix. The generalized minimization criterion is used to solve the following ordinary reduced rank regression problem:

min_rank(X)=kdet(B-XA)(B-XA)^T,     

On the well-posedness of a two-phase minimization problem

We prove a series of results concerning the emptiness and non-emptiness of a certain set of Sobolev functions related to the well-posedness of a two-phase minimization problem, involving both the p(x)-norm and the infinity norm. The results, although interesting in their own right, hold the promise of a wider applicability since they can be relevant in the context of other problems where minimization of the p-energy in a part of the domain is coupled with the more local minimization of the L^∞-norm on another region.     

The augmented Lagrangian method for a type of inverse quadratic programming problems over second-order cones

The focus of this paper is on studying an inverse second-order cone quadratic programming problem, in which the parameters in the objective function need to be adjusted as little as possible so that a known feasible solution becomes the optimal one. We formulate this problem as a minimization problem with cone constraints, and its dual, which has fewer variables than the original one, is a semismoothly differentiable (SC ¹) convex programming problem with both a linear inequality constraint and a linear second-order cone constraint. We demonstrate the global convergence of the augmented Lagrangian method with an exact solution to the subproblem and prove that the convergence rate of primal iterates, generated by the augmented Lagrangian method, is proportional to 1/r, and the rate of multiplier iterates is proportional to $1/\sqrt{r}$ , where r is the penalty parameter in the augmented Lagrangian. Furthermore, a semismooth Newton method with Armijo line search is constructed to solve the subproblems in the augmented Lagrangian approach. Finally, numerical results are reported to show the effectiveness of the augmented Lagrangian method with both an exact solution and an inexact solution to the subproblem for solving the inverse second-order cone quadratic programming problem.