Second-Order Global Optimality Conditions for Optimization Problems

Second-order optimality conditions are studied for the constrained optimization problem where the objective function and the constraints are compositions of convex functions and twice strictly differentiable functions. A second-order sufficient condition of a global minimizer is obtained by introducing a generalized representation condition. Second-order minimizer characterizations for a convex program and a linear fractional program are derived using the generalized representation condition     

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.     

Optimality conditions for an isolated minimum of order two in C constrained optimization

In this paper we obtain first and second-order optimality conditions for an isolated minimum of order two for the problem with inequality constraints and a set constraint. First-order sufficient conditions are derived in terms of generalized convex functions. In the necessary conditions we suppose that the data are continuously differentiable. A notion of strongly KT invex inequality constrained problem is introduced. It is shown that each Kuhn-Tucker point is an isolated global minimizer of order two if and only if the problem is strongly KT invex. The article could be considered as a continuation of [I. Ginchev, V.I. Ivanov, Second-order optimality conditions for problems with C¹ data, J. Math. Anal. Appl. 340 (2008) 646-657].     

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.     

一类多目标Lipschitz规划的对偶定理

Lipschitz函数定义了广义本性伪凸的概念,建立了多目标Lipschitz规划的Mond-Weir型对偶和Wolfe型对偶,证明了原规划与对偶规划之间的对偶定理。     

On representations of the feasible set in convex optimization

We consider the convex optimization problem \({\min_{\mathbf{x}} \{f(\mathbf{x}): g_j(\mathbf{x})\leq 0, j=1,\ldots,m\}}\) where f is convex, the feasible set \({\mathbf{K}}\) is convex and Slater’s condition holds, but the functions g _j ’s are not necessarily convex. We show that for any representation of \({\mathbf{K}}\) that satisfies a mild nondegeneracy assumption, every minimizer is a Karush-Kuhn-Tucker (KKT) point and conversely every KKT point is a minimizer. That is, the KKT optimality conditions are necessary and sufficient as in convex programming where one assumes that the g _j ’s are convex. So in convex optimization, and as far as one is concerned with KKT points, what really matters is the geometry of \({\mathbf{K}}\) and not so much its representation.     

Condition numbers and error bounds in convex programming

After a brief survey on condition numbers for linear systems of equalities, we analyse error bounds for convex functions and convex sets. The canonical representation of a convex set is defined. Other representations of a convex set by a convex function are compared with the canonical representation. Then, condition numbers are introduced for convex sets and their convex representations.     

可达到和可逼近总极小点的存在性和最优性

针对积分总极值，讨论并拓展了丰满集和丰满函数的概念，研究了拟上丰满和伪上丰满函数的总极值问题. 在总极值的变差积分最优性条件下，证明了拟上丰满函数的可达到极小点和伪上丰满函数的可逼近极小点的存在性.     

The proximal point algorithm in metric spaces

The proximal point algorithm, which is a well-known tool for finding minima of convex functions, is generalized from the classical Hilbert space framework into a nonlinear setting, namely, geodesic metric spaces of non-positive curvature. We prove that the sequence generated by the proximal point algorithm weakly converges to a minimizer, and also discuss a related question: convergence of the gradient flow.     

广义凸函数的特征性质

提出广义凸集、广义凸函数、中间点广义凸函数、端点广义凸函数四个定义,通过定义条件P1,研究条件P1所蕴含的等式关系,进而得到一个基础性定理一稠密性定理和一个相对条件较弱的推论,最后将结果应用于若干不同类型的广义凸函数类,尤其是s-凸函数、几何凸函数、rp-凸函数,得到它们所共有的一个特征性质,即满足稠密性定理．     

极大单调算子和非扩展映射的迭代收敛定理及其应用

In this paper, two iterative schemes for approximating common element of the set of zero points of maximal monotone operators and the set of fixed points of a kind of generalized nonexpansive mappings in a real uniformly smooth and uniformly convex Banach space are proposed. Two strong convergence theorems are obtained and their applications on finding the minimizer of a kind of convex functional are discussed, which extend some previous work.     

Continuous Gradient Projection Method in Hilbert Spaces

This paper is concerned with the asymptotic analysis of the trajectories of some dynamical systems built upon the gradient projection method in Hilbert spaces. For a convex function with locally Lipschitz gradient, it is proved that the orbits converge weakly to a constrained minimizer whenever it exists. This result remains valid even if the initial condition is chosen out of the feasible set and it can be extended in some sense to quasiconvex functions. An asymptotic control result, involving a Tykhonov-like regularization, shows that the orbits can be forced to converge strongly toward a well-specified minimizer. In the finite-dimensional framework, we study the differential inclusion obtained by replacing the classical gradient by the subdifferential of a continuous convex function. We prove the existence of a solution whose asymptotic properties are the same as in the smooth case.     

