-
作者：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...
-
作者：Yang, Wenzhuo; Xu, Huan
作者单位：National University of Singapore
摘要：This paper investigates the computational aspects of distributionally robust chance constrained optimization problems. In contrast to previous research that mainly focused on the linear case (with a few exceptions discussed in detail below), we consider the case where the constraints can be non-linear to the decision variable, and in particular to the uncertain parameters. This formulation is of great interest as it can model non-linear uncertainties that are ubiquitous in applications. Our ma...
-
作者：Adler, Ilan; Cottle, Richard W.; Pang, Jong-Shi
作者单位：University of California System; University of California Berkeley; Stanford University; University of Southern California
摘要：We identify a class of Linear Complementarity Problems (LCPs) that are solvable in strongly polynomial time by Lemke's Algorithm (Scheme 1) or by the Parametric Principal Pivoting Method (PPPM). This algorithmic feature for the class of problems under consideration here is attributable to the proper selection of the covering vector in Scheme 1 or the parametric direction vector in the PPPM which leads to solutions of limited and monotonically increasing support size; such solutions are sparse....
-
作者：Cervinka, Michal; Kanzow, Christian; Schwartz, Alexandra
作者单位：Czech Academy of Sciences; Institute of Information Theory & Automation of the Czech Academy of Sciences; Charles University Prague; University of Wurzburg; Technical University of Darmstadt
摘要：This paper considers optimization problems with cardinality constraints. Based on a recently introduced reformulation of this problem as a nonlinear program with continuous variables, we first define some problem-tailored constraint qualifications and then show how these constraint qualifications can be used to obtain suitable optimality conditions for cardinality constrained problems. Here, the (KKT-like) optimality conditions hold under much weaker assumptions than the corresponding result t...
