Weak sharp minima revisited, part II: application to linear regularity and error bounds

The notion of weak sharp minima is an important tool in the analysis of the perturbation behavior of certain classes of optimization problems as well as in the convergence analysis of algorithms designed to solve these problems. It has been studied extensively by several authors. This paper is the second of a series on this subject where the basic results on weak sharp minima in Part I are applied to a number of important problems in convex programming. In Part II we study applications to the linear regularity and bounded linear regularity of a finite collection of convex sets as well as global error bounds in convex programming. We obtain both new results and reproduce several existing results from a fresh perspective. We dedicate this paper to our friend and mentor Terry Rockafellar on the occasion of his 70th birthday. He has been our guide in mathematics as well as in the backcountry and waterways of the Olympic and Cascade mountains. Research supported in part by the National Science Foundation Grant DMS-0203175.     

Finite termination of the proximal point method for convex functions on Hadamard manifolds

In this article, we proved that the sequence generated by the proximal point method, associated to a unconstrained optimization problem in the Riemannian context, has finite termination when the objective function has a weak sharp minima on the solution set of the problem.     

Uniqueness conditions for Kuhn-Tucker points on a disk

Consider minimizingf onD which is diffeomorphic to a disk. Under a genericity assumption, the number of points onD satisfying the Kuhn-Tucker necessary conditions for minimum is odd. We give conditions which imply that a local minimum is global and a necessary and sufficient condition that a Kuhn-Tucker point is the solution. Convex transformable problems satisfy the latter condition.D may be of full dimension or be embedded on a manifold or it may be given by a system of concave inequalities.The work on which this paper is based was done while the author was visiting the Group for the Application of Mathematics and Statistics to Economics at the University of California, Berkeley, Spring 1981. The author would like to thank the Group, and Professor G. Debreu in particular, for the hospitality. He benefited from discussions with Professors S. Smale, A. Mas-Colell, K. Nishimura, and L. Chenault, among others. He also wishes to thank two referees of this journal for helpful comments.     

New Modified Function Method for Global Optimization

In this paper, a class of global optimization problems is considered. Corresponding to each local minimizer obtained, we introduced a new modified function and construct a corresponding optimization subproblem with one constraint. Then, by applying a local search method to the one-constraint optimization subproblem and using the local minimizer as the starting point, we obtain a better local optimal solution. This process is continued iteratively. A termination rule is obtained which can serve as stopping criterion for the iterating process. To demonstrate the efficiency of the proposed approach, numerical examples are solved.This research was partially supported by the National Science Foundation of China, Grant 10271073.     

New Uniform Parametric Error Bounds

A uniform parametric error bound is a uniform error estimate for feasible solutions of a family of parametric mathematical programming problems. It has been proven useful in exact penalty formulation for bilevel programming problems. In this paper, we derive new sufficient conditions for the existence of uniform parametric error bounds.     

Iteration-complexity of the subgradient method on Riemannian manifolds with lower bounded curvature

Abstract

The subgradient method for convex optimization problems on complete Riemannian manifolds with lower bounded sectional curvature is analysed in this paper. Iteration-complexity bounds of the subgradient method with exogenous step-size and Polyak's step-size are stablished, completing and improving recent results on the subject.     

带自由变量的广义几何规划全局求解的新算法

带自由变量的广义几何规划(FGGP)问题广泛出现在证券投资和工程设计等实际问题中.利用等价转换及对目标函数和约束函数的凸下界估计,提出一种求(FGGP)问题全局解的凸松弛方法.与已有方法相比,方法可处理符号项中含有更多变量的(FGGP)问题,且在最后形成的凸松弛问题中含有更少的变量和约束,从而在计算上更容易实现.最后数值实验表明文中方法是可行和有效的.     

Convex Kernel Underestimation of Functions with Multiple Local Minima

A function on Rⁿ with multiple local minima is approximated from below, via linear programming, by a linear combination of convex kernel functions using sample points from the given function. The resulting convex kernel underestimator is then minimized, using either a linear equation solver for a linear-quadratic kernel or by a Newton method for a Gaussian kernel, to obtain an approximation to a global minimum of the original function. Successive shrinking of the original search region to which this procedure is applied leads to fairly accurate estimates, within 0.0001% for a Gaussian kernel function, relative to global minima of synthetic nonconvex piecewise-quadratic functions for which the global minima are known exactly. Gaussian kernel underestimation improves by a factor of ten the relative error obtained using a piecewise-linear underestimator (O.L. Mangasarian, J.B. Rosen, and M.E. Thompson, Journal of Global Optimization, Volume 32, Number 1, Pages 1–9, 2005), while cutting computational time by an average factor of over 28.     

一类广义弧式凸函数的局部极小与整体极小的关系

