CGS algorithms for unconstrained minimization of functions

In 1952, Hestenes and Stiefel first established, along with the conjugate-gradient algorithm, fundamental relations which exist between conjugate direction methods for function minimization on the one hand and Gram-Schmidt processes relative to a given positive-definite, symmetric matrix on the other. This paper is based on a recent reformulation of these relations by Hestenes which yield the conjugate Gram-Schmidt (CGS) algorithm. CGS includes a variety of function minimization routines, one of which is the conjugate-gradient routine. This paper gives the basic equations of CGS, including the form applicable to minimizing general nonquadratic functions ofn variables. Results of numerical experiments of one form of CGS on five standard test functions are presented. These results show that this version of CGS is very effective.The preparation of this paper was sponsored in part by the US Army Research Office, Grant No. DH-ARO-D-31-124-71-G18.The authors wish to thank Mr. Paul Speckman for the many computer runs made using these algorithms. They served as a good check on the results which they had obtained earlier. Special thanks must go to Professor M. R. Hestenes whose constant encouragement and assistance made this paper possible.     

Extensions of CGS algorithms: Generalized least-square solutions

The CGS (conjugate Gram-Schmidt) algorithms of Hestenes and Stiefel are formulated so as to obtain least-square solutions of a system of equationsg(x)=0 inn independent variables. Both the linear caseg(x)=Ax–h and the nonlinear case are discussed. In the linear case, a least-square solution is obtained in no more thann steps, and a method of obtaining the least-square solution of minimum length is given. In the nonlinear case, the CGS algorithm is combined with the Gauss-Newton process to minimize sums of squares of nonlinear functions. Results of numerical experiments with several versions of CGS on test functions indicate that the algorithms are effective.The author wishes to express appreciation and to acknowledge the ideas and help of Professor M. R. Hestenes which made this paper possible.     

New algorithms for constrained minimax optimization

A constrained minimax problem is converted to minimization of a sequence of unconstrained and continuously differentiable functions in a manner similar to Morrison's method for constrained optimization. One can thus apply any efficient gradient minimization technique to do the unconstrained minimization at each step of the sequence. Based on this approach, two algorithms are proposed, where the first one is simpler to program, and the second one is faster in general. To show the efficiency of the algorithms even for unconstrained problems, examples are taken to compare the two algorithms with recent methods in the literature. It is found that the second algorithm converges faster with respect to the other methods. Several constrained examples are also tried and the results are presented.     

Convergent stepsizes for constrained optimization algorithms

A fundamental problem in constrained nonlinear optimization algorithms is the design of a satisfactory stepsize strategy which converges to unity. In this paper, we discuss stepsize strategies for Newton or quasi-Newton algorithms which require the solution of quadratic optimization subproblems. Five stepsize strategies are considered for three different subproblems, and the conditions under which the stepsizes will converge to unity are established. It is shown that these conditions depend critically on the convergence of the Hessian approximations used in the algorithms. The stepsize strategies are constructed using basic principles from which the conditions to unit stepsizes follow. Numerical results are discussed in an Appendix.Paper presented to the XI Symposium on Mathematical Programming, Bonn, Germany, 1982.This work was completed while the author was visiting the European University in Florence where, in particular, Professors Fitoussi and Velupillai provided the opportunity for its completion. The author is grateful to Dr. L. C. W. Dixon for his helpful comments and criticisms on numerous versions of the paper, and to R. G. Becker for programming the algorithms in Section 3 and for helpful discussions concerning these algorithms.     

An algorithm for constrained smoothing functions

In this paper we study a method for the approximation by a monotone smooth function of a discrete set of observations. By this method it is possible to obtain a completely automatic program. We show that the solution is monotone with probability tending to one and by the test examples that it is sufficient in the practical case.This work was supported by the Italian M.U.R.S.T.     

Genetic algorithms in constrained optimization

