-
作者：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 ...
-
作者：de Ruiter, Frans J. C. T.; Brekelmans, Ruud C. M.; den Hertog, Dick
作者单位：Tilburg University
摘要：In this note we show that multiple solutions exist for the production-inventory example in the seminal paper on adjustable robust optimization in Ben-Tal et al. (Math Program 99(2):351-376, 2004). All these optimal robust solutions have the same worst-case objective value, but the mean objective values differ up to 21.9 % and for individual realizations this difference can be up to 59.4 %. We show via additional experiments that these differences in performance become negligible when using a f...
-
作者：Kanzow, Christian
作者单位：University of Wurzburg
摘要：The multiplier-penalty approach is one of the classical methods for the solution of constrained optimization problems. This method was generalized to the solution of quasi-variational inequalities by Pang and Fukushima (Comput Manag Sci 2:21-56, 2005). Based on the recent improvements achieved for the multiplier-penalty approach for optimization, we generalize the method by Pang and Fukushima for quasi-variational inequalities in several respects: (a) We allow to compute inexact KKT-points of ...
-
作者：Scheinberg, Katya; Tang, Xiaocheng
作者单位：Lehigh University
摘要：Recently several methods were proposed for sparse optimization which make careful use of second-order information (Hsieh et al. in Sparse inverse covariance matrix estimation using quadratic approximation. In: NIPS, 2011; Yuan et al. in An improved GLMNET for l1-regularized logistic regression and support vector machines. National Taiwan University, Taipei City, 2011; Olsen et al. in Newton-like methods for sparse inverse covariance estimation. In: NIPS, 2012; Byrd et al. in A family of second...
