凸域内弦的平均长度

本文研究了凸域内弦的平均长度.通过广义支持函数与凸域的弦幂积分,建立了凸域内弦的平均长度的一般公式,并用此公式得出了圆域和矩形域内弦的平均长度.     

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.     

On the facial structure of set packing polyhedra

In this paper we address ourselves to identifying facets of the set packing polyhedron, i.e., of the convex hull of integer solutions to the set covering problem with equality constraints and/or constraints of the form . This is done by using the equivalent node-packing problem derived from the intersection graph associated with the problem under consideration. First, we show that the cliques of the intersection graph provide a first set of facets for the polyhedron in question. Second, it is shown that the cycles without chords of odd length of the intersection graph give rise to a further set of facets. A rather strong geometric property of this set of facets is exhibited.     

赋范线性空间中的广义凸集

文[1]拓广凸集的概念,在 R~(?) 中引入了伪凸、拟凸等广义凸集的概念,获得了它们的一些性质,因而可使得优化理论的研究更为深入.熟知,逼近理论在优化中的应用是非常广泛的(见[2]),本文试图把广义凸集引入赋范线性空间中,并侧重探究其逼近性质.自然,文[1]在 R~(?) 中得到的广义凸集的一些性质,大多数在赋范空间中都是成立的,且证明     

Convergence of the gradient projection method and Newton’s method as applied to optimization problems constrained by intersection of a spherical surface and a convex closed set

The gradient projection method and Newton’s method are generalized to the case of nonconvex constraint sets representing the set-theoretic intersection of a spherical surface with a convex closed set. Necessary extremum conditions are examined, and the convergence of the methods is analyzed.     

On Some Generalized Polyhedral Convex Constructions

Generalized polyhedral convex sets, generalized polyhedral convex functions on locally convex Hausdorff topological vector spaces, and the related constructions such as sum of sets, sum of functions, directional derivative, infimal convolution, normal cone, conjugate function, subdifferential are studied thoroughly in this paper. Among other things, we show how a generalized polyhedral convex set can be characterized through the finiteness of the number of its faces. In addition, it is proved that the infimal convolution of a generalized polyhedral convex function and a polyhedral convex function is a polyhedral convex function. The obtained results can be applied to scalar optimization problems described by generalized polyhedral convex sets and generalized polyhedral convex functions.     

Notes on L-/M-convex functions and the separation theorems

The concepts of L-convex function and M-convex function have recently been introduced by Murota as generalizations of submodular function and base polyhedron, respectively, and discrete separation theorems are established for L-convex/concave functions and for M-convex/concave functions as generalizations of Frank’s discrete separation theorem for submodular/supermodular set functions and Edmonds’ matroid intersection theorem. This paper shows the equivalence between Murota’s L-convex functions and Favati and Tardella’s submodular integrally convex functions, and also gives alternative proofs of the separation theorems that provide a geometric insight by relating them to the ordinary separation theorem in convex analysis. Received: November 27, 1997 / Accepted: December 16, 1999?Published online May 12, 2000     

Numerical Algorithm for Minimizing a Convex Function on the Intersection of a Smooth Surface and a Convex Compact Set

Computational Mathematics and Mathematical Physics - A numerical algorithm for minimizing a convex function on the set-theoretic intersection of a smooth surface and a convex compact set in...     

A weaker regularity condition for subdifferential calculus and Fenchel duality in infinite dimensional spaces

In this paper we present a new regularity condition for the subdifferential sum formula of a convex function with the precomposition of another convex function with a continuous linear mapping. This condition is formulated by using the epigraphs of the conjugates of the functions involved and turns out to be weaker than the generalized interior-point regularity conditions given so far in the literature. Moreover, it provides a weak sufficient condition for Fenchel duality regarding convex optimization problems in infinite dimensional spaces. As an application, we discuss the strong conical hull intersection property (CHIP) for a finite family of closed convex sets.     

近似凸集的某些性质

主要研究了两类近似凸集的关系和性质.首先,举例说明两类近似凸集没有相互包含关系.其次,在近似凸集(nearly convex)条件下,证明了在一定条件下函数上图是近似凸集与凸集的等价关系.同时,考虑了近似凸函数与函数上图是近似凸集的等价刻画、近似凸函数与函数水平集是近似凸集的必要性,并用例子说明近似凸函数与函数水平集是近似凸集的充分性不成立.最后,基于近似凸函数和拟凸函数的概念,给出了近似拟凸函数的概念并研究了近似拟凸函数与水平集是近似凸集的等价刻画.     

On solving general reverse convex programming problems by a sequence of linear programs and line searches

Many multiextremal global optimization problems can be formulated as problems of minimizing a linear function over the intersection of a convex set with the complement of a convex set (so-called canonical d.c. programs or general reverse convex programming problems). In this paper it is shown that these general reverse convex programming problems can be solved by a sequence of linear programs and univariate convex minimization problems (line searches).Parts of the present paper were accomplished while this author was on leave at the University of Trier as a fellow of the Alexander von Humboldt foundation.     

Iterative algorithm for minimizing a convex function at the intersection of a spherical surface and a convex compact set

