This is the BibTeX database of all papers and reports published by the participants to the Italian FIRB research project PN2O - Parallel Algorithms and Numerical Nonlinear Optimization For all details see the project homepage at http://dm.unife.it/pn2o. References sorted by year in descending order. Last updated: March 15, 2007. @Article{GL-07, author = "Gaviano, Marco and Lera, Daniela", title = "A global minimization algorithm for {L}ipschitz functions", journal = "Optimization Letters", year = "2007", volume = "to appear", abstract = "The global optimization problem min $f(x)$ subject to $x\in S=[a,b]$ with $a,b \in R^n$ that satisfies the Lipschitz condition (i) $|f(x) - f(y)| \leq L \| x-y \|_{\infty}$ for all $x,y \in S$, $L>0$, is considered. To solve it a new algorithm is introduced. This combines a local minimum algorithm with a procedure that decreases the measure of the region where the global minimum is located. Specifically, by making use of the condition (i), at each iteration of the algorithm it is constructed a sequence of intervals $s_j$, $s_j \subset S$, with the property that a global minimum is not contained in the union of all the $s_j$. A convergence property of the algorithm is given.", } @Article{L-07, author = "Landi, Germana", title = "The {L}agrange Method for the Regularization of Discrete Ill-Posed Problems", journal = "Computational Optimization and Applications (special issue)", year = "2007", volume = "to appear", abstract = "In many science and engineering applications, the discretization of linear ill-posed problems gives rise to large ill-conditioned linear systems with the right-hand side degraded by noise. The solution of such linear systems requires the solution of minimization problems with one quadratic constraint, depending on an estimate of the variance of the noise. This strategy is known as regularization. In this work, we propose a modification of the Lagrange method for the solution of the noise constrained regularization problem. We present the numerical results of test problems, image restoration and medical imaging denoising. Our results indicate that the proposed Lagrange method is effective and efficient in computing good regularized solutions of ill-conditioned linear systems and in computing the corresponding Lagrange multipliers. Moreover, our numerical experiments show that the Lagrange method is computationally convenient. Therefore, the Lagrange method is a promising approach for dealing with ill-posed problems.", } @Article{S-07a, author = "Sergeyev, Yaroslav D.", title = "Measuring fractals by infinite and infinitesimal numbers", journal = "Mathematical Methods, Physical Models \& Simulation in Science and Technology", year = "2007", pages = "to appear", abstract = "Traditional mathematical tools used for analysis of fractals allow one to distinguish results of self-similarity processes after a finite number of iterations. For example, the result of procedure of construction of Cantor?s set after two steps is different from that obtained after three steps. However, we are not able to make such a distinction at infinity. It is shown in this paper that infinite and infinitesimal numbers proposed recently allow one to measure results of fractal processes at different iterations at infinity too. First, the new technique is used to measure at infinity sets being results of Cantor?s procedure. Second, it is applied to calculate the lengths of polygonal geometric spirals at different points of infinity.", } @Article{S-07b, author = "Sergeyev, Yaroslav D.", title = "Blinking fractals and their quantitative analysis using infinite and infinitesimal numbers", journal = "Chaos, Solitons \& Fractals", year = "2007", volume = "33", pages = "50--75", number = "1", abstract = "The paper considers a new type of objects - blinking fractals - that are not covered by traditional theories studying dynamics of self-similarity processes. It is shown that the new approach allows one to give various quantitative characteristics of the newly introduced and traditional fractals using infinite and infinitesimal numbers proposed recently. In this connection, the problem of the mathematical modelling of continuity is discussed in detail. A strong advantage of the introduced computational paradigm consists of its well-marked numerical character and its own instrument - Infinity Computer - able to execute operations with infinite and infinitesimal numbers.", } @InBook{SKK-07b, chapter = "Univariate Algorithms for Solving Global Optimization Problems with Multiextremal Non-Differentiable Constraint", pages = "123--140", title = "Models and Algorithms for Global Optimization", publisher = "Springer", year = "2007", editor = "T{\"{o}}rn, A. and {\v{Z}}ilinskas, J.", author = "Sergeyev, Yaroslav D. and Khalaf, Falah M. H. and Kvasov, Dmitri E.", volume = "4", series = "Springer Optimization and Its Applications", abstract = "In this paper, Lipschitz univariate constrained global optimization problems where both the objective function and constraints can be multiextremal and non-differentiable are considered. The constrained problem is reduced to a discontinuous unconstrained problem by the index scheme without introducing additional parameters or variables. It is shown that the index approach proposed by R.G. Strongin for solving these problems in the framework of stochastic information algorithms can be successfully extended to geometric algorithms constructing non-differentiable discontinuous minorants for the reduced problem. A new geometric method using adaptive estimates of Lipschitz constants is described and its convergence conditions are established. Numerical experiments including comparison of the new algorithm with methods using penalty approach are presented.", } @Article{SKK-07a, author = "Sergeyev, Yaroslav D. and Kvasov, Dmitri E. and Khalaf, Falah M. H.", title = "A One-Dimensional Local Tuning Algorithm for Solving {GO} Problems with Partially Defined Constraints", journal = "Optimization Letters", year = "2007", volume = "1", pages = "85--99", number = "1", abstract = "Lipschitz one-dimensional constrained global optimization (GO) problems where both the objective function and constraints can be multiextremal and non-differentiable are considered in this paper. Problems, where the constraints are verified in a priori given order fixed by the nature of the problem are studied. Moreover, if a constraint is not satisfied at a point, then the remaining constraints and the objective function can be undefined at this point. The constrained problem is reduced to a discontinuous unconstrained problem by the index scheme without introducing additional parameters or variables. A new geometric method using adaptive estimates of local Lipschitz constants is introduced. The estimates are calculated by using the local tuning technique proposed recently. Numerical experiments show quite a satisfactory performance of the new method in comparison with the penalty approach and a method using a priori given Lipschitz constants.", } @Unpublished{B-06, author = "Bonettini, Silvia", title = "Some Preconditioned Conjugate Gradient Algorithms for the Solution of Equality Constrained Quadratic Programming Problems", year = "2006", abstract = "In this paper we consider the application of the preconditioned conjugate gradient (PCG) method to the solution of equality constrained quadratic programming problems. In particular, we consider three different PCG algorithms and two indefinite preconditioners. A special attention is given to the choice of the factorization method for the preconditioner. The numerical experiments show a comparison of the effectiveness of the proposed variants. Furthermore, we show the behaviour of the PCG method for the solution of the inner subproblem arising at each step of an interior point algorithm for the solution of nonlinear programming problems.", notes = "submitted", } @Article{BGR-06, author = "Bonettini, Silvia and Galligani, Emanuele and Ruggiero, Valeria", title = "Inner solvers for interior point methods for large scale nonlinear programming", journal = "Computational Optimization and Applications", year = "2006", volume = "to appear", pages = "Tech. Rep. 64, University of Modena and Reggio Emilia, Italy", abstract = "This paper deals with the solution of nonlinear programming problems arising from elliptic control problems by an interior point scheme. At each step of the scheme, we have to solve a large scale symmetric and indefinite system; inner iterative solvers, with adaptive stopping rule, can be used in order to avoid unnecessary inner iterations, especially when the current outer iterate is far from the solution. In this work, we analyze the method of multipliers and the preconditioned conjugate gradient method as inner solvers for interior point schemes. We discuss on the convergence of the whole approach, on the implementation details and we report results of a numerical experimentation on a set of large scale test problems arising from the discretization of elliptic control problems. A comparison with other interior point codes is also reported.", } @TechReport{BRT-06, author = "Bonettini, Silvia and Ruggiero, Valeria and Tinti, Federica", title = "On the solution of indefinite systems arising in nonlinear optimization", institution = "Department of Mathematics, University of Ferrara", year = "2006", number = "359", abstract = "We consider the application of the preconditioned conjugate gradient ({PCG}) method to the solution of indefinite linear systems arising in nonlinear optimization. Our approach is based on the choice of quasidefinite preconditioners and of a suitable factorization routine. Some theoretical and numerical results about these preconditioners are obtained. Furthermore, we show the behaviour of the {PCG} method for different representations of the indefinite systems and we compare the effectiveness of the proposed variants.", } @Article{BT-06, author = "Bonettini, Silvia and Tinti, Federica", title = "A nonmonotone semismooth inexact {N}ewton method", journal = "Optimization Methods and Software", year = "2006", volume = "to appear", abstract = "In this work we propose a variant of the inexact Newton method for the solution of semismooth nonlinear systems of equations. We introduce a nonmonotone scheme, which couples the inexact features with the nonmonotone strategies. For the nonmonotone scheme, we present the convergence theorems. Finally, we show how we can apply these strategies in the variational inequalities context and we present some numerical examples.", } @Article{CPS-06, author = "Carotenuto, L. and Pugliese, P. and Sergeyev, Yaroslav D.", title = "Maximizing performance and robustness of {PI} and {PID} controllers by global optimization", journal = "International Journal of Control and Intelligent Systems", year = "2006", volume = "34", pages = "225--235", number = "3", abstract = "This paper reports a new algorithm for global constrained optimization and shows its application to the design of PI and PID controllers. The algorithm is described in detail, and the features that make it suited for controller design are emphasized. Various design criteria and constraints are considered, for some plant models currently used as benchmarks. The numerical results show that the algorithm performs very well in all the tested cases: its flexibility and ease of use make it a valuable alternative to classical design procedures.", } @InProceedings{KKS-06, author = "Khalaf, Falah M. H. and Kvasov, Dmitri E. and Sergeyev, Yaroslav D.", title = "One-dimensional global optimization problems with multiextremal constraints", booktitle = "Proc.\ of the {VIII} Congress of the Italian Society for Applied and Industrial Mathematics {SIMAI}-2006", year = "2006", pages = "184", abstract = "Lipschitz univariate constrained global optimization problems where both the objective function and constraints can be multiextremal and non-differentiable are considered. The constrained problem is reduced to a discontinuous unconstrained problem by the index scheme without introducing additional parameters or variables. A new geometric method using adaptive estimates of Lipschitz constants is described, its convergence conditions are established. Numerical experiments including comparison of the new algorithm with methods using penalty approach are given. Algorithms with local tuning technique on behavior of both the objective function and constraints are considered.", } @InProceedings{KS-06, author = "Kvasov, Dmitri E. and Sergeyev, Yaroslav D.", title = "Global search based on efficient diagonal partitions and several techniques based on {L}ipschitz condition", booktitle = "Proceedings of the 3rd International Conference on Applied Mathematics {TICAM}", year = "2006", editor = "Bainov, D. and Nenov, S.", volume = "2", pages = "164--165", address = "Plovdiv, Bulgaria", abstract = "In this talk, we consider a global optimization problem of a multidimensional {``}black-box{''} function satisfying the Lipschitz condition over a hyperinterval with an unknown Lipschitz constant. Several techniques for obtaining the Lipschitz information are discussed and a novel technique balancing usage of local and global information during the search is proposed. A new efficient algorithm for solving this problem is presented.", } @Article{L-06, author = "Landi, Germana", title = "A Fast Truncated {L}agrange Method for Large-Scale Image Restoration Problems", journal = "Applied Mathematics and Computation", year = "2006", volume = "to appear", abstract = "In this work, we present a new method for the restoration of images degraded by noise and spatially invariant blur. In the proposed method, the original image restoration problem is replaced by an equality constrained minimization problem. A quasi-Newton method is applied to the first-order optimality conditions of the constrained problem. In each Newton iteration, the hessian of the lagrangian is approximated by a circulant matrix and the Fast Fourier Transform is used to compute the Newton step. The quasi-Newton iteration is terminated according to the discrepancy principle. Results of numerical experiments are presented to illustrate the effectiveness and usefulness of the proposed method.", } @Article{LL-06, author = "Landi, Germana and Loli Piccolomini, Elena", title = "Representation of high resolution images from low sampled {F}ourier data. Applications to dynamic {MRI}", journal = "Journal of Mathematical Imaging and Vision", year = "2006", volume = "26", pages = "27--40", number = "1--2", abstract = "In this work we propose the use of B-spline functions for the parametric representation of high resolution images from low sampled data in the Fourier domain. Traditionally, exponential basis functions are employed in this situation, but they produce artifacts and amplify the noise on the data. We present the method in an algorithmic form and carefully consider the problem of solving the ill-conditioned linear system arising from the method by an efficient regularization method. Two applications of the proposed method to dynamic Magnetic Resonance images are considered. Dynamic Magnetic Resonance acquires a time series of images of the same slice of the body; in order to fasten the acquisition, the data are low sampled in the Fourier space. Numerical experiments have been performed both on simulated and real Magnetic Resonance data. They show that the B-splines reduce the artifacts and the noise in the representation of high resolution Magnetic Resonance images from low sampled data.", } @Article{LZ-06, author = "Landi, Germana and Zama, Fabiana", title = "The active-set method for nonnegative regularization of linear ill-posed problems", journal = "Applied Mathematics and Computation", year = "2006", volume = "175", pages = "715--729", number = "1", abstract = "In this work, we analyze the behavior of the Active-Set method for the nonnegative regularization of discrete ill-posed problems. In many applications, the solution of a linear ill-posed problem is known to be nonnegative. Standard Tikhonov regularization often provides an approximated solution with negative entries. We apply the Active-Set method to find a nonnegative approximate solution of the linear system starting from the Tikhonov regularized one. Our numerical experiments show that the Active-Set method is effective in reducing the oscillations in the Tikhonov regularized solution and in providing a nonnegative regularized solution of the original linear system.", } @Article{MRSZ-06, author = "Morigi, Serena and Reichel, L. and Sgallari, Fiorella and Zama, Fabiana", title = "Iterative methods for ill-posed problems and semiconvergent sequences", journal = "Journal of Computational and Applied Mathematics", year = "2006", volume = "193", pages = "157--167", abstract = "Iterative schemes, such as {LSQR} and {RRGMRES}, are among the most efficient methods for the solution of large-scale ill-posed problems. The iterates generated by these methods form semiconvergent sequences. A meaningful approximation of the desired solution of an ill-posed problem often can be obtained by choosing a suitable member of this sequence. However, it is not always a simple matter to decide which member to choose. Semiconvergent sequences also arise when approximating integrals by asymptotic expansions, and considerable experience and analysis of how to choose a suitable member of a semiconvergent sequence in this context are available. The present note explores how the guidelines developed within the context of asymptotic expansions can be applied to iterative methods for ill-posed problems.", } @Article{RT-06, author = "Ruggiero, Valeria and Tinti, Federica", title = "A preconditioner for solving large scale variational inequality problems", journal = "International Journal of Computer Mathematics", year = "2006", volume = "83", pages = "723--739", number = "10", abstract = "The numerical solution of a large scale variational inequality problem can be obtained using the generalisation of an Inexact Newton method applied to a semismooth nonlinear system. This approach requires a sparse and large linear system to be solved at each step. In this work we obtain an approximate solution of this system by the LSQR algorithm of Paige and Saunders combined with a convenient preconditioner that is a variant of the incomplete LU-factorization. Since the computation of the factorization of the preconditioning matrix can be very expensive and memory consuming, we propose a preconditioner that admits block--factorization. Thus the direct factorization is only applied to submatrices of smaller sizes. Numerical experiments on a set of test-problems arising from the literature show the effectiveness of this approach.", } @Article{S-06a, author = "Sergeyev, Yaroslav D.", title = "Univariate global optimization with multiextremal non-differentiable constraints without penalty functions", journal = "Computational Optimization and Applications", year = "2006", volume = "34", pages = "229--248", number = "2", abstract = "This paper proposes a new algorithm for solving constrained global optimization problems where both the objective function and constraints are one-dimensional non-differentiable multiextremal Lipschitz functions. Multiextremal constraints can lead to complex feasible regions being collections of isolated points and intervals having positive lengths. The case is considered where the order the constraints are evaluated is fixed by the nature of the problem and a constraint i is defined only over the set where the constraint i-1 is satisfied. The objective function is defined only over the set where all the constraints are satisfied. In contrast to traditional approaches, the new algorithm does not use any additional parameter or variable. All the constraints are not evaluated during every iteration of the algorithm providing a significant acceleration of the search. The new algorithm either finds lower and upper bounds for the global optimum or establishes that the problem is infeasible. Convergence properties and numerical experiments showing a nice performance of the new method in comparison with the penalty approach are given.", } @InProceedings{S-06b, author = "Sergeyev, Yaroslav D.", title = "Finding the minimal root of an equation: applications and algorithms based on {L}ipschitz condition", booktitle = "Global Optimization -- Scientific and Engineering Case Studies", year = "2006", editor = "Pint{\'{e}}r, J. D.", pages = "441--460", publisher = "Springer", note = "Invited survey", abstract = "In this survey the problem of finding the minimal root to an equation is discussed. It is supposed that the equation under consideration can have many roots. In the case when the Lipschitz constant for the objective function or its first derivative is known a priori, two methods based on global optimization ideas are presented. The algorithms either find the minimal root or determine the global minimizers (in the case when the objective function has no roots). If the Lipschitz constants are unknown, there are introduced two methods adaptively estimating local Lipschitz constants during the search. This approach allows us to accelerate the search in comparison with the case with known a priori Lipschitz constants. Sufficient conditions for convergence of the new methods to the desired solution are established.", } @Article{SK-06, author = "Sergeyev, Yaroslav D. and Kvasov, Dmitri E.", title = "Global search based on efficient diagonal partitions and a set of {L}ipschitz constants", journal = "{SIAM} Journal on Optimization", year = "2006", volume = "16", pages = "910--937", number = "3", abstract = "In the paper, the global optimization problem of a multidimensional {``}black-box{''} function satisfying the Lipschitz condition over a hyperinterval with an unknown Lipschitz constant is considered. A new efficient algorithm for solving this problem is presented. At each iteration of the method a number of possible Lipschitz constants are chosen from a set of values varying from zero to infinity. This idea is unified with an efficient diagonal partition strategy. A novel technique balancing usage of local and global information during partitioning is proposed. A new procedure for finding lower bounds of the objective function over hyperintervals is also considered. It is demonstrated by extensive numerical experiments performed on more than 1600 multidimensional test functions that the new algorithm shows a very promising performance.", } @Article{SS-06a, author = "Sofroniou, Marc and Spaletta, Giulia", title = "Hybrid solvers for splitting and composition methods", journal = "Journal of Computational and Applied Mathematics", year = "2006", volume = "185", pages = "278--291", number = "2", abstract = "Composition and splitting are useful techniques for constructing special purpose integration methods for numerically solving many types of differential equations. In this article we will review these methods and summarise the essential ingredients of an implementation that has recently been added to a framework for solving differential equations in {M}athematica.", } @Article{SS-06b, author = "Sofroniou, Marc and Spaletta, Giulia", title = "Rounding error reduction in extrapolation method", journal = "Journal of Numerical Analysis, Industrial and Applied Mathematics, special issue {``}{N}umerical Computing in Problem Solving Environments{''}", year = "2006", volume = "to appear", abstract = "Extrapolation methods are very efficient when high accuracy is desired in a numerical solution of an ordinary differential equation. High order methods can suffer from cumulative rounding error propagation. A new formulation for reducing the effect of cumulative rounding errors is outlined here and numerical examples are given to illustrate the benefits over the standard formalism.", } @Article{SS-06c, author = "Sofroniou, Marc and Spaletta, Giulia", title = "Efficient computation of Krylov approximations to the matrix exponential and related functions", journal = "IMACS Journal, special issue {``}{S}tructural Dynamical Systems: Computational Aspects{''} (L.~Lopez, ed.)", year = "2006", volume = "to appear", note = "Invited paper", abstract = "In recent years there has been growing interest in the use of exponential integrators for solving large scale problems. Exponential integrators involve approximations to the exponential and related phi functions. Krylov subspace approximations to the exponential typically exhibit better convergence than those used in solving the linear systems that arise in conventional stiff integrators. In this work, we begin by revising the ideas used in {EXPOKIT} [Sidje R. B., {EXPOKIT}: A software package for computing matrix exponentials, {ACM} Trans.\ Math.\ Soft. 24(1) (1998), 130--156], which is perhaps the most complete software for computing the matrix exponential. We will then outline some new results which allow the computation of linear sums of phi functions acting on vectors at virtually the same cost as the computation of the matrix exponential itself. We then describe issues relating to error control and describe an enhancement that is particularly relevant to applications involving exponential integrators.", } @Article{Sp-06, author = "Spaletta, Giulia", title = "Reconstruction in Space and Visualization of a Planar Image: a Mathematical and Computational Introduction", journal = "Acta Biomedica", year = "2006", volume = "to appear", note = "Invited review", abstract = "Aim of this paper is to provide an introduction to the fundamental mathematical ideas involved in tridimensional image reconstruction. Particular attention is given to the case in which the bidimensional input data are represented of one or very few echographic or scintigraphic images.", } @Article{SC-06, author = "Spaletta, Giulia and Caucci, L.", title = "Constrained Iterations for Blind Deconvolution and Convexity Issues", journal = "Journal of Computational and Applied Mathematics", year = "2006", volume = "197", pages = "29--43", number = "1", abstract = "The need for image restoration arises in many applications of various scientific disciplines, such as medicine and astronomy and, in general, whenever an unknown image must be recovered from blurred and noisy data. The algorithm studied in this work restores the image without the knowledge of the blur, using little a priori information and a blind inverse filter iteration. The problem of interest here is an inverse one, that cannot be solved by simple filtering since it is ill posed. The imaging system is assumed to be linear and space invariant: this allows a simplified relationship between unknown and observed images, described by a 'point spread function' modeling the distortion. The blurring, though, makes the restoration ill conditioned: regularization is therefore also needed, obtained by adding constraints to the formulation. The restoration is modeled as a constrained minimization: particular attention is given here to the analysis of the objective function and on establishing whether or not it is a convex function, whose minima can be located by classic optimization techniques and descent methods.", } @Article{T-06, author = "Tinti, Federica", title = "Comparing two numerical approaches for solving variational inequality problems", year = "2006", volume = "submitted", abstract = "The numerical solution of a large scale variational inequality problem can be obtained using an Inexact Newton Method, or a generalization of it, to nonlinear system. In this work we compare two approaches: in the ¯rst one we solve a smooth nonlinear system using an interior point approach while in the second one we solve a nonsmooth nonlinear system using an semismooth approach. Both approaches require a sparse and large linear system to be solved at each step. We obtain an approximate solution of these systems by the LSQR algorithm of Paige and Saunders combined with a convenient preconditioner. We compare the two algorithms related to the two approaches. Numerical experiments on a set of test-problems arising from the literature show the effectiveness of the two methods.", } @Article{Z-06, author = "Zanni, Luca", title = "An improved gradient projection-based decomposition technique for support vector machines", journal = "Computational Management Science", year = "2006", volume = "3", pages = "131--145", number = "2", abstract = "In this paper we propose some improvements to a recent decomposition technique for the large quadratic program arising in training Support Vector Machines. As standard decomposition approaches, the technique we consider is based on the idea to optimize, at each iteration, a subset of the variables through the solution of a quadratic programming subproblem. The innovative features of this approach consist in using a very effective gradient projection method for the inner subproblems and a special rule for selecting the variables to be optimized at each step. These features allow to obtain promising performance by decomposing the problem into few large subproblems instead of many small subproblems as usually done by other decomposition schemes. We improve this technique by introducing a new inner solver and a simple strategy for reducing the computational cost of each iteration. We evaluate the effectiveness of these improvements by solving large-scale benchmark problems and by comparison with a widely used decomposition package.", } @Article{ZSZ-06b, author = "Zanni, Luca and Serafini, Thomas and Zanghirati, Gaetano", title = "Parallel Software for Training Large Scale Support Vector Machines on Multiprocessor Systems", journal = "Journal of Machine Learning Research", year = "2006", volume = "7", pages = "1467--1492", abstract = "Parallel software for solving the quadratic program arising in training support vector machines for classification problems is introduced. The software implements an iterative decomposition technique and exploits both the storage and the computing resources available on multiprocessor systems, by distributing the heaviest computational tasks of each decomposition iteration. Based on a wide range of recent theoretical advances, relevant decomposition issues, such as the quadratic subproblem solution, the gradient updating, the working set selection, are systematically described and their careful combination to get an effective parallel tool is discussed. A comparison with state-of-the-art packages on benchmark problems demonstrates the good accuracy and the remarkable time saving achieved by the proposed software. Furthermore, challenging experiments on real-world data sets with millions training samples highlight how the software makes large scale standard nonlinear support vector machines effectively tractable on common multiprocessor systems. This feature is not shown by any of the available codes.", } @InProceedings{ZSZ-06a, author = "Zanni, Luca and Serafini, Thomas and Zanghirati, Gaetano", title = "Parallel Training of Large-Scale Kernel Machines", booktitle = "{S}cience and {S}upercomputing at {CINECA}. Report 2005", year = "2006", editor = "Voli, Marco and Coluccia, Patrizia", pages = "415--419", address = "Bologna, Italy", publisher = "Monograf", abstract = "A parallel software to train linear and nonlinear SVMs for classification problems is presented, which is suitable for distributed memory multiprocessor systems. It solves the SVM quadratic programming problem by an iterative decomposition technique based on a well parallelizable gradient-projection solver for the inner subproblems. The numerical experience show the significant speedup that the proposed parallel package can achieve in training large-scale SVMs. The package is available at \url{http://dm.unife.it/gpdt}.", } @Article{B-05, author = "Bonettini, Silvia", title = "A Nonmonotone Inexact {N}ewton Method", journal = "Optimization Methods and Software", year = "2005", volume = "20", pages = "475--491", abstract = "In this paper we describe a variant of the Inexact Newton method for solving nonlinear systems of equations. We define a nonmonotone Inexact Newton step and a nonmonotone backtracking strategy. For this nonmonotone Inexact Newton scheme we present the convergence theorems. Finally, we show how we can apply these strategies to Inexact Newton Interior-Point method and we present some numerical examples.", } @Article{BGR-05, author = "Bonettini, Silvia and Galligani, Emanuele and Ruggiero, Valeria", title = "An Inexact {N}ewton Interior-Point Method Combined with {H}estenes Multipliers' Scheme for the Solution of {K}arush-{K}uhn-{T}ucker systems", journal = "Applied Mathematics and Computation", year = "2005", volume = "168", pages = "651--676", abstract = "This paper deals with the solution of nonlinear programming problems arising from elliptic control problems by {N}ewton Interior-Point method. At each step of the method we have to solve a large scale perturbed Newton system that is symmetric and indefinite; an inner iterative scheme, with adaptive stopping rule, can be used in order to avoid unnecessary inner iterations, especially when the current outer iterate is far from the solution. Under conditions that guarantee the nonsingularity of the matrix of the system and the boundedness of its inverse, the system can be viewed as the Lagrange necessary conditions for the minimum point of a quadratic programming problem and it can be efficiently solved by the iterative {H}estenes multipliers' scheme. This scheme involves at each iteration a solution of a smaller sparse symmetric positive definite system that can be solved by efficient direct sparse solvers. Numerical experiments on elliptic control problems with boundary and distributed control, show the effectiveness of this approach; generally one or two iterations of {H}estenes scheme are sufficient to satisfy the inner stopping rule.", } @Article{BR-05, author = "Bonettini, Silvia and Ruggiero, Valeria", title = "Some iterative methods for the solution of a symmetric indefinite {KKT} system", journal = "Computational Optimization and Applications", year = "2005", volume = "to appear", abstract = "This paper is concerned with the numerical solution of a {K}arush-{K}uhn-{T}ucker system. Such symmetric indefinite system arises when we solve a nonlinear programming problem by an Interior Point ({IP}) approach. In this framework, we discuss the effectiveness of two inner iterative solvers: the method of multipliers and the preconditioned conjugate gradient method. We discuss the implementation details of these algorithms in an {IP} scheme and we report the results of a numerical comparison on a set of large scale test problems arising from the discretization of elliptic control problems.", } @Article{GL-05, author = "Gaviano, Marco and Lera, Daniela", title = "Complexity of general continuous minimization problems: a survey", journal = "Optimization Methods and Software", year = "2005", volume = "20", pages = "525--544", number = "4--5", abstract = "The problem of finding a local or a global minimum of a real function on a subset $S$ of $R^n$ occurs in many real world problems. When $f$ is a general nonlinear function, deterministic as well as stochastic algorithms have been proposed. The numerical \emph{cost} of these algorithms, that can be the number of function evaluations or the number of elementary operations required when executed, has been investigated in the last few years. In this paper we survey the main results by classifying them according to the field they refer to: local minimization, global minimization and checking the optimality conditions. Further, some results concerning the information that an algorithm may use, are surveyed.", } @Article{LL-05, author = "Landi, Germana and Loli Piccolomini, Elena", title = "A Total Variation regularization strategy in dynamic {MRI}", journal = "Optimization Methods and Software", year = "2005", volume = "20", pages = "545--558", number = "4--5", abstract = "Recently, the application of Magnetic Resonance Imaging for the study of dynamic processes has increased the search of ever-faster dynamic imaging methods. The Keyhole method is a popular technique for fast dynamic imaging that unfortunately produces images affected by artifacts. In this work, we propose a Total Variation regularization strategy for post-processing the dynamic Keyhole images. The strategy consists of the solution of an unconstrained minimization problem whose Euler-Lagrange equation is solved by Newton method. A trace of the algorithm is given. Results of numerical experiments on simulated and real data are presented to illustrate the effectiveness of the proposed method. Our experimental results indicate that the method reduces the degrading artifacts and improves the quality of the final images.", } @Article{LLZ-05, author = "Loli Piccolomini, Elena and Landi, Germana and Zama, Fabiana", title = "A {B}-Spline parametric model for high resolution dynamic Magnetic Resonance Imaging", journal = "Applied Mathematics and Computations", year = "2005", volume = "164", pages = "133--148", abstract = "In this paper we propose a numerical method for the reconstruction of dynamic Magnetic Resonance images from limited data in the Fourier space. In some medical dynamic applications, temporal sequences of Magnetic Resonance data of the same slice of the body are acquired. In order to hasten the acquisition process, only the low frequencies are acquired for all the data sets, with the exception of the first one which is completely acquired. Then, it is not possible to use a Fourier technique to obtain high resolution images from limited data. In the proposed method, the images of the sequence are represented via a B-spline parametric model using {\em a priori} information from the first image. The use of B-splines is due to their computational efficiency and their good behaviour in image fitting and representation. The use of this parametric model allows to obtain high resolution images of good quality and zoom regions of interest without loosing important details. Mathematical and numerical aspects of the method are investigated and an outline of the algorithm is given. Reconstructions from simulated and experimental data are presented and analyzed.", } @Article{SZZ-05a, author = "Serafini, Thomas and Zanghirati, Gaetano and Zanni, Luca", title = "Gradient Projection Methods for Quadratic Programs and Applications in Training Support Vector Machines", journal = "Optimization Methods and Software", year = "2005", volume = "20", pages = "347--372", number = "2--3", abstract = "Gradient projection methods based on the Barzilai-Borwein spectral steplength choices are considered for quadratic programming problems with simple constraints. Well-known nonmonotone spectral projected gradient methods and variable projection methods are discussed. For both approaches the behavior of different combinations of the two spectral steplengths is investigated. A new adaptive steplength alternating rule is proposed that becomes the basis for a generalized version of the variable projection method (GVPM). Convergence results are given for the proposed approach and its effectiveness is shown by means of an extensive computational study on several test problems, including the special quadratic programs arising in training support vector machines. Finally, the GVPM behavior as inner QP solver in decomposition techniques for large-scale support vector machines is also evaluated.", } @Article{SZZ-05b, author = "Serafini, Thomas and Zanghirati, Gaetano and Zanni, Luca", title = "Some improvements to a parallel decomposition technique for training support vector machines", journal = "Lecture Notes in Computer Science", year = "2005", volume = "3666", pages = "9--17", abstract = "We consider a parallel decomposition technique for solving the large quadratic programs arising in training the learning methodology Support Vector Machine. At each iteration of the technique a subset of the variables is optimized through the solution of a quadratic programming subproblem. This inner subproblem is solved in parallel by a special gradient projection method. In this paper we consider some improvements to the inner solver: a new algorithm for the projection onto the feasible region of the optimization subproblem and new linesearch and steplength selection strategies for the gradient projection scheme. The effectiveness of the proposed improvements is evaluated, both in terms of execution time and relative speedup, by solving large-scale benchmark problems on a parallel architecture.", } @Article{S-05, author = "Sergeyev, Yaroslav D.", title = "Efficient partition of {N}-dimensional intervals in the framework of one-point-based algorithms", journal = "Journal of Optimization Theory and Applications", year = "2005", volume = "124", number = "2", abstract = "In this paper, the problem of the minimal description of the structure of a vector function f(x) over an N-dimensional interval is studied. Methods adaptively subdividing the original interval in smaller subintervals and evaluating f(x) at only one point within each subinterval are considered. Two partition strategies traditionally used for solving this problem are analyzed. A new partition strategy based on an efficient technique developed for diagonal algorithms is proposed and studied.", } @Article{SS-05c, author = "Sofroniou, Marc and Spaletta, Giulia", title = "Derivation of symmetric composition constants for symmetric integrators", journal = "Optimization Methods and Software", year = "2005", volume = "20", pages = "597--613", number = "4--5", abstract = "This work focuses on the derivation of composition methods for the numerical integration of ordinary differential equations, which give rise to very challenging optimization problems. Composition is a very useful technique for constructing high order approximations whilst conserving certain geometric properties. We survey existing composition methods and describe results of an intensive numerical search for new methods. Details of the search procedure are given along with numerical examples which indicate that the new methods perform better than previously known methods. Some insights into the location of global minima for these problems is obtained as a result.", } @Article{SS-05a, author = "Sofroniou, Marc and Spaletta, Giulia", title = "Complexity Analysis for Accurate Solution of Linear Systems", journal = "International Journal of Computer Mathematics", year = "2005", volume = "to appear", abstract = "The efficient solution of linear systems of equations $A X = B$ is a task that arises in various applied problems. In this work we describe a simplified complexity analysis that reliably shows when iterative solution procedures are advantageous over direct solution methods. The analysis involves an estimate of the condition number of a matrix and can be used to automatically decide at run time which method to use. Accurate solutions are sought, therefore it can be necessary to resort to high precision computations; the cost of linear algebra in high precision, though, can be prohibitively expensive. An established idea for the accurate solution of linear systems is to use iterative refinement (i) compute an initial solution $A X_0 = B$ in precision $p_0$; (ii) compute the residual $R_i = B-A X_i$ in precision $p_i$; (iii) compute a correction $A Z_i = R_i$ in precision $p_0$; (iv) correct the solution $X_{i+1} = X_i + Z_i$ in precision $p_i$. It has been recently shown that a modification of this algorithm can be advantageous for high precision computation [Geddes and Zheng, Exploiting Fast Hardware Floating Point in High Precision Computation, Procs {ISSAC}, 2003, 111--118]. This involves carrying out the linear solution and refinement steps (i) and (iii) using machine precision arithmetic $p_0$. Steps (ii) and (iv) are then performed in monotonically increasing precision $p_i > p_0$, using software arithmetic. Here we also outline a scaling technique that is advantageous when solving for the solution and correction steps using machine precision.", } @Article{SS-05b, author = "Sofroniou, Marc and Spaletta, Giulia", title = "Precise Numerical Computation", journal = "Journal of Logic and Algebraic Programming", year = "2005", volume = "64", pages = "113--134", number = "1", abstract = "Arithmetic systems such as those based on {IEEE} standards currently make no attempt to track the propagation of errors. A formal error analysis, however, can be complicated and is often confined to the realm of experts in numerical analysis. In recent years there has been a resurgence of interest in automated methods for accurately monitoring the error flow. In this work a floating point system based on significance arithmetic, in Mathematica, is described, together with its differences over conventional fixed precision floating point systems.", } @Article{SC-05, author = "Spaletta, Giulia and Caucci, L.", title = "Blind Restoration of Astronomical Images", journal = "{M}ath{S}ource, {Wolfram Media Inc.}, {USA}", year = "2005", pages = "paper and software package available at library.wolfram.com", abstract = "The atmosphere of the earth and the instruments of observation both constitute a source of distortion in astronomical imaging. Assuming linearity and space invariance of the image formation system, the observed image can be expressed as the convolution of the original image with the blurring function: if the latter is known, then we are faced with the inverse problem of classical deconvolution. The restoration algorithms considered here try to remove the blur using a priori constraints, without the knowledge of the blurring function; this approach is often referred to as blind deconvolution. It represents a variation of the methods proposed in [Kundur and Hatzinakos, A Novel Blind Deconvolution Scheme for Image Restoration using Recursive Filtering, {IEEE} Transactions on Signal Processing 46(2) 1998, 375--390] and [Ng, Plemmons and Qiao, Regularization of RIF Blind Image Deconvolution, {IEEE} Transactions on Image Processing 9(6) 2000, 1130--1134]. The programming environment is that of Mathematica. The effectiveness of this class of methods is tested on both simulated and real data derived from various applications. Comparison with the behavior of the methods by Kundur-Hatzinakos and by Ng-Plemmons-Qiao show the effectiveness of our variant.", } @InProceedings{T-05, author = "Tinti, Federica", title = "Numerical Solution for Pseudomonotone Variational Inequality Problems by Extragradient Methods", booktitle = "Variational Inequality and Application", year = "2005", editor = "Maugeri, Antonino and Giannessi, Franco", pages = "1101--1128", publisher = "Springer", abstract = "In this work we analyze from the numerical viewpoint the class of projection methods for solving pseudomonotone variational inequality problems. We focus on some specific extragradient-type methods that do not require differentiability of the operator and we address particular attention to the steplength choice. Subsequently, we analyze the hyperplane projection methods in which we construct an appropriate hyperplane which strictly separates the current iterate from the solutions of the problem. Finally, in order to illustrate the effectiveness of the proposed methods, we report the results of a numerical experimentation.", } @Article{ZL-05, author = "Zama, Fabiana and Loli Piccolomini, Elena", title = "A descent method for regularization of ill-posed problems", journal = "Optimization Methods and Software", year = "2005", volume = "20", pages = "615--625", number = "4--5", abstract = "In this paper we describe an iterative algorithm, called Descent-{TCG}, based on truncated Conjugate Gradients iterations to compute Tikhonov regularized solutions of ill-posed problems. The succession of approximatesolutions and regularization parameters, computed by the algorithm, is shown to decrease the value of the Tikhonov functional. Suitable termination criteria are built-up to define an inner-outer iteration scheme that computes a regularized solution. Numerical experiments are performed to compare this algorithm with other well established regularization methods. We observe that Descent-{TCG} has best results when the noise is high and always computes fairly reliable solutions, preventing dangerous error explosions as in other well established regularization methods. Finally, the Descent-{TCG} method is computationally advantageous especially for large size problems.", } @Article{BGR-04, author = "Bonettini, Silvia and Galligani, Emanuele and Ruggiero, Valeria", title = "{H}estenes' Method for Symmetric Indefinite Systems in Interior-Point Method", journal = "Rendiconti di Matematica e delle sue Applicazioni, Univerit{\`{a}} di {R}oma {``La Sapienza''}, Serie {VII}", year = "2004", volume = "24", pages = "185--199", abstract = "This paper deals with the analysis and the solution of the Karush-Kuhn-Tucker ({KKT}) system that arises at each iteration of an Interior-Point ({IP}) method for minimizing a nonlinear function subject to equality and inequality constraints. This system is generally large and sparse and it can be reduced so that the coefficient matrix is still sparse, symmetric and indefinite, with size equal to the number of the primal variables and of the equality constraints. Instead of transforming this reduced system to a quasidefinite form by regularization techniques used in available codes on {IP} methods, under standard assumptions on the nonlinear problem, it can be viewed as the optimality Lagrange conditions for an linear equality constrained quadratic programming problem, so that {H}estenes multipliers' method can be applied. Numerical experiments on elliptic control problems with boundary and distributed control show the effectiveness of Hestenes scheme as inner solver for {IP} methods.", } @Article{DR-04, author = "Durazzi, Carla and Ruggiero, Valeria", title = "A Note on the Global Convergence of the {N}ewton Interior-Point Method for Nonlinear Programming", journal = "J.\ Optimization Theory and Applications", year = "2004", volume = "120", pages = "188--208", number = "1", abstract = "The aim of this paper is to show that the theorem on the global convergence of the Newton Interior-Point (IP) method presented in El-Bakry A.S., Tapia R.A. et al., JOTA (1996) can be proved under weaker assumptions. Indeed, we assume the boundedness of the sequences of the multipliers related to nontrivial constraints instead of the hypothesis that the gradients of those inequality constraints corresponding to slack variables not bounded away from zero, are linear independent. Consequently, by some numerical examples we show that, in the implementation of the Newton IP method, the loss of the boundedness of the iteration sequence of the multipliers detects when the algorithm does not converge from the chosen starting point.", } @Article{FPS-04, author = "Famularo, D. and Pugliese, P. and Sergeyev, Yaroslav D.", title = "A global optimization technique for fixed-order control design", journal = "International Journal of Systems Science", year = "2004", volume = "35", pages = "425--434", number = "7", abstract = "A global optimization algorithm is used to solve the fixed-order controller synthesis problem for linear systems. The algorithm, which belongs to the information methods family, is described in some detail and numerical experiments are performed on test problems to show its effectiveness.", } @InProceedings{LLZ-04, author = "Landi, Germana and Loli Piccolomini, Elena and Zama, Fabiana", title = "A Total Variation based regularization strategy in Magnetic Resonance Imaging", booktitle = "Proccedings of {SPIE}", year = "2004", editor = "Bones, P. J. and Fiddy, M. A. and Millane, R. P.", volume = "5562", abstract = "In this paper we present some variational functionals for the regularization of Magnetic Resonance (MR) images, usually corrupted by noise and artifacts. The mathematical problem has a Tikhonov-like formulation, where the regularization functional is a nonlinear variational functional. The problem is numerically solved as an optimization problem with a quasi-Newton algorithm. The algorithm has been applied to MR images corrupted by noise and to dynamic MR images corrupted by truncation artifacts due to limited resolution. The results on test problems obtained from simulated and real data are presented. The functionals actually reduce noise and artifacts, provided that a good regularizing parameter is used.", abstrat = "In this paper we present some variational functionals for the regularization of {M}agnetic {R}esonance ({MR}) images, usually corrupted by noise and artifacts. The mathematical problem has a Tikhonov-like formulation, where the regularization functional is a nonlinear variational functional. The problem is numerically solved as an optimization problem with a quasi-Newton algorithm. The algorithm has been applied to {MR} images corrupted by noise and to dynamic {MR} images corrupted by truncation artifacts due to limited resolution. The results on test problems obtained from simulated and real data are presented. The functionals actually reduce noise and artifacts, provided that a good regularizing parameter is used.", } @Article{MCGST-04, author = "Mart{\'{\i}}nez, J. A. and Casado, L. G. and Garc{\'{\i}}a, I. and Sergeyev, Yaroslav D. and Toth, B.", title = "On an efficient use of gradient information for accelerating interval global optimization algorithms", journal = "Numerical Algorithms", year = "2004", volume = "37", pages = "61--69", abstract = "This paper analyzes and evaluates an efficient $n$-dimensional global optimization algorithm. It is a natural $n$-dimensional extension of the algorithm from L.G.\ Casado, I.\ Garc{\'{\i}}a, J.A.\ Mart{\'{\i}}nez and Ya.D.\ Sergeyev, New interval analysis support functions using gradient information in a global minimization algorithm, J.\ Global Optimization 25(4) (2003), 1-18. This algorithm takes advantage of all available information to estimate better bounds of the function. Numerical comparison made on a wide set of multiextremal test functions has shown that on average the new algorithm works faster than a traditional interval analysis global optimization method.", } @InProceedings{SZZ-04b, author = "Serafini, Thomas and Zanghirati, Gaetano and Zanni, Luca", title = "Parallel Decomposition Approaches for Training Support Vector Machines", booktitle = "Parallel Computing: Software Technology, Algorithms, Architectures and Applications", year = "2004", editor = "Joubert, G. R. and Nagel, W. E. and Peters, F. J. and Walter, W. V.", volume = "13", series = "Advances in Parallel Computing", pages = "259--266", address = "Amsterdam, The Netherlands", abstract = "We consider parallel decomposition techniques for solving the large quadratic programming (QP) problems arising in training support vector machines.A recent technique is improved by introducing an efficient solver for the inner QP subproblems and a {``}preprocessing{''} step useful to hot start the decomposition strategy. The effectiveness of the proposed improvements is evaluated by solving large-scale benchmark problems on different parallel architectures.", } @InProceedings{SZZ-04a, author = "Serafini, Thomas and Zanni, Luca and Zanghirati, Gaetano", title = "Training Support Vector Machines on Parallel Architectures", booktitle = "{S}cience and {S}upercomputing at {CINECA}. Report 2003", year = "2004", editor = "Voli, Marco and Coluccia, Patrizia", pages = "391--394", address = "Bologna, Italy", publisher = "Monograf", abstract = "The parallel solution of the large quadratic programming problem arising in training support vector machines is analysed. Some improvements to a recent decomposition technique are discussed. The effectiveness of the proposed approach is evaluated by solving large-scale benchmark problems on different parallel architectures.", } @Article{S-04a, author = "Sergeyev, Yaroslav D.", title = "Generation of symmetric exponential sums", journal = "Journal of Number Theory", year = "2004", volume = "108", pages = "60--75", number = "1", abstract = "In this paper, a new method for generation of infinite series of symmetric identities written for exponential sums in real numbers is proposed. Such systems have numerous applications in theory of numbers, chaos theory, algorithmic complexity, dynamic systems, etc. Properties of generated identities are studied. Relations of the introduced method for generation of symmetric exponential sums to the Morse-Hedlund sequence and to the theory of magic squares are established.", } @TechReport{S-04b, author = "Sergeyev, Yaroslav D.", title = "A new approach for executing calculations with finite, infinite, and infinitesimal quantities", institution = "ICAR-CNR", year = "2004", type = "Technical Report", number = "RT-ICAR-CS-04-14", address = "Rende (Cosenza), Italy", abstract = "All the existing computers are able to execute arithmetical operations only with finite numerals. Operations with infinite and infinitesimal quantities could not be realized. The paper introduces a new positional system with infinite radix allowing us to write down finite, infinite, and infinitesimal numbers as particular cases of a unique framework. This new numeral system gives possibility to introduce a new type of computer able to operate not only with finite numbers but also with infinite and infinitesimal ones. A possible organization of memory and arithmetic logic unit of such a computer are described briefly. The new approach both gives possibilities to execute calculations of a new type and simplifies fields of mathematics where usage of infinity and/or infinitesimals is necessary (for example, divergent series, limits, derivatives, and integrals).", pages = "46 pp", } @TechReport{SK-04, author = "Sergeyev, Yaroslav D. and Kvasov, Dmitri E.", title = "Diagonal {L}ipschitz global optimization algorithm working with a set of Lipschitz constants", institution = "ICAR-CNR", year = "2004", type = "Technical Report", number = "RT-ICAR-CS-04-15", address = "Cosenza, Italy", note = "33 pages", abstract = "In this report, the global optimization problem of a multidimensional black-box function satisfying the Lipschitz condition over a hyperinterval with an unknown Lipschitz constant is considered. A new efficient algorithm for solving this problem is presented. At each iteration of the method a number of possible Lipschitz constants is chosen from a set of values varying from zero to infinity. This idea is unified with an efficient diagonal partition strategy. A novel technique balancing usage of local and global information during partitioning is proposed. A new procedure for finding lower bounds of the objective function overhyperintervals is also considered. It is demonstrated by extensive numerical experiments performed on more than 1600 multidimensional test functions that the new algorithm shows a very promising performance.", } @Article{SS-04, author = "Sofroniou, Marc and Spaletta, Giulia", title = "Construction of explicit {R}unge-{K}utta pairs with stiffness detection", journal = "Mathematical and Computer Modelling", year = "2004", volume = "40", pages = "1157--1169", number = "11--12", abstract = "Explicit {R}unge-{K}utta schemes are the methods of choice for solving nonstiff systems of ordinary differential equations at low to medium tolerances. The construction of optimal formulae has been the subject of much research. In this article, it will be shown how to construct some low order formula pairs using tools from computer algebra. Our focus will be on methods that are equipped with local error detection (for adaptivity in the step size) and with the ability to detect stiffness. It will be demonstrated how criteria governing {``}optimal{''} tuning of free parameters and matching of the embedded method can be accomplished by forming a constrained optimization problem. In contrast to standard numerical optimization processes our approach finds an exact (infinite precision) global minimum. Quantitative measures will be given comparing our new methods with some established formula.", } @Article{Sp-04, author = "Spaletta, Giulia", title = "Approximation of a {3D} Volume from one {2D} Image. {A} Medical Application", journal = "Memorie della Accademia delle Scienze dell'Istituto di Bologna, serie I", year = "2004", volume = "vol. II", pages = "49--65", note = "Invited review", abstract = "We study the possibility for a tridimensional reconstruction of one lobe of the thyroid gland from a single bidimensional echographic or scintigraphic image. From a numerical point of view the scope is to provide an approximation to its volume, besides to a visualization of the gland in space, that is more accurate than the current way of estimating such a volume. We focus on a particular pathology of the thyroid, namely the Plummer nodule. Through the tridimensional information obtained, the aim is to perform both a functional and morphological analysis of the thyroid lobe affected by the Plummer pathology, in order to obtain therapeutic indication, to avoid the surgical extraction of the gland.", } @InProceedings{ZLL-04, author = "Zama, Fabiana and Loli Piccolomini, Elena and Landi, Germana", title = "A descent method for computing the {T}ikhonov regularized solution of linear inverse problems", booktitle = "Proccedings of {SPIE}", year = "2004", editor = "Bones, P. J. and Fiddy, M. A. and Millane, R. P.", volume = "5562", abstract = "In this paper we describe an iterative algorithm, called Descent-{TCG}, based on truncated Conjugate Gradient iterations to compute Tikhonov regularized solutions of linear ill-posed problems. Suitable termination criteria are built-up to define an inner-outer iteration scheme for the computation of a regularized solution. Numerical experiments are performed to compare the algorithm with other well-established regularization methods. We observe that the best Descent-{TCG} results occur for highly noised data and we always get fairly reliable solutions, preventing the dangerous error growth often appearing in other well-established regularization methods. Finally, the Descent-{TCG} method is computationally advantageous especially for large size problems.", } @TechReport{BA-03, author = "Baricordi, Alessia and Argentesi, Ilaria", title = "A Reference Guide to {``Hooking your solver to {AMPL}''}", institution = "Department of Mathematics, University of Ferrara", year = "2003", abstract = "{AMPL} is one of the most widely used modelling languages for Mathematical Programming. Invented by D. Gay and R. Fourer, it is able to model and solve problems ranging from student examples to very complex, higly nonlinear industrial applications. For the problem solution, {AMPL} needs to call an external solver that provides the capabilities required to solve the problem at hand. Despite the today quite wide set of numerical solvers supplying an {AMPL} interface (thus being callable from inside the {AMPL} interactive environment), it would be very interesting for both researchers and practitioners to be able to provide their own custom-made solvers to {AMPL}. Unfortunately, this is not as easy as one would hope. David Gay explains in its guide {``}{H}ooking your solver to {AMPL}{''} how to use some of the C coded {AMPL} library functions, in order to make {AMPL} working with a custom solver, but the description is quite fragmented and relates a lot on the C coded example routines coming with the {AMPL} freely downloadable version. In this report we try to build a more {``}structured{''} approach to the problem of hooking a custom solver to {AMPL}, by providing a sort of reference guide to the many library routines that one needs to call from its own code. This rough document is still just an {``}add-on{''} to the Gay's guide and it is intended to help the programmers to better understand how to call a given routine and where to find description/examples/suggestions on its use. These are the easier tasks. The most difficult tasks, that is to say which, why and when a routine must/can be called is still under development and the programmers are referred to the Gay's guide.", } @Article{CGMS-03, author = "Casado, L. G. and Garc{\'{i}}a, I. and Mart{\'{i}}nez, J. A. and Sergeyev, Yaroslav D.", title = "New interval analysis support functions using gradient information in a global minimization algorithm", journal = "Journal of Global Optimization", year = "2003", volume = "25", pages = "345--362", number = "4", abstract = "The performance of interval analysis branch-and-bound global optimization algorithms strongly depends on the efficiency of selection, bounding, elimination, division, and termination rules used in their implementation. All the information obtained during the search process has to be taken into account in order to increase algorithm efficiency, mainly when this information can be obtained and elaborated without additional cost (in comparison with traditional approaches). In this paper a new way to calculate interval analysis support functions for multiextremal univariate functions is presented. The new support functions are based on obtaining the same kind of information used in interval analysis global optimization algorithms. The new support functions enable us to develop more powerful bounding, selection, and rejection criteria and, as a consequence, to significantly accelerate the search. Numerical comparisons made on a wide set of multiextremal test functions have shown that on average the new algorithm works almost two times faster than a traditional interval analysis global optimization method.", } @Article{DR-03a, author = "Durazzi, Carla and Ruggiero, Valeria", title = "A {N}ewton Inexact Interior-Point Method for Large Scale Nonlinear Optimization Problems", journal = "Ann.\ Univ.\ Ferrara", year = "2003", volume = "49", pages = "333--357", abstract = "In this paper, we describe a variant of the Newton Interior-Point method in El Bakry A.S., Tapia R.A. et al., JOTA (1996), for nonlinear programming problems. In this scheme, the perturbation parameter can be chosen within a range of values and we can use an iterative method for solving the reduced linear system arising at each step. We have devised the inner termination rule which guarantees the global convergence of this Newton Inexact Interior-Point method. We remark that the required assumptions are weaker than those stated in El-Bakry A.S., Tapia R.A. et al., JOTA (1996), as shown by some numerical examples.", } @Article{DR-03b, author = "Durazzi, Carla and Ruggiero, Valeria", title = "Numerical Solution of Special Linear and Quadratic Programs via a Parallel Interior-Point", journal = "Parallel Computing", year = "2003", volume = "29", pages = "485--503", number = "4", abstract = "This paper concerns a parallel inexact Interior-Point ({IP}) method for solving linear and quadratic programs with a special structure in the constraint matrix and in the objective function. In order to exploit these features, a Preconditioned Coniugate Gradient ({PCG}) algorithm is used to approximately solve the normal equations or the reduced {KKT} system obtained from the linear inner system arising at each iteration of the {IP} method. A suitable adaptive termination rule for the {PCG} method enables to save computing time at the early steps of the outer scheme and, at the same time, it assures the global and the local superlinear convergence of the whole method. We analyse a parallel implementation of the method, referring some kinds of meaningful large-scale problems. In particular we discuss the data allocation and the workload distribution among the processors. The results of a numerical experimentation carried out on Cray {T3E} and {SGI} Origin 3800 show a good scalability of the parallel code and confirm the effectiveness of the method for problems with special structure.", } @InBook{DRZ-03, pages = "141--161", title = "Solving a Special Class of Discrete Optimal Control Problems via a Parallel Interior-Point Method", year = "2003", editor = "Daniele, Patrizia and Giannessi, Franco and Maugeri, Antonino", author = "Durazzi, Carla and Ruggiero, Valeria and Zanghirati, Gaetano", volume = "68", series = "Nonconvex Optimization and its Applications", abstract = "This paper is concerned with a parallel primal-dual Interior-Point method combined with the preconditioned conjugate gradient algorithm. Recently, the global convergence of this scheme has been proved and this approach has been used for solving linear stochastic programming and robust optimization problems on parallel computers. In this paper, we analyse the method for a more general formulation of a constrained quadratic programming problem and we provide the hypotheses for the global convergence of the obtained scheme. A large-scale application related to a class of discrete quadratic optimal control problems is presented: the numerical results on parallel architectures confirm the effectiveness of the {IPPCG} method on programs with special structure.", booktitle = "Equilibrium Problems and Variational Models", } @InBook{GRZ-03, chapter = "Variable Projection Methods for Large-Scale Quadratic Optimizaion in Data Analysis Applications", pages = "186--211", title = "Equilibrium Problems and Variational Models", publisher = "Kluwer Academic Publishers", year = "2003", editor = "Daniele, Patrizia and Giannessi, Franco and Maugeri, Antonino", author = "Galligani, Emanuele and Ruggiero, Valeria and Zanni, Luca", volume = "68", series = "Nonconvex Optimization and its Applications", abstract = "The paper concerns with the numerical evaluation of the variable projection method for quadratic programming problems in three data analysis applications. The three applications give rise to large-scale quadratic programs with remarkable differences in the Hessian definition and/or in the structure of the constraints.", } @Article{GKLS-03, author = "Gaviano, Marco and Kvasov, Dmitri E. and Lera, Daniela and Sergeyev, Yaroslav D.", title = "Algorithm 829: Software for Generation of Classes of Test Functions with Known Local and Global Minima for Global Optimization", journal = "{ACM} Transactions on Mathematical Software", year = "2003", volume = "29", pages = "469--480", number = "4", abstract = "A procedure for generating non-differentiable, continuously differentiable, and twice continuously differentiable classes of test functions for multiextremal multidimensional box-constrained global optimization is presented. Each test class consists of 100 functions. Test functions are generated by defining a convex quadratic function systematically distorted by polynomials in order to introduce local minima. To determine a class, the user defines the following parameters: (i)~problem dimension, (ii)~number of local minima, (iii)~value of the global minimum, (iv)~radius of the attraction region of the global minimizer, (v)~distance from the global minimizer to the vertex of the quadratic function. Then, all other necessary parameters are generated randomly for all 100 functions of the class. Full information about each test function including locations and values of all local minima is supplied to the user. Partial derivatives are also generated where possible.", } @Article{KPS-03, author = "Kvasov, Dmitri E. and Pizzuti, C. and Sergeyev, Yaroslav D.", title = "Local tuning and partition strategies for diagonal {GO} methods", journal = "Numerische Mathematik", year = "2003", volume = "94", pages = "93--106", number = "1", abstract = "In this paper, global optimization ({GO}) Lipschitz problems are considered where the multi-dimensional multiextremal objective function is determined over a hyperinterval. An efficient one-dimensional {GO} method using local tuning on the behavior of the objective function is generalized to the multi-dimensional case by the diagonal approach using two partition strategies. Global convergence conditions are established for the obtained diagonal geometric methods. Results of a wide numerical comparison show a strong acceleration reached by the new methods working with estimates of the local Lipschitz constants over different subregions of the search domain in comparison with the traditional approach.", } @Article{KS-03, author = "Kvasov, Dmitri E. and Sergeyev, Yaroslav D.", title = "Multidimensional global optimization algorithm based on adaptive diagonal curves", journal = "Computational Mathematics and Mathematical Physics", year = "2003", volume = "43", pages = "40--56", number = "1", abstract = "A classical global optimization problem is considered: minimization of a multidimensional multiextremal function that is Lipschitzian on a hyperinterval. A new information statistical algorithm for solving this problem is suggested. The new method relies on adaptive diagonal curves that combine the ideas of diagonal algorithms and Peano curves. Conditions for global convergence of the suggested algorithm are established. The results of extensive numerical experiments are presented to demonstrate the advantage of the new method as compared to traditional diagonal global optimization algorithms. The experiments corroborate confirm the theoretical conclusion that the advantage of the new method increases with the problem dimension.", } @InProceedings{LLZ-03, author = "Landi, Germana and Loli Piccolomini, Elena and Zama, Fabiana", title = "A Parallel Software for the Reconstruction of Dynamic {MRI} Sequences", booktitle = "Proceedings of the 10th {E}uropean meeting on {PVM}/{MPI}", year = "2003", pages = "511--519", month = sep # " 29 -- " # oct # " 2, 2003", abstract = "In this paper we present a parallel version of an existing Matlab software for dynamic Magnetic Resonance Imaging which implements a reconstruction technique based on B-spline Reduced-encoding Imaging by Generalized series Reconstruction. The parallel primitives used are provided by MatlabMPI. The parallel Matlab application is tested on a network of Linux workstations.", } @Article{LZ-03, author = "Loli Piccolomini, Elena and Zama, Fabiana", title = "An Experiment of parallel {SPECT} Data Reconstruction", journal = "Parallel Algorithms and Applications", year = "2003", volume = "18", pages = "107--119", number = "3", abstract = "In this work we consider the problem of reconstructing human brain sections from experimental data obtained from a Gamma camera equipped with parallel hole collimators. We compute least squares regularized solutions by means of weighted conjugate gradient iterations coupled with a suitable stopping rule. The computations are distributed to the Cray {T3E} parallel processors. In particular, two decomposition strategies are examinated and the results are compared.", } @Article{SZZ-03, author = "Serafini, Thomas and Zanghirati, Gaetano and Zanni, Luca", title = "Large Quadratic Programs in Training Gaussian Support Vector Machines", journal = "Rendiconti di {M}atematica e delle sue Applicazioni, {U}niversit{\`{a}} di {R}oma {``La Sapienza''}, serie {VII}", year = "2003", volume = "23", pages = "257--275", abstract = "We consider the numerical solution of the large convex quadratic program arising in training the learning machines named \emph{support vector machines}. Since the matrix of the quadratic form is dense and generally large, solution approaches based on explicit storage of this matrix are not practicable. Well known strategies for this quadratic program are based on decomposition techniques that split the problem into a sequence of smaller quadratic programming subproblems. For the solution of these subproblems we present an iterative projection-type method suited for the structure of the constraints and very effective in case of Gaussian support vector machines. We develop an appropriate decomposition technique designed to exploit the high performance of the proposed inner solver on medium or large subproblems. Numerical experiments on large-scale benchmark problems allow to compare this approach with another widely used decomposition technique. Finally, a parallel extension of the proposed strategy is described.", } @Article{SPF-03, author = "Sergeyev, Yaroslav D. and Pugliese, P. and Famularo, D.", title = "Index information algorithm with local tuning for solving multidimensional global optimization problems with multiextremal constraints", journal = "Mathematical Programming", year = "2003", volume = "96", pages = "489--512", number = "3", abstract = "Multidimensional optimization problems where the objective function and the constraints are multiextremal non-differentiable Lipschitz functions (with unknown Lipschitz constants) and the feasible region is a finite collection of robust nonconvex subregions are considered. Both the objective function and the constraints may be partially defined. To solve such problems an algorithm is proposed, that uses Peano space-filling curves and the index scheme to reduce the original problem to a Hölder one-dimensional one. Local tuning on the behaviour of the objective function and constraints is used during the work of the global optimization procedure in order to accelerate the search. The method neither uses penalty coefficients nor additional variables. Convergence conditions are established. Numerical experiments confirm the good performance of the technique.", } @Article{SS-03b, author = "Sofroniou, Marc and Spaletta, Giulia", title = "On the Construction of a new generalization of {R}unge-{K}utta Methods", journal = "Electronic Notes in Theoretical Computer Science", year = "2003", volume = "74", pages = "1--18", abstract = "We give an overview of the construction of algebraic conditions for determining the order of {R}unge-{K}utta methods and describe a novel extension for numerically solving systems of differential equations. The new schemes, called Elementary Differential {R}unge-{K}utta methods, include as a subset {R}unge-{K}utta methods, Taylor series methods, Multiderivative {R}unge-{K}utta methods. We outline how order conditions have been constructed for the new schemes using B-series and their composition and give details relating to a Mathematica implementation.", } @Article{SS-03c, author = "Sofroniou, Marc and Spaletta, Giulia", title = "Symmetric Composition of Symmetric Numerical Integration Methods", year = "2003", volume = "submitted", abstract = "This work focuses on the derivation of composition methods for the numerical integration of ordinary differential equations, which give rise to very challenging optimization problems. Composition is a very useful technique for constructing high order approximations whilst conserving certain geometric properties. We survey existing composition methods and describe results of an intensive numerical search for new methods. Details of the search procedure are given along with numerical examples which indicate that the new methods perform better than previously known methods. Some insights into the location of global minima for these problems is obtained as a results.", } @Article{SS-03a, author = "Sofroniou, Marc and Spaletta, Giulia", title = "Increment Formulation for Rounding Error Reduction in the Numerical Solution of Structured Differential Systems", journal = "Future Generation Computer Systems", year = "2003", volume = "19", pages = "375--383", number = "3", abstract = "Strategies for reducing the effect of cumulative rounding errors in geometric numerical integration are outlined. The focus is, in particular, on the solution of separable Hamiltonian systems using explicit symplectic integration methods and on solving orthogonal matrix differential systems using projection. Examples are given that demonstrate the advantages of an increment formulation over the standard implementation of conventional integrators. We describe how the aforementioned special purpose integration methods have been set up in a uniform, modular and extensible framework being developed in the problem solving environment Mathematica.", } @Article{StS-03, author = "Strongin, R. G. and Sergeyev, Yaroslav D.", title = "Global optimization: fractal approach and non-redundant parallelism", journal = "Journal of Global Optimization", year = "2003", volume = "27", pages = "25--50", number = "1", abstract = "More and more optimization problems arising in practice can not be solved by traditional optimization techniques making strong suppositions about the problem (differentiability, convexity, etc.). This happens because very often in real-life problems both the objective function and constraints can be multiextremal, non-differentiable, partially defined, and hard to be evaluated. In this paper, a modern approach for solving such problems (called global optimization problems) is described. This approach combines the following innovative and powerful tools: fractal approach for reduction of the problem dimension, index scheme for treating constraints, non-redundant parallel computations for accelerating the search. Through the paper, rigorous theoretical results are illustrated by figures and numerical examples.", } @Article{ZZ-03, author = "Zanghirati, Gaetano and Zanni, Luca", title = "A Parallel Solver for Large Quadratic Programs in Training Support Vector Machines", journal = "Parallel Computing", year = "2003", volume = "29", pages = "535--551", number = "4", abstract = "This work is concerned with the solution of the convex quadratic programming problem arising in training the learning machines named support vector machines. The problem is subject to box constraints and to a single linear equality constraint; it is dense and, for many practical applications, it becomes a large-scale problem. Thus, approaches based on explicit storage of the matrix of the quadratic form are not practicable. Here we present an easily parallelizable approach based on a decomposition technique that splits the problem into a sequence of smaller quadratic programming subproblems. These subproblems are solved by a variable projection method that is well suited to a parallel implementation and is very effective in the case of Gaussian support vector machines. Performance results are presented on well known large-scale test problems, in scalar and parallel environments. The numerical results show that the approach is comparable on scalar machines with a widely used technique and can achieve good efficiency and scalability on a multiprocessor system.", } @Article{CGS-02, author = "Casado, L. G. and Garc\`{\i}a, I. and Sergeyev, Yaroslav D.", title = "Interval algorithms for finding the minimal root in a set of multiextremal non-differentiable one-dimensional functions", journal = "{SIAM} Journal on Scientific Computing", year = "2002", volume = "24", pages = "359--376", number = "2", abstract = "Two problems very often arising in applications are considered. The first problem consists of finding the minimal root of an analytic one-dimensional function over a given interval. It is supposed that the objective function can be multiextremal and non-differentiable. Three new algorithms based on Interval Analysis and Branch-and-Bound Global Optimization approaches are proposed for solving this problem. The novelty of the new algorithms is basically in improving the elimination criteria and the order in which interval and point evaluations are realized. The introduced techniques accelerate the search in comparison with interval analysis methods traditionally used for finding roots of equations. The second problem considered in the paper is a generalization of the first one and deals with the search of the minimal root in a set of multiextremal and non-differentiable functions. The methods proposed for solving the first problem are generalized for solving the second. The main idea is in using the information obtained from any of the functions to reduce the search domain associated to all the functions. Numerical experiments carried out on a wide set of test functions demonstrate a quite satisfactory performance of the new algorithms in both cases.", } @Article{DR-02, author = "Durazzi, Carla and Ruggiero, Valeria", title = "Indefinitely Preconditioned Conjugate Gradient Method for Large Sparse Equality and Inequality Constrained Quadratic Problems", journal = "Numerical Linear Algebra and Applications", year = "2002", volume = "10", pages = "673--688", abstract = "This paper is concerned with the numerical solution of a symmetric indefinite system which is a generalization of the Karush-Kuhn-Tucker system. Following the recent approach of Luksan and Vlcek, we propose to solve this system by a Preconditioned Conjugate Gradient ({PCG}) algorithm and we devise two indefinite preconditioners with good theoretical properties. In particular, for one of these preconditioners, the finite termination property of the {PCG} method is stated. The {PCG} method combined with a parallel version of these preconditioners is used as inner solver within an inexact Interior-Point ({IP}) method for the solution of large and sparse quadratic programs. The numerical results obtained by a parallel code implementing the {IP} method on distributed memory multiprocessor systems enable us to confirm the effectiveness of the proposed approach for problems with special structure in the constraint matrix and in the objective function.", } @InProceedings{FSP-02, author = "Famularo, D. and Sergeyev, Yaroslav D. and Pugliese, P.", title = "Test Problems for {L}ipschitz univariate global optimization with multiextremal constraints", booktitle = "Stochastic and Global Optimization", year = "2002", editor = "Dzemyda, G. and Saltenis, V.", pages = "93--110", address = "Dordrecht", publisher = "Kluwer Academic Publishers", abstract = "In this paper, Lipschitz univariate constrained global optimization problems where both the objective function and constraints can be multiextremal are considered. Two sets of test problems are introduced, in the first one both the objective function and constraints are differentiable functions and in the second one they are non-differentiable. Each series of tests contains 3 problems with one constraint, 4 problems with 2 constraints, 3 problems with 3 constraints, and one infeasible problem with 2 constraints. All the problems are shown in Figures. Lipschitz constants and global solutions are given. For each problem it is indicated whether the optimum is located on the boundary or inside a feasible subregion and the number of disjoint feasible subregions is given. Results of numerical experiments executed with the introduced test problems using Pijavskii's method combined with a non-differentiable penalty function are presented.", } @Article{GL-02, author = "Gaviano, Marco and Lera, Daniela", title = "A complexity analysis of local search algorithms in global optimization", journal = "Optimization Methods and Software", year = "2002", volume = "17", pages = "113--127", number = "1", abstract = "In this paper a complexity analysis is performed for an algorithm which solves the global optimization problem (P): minimize a real function $f(x)$ in a subset $S$ of $R^n$. The algorithm yields local minimizations of (P) starting from points chosen at random in $S$, and then the global minimum is selected among the local ones found. The local search algorithm is based on the steepest-descent method combined either with an exact line search or with the Armijo procedure. In the first case it is found that the number of line searches required to solve (P) within a fixed accuracy depends linearly on the problem dimension; in the second case a similar result involving the number of function evaluations is established.", } @Article{LS-02, author = "Lera, Daniela and Sergeyev, Yaroslav D.", title = "Global minimization algorithms for {H}{\"{o}}lder functions", journal = "{BIT}", year = "2002", volume = "42", pages = "119--133", number = "1", abstract = "This paper deals with the one-dimensional global optimization problem where the objective function satisfies H{\"{o}}lder condition over a closed interval. A direct extension of the popular Piyavskii method proposed for Lipschitz functions to H{\"{o}}lder optimization requires an a priori estimate of the Hölder constant and solution to an equation of degree $N$ at each iteration. In this paper a new scheme is introduced. Three algorithms are proposed for solving one-dimensional H{\"{o}}lder global optimization problems. All of them work without solving equations of degree $N$. The case (very often arising in applications) when Hölder constant is not given a priori is considered. It is shown that local information about the objective function used inside the global procedure can accelerate the search significantly. Numerical experiments show quite promising performance of the new algorithms.", } @Article{LZZ-02, author = "Loli Piccolomini, Elena and Zama, Fabiana and Zanghirati, Gaetano", title = "Regularization Methods in Dynamic {MRI}", journal = "Applied Mathematics and Computations", year = "2002", volume = "132", pages = "325--339", abstract = "In this work we consider an inverse ill?posed problem coming from the area of dynamic Magnetic Resonance Imaging ({MRI}), where high resolution images must be reconstructed from incomplete data sets collected in the Fourier domain. The {RIGR} ({R}educed-{E}ncoding {I}maging by {G}eneralized series reconstruction) method used leads to ill-conditioned linear systems with hermitian Toeplitz matrix and noisy right hand side. We analyze the behaviour of some regularization methods, such as the {T}runcated {S}ingular {V}alue {D}ecomposition, the Lavrent'yev regularization method and Conjugate Gradients type iterative methods. For what concerns the choice of the regularization parameter, we use some known methods and we propose new heuristic criteria for iterative regularization methods. The simulations are carried on test problems obtained from real data acquired on a 1.5 Tesla Phillips system.", } @Article{MPS-02, author = "Molinaro, A. and Pizzuti, C. and Sergeyev, Yaroslav D.", title = "A diagonal global optimization method", year = "2002", pages = "251--263", abstract = "In this paper we consider the classical global optimization problem of searching the global minimum of a multiextremal multidimensional Lipschitz function over a hyperinterval. We present a new multidimensional diagonal algorithm belonging to the class of information global optimization methods. It is supposed that the Lipschitz constant is unknown and only the values of the objective function can be evaluated. The new method uses local tuning on the behaviour of the objective function to accelerate the search adaptively estimating local Lipschitz constants during minimization. Sufficient convergence conditions are established for the proposed technique. Numerical examples are also reported.", } @Article{SS-02b, author = "Sofroniou, Marc and Spaletta, Giulia", title = "Symplectic Methods for Separable Hamiltonian Systems", journal = "Lecture Notes in Computer Science", year = "2002", volume = "2331", pages = "506--515", abstract = "This paper focuses on the solution of separable {H}amiltonian systems using explicit symplectic integration methods. Strategies for reducing the effect of cumulative rounding errors are outlined and advantages over a standard formulation are demonstrated. Procedures for automatically choosing appropriate methods are also described.", } @Article{SS-02a, author = "Sofroniou, Marc and Spaletta, Giulia", title = "Solving Orthogonal Matrix Differential Systems in {M}athematica", journal = "Lecture Notes in Computer Science", year = "2002", volume = "2331", pages = "496--505", abstract = "A component of a new environment for the numerical solution of ordinary differential equations in {M}athematica is outlined. We briefly describe how special purpose integration methods can be constructed to solve structured dynamical systems. In particular we focus on the solution of orthogonal matrix differential systems using projection. Examples are given to illustrate the advantages of a projection scheme over conventional integration methods.", }