A class of collinear scaling algorithms for bound-constrained optimization: Convergence theorems

A family of algorithms for approximate solution of the bound-constrained minimization problem was introduced in [K.A. Ariyawansa, W.L. Tabor, A class of collinear scaling algorithms for bound-constrained optimization: Derivation and computational results, Technical Report 2003-1, Department of Mathematics, Washington State University, Pullman, WA, 2003, submitted for publication. Available at http://www.math.wsu.edu/math/TRS/2003-1.pdf]. These algorithms employ the standard barrier method, with the inner iteration based on trust region methods. Local models are conic functions rather than the usual quadratic functions, and are required to match first and second derivatives of the barrier function at the current iterate. The various members of the family are distinguished by the choice of a vector-valued parameter, which is the zero vector in the degenerate case that quadratic local models are used. This paper presents a convergence analysis of the family of algorithms presented in [K.A. Ariyawansa, W.L. Tabor, A class of collinear scaling algorithms for bound-constrained optimization: Derivation and computational results, Technical Report 2003-1, Department of Mathematics, Washington State University, Pullman, WA, 2003, submitted for publication. Available at http://www.math.wsu.edu/math/TRS/2003-1.pdf]. Specifically, convergence properties similar to those of barrier methods using quadratic local models are established.     

Variable metric algorithms: Necessary and sufficient conditions for identical behavior of nonquadratic functions

Huang (Ref. 1) introduced a general family of variable metric updating formulas and showed that, for a convex quadratic function, all members of this family generate the same sequence of points and converge in at mostn steps. Huang and Levy (Ref. 2) published numerical data showing the behavior of this family for nonquadratic functions and concluded that this family could be divided into subsets that also generate sequences of identical points on more general functions. In this paper, the necessary and sufficient conditions for a group of algorithms to form part of one of these subsets are given.     

Conjugate Gradient Algorithms: Quadratic Termination without Linear Searches

This paper studies the behaviour of a family of conjugate gradientoptimization algorithms, of which the best known is probablythat introduced in 1964 by Fletcher & Reeves. This familyhas the property that, on a quadratic function, the directionsgenerated by any member of the family are the same set of conjugatedirections providing that, at each iteration, an exact linearsearch is performed. In this paper a modification is introduced that enables thisset of conjugate directions to be generated without any accurateline searches. This enables the minimum of a quadratic functionto be found in, at most, (n+2) gradient evaluations. As themodification only requires the storage of two additional n-vectors,the storage advantage of conjugate gradient algorithms viz-?-vizvariable metric algorithms is maintained. Finally, a numerical study is reported in which the performanceof this new method is compared to that of various members ofthe unmodified family.     

Conjugate Directions without Linear Searches

A modified form of the Quasi-Newton family of variable metricalgorithms used in function minimization is proposed that hasquadratic termination without requiring linear searches. Mostmembers of the Quasi-Newton family rely for quadratic terminationon the fact that with accurate linear searches the directionsgenerated, form a conjugate set when the function is quadratic.With some members of the family the convergence of the sequenceof approximate inverse Hessian matrices to the true inverseHessian is also stable. With the proposed modification the samesequence of matrices and the same set of conjugate directionsare generated without accurate linear searches. On a quadratic function the proposal is also related to a suggestionby Hestenes which generates the same set of conjugate directionswithout accurate linear searches. Both methods therefore findthe minimum of an n dimensional quadratic function in at mostn+2 function and gradient calls. On non-quadratic functions the proposal retains the main advantagesclaimed for both the stable Quasi-Newton and Hestenes approaches.It shows promise in that it is competitive with the most efficientunconstrained optimization algorithms currently available.     

Specialised versus general-purpose algorithms for minimising functions that are sums of squared terms

A family of test-problems is described which is designed to investigate the relative efficiencies of general optimisation algorithms and specialised algorithms for the solution of nonlinear sums-of-squares problems. Five algorithms are tested on three members of the family, and it is shown that the best choice of algorithms is critically affected by the value of one parameter in the test functions.     

New algebraic approaches to classical boundary layer problems

Classical non-steady boundary layer equations are fundamental nonlinear partial differential equations in the boundary layer theory of fluid dynamics. In this paper, we introduce various schemes with multiple parameter functions to solve these equations and obtain many families of new explicit exact solutions with multiple parameter functions. Moreover, symmetry transformations are used to simplify our arguments. The technique of moving frame is applied in the three-dimensional case in order to capture the rotational properties of the fluid. In particular, we obtain a family of solutions singular on any moving surface, which may be used to study turbulence. Many other solutions are analytic related to trigonometric and hyperbolic functions, which reflect various wave characteristics of the fluid. Our solutions may also help engineers to develop more effective algorithms to find physical numeric solutions to practical models.     

On trust region methods for unconstrained minimization without derivatives

We consider some algorithms for unconstrained minimization without derivatives that form linear or quadratic models by interpolation to values of the objective function. Then a new vector of variables is calculated by minimizing the current model within a trust region. Techniques are described for adjusting the trust region radius, and for choosing positions of the interpolation points that maintain not only nonsingularity of the interpolation equations but also the adequacy of the model. Particular attention is given to quadratic models with diagonal second derivative matrices, because numerical experiments show that they are often more efficient than full quadratic models for general objective functions. Finally, some recent research on the updating of full quadratic models is described briefly, using fewer interpolation equations than before. The resultant freedom is taken up by minimizing the Frobenius norm of the change to the second derivative matrix of the model. A preliminary version of this method provides some very promising numerical results. Presented at NTOC 2001, Kyoto, Japan.     

Equality and inequality constrained optimization algorithms with convergent stepsizes

In this paper, we consider two algorithms for nonlinear equality and inequality constrained optimization. Both algorithms utilize stepsize strategies based on differentiable penalty functions and quadratic programming subproblems. The essential difference between the algorithms is in the stepsize strategies used. The objective function in the quadratic subproblem includes a linear term that is dependent on the penalty functions. The quadratic objective function utilizes an approximate Hessian of the Lagrangian augmented by the penalty functions. In this approximation, it is possible to ignore the second-derivative terms arising from the constraints in the penalty functions.The penalty parameter is determined using a strategy, slightly different for each algorithm, that ensures boundedness as well as a descent property. In particular, the boundedness follows as the strategy is always satisfied for finite values of the parameter.These properties are utilized to establish global convergence and the condition under which unit stepsizes are achieved. There is also a compatibility between the quadratic objective function and the stepsize strategy to ensure the consistency of the properties for unit steps and subsequent convergence rates.This research was funded by SERC and ESRC research contracts. The author is grateful to Professors Laurence Dixon and David Mayne for their comments. The numerical results in the paper were obtained using a program written by Mr. Robin Becker.     

Primal interior-point decomposition algorithms for two-stage stochastic extended second-order cone programming

ABSTRACT

We study and solve the two-stage stochastic extended second-order cone programming problem. We show that the barrier recourse functions and the composite barrier functions for this optimization problem are self-concordant families with respect to barrier parameters. These results are used to develop primal decomposition-based interior-point algorithms. The worst case iteration complexity of the developed algorithms is shown to be the same as that for the short- and long-step primal interior algorithms applied to the extensive formulation of our problem.     

Matrix conditioning and nonlinear optimization

In a series of recent papers, Oren, Oren and Luenberger, Oren and Spedicato, and Spedicato have developed the self-scaling variable metric algorithms. These algorithms alter Broyden's single parameter family of approximations to the inverse Hessian to a double parameter family. Conditions are given on the new parameter to minimize a bound on the condition number of the approximated inverse Hessian while insuring improved step-wise convergence.Davidon has devised an update which also minimizes the bound on the condition number while remaining in the Broyden single parameter family.This paper derives initial scalings for the approximate inverse Hessian which makes members of the Broyden class self-scaling. The Davidon, BFGS, and Oren—Spedicato updates are tested for computational efficiency and stability on numerous test functions, with the results indicating strong superiority computationally for the Davidon and BFGS update over the self-scaling update, except on a special class of functions, the homogeneous functions.     

A unified kernel function approach to primal-dual interior-point algorithms for convex quadratic SDO

Kernel functions play an important role in the design and analysis of primal-dual interior-point algorithms. They are not only used for determining the search directions but also for measuring the distance between the given iterate and the μ-center for the algorithms. In this paper we present a unified kernel function approach to primal-dual interior-point algorithms for convex quadratic semidefinite optimization based on the Nesterov and Todd symmetrization scheme. The iteration bounds for large- and small-update methods obtained are analogous to the linear optimization case. Moreover, this unifies the analysis for linear, convex quadratic and semidefinite optimizations.     

Two Novel Classes of Arbitrary High-Order Structure-Preserving Algorithms for Canonical Hamiltonian Systems

In this paper, we systematically construct two classes of structure-preserving schemes with arbitrary order of accuracy for canonical Hamiltonian systems. The one class is the symplectic scheme, which contains two new families of parameterized symplectic schemes that are derived by basing on the generating function method and the symmetric composition method, respectively. Each member in these schemes is symplectic for any fixed parameter. A more general form of generating functions is introduced, which generalizes the three classical generating functions that are widely used to construct symplectic algorithms. The other class is a novel family of energy and quadratic invariants preserving schemes, which is devised by adjusting the parameter in parameterized symplectic schemes to guarantee energy conservation at each time step. The existence of the solutions of these schemes is verified. Numerical experiments demonstrate the theoretical analysis and conservation of the proposed schemes.     

On the analysis of a simple evolutionary algorithm on quadratic pseudo-boolean functions

Evolutionary algorithms are randomized search heuristics, which are often used as function optimizers. In this paper the well-known (1+1) Evolutionary Algorithm ((1+1) EA) and its multistart variants are studied. Several results on the expected runtime of the (1+1) EA on linear or unimodal functions have already been presented by other authors. This paper is focused on quadratic pseudo-boolean functions, i.e., polynomials of degree 2, a class of functions containing NP-hard optimization problems. Subclasses of the class of all quadratic functions are identified where the (1+1) EA is efficient, for other subclasses the (1+1) EA has exponential expected runtime, but a large enough success probability within polynomial time such that a multistart variant of the (1+1) EA is efficient. Finally, a particular quadratic function is identified where the EA and its multistart variants fail in polynomial time with overwhelming probability.     

Differential gradient methods

A class of recently developed differential descent methods for function minimization is presented and discussed, and a number of algorithms are derived which minimize a quadratic function in a finite number of steps and rapidly minimize general functions. The main characteristics of our algorithms are that a more general curvilinear search path is used instead of a ray and that the eigensystem of the Hessian matrix is associated with the function minimization problem. The curvilinear search paths are obtained by solving certain initial-value systems of differential equations, which also suggest the development of modifications of known numerical integration techniques for use in function minimization. Results obtained on testing the algorithms on a number of test functions are also given and possible areas for future research indicated.     

The skew elliptical distributions and their quadratic forms

In this paper, a family of the skew elliptical distributions is defined and investigated. Some basic properties, such as stochastic representation, marginal and conditional distributions, distribution under linear transformations, moments and moment generating function are derived. The joint distribution of several quadratic forms is obtained. An example is given to show that the distributions of some statistics as the functions of the quadratic forms can be derived for various applications.     

Exponential time integration for fast finite element solutions of some financial engineering problems

We consider exponential time integration schemes for fast numerical pricing of European, American, barrier and butterfly options when the stock price follows a dynamics described by a jump-diffusion process. The resulting pricing equation which is in the form of a partial integro-differential equation is approximated in space using finite elements. Our methods require the computation of a single matrix exponential and we demonstrate using a wide range of numerical tests that the combination of exponential integrators and finite element discretisations with quadratic basis functions leads to highly accurate algorithms for cases when the jump magnitude is Gaussian. Comparison with other time-stepping methods are also carried out to illustrate the effectiveness of our methods.     

Accelerating the DC algorithm for smooth functions

We introduce two new algorithms to minimise smooth difference of convex (DC) functions that accelerate the convergence of the classical DC algorithm (DCA). We prove that the point computed by DCA can be used to define a descent direction for the objective function evaluated at this point. Our algorithms are based on a combination of DCA together with a line search step that uses this descent direction. Convergence of the algorithms is proved and the rate of convergence is analysed under the ?ojasiewicz property of the objective function. We apply our algorithms to a class of smooth DC programs arising in the study of biochemical reaction networks, where the objective function is real analytic and thus satisfies the ?ojasiewicz property. Numerical tests on various biochemical models clearly show that our algorithms outperform DCA, being on average more than four times faster in both computational time and the number of iterations. Numerical experiments show that the algorithms are globally convergent to a non-equilibrium steady state of various biochemical networks, with only chemically consistent restrictions on the network topology.     

A Class of Large-Update and Small-Update Primal-Dual Interior-Point Algorithms for Linear Optimization

In this paper we present a class of polynomial primal-dual interior-point algorithms for linear optimization based on a new class of kernel functions. This class is fairly general and includes the classical logarithmic function, the prototype self-regular function, and non-self-regular kernel functions as special cases. The analysis of the algorithms in the paper follows the same line of arguments as in Bai et al. (SIAM J. Optim. 15:101–128, [2004]), where a variety of non-self-regular kernel functions were considered including the ones with linear and quadratic growth terms. However, the important case when the growth term is between linear and quadratic was not considered. The goal of this paper is to introduce such class of kernel functions and to show that the interior-point methods based on these functions have favorable complexity results. They match the currently best known iteration bounds for the prototype self-regular function with quadratic growth term, the simple non-self-regular function with linear growth term, and the classical logarithmic kernel function. In order to achieve these complexity results, several new arguments had to be used. This research is partially supported by the grant of National Science Foundation of China 10771133 and the Program of Shanghai Pujiang 06PJ14039.