×

A parallel algorithm for a class of convex programs. (English) Zbl 0644.90068

Let q be a smooth strongly convex function (i.e., such that \(f-\rho \| \cdot \|^ 2\) is convex for some \(\rho >0)\) on \(R^ n\) and let \(C_ i\), \(i=1,...,m\), be closed convex sets in \(R^ n\). For solving the convex programming problem \(\min \{q(x)/x\in C=C_ 1\cap...\cap C_ m\}\), an iterative algorithm is proposed, whose main step in iteration k is to solve m independent subproblems, indexed by \(i=1,...,m\), each of which consists in finding the Euclidean projection of a certain \(w_ i^{(k-1)}\) (depending on a parameter \(\alpha\geq m/\rho)\) onto \(C_ i\). This decomposition into independent subproblems makes the algorithm suitable for parallel computation. The method also requires to evaluate the gradient of the conjugate function q * at a point in each iteration. Under some assumptions the algorithm converges and provides, at the same time, an optimal solution to Fenchel’s dual problem \(\min q^*(y)+ \delta^*(y|-C)\) (\(\delta\) denotes indicator function). The applicability of the method to linearly constrained programming, projection problems, definite quadratic programming, linear programming and to the solution of systems of linear equations and of generalized nonlinear inequalities is also discussed. Finally, it is shown that the algorithm can be adapted to the case when \(\rho\) is not known in advance, by adjusting \(\alpha\) iteratively. Since the method proposed in this paper is rather general, has nice convergence properties and can be easily implemented in the case of definite quadratic programming problems, it may serve as a good starting point for the design of parallel algorithms in optimization.

MSC:

90C25 Convex programming
65K05 Numerical mathematical programming methods
49M37 Numerical methods based on nonlinear programming
90C30 Nonlinear programming
90C20 Quadratic programming
90C55 Methods of successive quadratic programming type
PDFBibTeX XMLCite
Full Text: DOI