Complexity Estimation for an Algorithm of Searching for Zero of a Piecewise Linear Convex Function

It is known that the problem of the orthogonal projection of a point to the standard simplex can be reduced to solution of a scalar equation. In this article, the complexity is analyzed of an algorithm of searching for zero of a piecewise linear convex function which is proposed in [30]. The analysis is carried out of the best and worst cases of the input data for the algorithm. To this end, the largest and smallest numbers of iterations of the algorithm are studied as functions of the size of the input data. It is shown that, in the case of equality of elements of the input set, the algorithm performs the smallest number of iterations. In the case of different elements of the input set, the number of iterations is maximal and depends rather weakly on the particular values of the elements of the set. The results of numerical experiments with random input data of large dimension are presented.     

A derivative-free approximate gradient sampling algorithm for finite minimax problems

In this paper we present a derivative-free optimization algorithm for finite minimax problems. The algorithm calculates an approximate gradient for each of the active functions of the finite max function and uses these to generate an approximate subdifferential. The negative projection of 0 onto this set is used as a descent direction in an Armijo-like line search. We also present a robust version of the algorithm, which uses the ‘almost active’ functions of the finite max function in the calculation of the approximate subdifferential. Convergence results are presented for both algorithms, showing that either f(x ^k )→?∞ or every cluster point is a Clarke stationary point. Theoretical and numerical results are presented for three specific approximate gradients: the simplex gradient, the centered simplex gradient and the Gupal estimate of the gradient of the Steklov averaged function. A performance comparison is made between the regular and robust algorithms, the three approximate gradients, and a regular and robust stopping condition.     

Finding the projection of a point onto the intersection of convex sets via projections onto half-spaces

We present a modification of Dykstra's algorithm which allows us to avoid projections onto general convex sets. Instead, we calculate projections onto either a half-space or onto the intersection of two half-spaces. Convergence of the algorithm is established and special choices of the half-spaces are proposed.The option to project onto half-spaces instead of general convex sets makes the algorithm more practical. The fact that the half-spaces are quite general enables us to apply the algorithm in a variety of cases and to generalize a number of known projection algorithms.The problem of projecting a point onto the intersection of closed convex sets receives considerable attention in many areas of mathematics and physics as well as in other fields of science and engineering such as image reconstruction from projections.In this work we propose a new class of algorithms which allow projection onto certain super half-spaces, i.e., half-spaces which contain the convex sets. Each one of the algorithms that we present gives the user freedom to choose the specific super half-space from a family of such half-spaces. Since projecting a point onto a half-space is an easy task to perform, the new algorithms may be more useful in practical situations in which the construction of the super half-spaces themselves is not too difficult.     

Vector-Orthogonality and Lanczos-Type Methods

A method for solving a linear system is defined. It is a Lanczos-type method, but it uses formal vector orthogonality instead of scalar orthogonality. Moreover, the dimension of vector orthogonality may vary which gives a large freedom in leading the algorithm, and controlling the numerical problems. The ideas of truncated and restarted methods are revisited. The obtained residuals are exactly orthogonal to a space of increasing dimension. Some experiments are done, the problem of finding automaticaly good directions of projection remains partly open.     

Comparative study of two fast algorithms for projecting a point to the standard simplex

We consider two algorithms for orthogonal projection of a point to the standard simplex. These algorithms are fundamentally different; however, they are related to each other by the following fact: When one of them has the maximum run time, the run time of the other is minimal. Some particular domains are presented whose points are projected by the considered algorithms in the minimum and maximum number of iterations. The correctness of the conclusions is confirmed by the numerical experiments independently implemented in the MatLab environment and the Java programming language.     

A finite algorithm for finding the projection of a point onto the canonical simplex of ∝ n

An algorithm of successive location of the solution is developed for the problem of finding the projection of a point onto the canonical simplex in the Euclidean space ⁿ . This algorithm converges in a finite number of steps. Each iteration consists in finding the projection of a point onto an affine subspace and requires only explicit and very simple computations.     

Fast elliptic curve point multiplication based on binary and binary non-adjacent scalar form methods

This article presents two methods for developing algorithms of computing scalar multiplication in groups of points on an elliptic curve over finite fields. Two new effective algorithms have been presented: one of them is based on a binary Non-Adjacent Form of scalar representation and another one on a binary of scalar representation method. All algorithms were developed based on simple and composite operations with point and also based on affine and Jacobi coordinates systems taking into account the latest achievements in computing cost reduction. Theorems concerning their computational complexity are formulated and proved for these new algorithms. In the end of this article comparative analysis of both new algorithms among themselves and previously known algorithms are represented.     

