A multiplicative Gauss-Newton minimization algorithm:Theory and application to exponential functions

Multiplicative calculus(MUC) measures the rate of change of function in terms of ratios, which makes the exponential functions significantly linear in the framework of MUC.Therefore, a generally non-linear optimization problem containing exponential functions becomes a linear problem in MUC. Taking this as motivation, this paper lays mathematical foundation of well-known classical Gauss-Newton minimization(CGNM) algorithm in the framework of MUC. This paper formulates the mathematical derivation of proposed method named as multiplicative Gauss-Newton minimization(MGNM) method along with its convergence properties.The proposed method is generalized for n number of variables, and all its theoretical concepts are authenticated by simulation results. Two case studies have been conducted incorporating multiplicatively-linear and non-linear exponential functions. From simulation results, it has been observed that proposed MGNM method converges for 12972 points, out of 19600 points considered while optimizing multiplicatively-linear exponential function, whereas CGNM and multiplicative Newton minimization methods converge for only 2111 and 9922 points, respectively. Furthermore, for a given set of initial value, the proposed MGNM converges only after 2 iterations as compared to 5 iterations taken by other methods. A similar pattern is observed for multiplicatively-non-linear exponential function. Therefore, it can be said that proposed method converges faster and for large range of initial values as compared to conventional methods.     

Integrating accounting and multiplicative calculus: an effective estimation of learning curve

Numerical interpolation methods are essential for the estimation of nonlinear functions and they have a wide range of applications in economics and accounting. In this regard, the idea of using interpolation methods based on multiplicative calculus for suitable accounting problems is self-evident. The purpose of this study, therefore, is to develop a way to better estimate the learning curve, which is an exponentially decreasing function, based on multiplicative Lagrange interpolation. The results of this study show that the proposed multiplicative method of learning curve provides more accurate estimates of labour costs when compared to the conventional methods. This is because the exponential functions are linear in multiplicative calculus. Furthermore, the results reveal that using the proposed method enables cost and managerial accountants to better calculate both cost of unused capacity and product cost in a cumulative production represented by a nonlinear function. The results of this study are also expected to help researchers, practitioners, economists, business managers, and cost and managerial accountants to understand how to construct a multiplicative based learning curve to improve such decisions as pricing, profit planning, capacity management, and budgeting.     

Multiplicative Programming Problems: Analysis and Efficient Point Search Heuristic

Multiplicative programming problems are difficult global optimization problems known to be NP-hard. At the same time, these problems have some important applications in engineering, finance, economics, and other fields. This article has two purposes. The first is to present an analysis that shows several relationships between concave multiplicative programs and concave minimization problems, and between concave multiplicative programs and certain multiple-objective mathematical programs. The second purpose is to propose and report computational results for a heuristic efficient-point search algorithm that we have designed for use on linear multiplicative programming problems. To our knowledge, this is the first heuristic algorithm of its type. The theoretical and algorithmic results given in the article offer some potentially important new avenues for analyzing and solving multiplicative programming problems of various types.     

Empirical minimization

We investigate the behavior of the empirical minimization algorithm using various methods. We first analyze it by comparing the empirical, random, structure and the original one on the class, either in an additive sense, via the uniform law of large numbers, or in a multiplicative sense, using isomorphic coordinate projections. We then show that a direct analysis of the empirical minimization algorithm yields a significantly better bound, and that the estimates we obtain are essentially sharp. The method of proof we use is based on Talagrand's concentration inequality for empirical processes. Research partially supported by NSF under award DMS-0434393. Research partially supported by the Australian Research Council Discovery Porject DP0343616.     

Subspace correction multi‐level methods for elliptic eigenvalue problems

In this work, we apply the ideas of domain decomposition and multi‐grid methods to PDE‐based eigenvalue problems represented in two equivalent variational formulations. To find the lowest eigenpair, we use a “subspace correction” framework for deriving the multiplicative algorithm for minimizing the Rayleigh quotient of the current iteration. By considering an equivalent minimization formulation proposed by Mathew and Reddy, we can use the theory of multiplicative Schwarz algorithms for non‐linear optimization developed by Tai and Espedal to analyse the convergence properties of the proposed algorithm. We discuss the application of the multiplicative algorithm to the problem of simultaneous computation of several eigenfunctions also formulated in a variational form. Numerical results are presented. Copyright © 2001 John Wiley & Sons, Ltd.     

Linear multiplicative programming

An algorithm for solving a linear multiplicative programming problem (referred to as LMP) is proposed. LMP minimizes the product of two linear functions subject to general linear constraints. The product of two linear functions is a typical non-convex function, so that it can have multiple local minima. It is shown, however, that LMP can be solved efficiently by the combination of the parametric simplex method and any standard convex minimization procedure. The computational results indicate that the amount of computation is not much different from that of solving linear programs of the same size. In addition, the method proposed for LMP can be extended to a convex multiplicative programming problem (CMP), which minimizes the product of two convex functions under convex constraints.     

A graphical method for a class of Branin trajectories

