Global minimization algorithms for concave quadratic programming problems

Abstract: In this article, we consider the concave quadratic programming problem which is known to be NP hard. Based on the improved global optimality conditions by [Dür, M., Horst, R. and Locatelli, M., 1998, Necessary and sufficient global optimality conditions for convex maximization revisited, Journal of Mathematical Analysis and Applications, 217, 637–649] and [Hiriart-Urruty, J.B. and Ledyav, J.S., 1996, A note in the characterization of the global maxima of a convex function over a convex set, Journal of Convex Analysis, 3, 55–61], we develop a new approach for solving concave quadratic programming problems. The main idea of the algorithms is to generate a sequence of local minimizers either ending at a global optimal solution or at an approximate global optimal solution within a finite number of iterations. At each iteration of the algorithms we solve a number of linear programming problems with the same constraints of the original problem. We also present the convergence properties of the proposed algorithms under some conditions. The efficiency of the algorithms has been demonstrated with some numerical examples.     

Piecewise polynomial collocation for linear boundary value problems of fractional differential equations

We consider a class of boundary value problems for linear multi-term fractional differential equations which involve Caputo-type fractional derivatives. Using an integral equation reformulation of the boundary value problem, some regularity properties of the exact solution are derived. Based on these properties, the numerical solution of boundary value problems by piecewise polynomial collocation methods is discussed. In particular, we study the attainable order of convergence of proposed algorithms and show how the convergence rate depends on the choice of the grid and collocation points. Theoretical results are verified by two numerical examples.     

Landweber iterative method for an inverse source problem of time-fractional diffusion-wave equation on spherically symmetric domain

In this paper, an inverse source problem of time-fractional diffusion-wave equation on spherically symmetric domain is considered. In general, this problem is ill-posed. Landweber iterative method is used to solve this inverse source problem. The error estimates between the regularization solution and the exact solution are derived by an a-priori and an a-posteriori regularization parameters choice rules. The numerical examples are presented to verify the efficiency and accuracy of the proposed methods.     

Modified regularization method for the Cauchy problem of the Helmholtz equation

In this paper, the Cauchy problem for the Helmholtz equation is investigated. It is known that such problem is severely ill-posed. We propose a modified regularization method to solve it based on the solution given by the method of separation of variables. Convergence estimates are presented under two different a-priori bounded assumptions for the exact solution. Finally, numerical examples are given to show the effectiveness of the proposed numerical method.     

The finite criss-cross method for hyperbolic programming

In this paper the finite criss-cross method is generalized to solve hyperbolic (fractional linear) programming problems. Just as in the case of linear or quadratic programming the criss-cross method can be initialized with any, not necessarily feasible basic solution. It is known that if the feasible region of the problem is unbounded then some of the known algorithms fail to solve the problem. Our criss-cross algorithm does not have such drawback. Finiteness of the procedure is proved under the usual mild assumptions. Some small numerical examples illustrate the main features of the algorithm and show that our method generates different iterates than other earlier published methods.     

Spectral regularization method for solving a time-fractional inverse diffusion problem

In this paper, we consider an inverse problem for a time-fractional diffusion equation with one-dimensional semi-infinite domain. The temperature and heat flux are sought from a measured temperature history at a fixed location inside the body. We show that such problem is severely ill-posed and further apply a spectral regularization method to solve it based on the solution given by the Fourier method. Convergence estimates are presented under a priori bound assumptions for the exact solution. Finally, numerical examples are given to show that the proposed numerical method is effective.     

Weighted least squares solutions to general coupled Sylvester matrix equations

This paper is concerned with weighted least squares solutions to general coupled Sylvester matrix equations. Gradient based iterative algorithms are proposed to solve this problem. This type of iterative algorithm includes a wide class of iterative algorithms, and two special cases of them are studied in detail in this paper. Necessary and sufficient conditions guaranteeing the convergence of the proposed algorithms are presented. Sufficient conditions that are easy to compute are also given. The optimal step sizes such that the convergence rates of the algorithms, which are properly defined in this paper, are maximized and established. Several special cases of the weighted least squares problem, such as a least squares solution to the coupled Sylvester matrix equations problem, solutions to the general coupled Sylvester matrix equations problem, and a weighted least squares solution to the linear matrix equation problem are simultaneously solved. Several numerical examples are given to illustrate the effectiveness of the proposed algorithms.     

Geometrically adaptive grids for stiff Cauchy problems

A new method for automatic step size selection in the numerical integration of the Cauchy problem for ordinary differential equations is proposed. The method makes use of geometric characteristics (curvature and slope) of an integral curve. For grids generated by this method, a mesh refinement procedure is developed that makes it possible to apply the Richardson method and to obtain a posteriori asymptotically precise estimate for the error of the resulting solution (no such estimates are available for traditional step size selection algorithms). Accordingly, the proposed methods are more robust and accurate than previously known algorithms. They are especially efficient when applied to highly stiff problems, which is illustrated by numerical examples.     

A new regularization method for solving a time-fractional inverse diffusion problem

