A global optimization algorithm for solving the minimum multiple ratio spanning tree problem

This paper studies the sum-of-ratios version of the classical minimum spanning tree problem. We describe a branch-and-bound algorithm for solving the general version of the problem based on its image space representation. The suggested approach specifically addresses the difficulties arising in the case when the number of ratios exceeds two. The efficacy of our approach is demonstrated on randomly generated complete and sparse graph instances.     

An Efficient Algorithm for Quadratic Sum-of-Ratios Fractional Programs Problem

The quadratic sum-of-ratios fractional program problem has a broad range of applications in practical problems. This article will present an e?cient branch-and-bound algorithm for globally solving the quadratic sum-of-ratios fractional program problem. In this algorithm, lower bounds are computed by solving a series of parametric relaxation linear programming problems, which are established by utilizing new parametric linearizing technique. To enhance the computational speed of the proposed algorithm, a rectangle reducing tactic is used to reject a part of the investigated rectangle or the whole rectangle where there does not contain any global optimal solution of the quadratic sum-of-ratios fractional program problem. Compared with the known approaches, the proposed algorithm does not need to introduce new variables and constraints. Therefore, the proposed algorithm is more suitable for application in engineering.     

Solving the sum-of-ratios problems by a harmony search algorithm

The sum-of-ratios problems have numerous applications in economy and engineering. The sum-of-ratios problems are considered to be difficult, as these functions are highly nonconvex and multimodal. In this study, we propose a harmony search algorithm for solving a sum-of-ratios problem. Numerical examples are also presented to demonstrate the effectiveness and robustness of the proposed method. In all cases, the solutions obtained using this method are superior to those obtained from other methods.     

A stochastic gradient type algorithm for closed-loop problems

We focus on the numerical solution of closed-loop stochastic problems, and propose a perturbed gradient algorithm to achieve this goal. The main hurdle in such problems is the fact that the control variables are infinite-dimensional, due to, e.g., the information constraints. Alternatively said, control variables are feedbacks, i.e., functions. Such controls have hence to be represented in a finite way in order to solve the problem numerically. In the same way, the gradient of the criterion is itself an infinite-dimensional object. Our algorithm replaces this exact (and unknown) gradient by a perturbed one, which consists of the product of the true gradient evaluated at a random point and a kernel function which extends this gradient to the neighbourhood of the random point. Proceeding this way, we explore the whole space iteration after iteration through random points. Since each kernel function is perfectly known by a small number of parameters, say N, the control at iteration k is perfectly known as an infinite-dimensional object by at most N × k parameters. The main strength of this method is that it avoids any discretization of the underlying space, provided that we can sample as many points as needed in this space. Moreover, our algorithm can take into account the possible measurability constraints of the problem in a new way. Finally, the randomized strategy implemented by the algorithm causes the most probable parts of the space to be the most explored ones, which is a priori an interesting feature. In this paper, we first prove two convergence results of this algorithm in the strongly convex and convex cases, and then give some numerical examples showing the interest of this method for practical stochastic optimization problems. In Memoriam: Jean-Sébastien Roy passed away July 04, 2007. He was 33 years old.     

Minimization of Isotonic Functions Composed of Fractions

In this paper, we introduce a class of minimization problems whose objective function is the composite of an isotonic function and finitely many ratios. Examples of an isotonic function include the max-operator, summation, and many others, so it implies a much wider class than the classical fractional programming containing the minimax fractional program as well as the sum-of-ratios problem. Our intention is to develop a generic “Dinkelbach-like” algorithm suitable for all fractional programs of this type. Such an attempt has never been successful before, including an early effort for the sum-of-ratios problem. The difficulty is now overcome by extending the cutting plane method of Barros and Frenk (in J. Optim. Theory Appl. 87:103–120, 1995). Based on different isotonic operators, various cuts can be created respectively to either render a Dinkelbach-like approach for the sum-of-ratios problem or recover the classical Dinkelbach-type algorithm for the min-max fractional programming.     