The behavior of the two-point crossover operator, on candidate solutions to an optimization problem that is restricted to integer values and by some set of constraints, is investigated theoretically. This leads to the development of new genetic operators for the case in which the constraint system is linear.The computational difficulty asserted by many optimization problems has lead to exploration of a class of randomized algorithms based on biological adaption. The considerable interest that surrounds these evolutionary algorithms is largely centered on problems that have defied satisfactory illation by traditional means because of badly behaved or noisy objective functions, high dimensionality, or intractable algorithmic complexity. Under such conditions, these alternative methods have often proved invaluable.Despite their attraction, the applicability of evolutionary algorithms has been limited by a deficiency of general techniques to manage constraints, and the difficulty is compounded when the decision variables are discrete. Several new genetic operators are presented here that are guaranteed to preserve the feasibility of discrete aspirant solutions with respect to a system of linear constraints.To avoid performance degradation as the probability of finding a feasible and meaningful information exchange between two candidate solutions decreases, relaxations of the modified genetic crossover operator are also proposed. The effective utilization of these also suggests a manipulation of the genetic algorithm itself, in which the population is evanescently permitted to grow beyond its normal size.     

Heuristic algorithms for the cardinality constrained efficient frontier

This paper examines the application of genetic algorithm, tabu search and simulated annealing metaheuristic approaches to finding the cardinality constrained efficient frontier that arises in financial portfolio optimisation. We consider the mean-variance model of Markowitz as extended to include the discrete restrictions of buy-in thresholds and cardinality constraints. Computational results are reported for publicly available data sets drawn from seven major market indices involving up to 1318 assets. Our results are compared with previous results given in the literature illustrating the effectiveness of the proposed metaheuristics in terms of solution quality and computation time.     

Parallel algorithms for large-scale linearly constrained minimization problem

In this paper, two PVD-type algorithms are proposed for solving inseparable linear constraint optimization. Instead of computing the residual gradient function, the new algorithm uses the reduced gradients to construct the PVD directions in parallel computation, which can greatly reduce the computation amount each iteration and is closer to practical applications for solve large-scale nonlinear programming. Moreover, based on an active set computed by the coordinate rotation at each iteration, a feasible descent direction can be easily obtained by the extended reduced gradient method. The direction is then used as the PVD direction and a new PVD algorithm is proposed for the general linearly constrained optimization. And the global convergence is also proved.     

Approximation algorithms for constrained generalized tree alignment problem

In generalized tree alignment problem, we are given a set S of k biologically related sequences and we are interested in a minimum cost evolutionary tree for S. In many instances of this problem partial phylogenetic tree for S is known. In such instances, we would like to make use of this knowledge to restrict the tree topologies that we consider and construct a biologically relevant minimum cost evolutionary tree. So, we propose the following natural generalization of the generalized tree alignment problem, a problem known to be MAX-SNP Hard, stated as follows:

Constrained Generalized Tree Alignment Problem [S. Divakaran, Algorithms and heuristics for constrained generalized alignment problem, DIMACS Technical Report 2007-21, 2007]: Given a set S of k related sequences and a phylogenetic forest comprising of node-disjoint phylogenetic trees that specify the topological constraints that an evolutionary tree of S needs to satisfy, construct a minimum cost evolutionary tree for S.

In this paper, we present constant approximation algorithms for the constrained generalized tree alignment problem. For the generalized tree alignment problem, a special case of this problem, our algorithms provide a guaranteed error bound of 2−2/k.     

Augmented Lagrangian functions for constrained optimization problems

In this paper, in order to obtain some existence results about solutions of the augmented Lagrangian problem for a constrained problem in which the objective function and constraint functions are noncoercive, we construct a new augmented Lagrangian function by using an auxiliary function. We establish a zero duality gap result and a sufficient condition of an exact penalization representation for the constrained problem without the coercive or level-bounded assumption on the objective function and constraint functions. By assuming that the sequence of multipliers is bounded, we obtain the existence of a global minimum and an asymptotically minimizing sequence for the constrained optimization problem.     

Some proximal algorithms for linearly constrained general variational inequalities

Based on the classical proximal point algorithm (PPA), some PPA-based numerical algorithms for general variational inequalities (GVIs) have been developed recently. Inspired by these algorithms, in this article we propose some proximal algorithms for solving linearly constrained GVIs (LCGVIs). The resulted subproblems are regularized proximally, and they are allowed to be solved either exactly or approximately.     

Strip generation algorithms for constrained two-dimensional two-staged cutting problems