1 引言凸函数有一重要性质,即局部极小必为整体极小．在对凸函数所做的各种推广中,关于局部极小与整体极小的关系问题讨论甚多．本文引进了一种新的广义凸函数,即所谓的弧式严格局部拟凸函数,并证明了一个定义在Rn中紧弧式连通集M上的连续函数．若其每个局部极小均为整体极小,则此函数必为弧式严格局部拟凸函数．这是作者见     

Maximal element with applications to Nash equilibrium problems in Hadamard manifolds

ABSTRACT

The purpose of this paper is to study the existence of maximal elements with applications to Nash equilibrium problems for generalized games in Hadamard manifolds. By employing a KKM lemma, we establish a new maximal element theorem in Hadamard manifolds. As applications, some existence results of Nash equilibria for generalized games are derived. The results in this paper unify, improve and extend some known results from the literature.     

Singularities of Monotone Vector Fields and an Extragradient-type Algorithm

Bearing in mind the notion of monotone vector field on Riemannian manifolds, see [12--16], we study the set of their singularities and for a particularclass of manifolds develop an extragradient-type algorithm convergent to singularities of such vector fields. In particular, our method can be used forsolving nonlinear constrained optimization problems in Euclidean space, with a convex objective function and the constraint set a constant curvature Hadamard manifold. Our paper shows how tools of convex analysis on Riemannian manifolds can be used to solve some nonconvex constrained problem in a Euclidean space.O.P. Ferreira- was supported in part by CAPES, FUNAPE (UFG) and (CNPq).S.Z. Németh- was supported in part by grant No.T029572 of the National Research Foundation of Hungary.     

Global solutions of mathematical programs with intrinsically concave functions

An implicit enumeration technique for solving a certain type of nonconvex program is described. The method can be used for solving signomial programs with constraint functions defined by sums of quasiconcave functions and other types of programs with constraint functions called intrinsically concave functions. A signomial-type example is solved by this method. The algorithm is described together with a convergence proof. No computational results are available at present.     

E-Convex Sets, E-Convex Functions, and E-Convex Programming

A class of sets and a class of functions called E-convex sets and E-convex functions are introduced by relaxing the definitions of convex sets and convex functions. This kind of generalized convexity is based on the effect of an operator E on the sets and domain of definition of the functions. The optimality results for E-convex programming problems are established.     

关于“弱Lipschitz函数,它的广义次梯度及其在优化中的应用”一文的注记

本文证明张玉忠同志在“弱Ｌｉｐｓｃｈｉｔｚ函数、它的广义次梯度及其在优化中的应用”一文中定义的广义次梯度ｆ（π），当ｎ≥２时即为Ｒ￣ｎ，因此这种广义次梯度是没有多少应用价值的。     

On the Construction of Convex and Concave Envelope Formulas for Bilinear and Fractional Functions on Quadrilaterals

Convex and concave envelopes play important roles in various types of optimization problems. In this article, we present a result that gives general guidelines for constructing convex and concave envelopes of functions of two variables on bounded quadrilaterals. We show how one can use this result to construct convex and concave envelopes of bilinear and fractional functions on rectangles, parallelograms and trapezoids. Applications of these results to global optimization are indicated.     

A one-phase algorithm for semi-infinite linear programming

We present an algorithm for solving a large class of semi-infinite linear programming problems. This algorithm has several advantages: it handles feasibility and optimality together; it has very weak restrictions on the constraints; it allows cuts that are not near the most violated cut; and it solves the primal and the dual problems simultaneously. We prove the convergence of this algorithm in two steps. First, we show that the algorithm can find an-optimal solution after finitely many iterations. Then, we use this result to show that it can find an optimal solution in the limit. We also estimate how good an-optimal solution is compared to an optimal solution and give an upper bound on the total number of iterations needed for finding an-optimal solution under some assumptions. This algorithm is generalized to solve a class of nonlinear semi-infinite programming problems. Applications to convex programming are discussed.     

Existence of Global Minima for Constrained Optimization

We present a unified approach to establishing the existence of global minima of a (non)convex constrained optimization problem. Our results unify and generalize previous existence results for convex and nonconvex programs, including the Frank-Wolfe theorem, and for (quasi) convex quadratically constrained quadratic programs and convex polynomial programs. For example, instead of requiring the objective/constraint functions to be constant along certain recession directions, we only require them to linearly recede along these directions. Instead of requiring the objective/constraint functions to be convex polynomials, we only require the objective function to be a (quasi)convex polynomial over a polyhedral set and the constraint functions to be convex polynomials or the composition of coercive functions with linear mappings.We thank Professor Dimitri Bertsekas for his comments and support in the writing of this paper.     

On Anastassiou's Generalizations of the Ostrowski Inequality and Related Results

We provide a generalization of a recent result of Anastassiou related to thewell-known Ostrowski inequality, as well as some related results. Ourresults subsume, extend, and consolidate a number of known results.