In this paper, we consider an inverse problem for a time-fractional diffusion equation in a one-dimensional semi-infinite domain. The temperature and heat flux are sought from a measured temperature history at a fixed location inside the body. We show that such problem is severely ill-posed and further apply a new regularization method to solve it based on the solution given by the Fourier method. Convergence estimates are presented under the a priori bound assumptions for the exact solution. Finally, numerical examples are given to show that the proposed numerical method is effective.     

Maximum likelihood estimation of the Heston stochastic volatility model using asset and option prices: an application of nonlinear filtering theory

Let us suppose that the dynamics of the stock prices and of their stochastic variance is described by the Heston model, that is by a system of two stochastic differential equations with a suitable initial condition. The aim of this paper is to estimate the parameters of the Heston model and one component of the initial condition, that is the initial stochastic variance, from the knowledge of the stock and option prices observed at discrete times. The option prices considered refer to an European call on the stock whose prices are described by the Heston model. The method proposed to solve this problem is based on a filtering technique to construct a likelihood function and on the maximization of the likelihood function obtained. The estimated parameters and initial value component are characterized as being a maximizer of the likelihood function subject to some constraints. The solution of the filtering problem, used to construct the likelihood function, is based on an integral representation of the fundamental solution of the Fokker–Planck equation associated to the Heston model, on the use of the wavelet expansions presented in (Fatone et al. in High performance algorithms based on a new wavelet expansion for time dependent acoustic obstacle scattering. Commun. Computat. Phys. (2007), Research Developments in Acoustics, vol. 2, pp. 39–69. Transworld Research Network, Kerala (2005), New wavelet bases made of piecewise polynomial functions: approximation theory, quadrature rules and applications to kernel sparsification and image compression. SIAM J. Sci. Comput. (submitted)) to approximate the integral kernel appearing in the representation formula of the fundamental solution, on a simple truncation procedure to exploit the sparsifying properties of the wavelet expansions and on the use of the fast Fourier transform (FFT). The use of these techniques generates a very efficient and fully parallelizable numerical procedure to solve the filtering problem, this last fact makes possible to evaluate very efficiently the likelihood function and its gradient. As a byproduct of the solution of the filtering problem we have developed a stochastic variance tracking technique that gives very good results in numerical experiments. The maximum likelihood problem used in the estimation procedure is a low dimensional constrained optimization problem, its solution with ad hoc techniques is justified by the computational cost of evaluating the likelihood function and its gradient. We use parallel computing and a variable metric steepest ascent method to solve the maximum likelihood problem. Some numerical examples of the estimation problem using synthetic and real data, that is data relative to an index of the Milano stock exchange (S&PMIB30), obtained with a parallel implementation of the previous numerical method are presented. Very impressive speed up factors are obtained in the numerical examples using the parallel implementation of the numerical method proposed. The website: http://www.econ.univpm.it/pacelli/mariani/finance/w1 contains animations and some auxiliary material that helps the understanding of this paper and makes available to the interested users the computer programs used to produce the numerical experience presented. The numerical experience reported in this paper has been obtained using the computing grid of ENEA (Rome, Italy). The support and sponsorship of ENEA are gratefully acknowledged.     

Tikhonov regularization method for a backward problem for the time-fractional diffusion equation

This paper is devoted to solve a backward problem for a time-fractional diffusion equation with variable coefficients in a general bounded domain by the Tikhonov regularization method. Based on the eigenfunction expansion of the solution, the backward problem for searching the initial data is changed to solve a Fredholm integral equation of the first kind. The conditional stability for the backward problem is obtained. We use the Tikhonov regularization method to deal with the integral equation and obtain the series expression of solution. Furthermore, the convergence rates for the Tikhonov regularized solution can be proved by using an a priori regularization parameter choice rule and an a posteriori regularization parameter choice rule. Two numerical examples in one-dimensional and two-dimensional cases respectively are investigated. Numerical results show that the proposed method is effective and stable.     

第一阶段原有单纯形和对偶单纯形算法的计算比较

线性最优化广泛应用于经济与管理的各个领域.在线性规划问题的求解中,如果一个初始基本可行解没有直接给出,则常采用经典的两阶段法求解.对含有"≥"不等式约束的线性规划问题,讨论了第一阶段原有单纯形法和对偶单纯形法两种算法形式,并根据第一阶段问题的特点提出了改进的对偶单纯形枢轴准则.最后,通过大规模数值试验对两种算法进行计算比较,结果表明,改进后的对偶单纯形算法在计算效率上明显优于原有单纯形算法.     

Using modified maximum regret for finding a necessarily efficient solution in an interval MOLP problem

The current research concerns multiobjective linear programming problems with interval objective functions coefficients. It is known that the most credible solutions to these problems are necessarily efficient ones. To solve the problems, this paper attempts to propose a new model with interesting properties by considering the minimax regret criterion. The most important property of the new model is attaining a necessarily efficient solution as an optimal one whenever the set of necessarily efficient solutions is nonempty. In order to obtain an optimal solution of the new model, an algorithm is suggested. To show the performance of the proposed algorithm, numerical examples are given. Finally, some special cases are considered and their characteristic features are highlighted.     

