-
作者：Tseng, Paul
作者单位：University of Washington; University of Washington Seattle
摘要：An important issue in convex programming concerns duality gap. Various conditions have been developed over the years that guarantee no duality gap, including one developed by Rockafellar (Network flows and monotropic programming. Wiley-Interscience, New York, 1984)involving separable objective function and affine constraints. We show that this sufficient condition can be further relaxed to allow the constraint functions to be separable. We also refine a sufficient condition involving weakly an...
-
作者：Caprara, Alberto; Monaci, Michele
作者单位：University of Bologna; University of Padua
摘要：We consider geometric problems in which rectangles have to be packed into (identical) squares. These problems turn out to be very hard in practice, and ILP formulations in which variables specify the coordinates in the packing perform very poorly. While most methods developed so far are based on simple geometric considerations, a recent landmark result of Fekete and Schepers suggests to put these geometric aspects aside and use the most advanced tools for the one-dimensional case. In this pape...
-
作者：Bonnans, J. Frederic; Hermant, Audrey
作者单位：Institut Polytechnique de Paris; Ecole Polytechnique
摘要：The paper deals with optimal control problems with only one control variable and one state constraint, of arbitrary order. We consider the case of finitely many boundary arcs and touch times. We obtain a no-gap theory of second-order conditions, allowing to characterize second-order quadratic growth.
-
作者：Iusem, Alfredo; Seeger, Alberto
作者单位：Avignon Universite
摘要：The concept of antipodality relative to a closed convex cone K subset of R-d has been explored in detail in a recent work of ours. The antipodality problem consists of finding a pair of unit vectors in K achieving the maximal angle of the cone. Our attention now is focused not just in the maximal angle, but in the angular spectrum of the cone. By definition, the angular spectrum of a cone is the set of angles satisfying the stationarity (or criticality) condition associated to the maximization...
-
作者：Correa, Jose R.; Wagner, Michael R.
作者单位：California State University System; California State University East Bay; Universidad Adolfo Ibanez
摘要：We study classic machine sequencing problems in an online setting. Specifically, we look at deterministic and randomized algorithms for the problem of scheduling jobs with release dates on identical parallel machines, to minimize the sum of weighted completion times: Both preemptive and non-preemptive versions of the problem are analyzed. Using linear programming techniques, borrowed from the single machine case, we are able to design a 2.62-competitive deterministic algorithm for the non-pree...
-
作者：Qi, Liqun; Wang, Fei; Wang, Yiju
作者单位：Hong Kong Polytechnic University; Hunan City University; Qufu Normal University
摘要：As a global polynomial optimization problem, the best rank-one approximation to higher order tensors has extensive engineering and statistical applications. Different from traditional optimization solution methods, in this paper, we propose some Z-eigenvalue methods for solving this problem. We first propose a direct Z-eigenvalue method for this problem when the dimension is two. In multidimensional case, by a conventional descent optimization method, we may find a local minimizer of this prob...
-
作者：Nesterov, Yurii
作者单位：Universite Catholique Louvain
摘要：In this paper we present a new approach for constructing subgradient schemes for different types of nonsmooth problems with convex structure. Our methods are primal-dual since they are always able to generate a feasible approximation to the optimum of an appropriately formulated dual problem. Besides other advantages, this useful feature provides the methods with a reliable stopping criterion. The proposed schemes differ from the classical approaches (divergent series methods, mirror descent m...
-
作者：Faigle, Ulrich; Fujishige, Satoru
作者单位：University of Cologne; Kyoto University
摘要：We present a general model for set systems to be independence families with respect to set families which determine classes of proper weight functions on a ground set. Within this model, matroids arise from a natural subclass and can be characterized by the optimality of the greedy algorithm. This model includes and extends many of the models for generalized matroid-type greedy algorithms proposed in the literature and, in particular, integral polymatroids. We discuss the relationship between ...
-
作者：Epstein, Leah; Levin, Asaf
作者单位：Hebrew University of Jerusalem; University of Haifa
摘要：Bin packing is a well studied problem which has many applications. In this paper we design a robust APTAS for the problem. The robust APTAS receives a single input item to be added to the packing at each step. It maintains an approximate solution throughout this process, by slightly adjusting the solution for each new item. At each step, the total size of items which may migrate between bins must be bounded by a constant factor times the size of the new item. We show that such a property canno...
-
作者：Ito, Kazufumi; Kunisch, Karl
作者单位：University of Graz; North Carolina State University
摘要：This paper addresses the globalization of the semi-smooth Newton method for non-smooth equations F(x) = 0 in R-m with applications to complementarity and discretized l(1)-regularization problems. Assuming semi-smoothness it is shown that super-linearly convergent Newton methods can be globalized, if appropriate descent directions are used for the merit function |F(x)|(2). Special attention is paid to directions obtained from the primal-dual active set strategy.
