A perfect example for the BFGS method

Consider the BFGS quasi-Newton method applied to a general non-convex function that has continuous second derivatives. This paper aims to construct a four-dimensional example such that the BFGS method need not converge. The example is perfect in the following sense: (a) All the stepsizes are exactly equal to one; the unit stepsize can also be accepted by various line searches including the Wolfe line search and the Arjimo line search; (b) The objective function is strongly convex along each search direction although it is not in itself. The unit stepsize is the unique minimizer of each line search function. Hence the example also applies to the global line search and the line search that always picks the first local minimizer; (c) The objective function is polynomial and hence is infinitely continuously differentiable. If relaxing the convexity requirement of the line search function; namely, (b) we are able to construct a relatively simple polynomial example.     

Regularized Lotka-Volterra Dynamical System as Continuous Proximal-Like Method in Optimization

We introduce and study a new type of dynamical system which combines the continuous gradient method with a nonlinear Lotka-Volterra (LV) type of differential system within a logarithmic-quadratic proximal scheme. We prove a global existence and viability result for the resulting trajectory which holds for a general smooth function. The asymptotic behavior of the produced trajectory is analyzed and global convergence of the trajectory to a minimizer of the convex minimization problem over the nonnegative orthant is established. The implicit discretization which is at the origin of the proposed continuous dynamical system is an interior proximal scheme for minimizing a closed proper convex function, and convergence results and properties of the resulting discrete scheme are also established. We show finally that the trajectories of the family of regularized Lotka-Volterra systems, parametrized by the positive parameter associated with the quadratic proximal term, are uniformly convergent to the solution of the classical LV-dynamical system, as the parameter associated with the proximal term approaches zero.     

Solving nonlinearly constrained global optimization problem via an auxiliary function method

This paper considers the nonlinearly constrained continuous global minimization problem. Based on the idea of the penalty function method, an auxiliary function, which has approximately the same global minimizers as the original problem, is constructed. An algorithm is developed to minimize the auxiliary function to find an approximate constrained global minimizer of the constrained global minimization problem. The algorithm can escape from the previously converged local minimizers, and can converge to an approximate global minimizer of the problem asymptotically with probability one. Numerical experiments show that it is better than some other well known recent methods for constrained global minimization problems.     

Proximity Function Minimization Using Multiple Bregman Projections, with Applications to Split Feasibility and Kullback–Leibler Distance Minimization

Problems in signal detection and image recovery can sometimes be formulated as a convex feasibility problem (CFP) of finding a vector in the intersection of a finite family of closed convex sets. Algorithms for this purpose typically employ orthogonal or generalized projections onto the individual convex sets. The simultaneous multiprojection algorithm of Censor and Elfving for solving the CFP, in which different generalized projections may be used at the same time, has been shown to converge for the case of nonempty intersection; still open is the question of its convergence when the intersection of the closed convex sets is empty.Motivated by the geometric alternating minimization approach of Csiszár and Tusnády and the product space formulation of Pierra, we derive a new simultaneous multiprojection algorithm that employs generalized projections of Bregman to solve the convex feasibility problem or, in the inconsistent case, to minimize a proximity function that measures the average distance from a point to all convex sets. We assume that the Bregman distances involved are jointly convex, so that the proximity function itself is convex. When the intersection of the convex sets is empty, but the closure of the proximity function has a unique global minimizer, the sequence of iterates converges to this unique minimizer. Special cases of this algorithm include the Expectation Maximization Maximum Likelihood (EMML) method in emission tomography and a new convergence result for an algorithm that solves the split feasibility problem.     

Proximal Point Algorithm On Riemannian Manifolds

Abstract

In this paper we consider the minimization problem with constraints. We will show that if the set of constraints is a Riemannian manifold of nonpositive sectional curvature, and the objective function is convex in this manifold, then the proximal point method in Euclidean space is naturally extended to solve that class of problems. We will prove that the sequence generated by our method is well defined and converge to a minimizer point. In particular we show how tools of Riemannian geometry, more specifically the convex analysis in Riemannian manifolds, can be used to solve nonconvex constrained problem in Euclidean, space.     

Hierarchical controls in stochastic manufacturing systems with machines in tandem

