A quadratically approximate framework for constrained optimization,global and local convergence

This paper presents a quadratically approximate algorithm framework （QAAF） for solving general constrained optimization problems, which solves, at each iteration, a subproblem with quadratic objective function and quadratic equality together with inequality constraints. The global convergence of the algorithm framework is presented under the Mangasarian-Fromovitz constraint qualification （MFCQ）, and the conditions for superlinear and quadratic convergence of the algorithm framework are given under the MFCQ, the constant rank constraint qualification （CRCQ） as well as the strong second-order sufficiency conditions （SSOSC）. As an incidental result, the definition of an approximate KKT point is brought forward, and the global convergence of a sequence of approximate KKT points is analysed.     

Sequential stopping rules for the multistart algorithm in global optimisation

In this paper a sequential stopping rule is developed for the Multistart algorithm. A statistical model for the values of the observed local maxima of an objective function is introduced in the framework of Bayesian non-parametric statistics. A suitablea-priori distribution is proposed which is general enough and which leads to computationally manageable expressions for thea-posteriori distribution. Sequential stopping rules of thek-step look-ahead kind are then explicitly derived, and their numerical effectiveness compared.     

OnQ-order andR-order of convergence

We give sufficient conditions for a sequence to have theQ-order and/or theR-order of convergence greater than one. If an additional condition is satisfied, then the sequence has an exactQ-order of convergence. We show that our results are sharp and we compare them with older results.This work was supported in part by the National Science Foundation under Grant No. DMS-85-03365. The author wishes to thank J. E. Dennis and R. A. Tapia for helpful comments, and the referee for pointing out a number of typographical and mathematical errors in the original version of this paper.     

The least element property of center location on tree networks with applications to distance and precedence constrained problems

In the classicalp-center location model on a network there is a set of customers, and the primary objective is to selectp service centers that will minimize the maximum distance of a customer to a closest center. Suppose that thep centers receive their supplies from an existing central depot on the network, e.g. a warehouse. Thus, a secondary objective is to locate the centers that optimize the primary objective as close as possible to the central depot. We consider tree networks and twop-center models. We show that the set of optimal solutions to the primary objective has a semilattice structure with respect to some natural ordering. Using this property we prove that there is ap-center solution to the primary objective that simultaneously minimizes every secondary objective function which is monotone nondecreasing in the distances of thep centers from the existing central depot.Restricting the location models to a rooted path network (real line) we prove that the above results hold for the respective classicalp-median problems as well.     

A network location-allocation model trading off flow capturing andp-median objectives

The flow capturing and thep-median location—allocation models deal quite differently with demand for service in a network. Thep-median model assumes that demand is expressed at nodes and locates facilities to minimize the total distance between such demand nodes and the nearest facility. The flow-capturing model assumes that demand is expressed on links and locates facilities to maximize the one-time exposure of such traffic to facilities. Demand in a network is often of both types: it is expressed by passing flows and by consumers centred in residential areas, aggregated as nodes. We here present a hybrid model with the dual objective of serving both types of demand. We use this model to examine the tradeoff between serving the two types of demand in a small test network using synthetic demand data. A major result is the counter-intuitive finding that thep-median model is more susceptible to impairment by the flow capturing objective than is the flow capturing model to thep-median objective. The results encourage us to apply the model to a real-world network using actual traffic data.     

Discrete optimization on a multivariable boolean lattice

Consider the problem of finding the minimum value of a scalar objective function whose arguments are theN components of 2 ^N vector elements partially ordered as a Boolean lattice. If the function is strictly decreasing along any shortest path from the minimum point to its logical complement, then the minimum can be located precisely after sequential measurement of the objective function atN + 1 points. This result suggests a new line of research on discrete optimization problems.This paper was presented at the 7th Mathematical Programming Symposium, The Hague, The Netherlands.This research was supported in part by U.S. Office of Saline Water Grant No. 699.     

Global Convergence of Conjugate Gradient Methods without Line Search

Global convergence results are derived for well-known conjugate gradient methods in which the line search step is replaced by a step whose length is determined by a formula. The results include the following cases: (1) The Fletcher–Reeves method, the Hestenes–Stiefel method, and the Dai–Yuan method applied to a strongly convex LC ¹ objective function; (2) The Polak–Ribière method and the Conjugate Descent method applied to a general, not necessarily convex, LC ¹ objective function.     

Ordinary convex programs without a duality gap

In the Kuhn-Tucker theory of nonlinear programming, there is a close relationship between the optimal solutions to a given minimization problem and the saddlepoints of the corresponding Lagrangian function. It is shown here that, if the constraint functions and objective function arefaithfully convex in a certain broad sense and the problem has feasible solutions, then theinf sup andsup inf of the Lagrangian are necessarily equal.This work was supported in part by the Air Force Office of Scientific Research under Grant No. AF-AFOSR-1202-67B.     

An acceleration property of theE-algorithm for alternate sequences

We prove a convergence acceleration result by theE-algorithm for sequences whose error has an asymptotic expansion on the scale of comparison for which a determinantal relation holds. This result is generalized to the vector case. Moreover we prove a result which contains an acceleration property for columns and diagonals of theE array. This result is applied to some alternating series.     

OnA-stable implicit Runge-Kutta methods

An elementary proof is given of theA-stability of implicit Runge-Kutta methods for which the corresponding rational function is on the diagonal or one of the first two subdiagonals of the Padé table for the exponential function. The result is extended to give necessary and sufficient conditions for theA-stability ofn-stage methods of order greater than or equal to 2n–2.     

