Italian FIRB Project on
 Parallel Algorithms and Numerical Nonlinear Optimization

  Unit 1 research program

Description


Research activities
  1. Perturbed dumped Newton and SQP-IP methods for discretized optimal control problems
  2. Variable projection methods: a success approach for SVMs and large-scale simply contrained QP
  3. Adaptive diagonal space-filling curves: linking geometric Lipschitz and Bayesian approaches for non-differentiable global optimization.

 Research description

 The project of the research unit is concerned with the analysis and the development of nonlinear, local and global optimization methods for the numerical solution of high complexity problems in the context of  parallel computing.

Two topics will be considered:

  • local optimization methods,
  • global optimization methods.

 Three phases are provided for each topic:

  • determination of prototypical high complexity problems;
  • development and analysis of classical numerical methods and new parallel methods, with special attention devoted to theoretical convergence and numerical stability;
  • parallel implementation and evaluation of the algorithms with respect to both the multiprogramming degree and the performance parameters in the  context of parallel computing.

 A brief description follows.

Local Optimization

 Constrained optimization methods to solve optimal control problems, parameters identification and variational inequalities will be studied. The aim is to develop computational kernels for parallel computers.  We will study the following methods: the  sequential quadratic programming methods, the interior point methods, the  perturbed damped Newton method and projection methods. Discretization  techniques provide efficient methods for solving optimal control problems with  control and state constraints. There are two different approaches for the numerical solution of such control problems: a direct discretization of the whole problem leading to a large finite-dimensional constrained optimization problem (full discretization approach) or the use of an iterative method which reduces the original problem into a sequence of infinite-dimensional quadratic  control problems, which then still need to be discretized (SQP approach). The literature on the latter approach is quite extensive (see the special issue  "SQP-based direct discretization methods for practical optimal control  problems", V.H. Schultz ed., J. Comp. Appl. Math. 120 (2000)), while the former  one has more recently been considered for the solution of real-life problems,  since the new progress on the solution techniques for very large constrained nonlinear programming problems. A well-known full discretization method is the  Inexact Sequential Quadratic Programming Interior Point method (see, e.g., [W93,  LS99]). Sequential Quadratic Programming methods reduce the nonlinear problem into a sequence of quadratic subproblems; then, each of the quadratic  subproblems is solved by an Interior Point method only within a certain accuracy. As an alternative, we propose to solve directly the nonlinear discrete control problem with a Perturbed-Damped Newton method. The whole approach is suitable to parallel implementation. It is possible to establish a global convergence theory for this method. However, the determination of a "good" initial point of the whole iterative process is strongly recommented and we will analyze different strategies.

 The Variable Projection Methods can be used in the  solution of special constrained minimum problems and variational inequalities. These methods will be applied to particular minimum problems arising in Pattern Recognition. An interesting application of the Variable Projection methos is  concerned with a classification technique known as Support Vector Machine (SVM)[CV95]. From the computational point of view, the main effort in  the implementation of a SVM consists in solving a quadratic programming problem  with special constraints (box constraints and one linear equality constraint),  having size equal to the number of points of a data set called the training set. When this number is large, a decomposition technique may be used. We will analyse this technique, exploiting the parallel features of the approach, in order to heavely decrease the computational complexity of the problem.

Global optimization

 Among the techniques recently used for solving Lipschitz global optimization problems over hyperintervals, two promising approaches will be studied: diagonal algorithms  [P96] and methods based on Peano-Hilbert space-filling curves [SS00].  An additional, unifying approach will be studied, known as the technique of the adaptive diagonal curves. These tools will allow us  to construct new methods for solving non-differentiable problems by using  geometric Lipschitz ideas and a Bayesian approach. Convergence conditions for the  new algorithms will be studied in depth. In order to ensure an high convergence rate of the  new techniques, adaptive estimates of the local Lipschitz constants will be given by using the local tuning ideas.
The proposed methods will be generalized to the  case of problems with multiextremal partially defined constraints. When Lipschitz constans-based mathods are used to solve such problems, the reduction to the unconstrained case is not obvious; hence the index scheme [SS00] will be applied for  such a reduction. To lower the initial problem size, Peano-Hilbert space-filling curves will be adopted. A special study will be  devoted to the behaviour of the new techniques while solving reduced Holder one-dimensional problems. Since the methods to be developed will belong to the "Divide the best" family, it will be possible to construct their parallel  versions by applying the scheme introduced in [S98-2]. Convergence conditions  for the obtained parallel methods will be established. A deep study will be dedicated to the theoretical conditions for an efficient parallelization. Particularly, the problem of non-redundant parallelism will be faced.

In the case  of differentiable global optimization, stochastic methods using both local  searches and Lipschitz ideas will be proposed and analyzed.  Suitable test functions will be studied, together with the principles for their generation. All the proposed methods  will be first tested on workstation, then implemented on parallel computers. The parallel codes will be evaluated by using both ad hoc generated test functions and test functions taken from the literature, as well as some control problems.

References

[W93]

