-
作者：Coulonges, Sylvain; Pecher, Arnaud; Wagler, Annegret K.
作者单位：Otto von Guericke University; Universite de Bordeaux; Centre National de la Recherche Scientifique (CNRS)
摘要：Perfect graphs constitute a well-studied graph class with a rich structure, which is reflected by many characterizations with respect to different concepts. Perfect graphs are, for instance, precisely those graphs G where the stable set polytope STAB(G) equals the fractional stable set polytope QSTAB(G). The dilation ratio min{t : QSTAB(G) subset of t STAB(G)} of the two polytopes yields the imperfection ratio of G. It is NP-hard to compute and, for most graph classes, it is even unknown wheth...
-
作者：Borwein, Jonathan M.; Hamilton, Chris H.
作者单位：Dalhousie University
摘要：Of key importance in convex analysis and optimization is the notion of duality, and in particular that of Fenchel duality. This work explores improvements to existing algorithms for the symbolic calculation of subdifferentials and Fenchel conjugates of convex functions defined on the real line. More importantly, these algorithms are extended to enable the symbolic calculation of Fenchel conjugates on a class of real-valued functions defined on the real line. More importantly, these algorithms ...
-
作者：Hare, Warren; Sagastizabal, Claudia
作者单位：Instituto Nacional de Matematica Pura e Aplicada (IMPA); McMaster University
摘要：The proximal point mapping is the basis of many optimization techniques for convex functions. By means of variational analysis, the concept of proximal mapping was recently extended to nonconvex functions that are prox-regular and prox-bounded. In such a setting, the proximal point mapping is locally Lipschitz continuous and its set of fixed points coincide with the critical points of the original function. This suggests that the many uses of proximal points, and their corresponding proximal e...
-
作者：Karas, Elizabeth; Ribeiro, Ademir; Sagastizabal, Claudia; Solodov, Mikhail
作者单位：Universidade Federal do Parana
摘要：For solving nonsmooth convex constrained optimization problems, we propose an algorithm which combines the ideas of the proximal bundle methods with the filter strategy for evaluating candidate points. The resulting algorithm inherits some attractive features from both approaches. On the one hand, it allows effective control of the size of quadratic programming subproblems via the compression and aggregation techniques of proximal bundle methods. On the other hand, the filter criterion for acc...
-
作者：Auslender, Alfred; Teboulle, Marc
作者单位：Tel Aviv University; Centre National de la Recherche Scientifique (CNRS); Ecole Centrale de Lyon; Institut National des Sciences Appliquees de Lyon - INSA Lyon; Universite Claude Bernard Lyon 1; Universite Jean Monnet
摘要：We study subgradient projection type methods for solving non-differentiable convex minimization problems and monotone variational inequalities. The methods can be viewed as a natural extension of subgradient projection type algorithms, and are based on using non-Euclidean projection-like maps, which generate interior trajectories. The resulting algorithms are easy to implement and rely on a single projection per iteration. We prove several convergence results and establish rate of convergence ...
-
作者：Xu, Huifu; Zhang, Dali
作者单位：University of Southampton
摘要：Inspired by a recent work by Alexander et al. (J Bank Finance 30:583-605, 2006) which proposes a smoothing method to deal with nonsmoothness in a conditional value-at-risk problem, we consider a smoothing scheme for a general class of nonsmooth stochastic problems. Assuming that a smoothed problem is solved by a sample average approximation method, we investigate the convergence of stationary points of the smoothed sample average approximation problem as sample size increases and show that w.p...
-
作者：Penot, J. -P.; Zalinescu, C.
作者单位：Universite de Pau et des Pays de l'Adour; Centre National de la Recherche Scientifique (CNRS); Alexandru Ioan Cuza University
摘要：We use representations of maximal monotone operators for studying recession (or asymptotic) operators associated to maximal monotone operators. Such a concept is useful for dealing with unboundedness.
-
作者：Sherali, Hanif D.; Smith, J. Cole
作者单位：Virginia Polytechnic Institute & State University; State University System of Florida; University of Florida
摘要：In this paper, we consider a class of two-stage stochastic risk management problems, which may be stated as follows. A decision-maker determines a set of binary first-stage decisions, after which a random event from a finite set of possible outcomes is realized. Depending on the realization of this outcome, a set of continuous second-stage decisions must then be made that attempt to minimize some risk function. We consider a hierarchy of multiple risk levels along with associated penalties for...
-
作者：Todd, M. J.
作者单位：Cornell University
摘要：Suppose (x) over bar and (s) over bar lie in the interiors of a cone K and its dual K*, respectively. We seek dual ellipsoidal norms such that the product of the radii of the largest inscribed balls centered at (x) over bar and (s) over bar and inscribed in K and K *, respectively, is maximized. Here the balls are defined using the two dual norms. When the cones are symmetric, that is self-dual and homogeneous, the solution arises directly from the Nesterov-Todd primal-dual scaling. This shows...
-
作者：Lasserre, Jean B.
作者单位：Centre National de la Recherche Scientifique (CNRS)
摘要：We provide a sufficient condition on a class of compact basic semialgebraic sets K subset of R-n for their convex hull co(K) to have a semidefinite representation (SDr). This SDr is explicitly expressed in terms of the polynomials g(j) that define K. Examples are provided. We also provide an approximate SDr; that is, for every fixed epsilon > 0, there is a convex set K-epsilon such that co(K) subset of K-epsilon subset of co(K) + epsilon B (where B is the unit ball of R-n), and K-epsilon has a...