A numerical algorithm for minimizing a convex function on the set-theoretic intersection of a spherical surface and a convex compact set is proposed. The idea behind the algorithm is to reduce the original minimization problem to a sequence of convex programming problems. Necessary extremum conditions are examined, and the convergence of the algorithm is analyzed.     

非紧的一般化凸空间上不动点定理和supinfsup不等式

利用一般化凸空间上的KKM型定理得到有限交定理,然后作为应用讨论了在没有紧性限制的一般化凸空间上集值映射的不动点的存在问题以及Von Neumann-Fan型supinfsup不等式(等式)问题,最后给出了极大极小等式.     

强CHIP性质和广义限制域逼近的特征

本文研究了广义限制域的最佳逼近问题,在允许有有限个节点的情况下,引入次强内点条件的概念,并将优化理论中的强CHIP性质等概念应用到本文所研究的问题中,刻画了次强内点、强CHIP性质和最佳逼近的特征之间的关系.作为推论,我们得到了广义限制最佳逼近的Kolmogorov型和“零属于凸包”型等特征定理.     

Fenchel duality theorem in multiobjective programming problems with set functions

In this paper, we characterize a vector-valued convex set function by its epigraph. The concepts of a vector-valued set function and a vector-valued concave set function are given respectively. The definitions of the conjugate functions for a vector-valued convex set function and a vector-valued concave set function are introduced. Then a Fenchel duality theorem in multiobjective programming problem with set functions is derived.     

Generalized intersection cuts and a new cut generating paradigm

Intersection cuts are generated from a polyhedral cone and a convex set S whose interior contains no feasible integer point. We generalize these cuts by replacing the cone with a more general polyhedron C. The resulting generalized intersection cuts dominate the original ones. This leads to a new cutting plane paradigm under which one generates and stores the intersection points of the extreme rays of C with the boundary of S rather than the cuts themselves. These intersection points can then be used to generate in a non-recursive fashion cuts that would require several recursive applications of some standard cut generating routine. A procedure is also given for strengthening the coefficients of the integer-constrained variables of a generalized intersection cut. The new cutting plane paradigm yields a new characterization of the closure of intersection cuts and their strengthened variants. This characterization is minimal in the sense that every one of the inequalities it uses defines a facet of the closure.     

An axiomatic duality framework for the theta body and related convex corners

Lovász theta function and the related theta body of graphs have been in the center of the intersection of four research areas: combinatorial optimization, graph theory, information theory, and semidefinite optimization. In this paper, utilizing a modern convex optimization viewpoint, we provide a set of minimal conditions (axioms) under which certain key, desired properties are generalized, including the main equivalent characterizations of the theta function, the theta body of graphs, and the corresponding antiblocking duality relations. Our framework describes several semidefinite and polyhedral relaxations of the stable set polytope of a graph as generalized theta bodies. As a by-product of our approach, we introduce the notion of “Schur Lifting” of cones which is dual to PSD Lifting (more commonly used in SDP relaxations of combinatorial optimization problems) in our axiomatic generalization. We also generalize the notion of complements of graphs to diagonally scaling-invariant polyhedral cones. Finally, we provide a weighted generalization of the copositive formulation of the fractional chromatic number by Dukanovic and Rendl from 2010.     

BCQ条件和广义限制域最佳一致逼近的特征

研究了广义限制域的最佳一致逼近问题,在允许有有限个节点的情况下,引入次强内点条件的概念,并将优化理论中的BCQ条件等概念应用到本文所研究的问题中,刻划了次强内点条件、BCQ条件和最佳一致逼近的特征之间的关系.     

关于半连续函数与凸函数的注记

在半连续前提下,给出凸函数和严格凸函数的不等式刻划．指出非空凸集上的半连续函数满足中间点凸性时,成为凸函数,满足中间点严格凸性时,成为严格凸函数．最后定义F—G广义凸函数和条件p1,p2等概念,列举若干满足条件p1,p2的数量函数和向量函数,并指出,对于F—G广义凸函数,在条件p1,p2及一定连续性条件下,可以得到类似结果．     

Almost sure convergence of random projected proximal and subgradient algorithms for distributed nonsmooth convex optimization

Two distributed algorithms are described that enable all users connected over a network to cooperatively solve the problem of minimizing the sum of all users’ objective functions over the intersection of all users’ constraint sets, where each user has its own private nonsmooth convex objective function and closed convex constraint set, which is the intersection of a number of simple, closed convex sets. One algorithm enables each user to adjust its estimate using the proximity operator of its objective function and the metric projection onto one constraint set randomly selected from a number of simple, closed convex sets. The other determines each user’s estimate using the subdifferential of its objective function instead of the proximity operator. Investigation of the two algorithms’ convergence properties for a diminishing step-size rule revealed that, under certain assumptions, the sequences of all users generated by each of the two algorithms converge almost surely to the same solution. It also showed that the rate of convergence depends on the step size and that a smaller step size results in quicker convergence. The results of numerical evaluation using a nonsmooth convex optimization problem support the convergence analysis and demonstrate the effectiveness of the two algorithms.