-
作者：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...
-
作者：Hazan, Elad; Koren, Tomer
作者单位：Technion Israel Institute of Technology
摘要：We consider the fundamental problem of minimizing a general quadratic function over an ellipsoidal domain, also known as the trust region (sub)problem. We give the first provable linear-time (in the number of non-zero entries of the input) algorithm for approximately solving this problem. Specifically, our algorithm returns an -approximate solution in runtime of order N/, where N is the number of non-zero entries in the input. This matches the runtime of Nesterov's accelerated gradient descent...
-
作者：Iwata, Satoru; Kamiyama, Naoyuki; Katoh, Naoki; Kijima, Shuji; Okamoto, Yoshio
作者单位：University of Tokyo; Kyushu University; Kyoto University; Kyushu University; University of Electro-Communications - Japan
摘要：We show the existence of a polynomial-size extended formulation for the base polytope of a -sparsity matroid. For an undirected graph , the size of the formulation is when and when . To this end, we employ the technique developed by Faenza et al. recently that uses a randomized communication protocol.
-
作者：Dodangeh, M.; Vicente, L. N.
作者单位：Universidade de Coimbra; Universidade de Coimbra
摘要：In this paper we prove that the broad class of direct-search methods of directional type, based on imposing sufficient decrease to accept new iterates, exhibits the same worst case complexity bound and global rate of the gradient method for the unconstrained minimization of a convex and smooth function. More precisely, it will be shown that the number of iterations needed to reduce the norm of the gradient of the objective function below a certain threshold is at most proportional to the inver...
-
作者：Lan, Guanghui; Monteiro, Renato D. C.
作者单位：State University System of Florida; University of Florida; University System of Georgia; Georgia Institute of Technology
摘要：This paper considers a special class of convex programming (CP) problems whose feasible regions consist of a simple compact convex set intersected with an affine manifold. We present first-order methods for this class of problems based on an inexact version of the classical augmented Lagrangian (AL) approach, where the subproblems are approximately solved by means of Nesterov's optimal method. We then establish a bound on the total number of Nesterov's optimal iterations, i.e., the inner itera...
-
作者：Dash, Sanjeeb; Gunluk, Oktay; Moran R, Diego A.
作者单位：International Business Machines (IBM); IBM USA; Virginia Polytechnic Institute & State University; Universidad Adolfo Ibanez
摘要：Split cuts form a well-known class of valid inequalities for mixed-integer programming problems. Cook et al. (Math Program 47:155-174, 1990) showed that the split closure of a rational polyhedron P is again a polyhedron. In this paper, we extend this result from a single rational polyhedron to the union of a finite number of rational polyhedra. We then use this result to prove that cross cuts yield closures that are rational polyhedra. Cross cuts are a generalization of split cuts introduced b...
-
作者：Gonzaga, Clovis C.
作者单位：Universidade Federal de Santa Catarina (UFSC)
摘要：The existing choices for the step lengths used by the classical steepest descent algorithm for minimizing a convex quadratic function require in the worst case iterations to achieve a precision , where C is the Hessian condition number. We show how to construct a sequence of step lengths with which the algorithm stops in iterations, with a bound almost exactly equal to that of the Conjugate Gradient method.
-
作者：Ghaddar, Bissan; Vera, Juan C.; Anjos, Miguel F.
作者单位：Tilburg University; Universite de Montreal; Universite de Montreal; Polytechnique Montreal
摘要：Hierarchies of semidefinite programs have been used to approximate or even solve polynomial programs. This approach rapidly becomes computationally expensive and is often tractable only for problems of small size. In this paper, we propose a dynamic inequality generation scheme to generate valid polynomial inequalities for general polynomial programs. When used iteratively, this scheme improves the bounds without incurring an exponential growth in the size of the relaxation. As a result, the p...
