-
作者：Lan, Guanghui
作者单位：State University System of Florida; University of Florida
摘要：The main goal of this paper is to develop uniformly optimal first-order methods for convex programming (CP). By uniform optimality we mean that the first-order methods themselves do not require the input of any problem parameters, but can still achieve the best possible iteration complexity bounds. By incorporating a multi-step acceleration scheme into the well-known bundle-level method, we develop an accelerated bundle-level method, and show that it can achieve the optimal complexity for solv...
-
作者：Song, Wen; Xu, Xiaomei; Yao, Jen-Chih
作者单位：Harbin Normal University; Kaohsiung Medical University; King Abdulaziz University
摘要：In this note, we give a counterexample to show that the characterization formula for the condition numbers of a convex set of given in Coulibaly and Crouzeix (Math Program 116:79-113, 2009) is incorrect.
-
作者：Kozmik, Vaclav; Morton, David P.
作者单位：Charles University Prague; University of Texas System; University of Texas Austin
摘要：We consider a risk-averse multi-stage stochastic program using conditional value at risk as the risk measure. The underlying random process is assumed to be stage-wise independent, and a stochastic dual dynamic programming (SDDP) algorithm is applied. We discuss the poor performance of the standard upper bound estimator in the risk-averse setting and propose a new approach based on importance sampling, which yields improved upper bound estimators. Modest additional computational effort is requ...
-
作者：Maehara, Takanori; Murota, Kazuo
作者单位：Japan Science & Technology Agency (JST); Research Organization of Information & Systems (ROIS); National Institute of Informatics (NII) - Japan; University of Tokyo
摘要：A theoretical framework of difference of discrete convex functions (discrete DC functions) and optimization problems for discrete DC functions is established. Standard results in continuous DC theory are exported to the discrete DC theory with the use of discrete convex analysis. A discrete DC algorithm, which is a discrete analogue of the continuous DC algorithm (Concave-Convex procedure in machine learning) is proposed. The algorithm contains the submodular-supermodular procedure as a specia...
-
作者：Bonami, Pierre; Margot, Francois
作者单位：Aix-Marseille Universite; Carnegie Mellon University
摘要：For a mixed integer linear program where all integer variables are bounded, we study a reformulation introduced by Roy that maps general integer variables to a collection of binary variables. We study theoretical properties and empirical strength of rank-2 simple split cuts of the reformulation. We show that for a pure integer problem with two integer variables, these cuts are sufficient to obtain the integer hull of the problem, but that this does not generalize to problems in higher dimensio...
-
作者：Chekuri, Chandra; Ene, Alina
作者单位：University of Illinois System; University of Illinois Chicago; University of Illinois Chicago Hospital; Princeton University; University of Warwick; University of Warwick
摘要：We study the approximability of the All-or-Nothing multicommodity flow problem in directed graphs with symmetric demand pairs (SymANF). The input consists of a directed graph and a collection of (unordered) pairs of nodes . A subset of the pairs is routable if there is a feasible multicommodity flow in such that, for each pair , the amount of flow from to is at least one and the amount of flow from to is at least one. The goal is to find a maximum cardinality subset of the given pairs that can...
-
作者：Censor, Yair; Reem, Daniel
作者单位：University of Haifa
摘要：The convex feasibility problem (CFP) is at the core of the modeling of many problems in various areas of science. Subgradient projection methods are important tools for solving the CFP because they enable the use of subgradient calculations instead of orthogonal projections onto the individual sets of the problem. Working in a real Hilbert space, we show that the sequential subgradient projection method is perturbation resilient. By this we mean that under appropriate conditions the sequence g...
-
作者：Lasserre, Jean B.
作者单位：Centre National de la Recherche Scientifique (CNRS); Universite de Toulouse; Universite de Toulouse
摘要：We address the following generalization of the Lowner-John ellipsoid problem. Given a (non necessarily convex) compact set and an even integer , find an homogeneous polynomial of degree such that and has minimum volume among all such sets. We show that is a convex optimization problem even if neither nor are convex! We next show that has a unique optimal solution and a characterization with at most contacts points in is also provided. This is the analogue for of Lowner-John's theorem in the qu...
-
作者：Mordukhovich, B. S.; Nghia, T. T. A.
作者单位：Wayne State University
摘要：The paper is devoted to the study of tilt-stable local minimizers of general optimization problems in finite-dimensional spaces and its applications to classical nonlinear programs with twice continuously differentiable data. The importance of tilt stability has been well recognized from both theoretical and numerical aspects of optimization, and this notion has been extensively studied in the literature. Based on advanced tools of second-order variational analysis and generalized differentiat...
-
作者：Zolezzi, Tullio
作者单位：University of Genoa
摘要：A finite-dimensional mathematical programming problem with convex data and inequality constraints is considered. A suitable definition of condition number is obtained via canonical perturbations of the given problem, assuming uniqueness of the optimal solutions. The distance among mathematical programming problems is defined as the Lipschitz constant of the difference of the corresponding Kojima functions. It is shown that the distance to ill-conditioning is bounded above and below by suitable...