A simplicial branch and bound duality-bounds algorithm for the linear sum-of-ratios problem

In this article, we present and validate a simplicial branch and bound duality-bounds algorithm for globally solving the linear sum-of-ratios fractional program. The algorithm computes the lower bounds called for during the branch and bound search by solving ordinary linear programming problems. These problems are derived by using Lagrangian duality theory. The algorithm applies to a wide class of linear sum-of-ratios fractional programs. Two sample problems are solved, and the potential practical and computational advantages of the algorithm are indicated.     

Image space analysis of generalized fractional programs

The solution of a particular nonconvex program is usually very dependent on the structure of the problem. In this paper we identify classes of nonconvex problems involving either sums or products of ratios of linear terms which may be treated by analysis in a transformed space. In each class, the image space is defined by a mapping which associates a new variable with each original ratio of linear terms. In the image space, optimization is easy in certain directions, and the overall solution may be realized by sequentially optimizing in these directions.In addition to these ratio problems, we also show how to use image space analysis to treat the subclass of problems whose objective is to optimize a product of linear terms. For each class of nonconvex problems, we present an algorithm that locates global solutions by computing both upper and lower bounds on the solution and then solving a sequence of linear programming sub-problems. We also demonstrate the algorithms described in this paper by solving several example problems.     

Strong Convergence of a Split Common Fixed Point Problem

In this article, we present a new general algorithm for solving the split common fixed point problem in an infinite dimensional Hilbert space, which is to find a point which belongs to the common fixed point of a family of quasi-nonexpansive mappings such that its image under a linear transformation belongs to the common fixed point of another family of quasi-nonexpansive mappings in the image space. We establish the strong convergence for the algorithm to find a unique solution of the variational inequality, which is the optimality condition for the minimization problem. The algorithm and its convergence results improve and develop previous results in this field.     

Branch-and-Bound Outer Approximation Algorithm for Sum-of-Ratios Fractional Programs

In this article, a branch and-bound outer approximation algorithm is presented for globally solving a sum-of-ratios fractional programming problem. To solve this problem, the algorithm instead solves an equivalent problem that involves minimizing an indefinite quadratic function over a nonempty, compact convex set. This problem is globally solved by a branch-and-bound outer approximation approach that can create several closed-form linear inequality cuts per iteration. In contrast to pure outer approximation techniques, the algorithm does not require computing the new vertices that are created as these cuts are added. Computationally, the main work of the algorithm involves solving a sequence of convex programming problems whose feasible regions are identical to one another except for certain linear constraints. As a result, to solve these problems, an optimal solution to one problem can potentially be used to good effect as a starting solution for the next problem.     

Efficient numerical algorithm for solving the gravimetry problem of finding a lateral density in a layer: Parallel implementation

The paper is devoted to developing the new time- and memory-efficient algorithm BiCGSTABmem for solving the inverse gravimetry problem of determination of a variable density in a layer using the gravitational data. The problem is in solving the linear Fredholm integral equation of the first kind. After discretization of the domain and approximation of the integral operator, this problem is reduced to solving a large system of linear algebraic equations. It is shown that the matrix of coefficients is the Toeplitz-block-Toeplitz one in the case of the horizontal layer. For calculating and storing the elements of this matrix, we construct an efficient method, which significantly reduces the required memory and time. For the case of the curvilinear layer, we construct a method for approximating the parts of the matrix by a Toeplitz-block-Toeplitz one. This allows us to exploit the same efficient method for storing and processing the coefficient matrix in the case of a curvilinear layer. To solve the system of linear equations, we constructed the parallel algorithm on the basis of the stabilized biconjugated gradient method with using the Toeplitz-block-Toeplitz structure of the matrix. We implemented the BiCGSTAB and BiCGSTABmem algorithms for the Uran cluster supercomputer using the hybrid MPI + OpenMP technology. A model problem with synthetic data was solved for a large grid. It was shown that the new BiCGSTABmem algorithm reduces the computation time in comparison with the BiCGSTAB. Scalability of the parallel algorithm was studied.     