This paper presents an asymptotic analysis of hierarchical production planning in a manufacturing system with serial machines that are subject to breakdown and repair, and with convex costs. The machines capacities are modeled as Markov chains. Since the number of parts in the internal buffers between any two machines needs to be non-negative, the problem is inherently a state constrained problem. As the rate of change in machines states approaches infinity, the analysis results in a limiting problem in which the stochastic machines capacity is replaced by the equilibrium mean capacity. A method of “lifting” and “modification” is introduced in order to construct near optimal controls for the original problem by using near optimal controls of the limiting problem. The value function of the original problem is shown to converge to the value function of the limiting problem, and the convergence rate is obtained based on some a priori estimates of the asymptotic behavior of the Markov chains. As a result, an error estimate can be obtained on the near optimality of the controls constructed for the original problem.     

Second-order global optimality conditions for convex composite optimization

In recent years second-order sufficient conditions of an isolated local minimizer for convex composite optimization problems have been established. In this paper, second-order optimality conditions are obtained of aglobal minimizer for convex composite problems with a non-finite valued convex function and a twice strictly differentiable function by introducing a generalized representation condition. This result is applied to a minimization problem with a closed convex set constraint which is shown to satisfy the basic constraint qualification. In particular, second-order necessary and sufficient conditions of a solution for a variational inequality problem with convex composite inequality constraints are obtained. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

Two fundamental convergence theorems for nonlinear conjugate gradient methods and their applications

