A rank-one algorithm for unconstrained function minimization

A rank-one algorithm is presented for unconstrained function minimization. The algorithm is a modified version of Davidon's variance algorithm and incorporates a limited line search. It is shown that the algorithm is a descent algorithm; for quadratic forms, it exhibits finite convergence, in certain cases. Numerical studies indicate that it is considerably superior to both the Davidon-Fletcher-Powell algorithm and the conjugate-gradient algorithm.     

A faster strongly polynomial time algorithm for submodular function minimization

We consider the problem of minimizing a submodular function f defined on a set V with n elements. We give a combinatorial algorithm that runs in O(n ⁵EO  +  n ⁶) time, where EO is the time to evaluate f(S) for some . This improves the previous best strongly polynomial running time by more than a factor of n. We also extend our result to ring families.     

Coordinatewise domain scaling algorithm for M-convex function minimization

We present a polynomial time scaling algorithm for the minimization of an M-convex function. M-convex functions are nonlinear discrete functions with (poly)matroid structures, which are being recognized as playing a fundamental role in tractable cases of discrete optimization. The algorithm is applicable also to a variant of quasi M-convex functions.Mathematics Subject Classification (2000):90C27, 68W40, 05B35This work is supported by a Grant-in-Aid for Scientific Research from the Ministry of Education, Culture, Sports, Science and Technology of Japan.     

A modified Newton method for minimization

Some promising ideas for minimizing a nonlinear function, whose first and second derivatives are given, by a modified Newton method, were introduced by Fiacco and McCormick (Ref. 1). Unfortunately, in developing a method around these ideas, Fiacco and McCormick used a potentially unstable, or even impossible, matrix factorization. Using some recently developed techniques for factorizing an indefinite symmetric matrix, we are able to produce a method which is similar to Fiacco and McCormick's original method, but avoids the difficulties of the original method.Both authors gratefully acknowledge the award of a research fellowship from the British Science Research Council.     

A modified secant method for unconstrained minimization

This paper presents a new globally convergent secant method for unconstrained optimization. The root rate of convergence of this algorithm is superlinear, between 1 and 2, decreasing with dimension of the problem. It is shown that on a class of problems, it is substantially more efficient than a number of other algorithms.     

A global minimization algorithm for Lipschitz functions

The global optimization problem with and f(x) satisfying the Lipschitz condition , is considered. To solve it a region-search algorithm is introduced. This combines a local minimum algorithm with a procedure that at the ith iteration finds a region S _i where the global minimum has to be searched for. Specifically, by making use of the Lipschitz condition, S _i , which is a sequence of intervals, is constructed by leaving out from S _i-1 an interval where the global minimum cannot be located. A convergence property of the algorithm is given. Further, the ratio between the measure of the initial feasible region and that of the unexplored region may be used as stop rule. Numerical experiments are carried out; these show that the algorithm works well in finding and reducing the measure of the unexplored region.     

A generalized conjugate gradient algorithm for minimization

Summary A generalized conjugate gradient algorithm which is invariant to a nonlinear scaling of a strictly convex quadratic function is described, which terminates after at mostn steps when applied to scaled quadratic functionsf: R _n R₁ of the formf(x)=h(F(x)) withF(x) strictly convex quadratic andhC ¹ (R₁) an arbitrary strictly monotone functionh. The algorithm does not suppose the knowledge ofh orF but only off(x) and its gradientg(x).     

A modified wolfe dual for weak vector minimization

A version of the Wolfe dual problem is constructed for constained weak minimization of a vector objective function, in finite or infinite dimensions (e.g. continuous programming) The usual convex requirements are weakened to invex. Weak duality is replaced by an inclusion, constructed using the cone defining the weak minimum. Relations with Pareto (or proper Pareto) minima are discussed.     

A modified homogeneous potential reduction algorithm for solving the monotone semidefinite linear complementarity problem