A Revision of the Trapezoidal Branch-and-Bound Algorithm for Linear Sum-of-Ratios Problems

In this paper, we point out a theoretical flaw in Kuno [(2002)Journal of Global Optimization 22, 155–174] which deals with the linear sum-of-ratios problem, and show that the proposed branch-and-bound algorithm works correctly despite the flaw. We also note a relationship between a single ratio and the overestimator used in the bounding operation, and develop a procedure for tightening the upper bound on the optimal value. The procedure is not expensive, but the revised algorithms incorporating it improve significantly in efficiency. This is confirmed by numerical comparisons between the original and revised algorithms. The author was partially supported by the Grand-in-Aid for Scientific Research (C)(2) 15560048 from the Japan Society for the Promotion of Science.     

Improving projection‐based eigensolvers via adaptive techniques

We consider subspace iteration (or projection‐based) algorithms for computing those eigenvalues (and associated eigenvectors) of a Hermitian matrix that lie in a prescribed interval. For the case that the projector is approximated with polynomials, we present an adaptive strategy for selecting the degree of these polynomials such that convergence is achieved with near‐to‐optimum overall work without detailed a priori knowledge about the eigenvalue distribution. The idea is then transferred to the approximation of the projector by numerical integration, which corresponds to FEAST algorithm proposed by E. Polizzi in 2009. [E. Polizzi: Density‐matrix‐based algorithm for solving eigenvalue problems. Phys. Rev. B 2009; 79 :115112]. Here, our adaptation controls the number of integration nodes. We also discuss the interaction of the method with search space reduction methods.     

Successive projection method for solving the unbalanced Procrustes problem

We present a successive projection method for solving the unbalanced Procrustes problem: given matrix A∈Rn×n and B∈Rn×k, n>k, minimize the residual‖AQ-B‖F with the orthonormal constraint QTQ = Ik on the variant Q∈Rn×k. The presented algorithm consists of solving k least squares problems with quadratic constraints and an expanded balance problem at each sweep. We give a detailed convergence analysis. Numerical experiments reported in this paper show that our new algorithm is superior to other existing methods.     

An inverse problem for space‐fractional backward diffusion problem

In this paper, an inverse problem for space‐fractional backward diffusion equation, which is highly ill‐posed, is considered. This problem is obtained from the classical diffusion equation by replacing the second‐order space derivative with a Riesz–Feller derivative of order α ∈ (0,2]. We show that such a problem is severely ill‐posed, and further present a simplified Tikhonov regularization method to deal with this problem. Convergence estimate is presented under a priori choice of regularization parameter. Numerical experiments are given to illustrate the accuracy and efficiency of the proposed method. Copyright © 2013 John Wiley & Sons, Ltd.     

Reference variable methods of solving min–max optimization problems

In this paper, reference variable methods are proposed for solving nonlinear Minmax optimization problems with unconstraint or constraints for the first time, it uses reference decision vectors to improve the methods in Vincent and Goh (J Optim Theory Appl 75:501–519, 1992) such that its algorithm is convergent. In addition, a new method based on KKT conditions of min or max constrained optimization problems is also given for solving the constrained minmax optimization problems, it makes the constrained minmax optimization problems a problem of solving nonlinear equations by a complementarily function. For getting all minmax optimization solutions, the cost function f(x, y) can be constrained as M ₁ < f(x, y) < M ₂ by using different real numbers M ₁ and M ₂. To show effectiveness of the proposed methods, some examples are taken to compare with results in the literature, and it is easy to find that the proposed methods can get all minmax optimization solutions of minmax problems with constraints by using different M ₁ and M ₂, this implies that the proposed methods has superiority over the methods in the literature (that is based on different initial values to get other minmax optimization solutions).     