Improving the efficiency of DC global optimization methods by improving the DC representation of the objective function

There are infinitely many ways of representing a d.c. function as a difference of convex functions. In this paper we analyze how the computational efficiency of a d.c.optimization algorithm depends on the representation we choose for the objective function, and we address the problem of characterizing and obtaining a computationally optimal representation. We introduce some theoretical concepts which are necessary for this analysis and report some numerical experiments.      

Six Kinds of Roughly Convex Functions

This paper considers six kinds of roughly convex functions, namely: δ-convex, midpoint δ-convex, ρ-convex, γ-convex, lightly γ-convex, and midpoint γ-convex functions. The relations between these concepts are presented. It is pointed out that these roughly convex functions have two optimization properties: each r-local minimizer is a global minimizer, and if they assume their maximum on a bounded convex domain D (in a Hilbert space), then they do so at least at one r-extreme point of D, where r denotes the roughness degree of these functions. Furthermore, analytical properties are investigated, such as boundedness, continuity, and conservation properties.     

Necessary and sufficient optimality conditions for mathematical programs with equilibrium constraints

In this paper we consider a mathematical program with equilibrium constraints (MPEC) formulated as a mathematical program with complementarity constraints. Various stationary conditions for MPECs exist in literature due to different reformulations. We give a simple proof to the M-stationary condition and show that it is sufficient for global or local optimality under some MPEC generalized convexity assumptions. Moreover, we propose new constraint qualifications for M-stationary conditions to hold. These new constraint qualifications include piecewise MFCQ, piecewise Slater condition, MPEC weak reverse convex constraint qualification, MPEC Arrow-Hurwicz-Uzawa constraint qualification, MPEC Zangwill constraint qualification, MPEC Kuhn-Tucker constraint qualification, and MPEC Abadie constraint qualification.     

Stable generalization of convex functions

A kind of generalized convex functions is said to be stable with respect to some property (P) if this property is maintaincd during an arbitrary function from this class is disturbed by a linear functional with sufficiently small norm. Unfortunately. known generallzed convexities iike quasicunvexity, explicit quasiconvexity. and pseudoconvexity are not stable with respect to such optimization properties which are expected to be true by these generalizations, even if the domain ol the functions is compact. Therefore, we introduce the notion of s-quasiconvex functions. These functions are quasiconvex, explicitly quasicon vex. and pseudoconvex if they are continuously differentiable. Especially, the s-quasiconvexity is stable with respect to the following important properties: (Pl) all lower level sets are convex, (P2) each local minimum is a global minimum. and (P3) each stationary point is a global minimizer. In this paper, different aspects. of s–quasiconvexity and its stability are investigated.     

一类带阻尼项的二阶Hamilton系统的多重周期解

利用临界点理论研究带阻尼项的二阶Hamilton系统周期解的存在性.在具有部分周期位势和线性增长非线性项时,根据广义鞍点定理定理,得到了系统多重周期解存在的充分条件.     

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.     

A Discrete Chebyshev Approximation Problem by Means of Several Polynomials

The problem of approximation of a given function on a given set by a polynomial of a fixed degree in the Chebyshev metric (the Chebyshev polynomial approximation problem) is a typical problem of Nonsmooth Analysis (to be more precise, it is a convex nonsmooth problem). It has many important applications, both in mathematics and in practice. The theory of Chebyshev approximations enjoys very nice properties (the most famous being the Chebyshev alternation rule). In the present article the problem of approximation of a given function on a given finite set of points by several polynomials is studied. As a criterion function, the maximin deviation is taken. The resulting functional is nonsmooth and nonconvex and therefore the problem becomes multiextremal and may have local minimizers which are not global ones. A necessary and sufficient condition for a point to be a local minimizer is proved. It is shown that a generalized alternation rule is still valid. Sufficient conditions for a point to be a strict local minimizer are established as well. These conditions are also formulated in terms of alternants. An exchange algorithm for finding a local minimizer is constructed. An k -exchange algorithm, allowing to find a "better" local minimizer is stated. Numerical examples illustrating the theory are presented.     

Coxian representations of generalized Erlang distributions

This paper studies Coxian representations of generalized Erlang distributions. A nonlinear program is derived for computing the parameters of minimal Coxian representations of generalized Erlang distributions. The nonlinear program is also used to characterize the triangular order and the admissible region of generalized Erlang distributions. It is shown that the admissible region associated with a triangular order may not be convex. For generalized Erlang distributions of ME-order 3, a minimal Coxian representation is found explicitly. In addition, an algorithm is developed for computing a special type of ordered Coxian representations - the bivariate Coxian representation - for generalized Erlang distributions.