Geometrically convergent projection method in matrix games

We propose a method which evaluates the solution of a matrix game. We reduce the problem of the search for the solution to a convex feasibility problem for which we present a method of projection onto an acute cone. The algorithm converges geometrically. At each iteration, we apply a combinatorial algorithm in order to evaluate the projection onto the standard simplex.     

Charged ball method for solving some computational geometry problems

The concept of replacement of the initial stationary optimization problem with some nonstationary mechanical system tending with time to the position of equilibrium, which coincides with the solution of the initial problem, makes it possible to construct effective numerical algorithms. First, differential equations of the movement should be derived. Then we pass to the difference scheme and define the iteration algorithm. There is a wide class of optimization methods constructed in such a way. One of the most known representatives of this class is the heavy ball method. As a rule, such type of algorithms includes parameters that highly affect the convergence rate. In this paper, the charged ball method, belonging to this class, is proposed and investigated. It is a new effective optimization method that allows solving some computational geometry problems. A problem of orthogonal projection of a point onto a convex closed set with a smooth boundary and the problem of finding the minimum distance between two such sets are considered in detail. The convergence theorems are proved, and the estimates for the convergence rate are found. Numerical examples illustrating the work of the proposed algorithms are given.     

Proximal minimizations with D-functions and the massively parallel solution of linear network programs

This paper discusses the massively parallel solution of linear network programs. It integrates the general algorithmic framework of proximal minimization with D-functions (PMD) with primal-dual row-action algorithms. Three alternative algorithmic schemes are studied: quadratic proximal point, entropic proximal point, and least 2-norm perturbations. Each is solving a linear network problem by solving a sequence of nonlinear approximations. The nonlinear subproblems decompose for massively parallel computing. The three algorithms are implemented on a Connection Machine CM-2 with up to 32K processing elements, and problems with up to 16 million variables are solved. A comparison of the three algorithms establishes their relative efficiency. Numerical experiments also establish the best internal tactics which can be used when implementing proximal minimization algorithms. Finally, the new algorithms are compared with an implementation of the network simplex algorithm executing on a CRAY Y-MP vector supercomputer.     

A Projection-Proximal Point Algorithm for Solving Generalized Variational Inequalities

In this paper, a projection-proximal point method for solving a class of generalized variational inequalities is considered in Hilbert spaces. We investigate a general iterative algorithm, which consists of an inexact proximal point step followed by a suitable orthogonal projection onto a hyperplane. We prove the convergence of the algorithm for a pseudomonotone mapping with weakly upper semicontinuity and weakly compact and convex values. We also analyze the convergence rate of the iterative sequence under some suitable conditions.     

A Two-Phase Algorithm for a Variational Inequality Formulation of Equilibrium Problems

We introduce an explicit algorithm for solving nonsmooth equilibrium problems in finite-dimensional spaces. A particular iteration proceeds in two phases. In the first phase, an orthogonal projection onto the feasible set is replaced by projections onto suitable hyperplanes. In the second phase, a projected subgradient type iteration is replaced by a specific projection onto a halfspace. We prove, under suitable assumptions, convergence of the whole generated sequence to a solution of the problem. The proposed algorithm has a low computational cost per iteration and, some numerical results are reported.     

Further applications of a splitting algorithm to decomposition in variational inequalities and convex programming

A classical method for solving the variational inequality problem is the projection algorithm. We show that existing convergence results for this algorithm follow from one given by Gabay for a splitting algorithm for finding a zero of the sum of two maximal monotone operators. Moreover, we extend the projection algorithm to solveany monotone affine variational inequality problem. When applied to linear complementarity problems, we obtain a matrix splitting algorithm that is simple and, for linear/quadratic programs, massively parallelizable. Unlike existing matrix splitting algorithms, this algorithm converges under no additional assumption on the problem. When applied to generalized linear/quadratic programs, we obtain a decomposition method that, unlike existing decomposition methods, can simultaneously dualize the linear constraints and diagonalize the cost function. This method gives rise to highly parallelizable algorithms for solving a problem of deterministic control in discrete time and for computing the orthogonal projection onto the intersection of convex sets.This research is partially supported by the U.S. Army Research Office, contract DAAL03-86-K-0171 (Center for Intelligent Control Systems), and by the National Science Foundation under grant NSF-ECS-8519058.Thanks are due to Professor J.-S. Pang for his helpful comments.     

