Minkowski's successive minima and the zeros of a convexity-function

For a convex bodyK?E ^d letV _i (K),i=0, 1,...,d denote its normalized quermassintegrals. We show that there are various inequalities between the zeros of the polynomial W(?μ K) = ∑ _i=0 ^d V_i(K)(?μ)ⁱ and Minkowski's successive minima in geometry of numbers.     

On the successive minima of a bounded star domain

Sunto. è dato nel seguente capoverso

---

---

Dedicated to Max Dehn.     

Inequalities between successive minima and intrinsic volumes of a convex body

The second theorem of Minkowski establishes a relation between the successive minima and the volume of a 0-symmetric convex body. Based on this theorem we will prove a series of inequalities connecting the product of certain successive minima with certain intrinsic volumes.     

Path properties of successive sample minima from stationary processes

Probability Theory and Related Fields -     

Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice

Let _i(L), _i(L^*) denote the successive minima of a latticeL and its reciprocal latticeL ^*, and let [b₁,..., b _n ] be a basis ofL that is reduced in the sense of Korkin and Zolotarev. We prove that and, where and _j denotes Hermite's constant. As a consequence the inequalities are obtained forn7. Given a basisB of a latticeL in ^m of rankn andx ^m , we define polynomial time computable quantities(B) and(x,B) that are lower bounds for ₁(L) and(x,L), where(x,L) is the Euclidean distance fromx to the closest vector inL. If in additionB is reciprocal to a Korkin-Zolotarev basis ofL ^*, then ₁(L) _n ^* (B) and.The research of the second author was supported by NSF contract DMS 87-06176. The research of the third author was performed at the University of California, Berkeley, with support from NSF grant 21823, and at AT&T Bell Laboratories.     

A note on functions whose local minima are global

In this note, we introduce a new class of generalized convex functions and show that a real functionf which is continuous on a compact convex subsetM of ⁿ and whose set of global minimizers onM is arcwise-connected has the property that every local minimum is global if, and only if,f belongs to that class of functions.     

A new successive quadratic programming algorithm

The main difficulties encountered in the successive quadratic programming methods are the choice of penalty parameter, the choice of steplenth, and the Maratos effect. An algorithm without penalty parameters is presented in this paper. The choice of steplength parameters is based on the method of trust region. Global convergence and local superlinear convergence are proved under suitable assumption.     

A descent algorithm for constrained stochastic extrema

In situations where it is not feasible to find an optimal feedback control law for a stochastic system, an open-loop law can often be derived by optimization. This article presents a method of finding the extremum of certain stochastic functionals analogous to the steepest descent method. Necessary conditions for the convergence of the algorithm are given. Two examples illustrate the use of the algorithm.This research was supported by the Office of Naval Research, Contract No. Nonr-1866 (16) and by the National Aeronautics and Space Administration, Grant No. NGR-22-007-068.     

A note on functions whose local minima are global

In this note, a simple proof of a theorem concerning functions whose local minima are global is presented and some closedness properties of this class of functions are discussed.The authors would like to thank Dr. Tatsuro Ichiishi of CORE for outlining the new proof of Theorem 2.1.This research was done while the author was a research fellow at the Center for Operations Research and Econometrics, University of Louvain, Heverlee, Belgium.     

A parallel descent algorithm for convex programming

In this paper, we propose a parallel decomposition algorithm for solving a class of convex optimization problems, which is broad enough to contain ordinary convex programming problems with a strongly convex objective function. The algorithm is a variant of the trust region method applied to the Fenchel dual of the given problem. We prove global convergence of the algorithm and report some computational experience with the proposed algorithm on the Connection Machine Model CM-5.     

A descent algorithm for nonsmooth convex optimization

This paper presents a new descent algorithm for minimizing a convex function which is not necessarily differentiable. The algorithm can be implemented and may be considered a modification of the ε-subgradient algorithm and Lemarechal's descent algorithm. Also our algorithm is seen to be closely related to the proximal point algorithm applied to convex minimization problems. A convergence theorem for the algorithm is established under the assumption that the objective function is bounded from below. Limited computational experience with the algorithm is also reported.     

Learning gradients by a gradient descent algorithm