The construction of Branin trajectories for locating the stationary points of a scalar function of many variables involves, in the general case, the numerical solution of a set of simultaneous ordinary differential equations, or some equivalent numerical procedure. For a function of only two variables which is separable in either the multiplicative or additive sense, it is shown that Branin trajectories may be obtained by a graphical method due to Volterra.The authors are indebted to Dr. L. C. W. Dixon for his helpful comments on the original draft of this paper.     

Collocation method using sinc and Rational Legendre functions for solving Volterra’s population model

This paper proposes two approximate methods to solve Volterra’s population model for population growth of a species in a closed system. Volterra’s model is a nonlinear integro-differential equation on a semi-infinite interval, where the integral term represents the effect of toxin. The proposed methods have been established based on collocation approach using Sinc functions and Rational Legendre functions. They are utilized to reduce the computation of this problem to some algebraic equations. These solutions are also compared with some well-known results which show that they are accurate.     

A unified approach to parallel space decomposition methods

We consider (relaxed) additive and multiplicative iterative space decomposition methods for the minimization of sufficiently smooth functionals without constraints. We develop a general framework which unites existing approaches from both parallel optimization and finite elements. Specifically this work unifies earlier research on the parallel variable distribution method in minimization, space decomposition methods for convex functionals, algebraic Schwarz methods for linear systems and splitting methods for linear least squares. We develop a general convergence theory within this framework, which provides several new results as well as including known convergence results.     

Solving multi-objective parallel machine scheduling problem by a modified NSGA-II

In this paper, we modify a Multi-Objective Evolutionary Algorithm, known as Nondominated sorting Genetic Algorithm-II (NSGA-II) for a parallel machine scheduling problem with three objectives. The objectives are – (1) minimization of total cost due tardiness, (2) minimization of the deterioration cost and (3) minimization of makespan. The formulated problem has been solved by three Multi-Objective Evolutionary Algorithms which are: (1) the original NSGA-II (Non-dominated Sorting Genetic Algorithm–II), (2) SPEA2 (Strength Pareto Evolutionary Algorithm-2) and (3) a modified version of NSGA-II as proposed in this paper. A new mutation algorithm has also been proposed depending on the type of problem and embedded in the modified NSGA-II. The results of the three algorithms have been compared and conclusions have been drawn. The modified NSGA-II is observed to perform better than the original NSGA-II. Besides, the proposed mutation algorithm also works effectively, as evident from the experimental results.     

A Branch and Bound Algorithm for Solving Low Rank Linear Multiplicative and Fractional Programming Problems

This paper is concerned with a practical algorithm for solving low rank linear multiplicative programming problems and low rank linear fractional programming problems. The former is the minimization of the sum of the product of two linear functions while the latter is the minimization of the sum of linear fractional functions over a polytope. Both of these problems are nonconvex minimization problems with a lot of practical applications. We will show that these problems can be solved in an efficient manner by adapting a branch and bound algorithm proposed by Androulakis–Maranas–Floudas for nonconvex problems containing products of two variables. Computational experiments show that this algorithm performs much better than other reported algorithms for these class of problems.     

Low Tucker rank tensor completion using a symmetric block coordinate descent method

Low Tucker rank tensor completion has wide applications in science and engineering. Many existing approaches dealt with the Tucker rank by unfolding matrix rank. However, unfolding a tensor to a matrix would destroy the data's original multi-way structure, resulting in vital information loss and degraded performance. In this article, we establish a relationship between the Tucker ranks and the ranks of the factor matrices in Tucker decomposition. Then, we reformulate the low Tucker rank tensor completion problem as a multilinear low rank matrix completion problem. For the reformulated problem, a symmetric block coordinate descent method is customized. For each matrix rank minimization subproblem, the classical truncated nuclear norm minimization is adopted. Furthermore, temporal characteristics in image and video data are introduced to such a model, which benefits the performance of the method. Numerical simulations illustrate the efficiency of our proposed models and methods.     

Heuristic Methods for Linear Multiplicative Programming

The linear multiplicative programming is the minimization of the product of affine functions over a polyhedral set. The problem with two affine functions reduces to a parametric linear program and can be solved efficiently. For the objective function with more than two affine functions multiplied, no efficient algorithms that solve the problem to optimality have been proposed, however Benson and Boger have proposed a heuristic algorithm that exploits links of the problem with concave minimization and multicriteria optimization. We will propose a heuristic method for the problem as well as its modification to enhance the accuracy of approximation. Computational experiments demonstrate that the method and its modification solve randomly generated problems within a few percent of relative error.     

On convergence and complexity of the modified forward‐backward method involving new linesearches for convex minimization

In optimization theory, convex minimization problems have been intensively investigated in the current literature due to its wide range in applications. A major and effective tool for solving such problem is the forward‐backward splitting algorithm. However, to guarantee the convergence, it is usually assumed that the gradient of functions is Lipschitz continuous and the stepsize depends on the Lipschitz constant, which is not an easy task in practice. In this work, we propose the modified forward‐backward splitting method using new linesearches for choosing suitable stepsizes and discuss the convergence analysis including its complexity without any Lipschitz continuity assumption on the gradient. Finally, we provide numerical experiments in signal recovery to demonstrate the computational performance of our algorithm in comparison to some well‐known methods. Our reports show that the proposed algorithm has a good convergence behavior and can outperform the compared methods.     