ON AN EFFICIENT IMPLEMENTATION OF THE FACE ALGORITHM FOR LINEAR PROGRAMMING＊

In this paper, we consider the solution of the standard linear programming [Lt＇）. A remarkable result in LP claims that all optimal solutions form an optimal face of the underlying polyhedron. In practice, many real-world problems have infinitely many optimal solutions and pursuing the optimal face, not just an optimal vertex, is quite desirable. The face algorithm proposed by Pan [19] targets at the optimal face by iterating from face to face, along an orthogonal projection of the negative objective gradient onto a relevant null space. The algorithm exhibits a favorable numerical performance by comparing the simplex method. In this paper, we further investigate the face algorithm by proposing an improved implementation. In exact arithmetic computation, the new algorithm generates the same sequence as Pan＇s face algorithm, but uses less computational costs per iteration, and enjoys favorable properties for sparse problems.     

Another version of the proximal point algorithm in a Banach space

In this paper, we study some non-traditional schemes of proximal point algorithm for nonsmooth convex functionals in a Banach space. The proximal approximations to their minimal points and/or their minimal values are considered separately for unconstrained and constrained minimization problems on convex closed sets. For the latter we use proximal point algorithms with the metric projection operators and first establish the estimates of the convergence rate with respect to functionals. We also investigate the perturbed projection proximal point algorithms and prove their stability. Some results concerning the classical proximal point method for minimization problems in a Banach space is also presented in this paper.     

Iterative Algorithms for Equilibrium Problems

We consider equilibrium problems in the framework of the formulation proposed by Blum and Oettli, which includes variational inequalities, Nash equilibria in noncooperative games, and vector optimization problems, for instance, as particular cases. We show that such problems are particular instances of convex feasibility problems with infinitely many convex sets, but with additional structure, so that projection algorithms for convex feasibility can be modified in order to improve their convergence properties, mainly achieving global convergence without either compactness or coercivity assumptions. We present a sequential projections algorithm with an approximately most violated constraint control strategy, and two variants where exact orthogonal projections are replaced by approximate ones, using separating hyperplanes generated by subgradients. We include full convergence analysis of these algorithms.     

Composite orthogonal projection methods for large matrix eigenproblems

For classical orthogonal projection methods for large matrix eigenproblems, it may be much more difficult for a Ritz vector to converge than for its corresponding Ritz value when the matrix in question is non-Hermitian. To this end, a class of new refined orthogonal projection methods has been proposed. It is proved that in some sense each refined method is a composite of two classical orthogonal projections, in which each refined approximate eigenvector is obtained by realizing a new one of some Hermitian semipositive definite matrix onto the same subspace. Apriori error bounds on the refined approximate eigenvector are established in terms of the sine of acute angle of the normalized eigenvector and the subspace involved. It is shown that the sufficient conditions for convergence of the refined vector and that of the Ritz value are the same, so that the refined methods may be much more efficient than the classical ones.     

On variable-step relaxed projection algorithm for variational inequalities

Projection algorithms are practically useful for solving variational inequalities (VI). However some among them require the knowledge related to VI in advance, such as Lipschitz constant. Usually it is impossible in practice. This paper studies the variable-step basic projection algorithm and its relaxed version under weakly co-coercive condition. The algorithms discussed need not know constant/function associated with the co-coercivity or weak co-coercivity and the step-size is varied from one iteration to the next. Under certain conditions the convergence of the variable-step basic projection algorithm is established. For the practical consideration, we also give the relaxed version of this algorithm, in which the projection onto a closed convex set is replaced by another projection at each iteration and latter is easy to calculate. The convergence of relaxed scheme is also obtained under certain assumptions. Finally we apply these two algorithms to the Split Feasibility Problem (SFP).     

Locked and Unlocked Polygonal Chains in Three Dimensions

This paper studies movements of polygonal chains in three dimensions whose links are not allowed to cross or change length. Our main result is an algorithmic proof that any simple closed chain that initially takes the form of a planar polygon can be made convex in three dimensions. Other results include an algorithm for straightening open chains having a simple orthogonal projection onto some plane, and an algorithm for making convex any open chain initially configured on the surface of a polytope. All our algorithms require only O(n) basic ``moves.' Received October 9, 1999, and in revised form February 6, 2001, and April 26, 2001. Online publication August 28, 2001.