In this paper, we study the performance of the Semidefinite Linear Complementarity Problem (SDLCP) for symmetric matrices that is equipped with a continuously differentiable potential function. A practical homogeneous self-dual potential reduction algorithm based on this potential function is prescribed, and we establish a computational basis for interior point methods with the use of HKM directions towards the central trajectory for the monotone SDLCP. Our computational implementation maintains a global linear polynomial time convergence, while achieving strong practical performance in comparison with existing solution methods.     

A relaxation algorithm for the minimization of a quasiconcave function on a convex polyhedron

A study was made of the global minimization of a general quasiconcave function on a convex polyhedron. This nonconvex problem arises in economies of scale environments and in alternative formulations of other well-known problems, as in the case of bilinear programming.Although not very important in our final results, a local minimum can be easily obtained. However, a major aspect is the existence of two families of lower bounds on the optimal functional value: one is provided by non-linear programming duality, the other is derived from a lexicographic ordering of basic solutions which allows the use of relaxation concepts. These results were exploited in a finite algorithm for obtaining the global minimum whose initial implementation has had encouraging performance.     

A descent method for submodular function minimization

We show a descent method for submodular function minimization based on an oracle for membership in base polyhedra. We assume that for any submodular function f: ?→R on a distributive lattice ?⊆2 ^V with ?,V∈? and f(?)=0 and for any vector x∈R ^V where V is a finite nonempty set, the membership oracle answers whether x belongs to the base polyhedron associated with f and that if the answer is NO, it also gives us a set Z∈? such that x(Z)>f(Z). Given a submodular function f, by invoking the membership oracle O(|V|²) times, the descent method finds a sequence of subsets Z ₁,Z ₂,···,Z _k of V such that f(Z ₁)>f(Z ₂)>···>f(Z _k )=min{f(Y) | Y∈?}, where k is O(|V|²). The method furnishes an alternative framework for submodular function minimization if combined with possible efficient membership algorithms. Received: September 9, 2001 / Accepted: October 15, 2001?Published online December 6, 2001     

A pseudo Newton-Raphson method for function minimization

A pseudo Newton-Raphson algorithm for function minimization is presented. As in all such algorithms, an estimate of the inverse Hessian is calculated. In this case, the estimate is of the formXZX ^T , whereZ is a diagonal matrix; and this feature permits the use of the simple procedures to maintain the positive definiteness ofZ, and hence of the restriction ofXZX ^T to the range ofX. The algorithm is shown to have finite convergence for quadratic functions and asymptotic convergence for a fairly general class of functions. Some numerical results are presented, and the extension of the algorithm to deal with linear equality and inequality constraints is briefly discussed.R. Mamen acknowledges with gratitude the financial support afforded by an Athlone Fellowship and a National Research Council of Canada Post-Graduate Bursary. Dr. S. C. Chuang made useful comments on some of the proofs. Some of the results are closely related to those of Allwright (Ref. 1).     

A polynomial oracle-time algorithm for convex integer minimization

In this paper we consider the solution of certain convex integer minimization problems via greedy augmentation procedures. We show that a greedy augmentation procedure that employs only directions from certain Graver bases needs only polynomially many augmentation steps to solve the given problem. We extend these results to convex N-fold integer minimization problems and to convex 2-stage stochastic integer minimization problems. Finally, we present some applications of convex N-fold integer minimization problems for which our approach provides polynomial time solution algorithms.     

A rapidly convergent five-point algorithm for univariate minimization

This paper presents an algorithm for minimizing a function of one variable which uses function, but not derivative, values at five-points to generate each iterate. It employs quadratic and polyhedral approximations together with a safeguard. The basic method without the safeguard exhibits a type of better than linear convergence for certain piecewise twice continuously differentiable functions. The safeguard guarantees convergence to a stationary point for very general functions and preserves the better than linear convergence of the basic method.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.Research sponsored by the Institut National de Recherche en Informatique et Automatique, Rocquencourt, France, and by the Air Force Office of Scientific Research, Air Force System Command, USAF, under Grant Number AFOSR-83-0210.Research sponsored, in part, by the Institut National de Recherche en Informatique et Automatique, Rocquencourt, France.     