Zero duality gap for a class of nonconvex optimization problems

By an equivalent transformation using thepth power of the objective function and the constraint, a saddle point can be generated for a general class of nonconvex optimization problems. Zero duality gap is thus guaranteed when the primal-dual method is applied to the constructed equivalent form.The author very much appreciates the comments from Prof. Douglas J. White.     

The Convergence of a Levenberg–Marquardt Method for Nonlinear Inequalities

In this paper, we consider the least l ₂-norm solution for a possibly inconsistent system of nonlinear inequalities. The objective function of the problem is only first-order continuously differentiable. By introducing a new smoothing function, the problem is approximated by a family of parameterized optimization problems with twice continuously differentiable objective functions. Then a Levenberg–Marquardt algorithm is proposed to solve the parameterized smooth optimization problems. It is proved that the algorithm either terminates finitely at a solution of the original inequality problem or generates an infinite sequence. In the latter case, the infinite sequence converges to a least l ₂-norm solution of the inequality problem. The local quadratic convergence of the algorithm was produced under some conditions.     

On the superlinear local convergence of a filter-SQP method

Transition to superlinear local convergence is shown for a modified version of the trust-region filter-SQP method for nonlinear programming introduced by Fletcher, Leyffer, and Toint [8]. Hereby, the original trust-region SQP-steps can be used without an additional second order correction. The main modification consists in using the Lagrangian function value instead of the objective function value in the filter together with an appropriate infeasibility measure. Moreover, it is shown that the modified trust-region filter-SQP method has the same global convergence properties as the original algorithm in [8].Mathematics Subject Classification (2000): 90C55, 65K05, 90C30     

A pathological semi-infinite program verifying Karlovitz's conjecture

In 1965, Duffin and Karlovitz approximated semi-infinite linear programs by a sequence of linear programs where thenth approximating program minimizes the objective function, subject to the firstn constraints. At that time, Karlovitz conjectured the existence of a semi-infinite convex program without a duality gap, whose approximating programs have a duality gap. The purpose of this note is to provide such an example.The author completed this work while at the University of Illinois at Urbana-Champaign, Illinois.     

Necessary and sufficient optimality conditions for a class of nonsmooth minimization problems

The purpose of this paper is to derive, in a unified way, second order necessary and sufficient optimality criteria, for four types of nonsmooth minimization problems: thediscrete minimax problem, thediscrete l ₁-approximation, the minimization of theexact penalty function and the minimization of theclassical exterior penalty function. Our results correct and supplement conditions obtained by various authors in recent papers.     

Zeta functions of<Emphasis Type="Italic">q</Emphasis>-perfect numbers

We introduce a notion ofq-analogue of the perfect numbers. We also define a new zeta function which we call a zeta function ofq-perfect numbers. In this paper, the properties of theq-perfect numbers and the zeta functions are studied. Especially, we determine theq-perfect numbers whenq is a root of unity.     

Nonlinear programming without a penalty function or a filter

A new method is introduced for solving equality constrained nonlinear optimization problems. This method does not use a penalty function, nor a filter, and yet can be proved to be globally convergent to first-order stationary points. It uses different trust-regions to cope with the nonlinearities of the objective function and the constraints, and allows inexact SQP steps that do not lie exactly in the nullspace of the local Jacobian. Preliminary numerical experiments on CUTEr problems indicate that the method performs well.      

Topographical Multilevel Single Linkage

An iterative topographical Multilevel Single Linkage (TMSL) method has been introduced. The approach uses topographical information on the objective function, in particular theg-nearest-neighbour graph. The algorithm uses evenly distributed points from a Halten sequence of uniform limiting density. We discuss the implementation of the algorithm and compare its performance with other well-known algorithms. The new algorithm performs much better (in some cases several times) than the Multilevel Single Linkage method in terms of number of function evaluations but is not quite so competitive with respect to CPU time.     

Network planning under uncertainty with an application to hydropower generation

Summary We present a general modeling framework for therobust optimization of linear network problems with uncertainty in the values of the right-hand side. In contrast to traditional approaches in mathematical programming, we use scenarios to characterize the uncertainty. Solutions are obtained for each scenario and these individual scenarios are aggregated to yield a nonanticipative or implementable policy that minimizes the regret of wrong decisions. A given solution is termed robust if it minimizes the sum over the scenarios of the weighted upper difference between the objective function value for the solution and the objective function value for the optimal solution for each scenario, while satisfying certain nonanticipativity constraints. This approach results in a huge model with a network submodel per scenario plus coupling constraints. Several decomposition approaches are considered, namely Dantzig-Wolfe decomposition, various types of Benders decomposition and different quadratic network approaches for approximating Augmented Lagrangian decomposition. We present computational results for these methods, including two implementation versions of the Lagrangian based method: a sequential implementation and a parallel implementation on a network of three workstations.     

A Trust Region Method for Optimization Problem with Singular Solutions

In this paper, we propose a trust region method for minimizing a function whose Hessian matrix at the solutions may be singular. The global convergence of the method is obtained under mild conditions. Moreover, we show that if the objective function is LC ² function, the method possesses local superlinear convergence under the local error bound condition without the requirement of isolated nonsingular solution. This is the first regularized Newton method with trust region technique which possesses local superlinear (quadratic) convergence without the assumption that the Hessian of the objective function at the solution is nonsingular. Preliminary numerical experiments show the efficiency of the method. This work is partly supported by the National Natural Science Foundation of China (Grant Nos. 70302003, 10571106, 60503004, 70671100) and Science Foundation of Beijing Jiaotong University (2007RC014).