The constrained two-dimensional cutting (C_TDC) problem consists of determining a cutting pattern of a set of n small rectangular piece types on a rectangular stock plate of length L and width W, as to maximize the sum of the profits of the pieces to be cut. Each piece type i, i = 1, …, n, is characterized by a length l_i, a width w_i, a profit (or weight) c_i and an upper demand value b_i. The upper demand value is the maximum number of pieces of type i which can be cut on rectangle (L, W). In this paper, we study the two-staged fixed orientation C_TDC, noted FC_2TDC. It is a classical variant of the C_TDC where each piece is produced, in the final cutting pattern, by at most two guillotine cuts, and each piece has a fixed orientation. We solve the FC_2TDC problem using several approximate algorithms, that are mainly based upon a strip generation procedure. We evaluate the performance of these algorithms on instances extracted from the literature.     

Superlinearly convergent quasi-newton algorithms for nonlinearly constrained optimization problems

A class of algorithms for nonlinearly constrained optimization problems is proposed. The subproblems of the algorithms are linearly constrained quadratic minimization problems which contain an updated estimate of the Hessian of the Lagrangian. Under suitable conditions and updating schemes local convergence and a superlinear rate of convergence are established. The convergence proofs require among other things twice differentiable objective and constraint functions, while the calculations use only first derivative data. Rapid convergence has been obtained in a number of test problems by using a program based on the algorithms proposed here.Research supported by NSF Grant GJ-35292 at the University of Wisconsin.     

Universal algorithms for evaluating boolean functions

Theorems relating the most important concepts of switching theory to a new kind of difference operator are stated. This difference operator is then used as a unifying concept to solve, by means of a new type of algorithm, several problems arising in logical design.     

A class of quadratically convergent algorithms for constrained function minimization

The problem of minimizing a functionf(x) subject to the constraint ?(x)=0 is considered. Here,f is a scalar,x is ann-vector, and ? is anm-vector, wherem <n. A general quadratically convergent algorithm is presented. The conjugate-gradient algorithm and the variable-metric algorithms for constrained function minimization can be obtained as particular cases of the general algorithm. It is shown that, for a quadratic function subject to a linear constraint, all the particular algorithms behave identically if the one-dimensional search for the stepsize is exact. Specifically, they all produce the same sequence of points and lead to the constrained minimal point in no more thann ?r descent steps, wherer is the number of linearly independent constraints. The algorithms are then modified so that they can also be employed for a nonquadratic function subject to a nonlinear constraint. Some particular algorithms are tested through several numerical examples.     

Some theoretical limitations of second-order algorithms for smooth constrained optimization

In second-order algorithms, we investigate the relevance of the constant rank of the full set of active constraints in ensuring global convergence to a second-order stationary point under a constraint qualification. We show that second-order stationarity is not expected in the non-constant rank case if the growth of so-called tangent AKKT2 sequences is not controlled. Since no algorithm controls their growth, we argue that there is a theoretical limitation of algorithms in finding second-order stationary points without constant rank assumptions.     

On a subproblem of trust region algorithms for constrained optimization

We study a subproblem that arises in some trust region algorithms for equality constrained optimization. It is the minimization of a general quadratic function with two special quadratic constraints. Properties of such subproblems are given. It is proved that the Hessian of the Lagrangian has at most one negative eigenvalue, and an example is presented to show that the Hessian may have a negative eigenvalue when one constraint is inactive at the solution.Research supported by a Research Fellowship of Fitzwilliam College, Cambridge, and by a research grant from the Chinese Academy of Sciences.     

An algorithm for computing constrained smoothing spline functions

Summary The problem of computing constrained spline functions, both for ideal data and noisy data, is considered. Two types of constriints are treated, namely convexity and convexity together with monotonity. A characterization result for constrained smoothing splines is derived. Based on this result a Newton-type algorithm is defined for computing the constrained spline function. Thereby it is possible to apply the constraints over a whole interval rather than at a discrete set of points. Results from numerical experiments are included.     

Modified potential energy functions for constrained molecular dynamics

In molecular dynamics the highly oscillatory vibrations in the chemical bonds are often replaced by holonomic constraints that freeze the bond length/angle to its equilibrium value. In some cases this approach can be justified if the force constants of the bond vibrations are sufficiently large. However, for moderate values of the force constant, the constrained system might lead to a dynamical behavior that is too “rigid” compared to the flexible model. To compensate for this effect, the concept of soft constraints was introduced in [7,12,13]. However, its implementation is rather expensive. In this paper, we suggest an alternative approach that modifies the force field instead of the constraint functions. This leads to a more efficient method that avoids the resonance induced instabilities of multiple-time-stepping [5] and the above described effect of standard constrained dynamics. This revised version was published online in June 2006 with corrections to the Cover Date.