-
作者：Kucukyavuz, Simge; Noyan, Nilay
作者单位：University System of Ohio; Ohio State University; Sabanci University
摘要：We consider a class of stochastic optimization problems that features benchmarking preference relations among random vectors representing multiple random performance measures (criteria) of interest. Given a benchmark random performance vector, preference relations are incorporated into the model as constraints, which require the decision-based random vector to be preferred to the benchmark according to a relation based on multivariate conditional value-at-risk (CVaR) or second-order stochastic...
-
作者：Baes, Michel; Oertel, Timm; Weismantel, Robert
作者单位：University of Zurich; Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：We extend in two ways the standard Karush-Kuhn-Tucker optimality conditions to problems with a convex objective, convex functional constraints, and the extra requirement that some of the variables must be integral. While the standard Karush-Kuhn-Tucker conditions involve separating hyperplanes, our extension is based on mixed-integer-free polyhedra. Our optimality conditions allow us to define an exact dual of our original mixed-integer convex problem.
-
作者：Condat, Laurent
作者单位：Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS)
摘要：A new algorithm is proposed to project, exactly and in finite time, a vector of arbitrary size onto a simplex or an -norm ball. It can be viewed as a Gauss-Seidel-like variant of Michelot's variable fixing algorithm; that is, the threshold used to fix the variables is updated after each element is read, instead of waiting for a full reading pass over the list of non-fixed elements. This algorithm is empirically demonstrated to be faster than existing methods.
-
作者：Shtern, Shimrit; Ben-Tal, Aharon
作者单位：Technion Israel Institute of Technology; Tilburg University; Columbia University
摘要：Tracking problems are prevalent in the present day GPS and video systems. The problem of target tracking is a specific case of dynamic linear system estimation with additive noise. The most widely used filter for these systems is the Kalman filter (KF). The optimality of the KF and similar Bayesian filters is guaranteed under particular probabilistic assumptions. However, in practice, and specifically in applications such as tracking, these probabilistic assumptions are not realistic; indeed, ...
-
作者：Kogan, Alexander; Lejeune, Miguel A.; Luedtke, James
作者单位：Rutgers University System; Rutgers University Newark; Rutgers University New Brunswick; George Washington University; University of Wisconsin System; University of Wisconsin Madison
-
作者：Aronna, M. S.; Bonnans, J. F.; Goh, B. S.
作者单位：Getulio Vargas Foundation; Institut Polytechnique de Paris; Ecole Polytechnique; Institut Polytechnique de Paris; ENSTA Paris; Ecole Polytechnique; Curtin University Malaysia
摘要：In this article we establish new second order necessary and sufficient optimality conditions for a class of control-affine problems with a scalar control and a scalar state constraint. These optimality conditions extend to the constrained state framework the Goh transform, which is the classical tool for obtaining an extension of the Legendre condition.
-
作者：Dobre, Cristian; Duer, Mirjam; Frerick, Leonhard; Vallentin, Frank
作者单位：Wageningen University & Research; Universitat Trier; University of Cologne
摘要：In the last decade, copositive formulations have been proposed for a variety of combinatorial optimization problems, for example the stability number (independence number). In this paper, we generalize this approach to infinite graphs and show that the stability number of an infinite graph is the optimal solution of some infinite-dimensional copositive program. For this we develop a duality theory between the primal convex cone of copositive kernels and the dual convex cone of completely posit...
-
作者：Garber, Dan; Hazan, Elad
作者单位：Technion Israel Institute of Technology
摘要：We consider semidefinite optimization in a saddle point formulation where the primal solution is in the spectrahedron and the dual solution is a distribution over affine functions. We present an approximation algorithm for this problem that runs in sublinear time in the size of the data. To the best of our knowledge, this is the first algorithm to achieve this. Our algorithm is also guaranteed to produce low-rank solutions. We further prove lower bounds on the running time of any algorithm for...
-
作者：Protasov, Vladimir Yu.
作者单位：Lomonosov Moscow State University
摘要：We develop an iterative optimization method for finding the maximal and minimal spectral radius of a matrix over a compact set of nonnegative matrices. We consider matrix sets with product structure, i.e., all rows are chosen independently from given compact sets (row uncertainty sets). If all the uncertainty sets are finite or polyhedral, the algorithm finds the matrix with maximal/minimal spectral radius within a few iterations. It is proved that the algorithm avoids cycling and terminates w...
-
作者：Hirai, Hiroshi
作者单位：University of Tokyo
摘要：A -extension of graph is a metric on a set containing the vertex set of such that extends the shortest path metric of and for all there exists a vertex in with . The minimum -extension problem 0-Ext on is: given a set and a nonnegative cost function defined on the set of all pairs of , find a -extension of with minimum. The -extension problem generalizes a number of basic combinatorial optimization problems, such as minimum -cut problem and multiway cut problem. Karzanov proved the polynomial ...