First‐Order system least squares for generalized‐Newtonian coupled Stokes‐Darcy flow

The coupled problem for a generalized Newtonian Stokes flow in one domain and a generalized Newtonian Darcy flow in a porous medium is studied in this work. Both flows are treated as a first‐order system in a stress‐velocity formulation for the Stokes problem and a volumetric flux‐hydraulic potential formulation for the Darcy problem. The coupling along an interface is done using the well‐known Beavers–Joseph–Saffman interface condition. A least squares finite element method is used for the numerical approximation of the solution. It is shown that under some assumptions on the viscosity the error is bounded from above and below by the least squares functional. An adaptive refinement strategy is examined in several numerical examples where boundary singularities are present. Due to the nonlinearity of the problem a Gauss–Newton method is used to iteratively solve the problem. It is shown that the linear variational problems arising in the Gauss–Newton method are well posed. © 2014 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 31: 1150–1173, 2015     

INERTIAL ALGORITHMS FOR THE STATIONARY NAVIER-STOKES EQUATIONS

Several kind of new numerical schemes for the stationary Navier-Stokes equations based on the virtue of Inertial Manifold and Approximate Inertial Manifold, which we call them inertial algorithms in this paper, together with their error estimations are presented. All these algorithms are constructed under an uniform frame, that is to construct some kind of new projections for the Sobolev space in which the true solution is sought. It is shown that the proposed inertial algorithms can greatly improve the convergence rate of the standard Galerkin approximate solution with lower computing effort. And some numerical examples are also given to verify results of this paper.     

Solving some optimal path planning problems using an approach based on measure theory

In this paper we solve a collection of optimal path planning problems using a method based on measure theory. First we consider the problem as an optimization problem and then we convert it to an optimal control problem by defining some artificial control functions. Then we perform a metamorphosis in the space of problem. In fact we define an injection between the set of admissible pairs, containing the control vector function and a collision-free path defined on free space and the space of positive Radon measures. By properties of this kind of measures we obtain a linear programming problem that its solution gives rise to constructing approximate optimal trajectory of the original problem. Some numerical examples are proposed.     

Computational method for optimal control of switched systems with input and state constraints

In this paper, we consider an optimal control problem of switched systems with input and state constraints. Since the complexity of such constraint and switching laws, it is difficult to solve the problem using standard optimization techniques. In addition, although conjugate gradient algorithms are very useful for solving nonlinear optimization problem, in practical implementations, the existing Wolfe condition may never be satisfied due to the existence of numerical errors. And the mode insertion technique only leads to suboptimal solutions, due to only certain mode insertions being considered. Thus, based on an improved conjugate gradient algorithm and a discrete filled function method, an improved bi-level algorithm is proposed to solve this optimization problem. Convergence results indicate that the proposed algorithm is globally convergent. Three numerical examples are solved to illustrate the proposed algorithm converges faster and yields a better cost function value than existing bi-level algorithms.     

On Smoothing l1 Exact Penalty Function for Constrained Optimization Problems

This article introduces a smoothing technique to the l₁ exact penalty function. An application of the technique yields a twice continuously differentiable penalty function and a smoothed penalty problem. Under some mild conditions, the optimal solution to the smoothed penalty problem becomes an approximate optimal solution to the original constrained optimization problem. Based on the smoothed penalty problem, we propose an algorithm to solve the constrained optimization problem. Every limit point of the sequence generated by the algorithm is an optimal solution. Several numerical examples are presented to illustrate the performance of the proposed algorithm.     

Charged ball method for solving some computational geometry problems

The concept of replacement of the initial stationary optimization problem with some nonstationary mechanical system tending with time to the position of equilibrium, which coincides with the solution of the initial problem, makes it possible to construct effective numerical algorithms. First, differential equations of the movement should be derived. Then we pass to the difference scheme and define the iteration algorithm. There is a wide class of optimization methods constructed in such a way. One of the most known representatives of this class is the heavy ball method. As a rule, such type of algorithms includes parameters that highly affect the convergence rate. In this paper, the charged ball method, belonging to this class, is proposed and investigated. It is a new effective optimization method that allows solving some computational geometry problems. A problem of orthogonal projection of a point onto a convex closed set with a smooth boundary and the problem of finding the minimum distance between two such sets are considered in detail. The convergence theorems are proved, and the estimates for the convergence rate are found. Numerical examples illustrating the work of the proposed algorithms are given.     

Wavelet-Galerkin method for solving parabolic equations in finite domains

A novel wavelet-Galerkin method tailored to solve parabolic equations in finite domains is presented. The emphasis of the paper is on the development of the discretization formulations that are specific to finite domain parabolic equations with arbitrary boundary conditions based on weak form functionals. The proposed method also deals with the development of algorithms for computing the associated connection coefficients at arbitrary points. Here the Lagrange multiplier method is used to enforce the essential boundary conditions. The numerical results on a two-dimensional transient heat conducting problem are used to validate the proposed wavelet-Galerkin algorithm as an effective numerical method to solve finite domain parabolic equations.