-
作者：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...
-
作者：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...
