Optimization problems

On a Parallel Interior-Point Method for Quadratic Programs with Special Structure
C. Durazzi & V. Ruggiero
(Department of Mathematics, University of Ferrara, Italy)

A crucial issue for an efficient implementation of Interior-Point (IP) methods is the solution of the linear system arising at each iteration for finding the search direction. The present state-of-the-art codes on IP methods for linear and quadratic programming (LP, QP) problems use direct inner solvers. However, iterative methods can be used with success on special classes of large-scale problems, having a particular structure in the matrix of the linear constraints.
In particular, for the solution of LP and separable QP problems, we proposed in [Durazzi, Ruggiero, Zanghirati, JOTA, 2001] a parallel IP method, named IPPCG method, that uses the preconditioned conjugate gradient algorithm for solving the normal equations, obtained by the reduction of the linear inner system. For non separable QP problems, an extension of the IPPCG method is considered in [Durazzi, Ruggiero, 2001], where, at each step of the method, instead of the normal equations, the reduced KKT system is solved by an iterative method. Also in this case, following the suggestions in [Luksan, Vlcek, Numer. Linear Algebra Appl., 1998], a PCG method with convenient indefinite preconditioner can be used.
Furthermore, a sufficient condition for an approximate solution of the inner linear system is devised so that the global and the local superlinear convergence of the IPPCG method is assured. This condition can be used as an adaptive stopping rule for the iterative inner solver.
Numerical experiments on parallel computers confirm the effectiveness of the IPPCG method for programs with special structure, such as discrete quadratic optimal control problems or stochastic programming and robust optimization problems.

The Newton-Arithmetic Mean Method for the Solution of Nonlinear Systems
Emanuele Galligani
(Dipartimento di Matematica Università di Modena e Reggio Emilia, Italy)

This paper is concerned with the development of the Newton-Arithmetic Mean method for large systems of nonlinear equations with block-partitioned jacobian matrix.

This method is well suited for implementation on a parallel computer; its degree of decomposition is very high.

The convergence of the method is analysed for the class of systems whose jacobian matrix satisfies an affine invariant Lipschitz condition. An estimation of the radius of the attraction ball is given.

Special attention is reserved to the case of weakly nonlinear systems; theorems about the monotone convergence of the method are proved under the hypothesis of positive boundedness on the nonlinear mapping.

An application of the method for solving real paractical problems related to the study of reaction-diffusion processes and of interacting populations is described.

A class of globally convergent ABS algorithms for nonlinear systems
Ladislav Luksan
(Czech Science Academy)

We present a globally convergent modification of the nonlinear ABS algorithm based upon the globalization technique developed by Luksan. Numerical results within the ABSPACK project show that the modified algorithm is very robust, providing actually the best performance of all tested codes in terms of number of solved problems.

On the nonlinear ABS algorithm for problems with singular Jacobian at solution
Zunquan Xia
(Dalian Un. Technology)

We discuss the performance of the ABS nonlinear algorithms in the case where the Jacobian is rank deficient at a local solution. We show the existence of ABS methods that keep a q-quadratic rate of convergence in this case.

Large Quadratic Programs in Training Support Vector Machines
Luca Zanni & Gaetano Zanghirati
(Department of Mathematics, University of Modena and Reggio-Emilia, Italy)

We consider the numerical solution of the quadratic programming (QP) problem arising in training the learning machines named Support Vector Machines (SVMs). Given a training set $D=\left\{({\bf p}_i,y_i), i=1,\dots,n, {\bf p}_i\in R^m,\ y_i\in\{-1,1\} \right\}$ of labeled examples, the SVM learning technique performs pattern recognition by finding a decision surface obtained by solving a convex quadratic program of the form:

$$\begin{array}{rl} \text{minimize} & \frac{1}{2} {\bf x}^T G {... ... x_i =0, \qquad 0\le x_j \le C, \qquad j=1,\dots,n. \end{array}$$ (1)

The size of the quadratic program is equal to the number of training examples and, consequently, in many interesting applications we must solve a large QP problem ($n$ $\gg$ 10000). Since the matrix $G$ is dense, the main approaches for solving this large quadratic program are based on special decomposition techniques, that avoid explicit storage of $G$ by splitting the original problem into a sequence of smaller QP subproblems. The aim of this work is to introduce an efficient iterative solver for these QP subproblems when problem (1) arises in training SVMs with Gaussian kernels, that is, when the entries $G_{ij}$ of $G$ are defined by $G_{ij}=y_iy_j\exp\left(-\Vert{\bf p}_i - {\bf p}_j\Vert^2/(2\sigma^2)\right)$. The solver is a projection-type method that requires a matrix-vector multiplication and the solution of a singly constrained separable QP problem at each iteration. An appropriate updating rule for the projection parameter of the method is proposed in order to produce a good convergence rate. The effectiveness of the approach is evaluated by solving several benchmark problems and by comparison with well known QP packages. Furthermore, a parallel implementation of the decomposition technique is tested on a multiprocessor system.