Accelerating the DC algorithm for smooth functions

We introduce two new algorithms to minimise smooth difference of convex (DC) functions that accelerate the convergence of the classical DC algorithm (DCA). We prove that the point computed by DCA can be used to define a descent direction for the objective function evaluated at this point. Our algorithms are based on a combination of DCA together with a line search step that uses this descent direction. Convergence of the algorithms is proved and the rate of convergence is analysed under the ?ojasiewicz property of the objective function. We apply our algorithms to a class of smooth DC programs arising in the study of biochemical reaction networks, where the objective function is real analytic and thus satisfies the ?ojasiewicz property. Numerical tests on various biochemical models clearly show that our algorithms outperform DCA, being on average more than four times faster in both computational time and the number of iterations. Numerical experiments show that the algorithms are globally convergent to a non-equilibrium steady state of various biochemical networks, with only chemically consistent restrictions on the network topology.     

THE CONVERGENCE OF BROYDEN ALGORITHMS FOR LC GRADIENT FUNCTION

1. IntroductionWe know that the variable metric algorithms, such as the Broyden algorithms, are veryefficient methods for solving the nonlinear programming problem:With exact line search, [11 proved that all the Broyden algorithms produce the same iterations for general functions. [21 proved that the rate of convergellce of these algorithms isone-step superlinear for the uniformly convex object function, and [3] proved that if thepoints given by these algorithms are convergent they are globall…     

Optimization problems for nonstationary wave processes

We give a general formulation of the optimization problem for nonstationary hyperbolic systems. Gradient algorithms are used for a directed numerical search. The adjoint problem is obtained in general form in order to compute the gradient. We prove that the types and characteristics of the direct and adjoint problems are the same. We recommend the use of identical total count difference schemes to solve both problems. Translated fromTeoreticheskaya i Prikladnaya Mekhanika, No. 24, 1993, pp. 89–93.     

The analysis of the stability of some integer programming algorithms with respect to the objective function

In this paper we define the notion of the stability with respect to the objective function for a wide class of integer linear programming algorithms. We study the stability of some of them under small variations of coefficients in the objective function. We prove the existence of both stable and unstable versions of the L-class enumeration algorithms. We show that some branch and bound algorithms, as well as some decomposition algorithms with Benders cuts, are unstable. We propose a modification of the considered decomposition algorithms that makes the latter stable with respect to the objective function.     

一类带非精确线搜索的修改的Broyden算法

对于文（８）和（１４）中提出的修改的Ｂｒｏｙｄｅｎ算法，本文讨论它在线搜索非精确时的收敛性质，证明这类算法作用于梯度满足Ｌｉｐｓｃｈｉｔｚ条件的目标函数时是整体收敛的，当目标函数一致凸时，算法是Ｑ－超线性收敛和二阶收敛的。     

Schwarz methods for inequalities with contraction operators

We prove the convergence of some multiplicative and additive Schwarz methods for inequalities which contain contraction operators. The problem is stated in a reflexive Banach space and it generalizes the well-known fixed-point problem in the Hilbert spaces. Error estimation theorems are given for three multiplicative algorithms and two additive algorithms. We show that these algorithms are in fact Schwarz methods if the subspaces are associated with a decomposition of the domain. Also, for the one- and two-level methods in the finite element spaces, we write the convergence rates as functions of the overlapping and mesh parameters. They are similar with the convergence rates of these methods for linear problems. Besides the direct use of the five algorithms for the inequalities with contraction operators, we can use the above results to obtain the convergence rate of the Schwarz method for other types of inequalities or nonlinear equations. In this way, we prove the convergence and estimate the error of the one- and two-level Schwarz methods for some inequalities in Hilbert spaces which are not of the variational type, and also, for the Navier–Stokes problem. Finally, we give conditions of existence and uniqueness of the solution for all problems we consider. We point out that these conditions and the convergence conditions of the proposed algorithms are of the same type.     

A Class of Modified Broyden Algorithms

S1.IntroductionWeknowthatthevariablemetricalgorithms,suchastheBroydenalgorithms,areveryusefulandefficientmethodsforsolvingthenonlinearprogrammingproblem'min{f(x);xER"}-(1.1)Withexactlinearsearch,Powell(1971)provesthattherateofconvergenceofthesealgorithmsisone-stepsuperlinearfortheuniformlyconvexobjectivefunction,andifthepointsgivenbytheseaJgorithmsareconvergent,PuandYu(199o)provethattheyaregloballyconvergentforthecontinuousdifferentiablefunction.Withoutexactlinearsearchseveralresultshavebee…     

Convergence Estimates of Multilevel Additive and Multiplicative Algorithms for Non-symmetric and Indefinite Problems

New uniform estimates for multigrid algorithms are established for certain non-symmetric indefinite problems. In particular, we are concerned with the simple additive algorithm and multigrid (V(1,0)-cycle) algorithms given in [5]. We prove, without full elliptic regularity assumption, that these algorithms have uniform reduction per iteration, independent of the finest mesh size and number of refinement levels, provided that the coarsest mesh size is sufficiently small.     

Absorbing sets of homogeneous subtractive algorithms

We consider homogeneous multidimensional continued fraction algorithms, in particular a family of maps which was introduced by F. Schweiger. We prove his conjecture regarding the existence of an absorbing set for those maps. We also establish that their renormalisations are nonergodic which disproves another conjecture due to Schweiger. Other homogeneous algorithms are also analysed including ones which are ergodic.     

Neighborhood-following algorithms for linear programming

In this paper, we present neighborhood-following algorithms for linear programming. When the neighborhood is a wide neighborhood, our algorithms are wide neighborhood primal-dual interior point algorithms. If the neighborhood degenerates into the central path, our algorithms also degenerate into path-following algorithms. We prove that our algorithms maintain the O(n~(1/2)L)-iteration complexity still, while the classical wide neighborhood primal-dual interior point algorithms have only the O(nL)-iteration complexity. We also proved that the algorithms are quadratic convergence if the optimal vertex is nondegenerate. Finally, we show some computational results of our algorithms.     

Weak Convergence of Greedy Algorithms in Banach Spaces

We study the convergence of certain greedy algorithms in Banach spaces. We introduce the WN property for Banach spaces and prove that the algorithms converge in the weak topology for general dictionaries in uniformly smooth Banach spaces with the WN property. We show that reflexive spaces with the uniform Opial property have the WN property. We show that our results do not extend to algorithms which employ a ‘dictionary dual’ greedy step.     

Estimates of the Rate of Convergence of Runge–Kutta-Type Algorithms with Random Errors and with Consideration of the Calculation Time

We study conditions for the convergence of new types of algorithms, the recurrence algorithms with random calculation time and random errors, by using limit theorems for processes with semi-Markov switches. We prove theorems of the averaging-principle type. Concrete applications to numerical procedures of Runge–Kutta-type are obtained.     

<Emphasis Type="Italic">C</Emphasis><Superscript>0</Superscript>IPG adaptive algorithms for the biharmonic eigenvalue problem

This paper focuses on C ⁰IPG adaptive algorithms for the biharmonic eigenvalue problem with the clamped boundary condition. We prove the reliability and efficiency of the a posteriori error indicator of the approximating eigenfunctions and analyze the reliability of the a posteriori error indicator of the approximating eigenvalues. We present two adaptive algorithms, and numerical experiments indicate that both algorithms are efficient.     

Cubically convergent methods for selecting the regularization parameters in linear inverse problems

We present three cubically convergent methods for choosing the regularization parameters in linear inverse problems. The detailed algorithms are given and the convergence rates are estimated. Our basic tools are Tikhonov regularization and Morozov's discrepancy principle. We prove that, in comparison with the standard Newton method, the computational costs for our cubically convergent methods are nearly the same, but the number of iteration steps is even less. Numerical experiments for an elliptic boundary value problem illustrate the efficiency of the proposed algorithms.     

Duality theorems and algorithms for linear programming in measure spaces

The purpose of this paper is to present some results on linear programming in measure spaces (LPM). We prove that, under certain conditions, the optimal value of an LPM is equal to the optimal value of the dual problem (DLPM). We also present two algorithms for solving various LPM problems and prove the convergence properties of these algorithms.     

Duality theorems and algorithms for linear programming in measure spaces

The purpose of this paper is to present some results on linear programming in measure spaces (LPM). We prove that, under certain conditions, the optimal value of an LPM is equal to the optimal value of the dual problem (DLPM). We also present two algorithms for solving various LPM problems and prove the convergence properties of these algorithms.     

Isomorphic scheduling problems

We consider general properties of isomorphic scheduling problems that constitute a new class of pairs of mutually related scheduling problems. Any such a pair is composed of a scheduling problem with fixed job processing times and its time-dependent counterpart with processing times that are proportional-linear functions of the job starting times. In order to introduce the class formally, first we formulate a generic scheduling problem with fixed job processing times and define isomorphic problems by a one-to-one transformation of instances of the generic problem into instances of time-dependent scheduling problems with proportional-linear job processing times. Next, we prove basic properties of isomorphic scheduling problems and show how to convert polynomial algorithms for scheduling problems with fixed job processing times into polynomial algorithms for proportional-linear counterparts of the original problems. Finally, we show how are related approximation algorithms for isomorphic problems. Applying the results, we establish new worst-case results for time-dependent parallel-machine scheduling problems and prove that many single- and dedicated-machine time-dependent scheduling problems with proportional-linear job processing times are polynomially solvable.     

Extragradient Methods for Solving Equilibrium Problems,Variational Inequalities,and Fixed Point Problems

In this paper, we propose the new extragradient algorithms for an α-inverse-strongly monotone operator and a relatively nonexpansive mapping in Banach spaces. We prove convergence theorems by this methods under suitable conditions. Applying our algorithms, we find a zero paint of maximal monotone operators. Using FMINCON optimization toolbox in MATLAB, we give an example to illustrate the usability of our results.     

Iterative algorithms with variable anchors for non-expansive mappings

In this paper, we suggest and analyze some new iterative algorithms with variable anchors for non-expansive mapping in Banach spaces. We prove that the proposed iterative algorithms converge strongly to a fixed point of some non-expansive mapping. We also obtain some corollaries which include some results as special cases. Furthermore, we conclude the strong convergence of the so-called viscosity iterative algorithms.     

Computing the volume,counting integral points,and exponential sums

We design polynomial-time algorithms for some particular cases of the volume computation problem and the integral points counting problem for convex polytopes. The basic idea is a reduction to the computation of certain exponential sums and integrals. We give elementary proofs of some known identities between these sums and integrals and prove some new identities. This research was partially supported by the Mittag-Leffler Institute.