1期

最新文章

• DC decomposition of nonconvex polynomials with algebraic techniques AI翻译
  作者：Ahmadi, Amir Ali; Hall, Georgina
  作者单位：Princeton University
  摘要：We consider the problem of decomposing a multivariate polynomial as the difference of two convex polynomials. We introduce algebraic techniques which reduce this task to linear, second order cone, and semidefinite programming. This allows us to optimize over subsets of valid difference of convex decompositions (dcds) and find ones that speed up the convex-concave procedure. We prove, however, that optimizing over the entire set of dcds is NP-hard.
• DC formulations and algorithms for sparse optimization problems AI翻译
  作者：Gotoh, Jun-ya; Takeda, Akiko; Tono, Katsuya
  作者单位：Chuo University; Research Organization of Information & Systems (ROIS); Institute of Statistical Mathematics (ISM) - Japan; RIKEN; NEC Corporation
  摘要：We propose a DC (Difference of two Convex functions) formulation approach for sparse optimization problems having a cardinality or rank constraint. With the largest-k norm, an exact DC representation of the cardinality constraint is provided. We then transform the cardinality-constrained problem into a penalty function form and derive exact penalty parameter values for some optimization problems, especially for quadratic minimization problems which often appear in practice. A DC Algorithm (DCA...
• Wait-and-judge scenario optimization AI翻译
  作者：Campi, M. C.; Garatti, S.
  作者单位：University of Brescia; Polytechnic University of Milan
  摘要：We consider convex optimization problems with uncertain, probabilistically described, constraints. In this context, scenario optimization is a well recognized methodology where a sample of the constraints is used to describe uncertainty. One says that the scenario solution generalizes well, or has a high robustness level, if it satisfies most of the other constraints besides those in the sample. Over the past 10 years, the main theoretical investigations on the scenario approach have related t...
• Data-driven inverse optimization with imperfect information AI翻译
  作者：Esfahani, Peyman Mohajerin; Shafieezadeh-Abadeh, Soroosh; Hanasusanto, Grani A.; Kuhn, Daniel
  作者单位：Delft University of Technology; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; University of Texas System; University of Texas Austin
  摘要：In data-driven inverse optimization an observer aims to learn the preferences of an agent who solves a parametric optimization problem depending on an exogenous signal. Thus, the observer seeks the agent's objective function that best explains a historical sequence of signals and corresponding optimal actions. We focus here on situations where the observer has imperfect information, that is, where the agent's true objective function is not contained in the search space of candidate objectives,...
• Theoretical challenges towards cutting-plane selection AI翻译
  作者：Dey, Santanu S.; Molinaro, Marco
  作者单位：University System of Georgia; Georgia Institute of Technology; Pontificia Universidade Catolica do Rio de Janeiro
  摘要：While many classes of cutting-planes are at the disposal of integer programming solvers, our scientific understanding is far from complete with regards to cutting-plane selection, i.e., the task of selecting a portfolio of cutting-planes to be added to the LP relaxation at a given node of the branch-and-bound tree. In this paper we review the different classes of cutting-planes available, known theoretical results about their relative strength, important issues pertaining to cut selection, and...
• Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization AI翻译
  作者：Gribling, Sander; de Laat, David; Laurent, Monique
  作者单位：Centrum Wiskunde & Informatica (CWI); Tilburg University
  摘要：In this paper we study optimization problems related to bipartite quantum correlations using techniques from tracial noncommutative polynomial optimization. First we consider the problem of finding the minimal entanglement dimension of such correlations. We construct a hierarchy of semidefinite programming lower bounds and show convergence to a new parameter: the minimal average entanglement dimension, which measures the amount of entanglement needed to reproduce a quantum correlation when acc...
• Optimal estimation of sensor biases for asynchronous multi-sensor data fusion AI翻译
  作者：Pu, Wenqiang; Liu, Ya-Feng; Yan, Junkun; Liu, Hongwei; Luo, Zhi-Quan
  作者单位：Xidian University; Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; The Chinese University of Hong Kong, Shenzhen; Shenzhen Research Institute of Big Data
  摘要：An important step in a multi-sensor surveillance system is to estimate sensor biases from their noisy asynchronous measurements. This estimation problem is computationally challenging due to the highly nonlinear transformation between the global and local coordinate systems as well as the measurement asynchrony from different sensors. In this paper, we propose a novel nonlinear least squares formulation for the problem by assuming the existence of a reference target moving with an (unknown) co...
• Minimization of transformed penalty: theory, difference of convex function algorithm, and robust application in compressed sensing AI翻译
  作者：Zhang, Shuai; Xin, Jack
  作者单位：University of California System; University of California Irvine
  摘要：We study the minimization problem of a non-convex sparsity promoting penalty function, the transformed (TL1), and its application in compressed sensing (CS). The TL1 penalty interpolates and norms through a nonnegative parameter , similar to with , and is known to satisfy unbiasedness, sparsity and Lipschitz continuity properties. We first consider the constrained minimization problem, and discuss the exact recovery of norm minimal solution based on the null space property (NSP). We then prove...
• Relaxations and approximations of chance constraints under finite distributions AI翻译
  作者：Ahmed, Shabbir; Xie, Weijun
  作者单位：University System of Georgia; Georgia Institute of Technology; Virginia Polytechnic Institute & State University
  摘要：Optimization problems with constraints involving stochastic parameters that are required to be satisfied with a prespecified probability threshold arise in numerous applications. Such chance constrained optimization problems involve the dual challenges of stochasticity and nonconvexity. In the setting of a finite distribution of the stochastic parameters, an optimization problem with linear chance constraints can be formulated as a mixed integer linear program (MILP). The natural MILP formulat...
• Binary extended formulations of polyhedral mixed-integer sets AI翻译
  作者：Dash, Sanjeeb; Gunluk, Oktay; Hildebrand, Robert
  作者单位：International Business Machines (IBM); IBM USA; Virginia Polytechnic Institute & State University
  摘要：We analyze different ways of constructing binary extended formulations of polyhedral mixed-integer sets with bounded integer variables and compare their relative strength with respect to split cuts. We show that among all binary extended formulations where each bounded integer variable is represented by a distinct collection of binary variables, what we call unimodular extended formulations are the strongest. We also compare the strength of some binary extended formulations from the literature...