Split common fixed point and common null point problem

In this paper, we present a new algorithm for solving the split common null point and common fixed point problem, to find a point that belongs to the common element of common zero points of an infinite family of maximal monotone operators and common fixed points of an infinite family of demicontractive mappings such that its image under a linear transformation belongs to the common zero points of another infinite family of maximal monotone operators and its image under another linear transformation belongs to the common fixed point of another infinite family of demicontractive mappings in the image space. We establish strong convergence for the algorithm to find a unique solution of the variational inequality, which is the optimality condition for the minimization problem. As special cases, we shall use our results to study the split equilibrium problems and the split optimization problems.     

Optimal Covering of Plane Domains by Circles Via Hyperbolic Smoothing

We consider the problem of optimally covering plane domains by a given number of circles. The mathematical modeling of this problem leads to a min–max–min formulation which, in addition to its intrinsic multi-level nature, has the significant characteristic of being non-differentiable. In order to overcome these difficulties, we have developed a smoothing strategy using a special class C^∞ smoothing function. The final solution is obtained by solving a sequence of differentiable subproblems which gradually approach the original problem. The use of this technique, called Hyperbolic Smoothing, allows the main difficulties presented by the original problem to be overcome. A simplified algorithm containing only the essential of the method is presented. For the purpose of illustrating both the actual working and the potentialities of the method, a set of computational results is presented.     

Optimization for Inconsistent Split Feasibility Problems

The split feasibility problem deals with finding a point in a closed convex subset of the domain space of a linear operator such that the image of the point under the linear operator is in a prescribed closed convex subset of the image space. The split feasibility problem and its variants and generalizations have been widely investigated as a means for resolving practical inverse problems in various disciplines. Many iterative algorithms have been proposed for solving the problem. This article discusses a split feasibility problem which does not have a solution, referred to as an inconsistent split feasibility problem. When the closed convex set of the domain space is the absolute set and the closed convex set of the image space is the subsidiary set, it would be reasonable to formulate a compromise solution of the inconsistent split feasibility problem by using a point in the absolute set such that its image of the linear operator is closest to the subsidiary set in terms of the norm. We show that the problem of finding the compromise solution can be expressed as a convex minimization problem over the fixed point set of a nonexpansive mapping and propose an iterative algorithm, with three-term conjugate gradient directions, for solving the minimization problem.     

Corrigendum to “Discrepancy principle for the dynamical systems method” [Communications in Nonlinear Science and Numerical Simulation 10 (2005) 95–101]

Consider an operator equation B(u) − f = 0 in a real Hilbert space. Let us call this equation ill-posed if the operator B′(u) is not boundedly invertible, and well-posed otherwise. The dynamical systems method (DSM) for solving this equation consists of a construction of a Cauchy problem, which has the following properties: (1) it has a global solution for an arbitrary initial data, (2) this solution tends to a limit as time tends to infinity, (3) the limit is the minimal-norm solution to the equation B(u) = f. A global convergence theorem is proved for DSM for equation B(u) − f = 0 with monotone operators B.     

Superlinear／Quadratic One-step Smoothing Newton Methodf or P0-NCP

We propose a one-step smoothing Newton method for solving the non-linear complementarity problem with P0-function (P0-NCP) based on the smoothing symmetric perturbed Fisher function(for short, denoted as the SSPF-function). The proposed algorithm has to solve only one linear system of equations and performs only one line search per iteration. Without requiring any strict complementarity assumption at the P0-NCP solution, we show that the proposed algorithm converges globally and superlinearly under mild conditions. Furthermore, the algorithm has local quadratic convergence under suitable conditions. The main feature of our global convergence results is that we do not assume a priori the existence of an accumulation point. Compared to the previous literatures, our algorithm has stronger convergence results under weaker conditions.