S.J. Wright, Interior Point Methods for Optimal Control of Discrete Time Systems, JOTA 77 (1993).

[LS99]

 F. Leibfritz, E.W. Sachs, Inexact SQP  interior point methods and large scale optimal control problems,  SIAM J. Control Optim. 38 (1999).

[CV95]

C. Cortes, V.N. Vapnik, Support Vector Network,  Machine Learning 20 (1995).

[P96]

J.D. Pintér, Global Optimization in Action,  Kluwer Academic Publ. (1996).

[SS00]

R.G. STRongin, Ya.D. Sergeyev, Global Optimization with non-convex constraints: sequential and parallel algorithms,  Kluwer Academic Publ. (2000).

[S98-2]

Ya.D. Sergeyev, On convergence of “Divide  the best” global optimization algorithms, Optimization 44 (1998).


[Top]

 Research Activities


Perturbed dumped Newton and SQP-IP methods for discretized optimal control problems

Researchers. V. Ruggiero, S. Bonettini, F. Tinti.

Description. In order to solve discretized optimal control problems, we will consider both "SQP-Interior Point" and "Perturbed Dumped Newton" methods.  For the latter, there is the possibility to adaptively modify the perturbation parameter in the Karush-Kuhn-Tucker system and the accuracy of the solution in the perturbed Newton equation, when one is still far  away from the solution of the problem at an early stage. The whole approach is suitable to parallel implementation. It is possible to establish a global  convergence theory for this method. However, the determination of a "good"  initial point of the whole iterative process is strongly recommented; we will analyze different strategies, as penalization and continuation methods. We will first determine a set of test problems and then we will compare the  considered methods on parallel architectures.

Expected results. Study and analysis of classical methods and new methods; analysis of the more promising algorithms, with special attention to the parallel architectures  and numerical experimentation. Development of the computational kernels for  some meaningful model problems. Achievement of benchmarks for the performance evaluation of the methods related to the above codes.

[Top]


Variable projection methods: a success approach for SVMs and large-scale simply contrained QP

Researchers. L. Zanni, G. Zanghirati.

Description. We will continue the investigation of the Variable Projection methods.  These methods will be applied to special minimum problems arising in Pattern Recognition. An interesting application of the Variable Projection methos is concerned with the binary classification technique, known as Support Vector  Machine (SVM). From the computational point of view, the main effort in the  implementation of a SVM consists in solving a quadratic programming problem with special constraints, having size equal to the number of points of the  training set. When this number is large, a decomposition technique may be used. We will develop this technique, exploiting the parallel features of the approach,  in order to heavely decrease the computational complexity of the problem. To evaluate the effectiveness of the parallel code, it will be compared with already available codes.

Expected results. Analysis of the Variable Projection Methods for the implementation of a SVM; implementation of decomposition techniques on parallel architectures and numerical  experimentation. Achievement of benchmarks for the performance evaluation of the underlying methods.

[Top]


Adaptive diagonal space-filling curves: linking geometric  Lipschitz and Bayesian approaches for non-differentiable global optimization

Researchers. Ya. D. Sergeyev, D. Lera, D. Kvasov.

Description. We will analyze global osptimization methods based on adaptive diagonal space-filling curves. These instruments will allow us to construct new methods for solving non-differentiable problems by using geometric Lipschitz ideas and Bayesian approach. Convergence conditions for the new algorithms will be studied in depth. In order to ensure a fast speed of the new techniques, adaptive estimates of the local Lipschitz constants will be done by using the local tuning ideas. The methods proposed will be generalized to the case of problems with multiextremal partially defined constraints. Since for such problems and methods working with Lipschitz constans reduction to the unconstrained case is not obvious, the index scheme will be applied for such a reduction. In order to reduce the dimension of the initial problem, Peano-Hilbert space-filling curves will be adopted. A special study will be dedicated to behavior of the new techniques while solving reduced Holder one-dimensional problems. Since the methods to be developed will belong to the "Divide the best" family, it will be possible to construct their parallel versions by applying the scheme introduced in. Convergence conditions for the obtained parallel methods will be established. A deep study will be dedicated to obtaining theoretical conditions of an efficient parallelization. Particularly, the problem of non-redundant parallelism will be faced, i.e., establishing a number of parallel processors which will not lead to generation of redundant (in comparison with the sequential case) calculations. In the case of differentiable global optimization, stochastic methods using both local searches and Lipschitz ideas will be proposed and studied. A study on test functions and principles of their generation will be done. All the methods proposed will be implemented (after the first tests on workstation) on parallel computers and tested o n ad hoc generated test functions, test functions taken from literature, and some control problems.

Expected results. Study and analysis of classical methods and new methods; analysis of the more promising algorithms, with special attention to the parallel architectures and numerical experimentation. Development of the computational kernels for some meaningful model problems. Achievement of benchmarks for the performance evaluation of the methods related to the above codes.

[Top]




Status: completed.
Info: g.zanghirati@unife.it

 Last updated: 15/3/2007.