1. IntroductionWe consider the global convergence of conjugate gradient methods for the unconstrainednonlinear optimization problemadn f(x),where f: Re - RI is continuously dtherelltiable and its gradiellt is denoted by g. Weconsider only the cajse where the methods are implemented without regular restarts. Theiterative formula is given byXk 1 = Xk Akdk, (1'1).and the seaxch direction da is defined bywhere gb is a scalar, ^k is a stenlength, and gb denotes g(xk).The best-known formulas fo…     

Optimality properties of an Augmented Lagrangian method on infeasible problems

Sometimes, the feasible set of an optimization problem that one aims to solve using a Nonlinear Programming algorithm is empty. In this case, two characteristics of the algorithm are desirable. On the one hand, the algorithm should converge to a minimizer of some infeasibility measure. On the other hand, one may wish to find a point with minimal infeasibility for which some optimality condition, with respect to the objective function, holds. Ideally, the algorithm should converge to a minimizer of the objective function subject to minimal infeasibility. In this paper the behavior of an Augmented Lagrangian algorithm with respect to those properties will be studied.     

Linear Convergence Rates for Variants of the Alternating Direction Method of Multipliers in Smooth Cases

In the present paper, we propose a novel convergence analysis of the alternating direction method of multipliers, based on its equivalence with the overrelaxed primal–dual hybrid gradient algorithm. We consider the smooth case, where the objective function can be decomposed into one differentiable with Lipschitz continuous gradient part and one strongly convex part. Under these hypotheses, a convergence proof with an optimal parameter choice is given for the primal–dual method, which leads to convergence results for the alternating direction method of multipliers. An accelerated variant of the latter, based on a parameter relaxation, is also proposed, which is shown to converge linearly with same asymptotic rate as the primal–dual algorithm.     

Global Optimization by Multilevel Coordinate Search

Inspired by a method by Jones et al. (1993), we present a global optimization algorithm based on multilevel coordinate search. It is guaranteed to converge if the function is continuous in the neighborhood of a global minimizer. By starting a local search from certain good points, an improved convergence result is obtained. We discuss implementation details and give some numerical results.     

A quadratically convergent local algorithm on minimizing sums of the largest eigenvalues of a symmetric matrix

In this paper, we consider the problem on minimizing sums of the largest eigenvalues of a symmetric matrix which depends on the decision variable affinely. An important application of this problem is the graph partitioning problem, which arises in layout of circuit boards, computer logic partitioning, and paging of computer programs. Given 0, we first derive an optimality condition which ensures that the objective function is within error bound of the solution. This condition may be used as a practical stopping criterion for any algorithm solving the underlying problem. We also show that, in a neighborhood of the minimizer, the optimization problem can be equivalently formulated as a smooth constrained problem. An existing algorithm on minimizing the largest eigenvalue of a symmetric matrix is shown to be applicable here. This algoritm enjoys the property that if started close enough to the minimizer, then it will converge quadratically. To implement a practical algorithm, one needs to incorporate some technique to generate a good starting point. Since the problem is convex, this can be done by using an algorithm for general convex optimization problems (e.g., Kelley's cutting plane method or ellipsoid methods), or an algorithm specific for the optimization problem under consideration (e.g., the algorithm developed by Cullum, Donath, and Wolfe). Such union ensures that the overall algorithm has global convergence with quadratic rate. Finally, the results presented in this paper are readily extended on minimizing sums of the largest eigenvalues of a Hermitian matrix.Some of results in this paper were given in [19] without proofs.     

On the heat flow on metric measure spaces: existence, uniqueness and stability

We prove existence and uniqueness of the gradient flow of the Entropy functional under the only assumption that the functional is λ-geodesically convex for some ${\lambda\in\mathbb {R}}$ . Also, we prove a general stability result for gradient flows of geodesically convex functionals which Γ?converge to some limit functional. The stability result applies directly to the case of the Entropy functionals on compact spaces.     

On the truncated conjugate gradient method

In this paper, we consider the truncated conjugate gradient method for minimizing a convex quadratic function subject to a ball trust region constraint. It is shown that the reduction in the objective function by the solution obtained by the truncated CG method is at least half of the reduction by the global minimizer in the trust region. Received January 19, 1999 / Revised version received October 1, 1999?Published online November 30, 1999     

Ein Approximationssatz für konvexe Körper

It is shown that a convex body in n-dimensional Euclidean space can be approximated by a sequence of smooth convex bodies in such a way that the principal radii of curvature converge in a certain sense. This fact is used to characterize those first surface measures of convex bodies which belong to polytopes. Furthermore it is proved that the support function of a convex body whose first surface measure has bounded density must have continuous first partial derivatives.     

New Sufficiency for Global Optimality and Duality of Mathematical Programming Problems via Underestimators

We present new conditions for a Karush-Kuhn-Tucker point to be a global minimizer of a mathematical programming problem which may have many local minimizers that are not global. The new conditions make use of underestimators of the Lagrangian at the Karush-Kuhn-Tucker point. We establish that a Karush-Kuhn-Tucker point is a global minimizer if the Lagrangian admits an underestimator, which is convex or, more generally, has the property that every stationary point is a global minimizer. In particular, we obtain sufficient conditions by using the fact that the biconjugate function of the Lagrangian is a convex underestimator at a point whenever it coincides with the Lagrangian at that point. We present also sufficient conditions for weak and strong duality results in terms of underestimators. The authors are grateful to Professor Gue Myung Lee, Pukyong National University, Korea, and the referees for their comments and suggestions which have contributed to the final preparation of the paper. The work was partially supported by the Australian Research Council Discovery Project Grant.     

Critical points of solutions of degenerate elliptic equations in the plane

We study the minimizer u of a convex functional in the plane which is not Gâteaux-differentiable. Namely, we show that the set of critical points of any C ¹-smooth minimizer can not have isolated points. Also, by means of some appropriate approximating scheme and viscosity solutions, we determine an Euler–Lagrange equation that u must satisfy. By applying the same approximating scheme, we can pair u with a function v which may be regarded as the stream function of u in a suitable generalized sense.     

Optimality Conditions and Characterizations of the Solution Sets in Generalized Convex Problems and Variational Inequalities

We derive necessary and sufficient conditions for optimality of a problem with a pseudoconvex objective function, provided that a finite number of solutions are known. In particular, we see that the gradient of the objective function at every minimizer is a product of some positive function and the gradient of the objective function at another fixed minimizer. We apply this condition to provide several complete characterizations of the solution sets of set-constrained and inequality-constrained nonlinear programming problems with pseudoconvex and second-order pseudoconvex objective functions in terms of a known solution. Additionally, we characterize the solution sets of the Stampacchia and Minty variational inequalities with a pseudomonotone-star map, provided that some solution is known.     

Fixed point iteration processes for asymptotic pointwise nonexpansive mappings in Banach spaces

Let X be a uniformly convex Banach space with the Opial property. Let T:C→C be an asymptotic pointwise nonexpansive mapping, where C is bounded, closed and convex subset of X. In this paper, we prove that the generalized Mann and Ishikawa processes converge weakly to a fixed point of T. In addition, we prove that for compact asymptotic pointwise nonexpansive mappings acting in uniformly convex Banach spaces, both processes converge strongly to a fixed point.     

An optimality criterion for global quadratic optimization

In this paper we prove a sufficient condition that a strong local minimizer of a bounded quadratic program is the unique global minimizer. This sufficient condition can be verified computationally by solving a linear and a convex quadratic program and can be used as a quality test for local minimizers found by standard indefinite quadratic programming routines.Part of this work was done while the author was at the University of Wisconsin-Madison.