Outcome-Space Cutting-Plane Algorithm for Linear Multiplicative Programming

This article presents an outcome-space pure cutting-plane algorithm for globally solving the linear multiplicative programming problem. The framework of the algorithm is taken from a pure cutting-plane decision set-based method developed by Horst and Tuy for solving concave minimization problems. By adapting this method to an outcome-space reformulation of the linear multiplicative programming problem, rather than applying directly the method to the original decision-set formulation, it is expected that considerable computational savings can be obtained. Also, we show how additional computational benefits might be obtained by implementing the new algorithm appropriately. To illustrate the new algorithm, we apply it to the solution of a sample problem.     

Techniques for approximating a spatially varying Euler-Bernoulli model with a constant coefficient model

Developing accurate models to describe the behaviour of a physical system often results in differential equations with spatially varying coefficients. A notable example of this that appears in many applications is the Euler-Bernoulli beam equation for transverse vibrations. This equation with spatially varying coefficients, such as when the bending stiffness or mass per unit length varies along the length of the beam, is of interest in the current research. Methods for approximating the Euler-Bernoulli equation with periodically varying coefficients have been proposed yet there is still a need for methods that approximate the more general, non-periodically varying, cases. The goal of this research is to obtain a constant coefficient Euler-Bernoulli equation that accurately approximates the original spatially varying equation using an inverse problem approach. Obtaining such an approximation has advantages in control applications where a constant coefficient model is strongly preferred for computational efficiency. The motivation for this research stems from previous work by the authors on modelling cable-harnessed structures. The spatially varying equation is solved using the Lindstedt-Poincaré perturbation method and these results are used to determine the approximate model. Multiple inverse problem methods for determining the coefficients in the approximate model are considered including metric minimization, the modal participation factor (MPF), and the proper orthogonal decomposition (POD). Continuous version of POD and MPF methods are obtained. Several wrapping patterns and boundary conditions are considered for comparison and the results are in good agreement with analytical and finite element analysis (FEA) results.     

Constrained matrix optimization with applications

In this work we study a minimization problem for a matrix-valued function under linear constraints, in the case of a singular matrix. The proposed method differs from others on the restriction of the minimizing matrix to the range of the corresponding quadratic function. Moreover, we present two applications of the proposed minimization method in Linear Regression and B-spline smoothing.     

Alternating Minimization as Sequential Unconstrained Minimization: A Survey

Sequential unconstrained minimization is a general iterative method for minimizing a function over a given set. At each step of the iteration we minimize the sum of the objective function and an auxiliary function. The aim is to select the auxiliary functions so that, at least, we get convergence in function value to the constrained minimum. The SUMMA is a broad class of these methods for which such convergence holds. Included in the SUMMA class are the barrier-function methods, entropic and other proximal minimization algorithms, the simultaneous multiplicative algebraic reconstruction technique, and, after some reformulation, penalty-function methods. The alternating minimization method of Csiszár and Tusnády also falls within the SUMMA class, whenever their five-point property holds. Therefore, the expectation maximization maximum likelihood algorithm for the Poisson case is also in the SUMMA class.     

LOCAL REGULARIZATION METHODS FOR THE STABILIZATION OF LINEAR ILL-POSED EQUATIONS OF VOLTERRA TYPE

Inverse problems based on first-kind Volterra integral equations appear naturally in the study of many applications, from geophysical problems to the inverse heat conduction problem. The ill-posedness of such problems means that a regularization technique is required, but classical regularization schemes like Tikhonov regularization destroy the causal nature of the underlying Volterra problem and, in general, can produce oversmoothed results. In this paper we investigate a class of local regularization methods in which the original (unstable) problem is approximated by a parameterized family of well-posed, second-kind Volterra equations. Being Volterra, these approximating second-kind equations retain the causality of the original problem and allow for quick sequential solution techniques. In addition, the regularizing method we develop is based on the use of a regularization parameter which is a function (rather than a single constant), allowing for more or less smoothing at localized points in the domain. We take this approach even further by adopting the flexibility of an additional penalty term (with variable penalty function) and illustrate the sequential selection of the penalty function in a numerical example.     

B-Spline collocation method for linear and nonlinear Fredholm and Volterra integro-differential equations

A numerical method based on quintic B-spline has been developed to solve the linear and nonlinear Fredholm and Volterra integro-differential equations up to order 4. The solution and its derivatives are collocated by quintic B-spline and then the integral equation is approximated by the 4-points Gauss–Turán quadrature formula with respect to the weight function Legendre. The error analysis of proposed numerical method is studied theoretically. Numerical results are given to illustrate the efficiency of the proposed method which shows that our method can be applied for large values of N. The results are compared with the results obtained by other methods which show that our method is accurate.