-
作者：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 ...
-
作者：Nagarajan, Viswanath; Shi, Cong
作者单位：University of Michigan System; University of Michigan
摘要：We consider the following two deterministic inventory optimization problems with non-stationary demands. Submodular joint replenishment problem. This involves multiple item types and a single retailer who faces demands over a finite planning horizon of T periods. In each time period, any subset of item-types can be ordered incurring a joint ordering cost which is submodular. Moreover, items can be held in inventory while incurring a holding cost. The objective is to find a sequence of orders t...
-
作者：Dorsch, Dominik; Gomez, Walter; Shikhman, Vladimir
作者单位：RWTH Aachen University; Universidad de La Frontera; Universite Catholique Louvain
摘要：We derive a new genericity result for nonlinear semidefinite programming (NLSDP). Namely, almost all linear perturbations of a given NLSDP are shown to be nondegenerate. Here, nondegeneracy for NLSDP refers to the transversality constraint qualification, strict complementarity and second-order sufficient condition. Due to the presence of the second-order sufficient condition, our result is a nontrivial extension of the corresponding results for linear semidefinite programs (SDP) from Alizadeh ...
-
作者：Han, Jinil; Lee, Kyungsik; Lee, Chungmok; Choi, Ki-Seok; Park, Sungsoo
作者单位：Universite Catholique Louvain; Korea Advanced Institute of Science & Technology (KAIST); Seoul National University (SNU); Seoul National University (SNU); Hankuk University Foreign Studies
摘要：We consider a certain class of chance-constrained binary knapsack problem where each item has a normally distributed random weight that is independent of the other items. For this problem we propose an efficient pseudo-polynomial time algorithm based on the robust optimization approach for finding a solution with a theoretical bound on the probability of satisfying the knapsack constraint. Our algorithm is tested on a wide range of random instances, and the results demonstrate that it provides...
-
作者：de Oliveira, Welington; Solodov, Mikhail
摘要：We propose a bundle method for minimizing nonsmooth convex functions that combines both the level and the proximal stabilizations. Most bundle algorithms use a cutting-plane model of the objective function to formulate a subproblem whose solution gives the next iterate. Proximal bundle methods employ the model in the objective function of the subproblem, while level methods put the model in the subproblem's constraints. The proposed algorithm defines new iterates by solving a subproblem that e...
-
作者：Kim, Sunyoung; Kojima, Masakazu; Toh, Kim-Chuan
作者单位：Ewha Womans University; Chuo University; National University of Singapore
摘要：We propose an efficient computational method for linearly constrained quadratic optimization problems (QOPs) with complementarity constraints based on their Lagrangian and doubly nonnegative (DNN) relaxation and first-order algorithms. The simplified Lagrangian-completely positive programming (CPP) relaxation of such QOPs proposed by Arima, Kim, and Kojima in 2012 takes one of the simplest forms, an unconstrained conic linear optimization problem with a single Lagrangian parameter in a CPP mat...
-
作者：Richtarik, Peter; Takac, Martin
作者单位：University of Edinburgh
摘要：In this work we show that randomized (block) coordinate descent methods can be accelerated by parallelization when applied to the problem of minimizing the sum of a partially separable smooth convex function and a simple separable convex function. The theoretical speedup, as compared to the serial method, and referring to the number of iterations needed to approximately solve the problem with high probability, is a simple expression depending on the number of parallel processors and a natural ...
-
作者：Xia, Yong; Wang, Shu; Sheu, Ruey-Lin
作者单位：Beihang University; National Cheng Kung University
摘要：Let and be two quadratic functions having symmetric matrices and . The S-lemma with equality asks when the unsolvability of the system implies the existence of a real number such that . The problem is much harder than the inequality version which asserts that, under Slater condition, is unsolvable if and only if for some . In this paper, we show that the S-lemma with equality does not hold only when the matrix has exactly one negative eigenvalue and is a non-constant linear function (). As an ...