We propose a stochastic gradient descent algorithm for learning the gradient of a regression function from random samples of function values. This is a learning algorithm involving Mercer kernels. By a detailed analysis in reproducing kernel Hilbert spaces, we provide some error bounds to show that the gradient estimated by the algorithm converges to the true gradient, under some natural conditions on the regression function and suitable choices of the step size and regularization parameters.     

Characterizations of strict local minima and necessary conditions for weak sharp minima

In nonlinear programming, sufficient conditions of orderm usually identify a special type of local minimizer, here termed a strict local minimizer of orderm. In this paper, it is demonstrated that, if a constraint qualification is satisfied, standard sufficient conditions often characterize this special sort of minimizer. The first- and second-order cases are treated in detail. Necessary conditions for weak sharp local minima of orderm, a larger class of local minima, are also presented.This paper was completed during a sabbatical leave at the University of Waterloo. The author is grateful for the help and support of the Department of Combinatorics and Optimization. The helpful comments of the referees are also appreciated.     

Existence of local minima for capillarity problems

In this paper we study problems in capillarity theory associated with energy functionals for which no lower bounds exist. We treat the cases of pendent and rotating liquid drops. In order to show the existence of local minima we prove suitablea priori estimates for their diameter. To obtain these results sufficient conditions on the included volume depending respectively on the centrifugal and gravitational potential must be satisfied.     

A successive approximation algorithm for stochastic control problems

We consider optimal stochastic control problems in which the state variables are governed by Itô equations. A successive approximation algorithm for optimal stochastic control is obtained. This algorithm, together with the existing numerical methods for parabolic or elliptic PDEs, provides numerical schemes for the solution of Bellman equations.     

A descent algorithm without line search for unconstrained optimization

In this paper, a new descent algorithm for solving unconstrained optimization problem is presented. Its search direction is descent and line search procedure can be avoided except for the first iteration. It is globally convergent under mild conditions. The search direction of the new algorithm is generalized and convergence of corresponding algorithm is also proved. Numerical results show that the algorithm is efficient for given test problems.     

A feasible descent algorithm for solving variational inequality problems

In this paper, for solving variational inequality problems (VIPs) we propose a feasible descent algorithm via minimizing the regularized gap function of Fukushima. Under the condition that the underlying mapping of VIP is strongly monotone, the algorithm is globally convergent for any regularized parameter, which is nice because it bypasses the necessity of knowing the modulus of strong monotonicity, a knowledge that is requested by other similar algorithms. Some preliminary computational results show the efficiency of the proposed method.     

A robust implementation of a sequential quadratic programming algorithm with successive error restoration

We consider sequential quadratic programming methods for solving constrained nonlinear programming problems. It is generally believed that these methods are sensitive to the accuracy by which partial derivatives are provided. One reason is that differences of gradients of the Lagrangian function are used for updating a quasi-Newton matrix, e.g., by the BFGS formula. The purpose of this paper is to show by numerical experimentation that the method can be stabilized substantially. The algorithm applies non-monotone line search and internal and external restarts in case of errors due to inaccurate derivatives while computing the search direction. Even in case of large random errors leading to partial derivatives with at most one correct digit, termination subject to an accuracy of 10⁻⁷ can be achieved in 90% of 306 problems of a standard test suite. On the other hand, the original version with monotone line search and without restarts solves only 30% of these problems under the same test environment. In addition, we show how initial and periodic scaled restarts improve the efficiency in situations with slow convergence.     

A bound on local minima of arrangements that implies the upper bound theorem

This paper shows that thei-level of an arrangement of hyperplanes inE ^d has at most local minima. This bound follows from ideas previously used to prove bounds on (≤k)-sets. Using linear programming duality, the Upper Bound Theorem is obtained as a corollary, giving yet another proof of this celebrated bound on the number of vertices of a simple polytope inE ^d withn facets.     

A new descent algorithm for solving quadratic bilevel programming problems

1. IntroductionA bilevel programming problem (BLPP) involves two sequential optimization problems where the constraint region of the upper one is implicitly determined by the solutionof the lower. It is proved in [1] that even to find an approximate solution of a linearBLPP is strongly NP-hard. A number of algorithms have been proposed to solve BLPPs.Among them, the descent algorithms constitute an important class of algorithms for nonlinear BLPPs. However, it is assumed for almost all…