A modified alternating direction method for convex minimization problems

The alternating direction method is an attractive approach for large problems. The convergence proof of the method is based on the exact solutions of the subproblems. Computing the solution of the subproblems exactly can be expensive if the number of unknowns is large. In this paper, for convex quadratic minimization problems, we propose a modified alternating direction method which can overcome the above mentioned disadvantage.     

An effective algorithm for minimization

An algorithm is proposed for minimizing certain niceC ² functionsf onE _n assuming only a computational knowledge off andf. It is shown that the algorithm provides global convergence at a rate which is eventually superlinear and possibly quadratic. The algorithm is purely algebraic and does not require the minimization of any functions of one variable.Numerical computation on specific problems with as many as six independent variables has shown that the method compares very favorably with the best of the other known methods. The method is compared with theFletcher andPowell method for a simple two dimensional test problem and for a six dimensional problem arising in control theory.Supported by Air Force grant AF-AFO SR-93 7-65 and Boeing Scientific Research Laboratories.     

A combined conjugate-gradient quasi-Newton minimization algorithm

Although quasi-Newton algorithms generally converge in fewer iterations than conjugate gradient algorithms, they have the disadvantage of requiring substantially more storage. An algorithm will be described which uses an intermediate (and variable) amount of storage and which demonstrates convergence which is also intermediate, that is, generally better than that observed for conjugate gradient algorithms but not so good as in a quasi-Newton approach. The new algorithm uses a strategy of generating a form of conjugate gradient search direction for most iterations, but it periodically uses a quasi-Newton step to improve the convergence. Some theoretical background for a new algorithm has been presented in an earlier paper; here we examine properties of the new algorithm and its implementation. We also present the results of some computational experience.This research was supported by the National Research Council of Canada grant number A-8962.     

A biased random-key genetic algorithm for road congestion minimization

One of the main goals in transportation planning is to achieve solutions for two classical problems, the traffic assignment and toll pricing problems. The traffic assignment problem aims to minimize total travel delay among all travelers. Based on data derived from the first problem, the toll pricing problem determines the set of tolls and corresponding tariffs that would collectively benefit all travelers and would lead to a user equilibrium solution. Obtaining high-quality solutions for this framework is a challenge for large networks. In this paper, we propose an approach to solve the two problems jointly, making use of a biased random-key genetic algorithm for the optimization of transportation network performance by strategically allocating tolls on some of the links of the road network. Since a transportation network may have thousands of intersections and hundreds of road segments, our algorithm takes advantage of mechanisms for speeding up shortest-path algorithms.     

A parallel algorithm for constrained concave quadratic global minimization

The global minimization of large-scale concave quadratic problems over a bounded polyhedral set using a parallel branch and bound approach is considered. The objective function consists of both a concave part (nonlinear variables) and a strictly linear part, which are coupled by the linear constraints. These large-scale problems are characterized by having the number of linear variables much greater than the number of nonlinear variables. A linear underestimating function to the concave part of the objective is easily constructed and minimized over the feasible domain to get both upper and lower bounds on the global minimum function value. At each minor iteration of the algorithm, the feasible domain is divided into subregions and linear underestimating problems over each subregion are solved in parallel. Branch and bound techniques can then be used to eliminate parts of the feasible domain from consideration and improve the upper and lower bounds. It is shown that the algorithm guarantees that a solution is obtained to within any specified tolerance in a finite number of steps. Computational results are presented for problems with 25 and 50 nonlinear variables and up to 400 linear variables. These results were obtained on a four processor CRAY2 using both sequential and parallel implementations of the algorithm. The average parallel solution time was approximately 15 seconds for problems with 400 linear variables and a relative tolerance of 0.001. For a relative tolerance of 0.1, the average computation time appears to increase only linearly with the number of linear variables.