-
作者：Tseng, Paul; Bomze, Immanuel M.; Schachinger, Werner
作者单位：University of Vienna; University of Washington; University of Washington Seattle
摘要：We propose a first-order interior-point method for linearly constrained smooth optimization that unifies and extends first-order affine-scaling method and replicator dynamics method for standard quadratic programming. Global convergence and, in the case of quadratic program, (sub)linear convergence rate and iterate convergence results are derived. Numerical experience on simplex constrained problems with 1000 variables is reported.
-
作者：Cornuejols, G.; Liberti, L.; Nannicini, G.
作者单位：Institut Polytechnique de Paris; Ecole Polytechnique; Carnegie Mellon University; Aix-Marseille Universite
摘要：Within the context of solving Mixed-Integer Linear Programs by a Branch-and-Cut algorithm, we propose a new strategy for branching. Computational experiments show that, on the majority of our test instances, this approach enumerates fewer nodes than traditional branching. On average, on instances that contain both integer and continuous variables the number of nodes in the enumeration tree is reduced by more than a factor of two, and computing time is comparable. On a few instances, the improv...
-
作者：Izmailov, A. F.; Solodov, M. V.
作者单位：Instituto Nacional de Matematica Pura e Aplicada (IMPA); Lomonosov Moscow State University
摘要：It has been previously demonstrated that in the case when a Lagrange multiplier associated to a given solution is not unique, Newton iterations [e. g., those of sequential quadratic programming (SQP)] have a tendency to converge to special multipliers, called critical multipliers (when such critical multipliers exist). This fact is of importance because critical multipliers violate the second-order sufficient optimality conditions, and this was shown to be the reason for slow convergence typic...
-
作者：Cartis, Coralia; Gould, Nicholas I. M.; Toint, Philippe L.
作者单位：University of Edinburgh; UK Research & Innovation (UKRI); Science & Technology Facilities Council (STFC); STFC Rutherford Appleton Laboratory; University of Oxford; University of Namur
摘要：An Adaptive Regularisation algorithm using Cubics (ARC) is proposed for unconstrained optimization, generalizing at the same time an unpublished method due to Griewank (Technical Report NA/12, 1981, DAMTP, University of Cambridge), an algorithm by Nesterov and Polyak (Math Program 108(1):177-205, 2006) and a proposal by Weiser et al. (Optim Methods Softw 22(3):413-431, 2007). At each iteration of our approach, an approximate global minimizer of a local cubic regularisation of the objective fun...
-
作者：Dunagan, John; Spielman, Daniel A.; Teng, Shang-Hua
作者单位：Yale University; Microsoft; Boston University
摘要：nn We perform a smoothed analysis of Renegar's condition number for linear programming by analyzing the distribution of the distance to ill-posedness of a linear program subject to a slight Gaussian perturbation. In particular, we show that for every n-by-d matrix (A) over bar, n-vector (b) over bar, and d-vector (c) over bar satisfying parallel to(A) over bar, (b) over bar, (c) over bar parallel to(F) <= 1and every sigma <= 1, E-A,E-b,E-c[log C(A,b,c)] = O(log(nd/sigma)), where A, b and c are...
-
作者：Ibaraki, Toshihide; Imamichi, Takashi; Koga, Yuichi; Nagamochi, Hiroshi; Nonobe, Koji; Yagiura, Mutsunori
作者单位：Nagoya University; Kwansei Gakuin University; Kyoto University; Hosei University
摘要：MAX-2-SAT is one of the representative combinatorial problems and is known to be NP-hard. Given a set of m clauses on n propositional variables, where each clause contains at most two literals and is weighted by a positive real, MAX-2-SAT asks to find a truth assignment that maximizes the total weight of satisfied clauses. In this paper, we propose branch-and-bound exact algorithms for MAX-2-SAT utilizing three kinds of lower bounds. All lower bounds are based on a directed graph that represen...
-
作者：Mackin, Patrick D.; Roy, Asim; Wallenius, Jyrki
作者单位：Aalto University; Black Hills State University; Arizona State University; Arizona State University-Tempe
摘要：To make a decision that is defined by multiple, conflicting objectives it is necessary to know the relative importance of the different objectives. In this paper we present an interactive method and the underlying theory for solving multiple objective mathematical programming problems defined by a convex feasible region and concave, continuously differentiable objective functions. The relative importance of the different objectives for a decision maker is elicited by using binary comparisons o...
-
作者：Goyal, Vineet; Genc-Kaya, Latife; Ravi, R.
作者单位：Carnegie Mellon University; Massachusetts Institute of Technology (MIT)
摘要：We consider a quadratic programming (QP) problem (Pi) of the form min x(T) Cx subject to Ax >= b, x >= 0 where C is an element of R-+(nxn), rank(C) = 1 and A is an element of R-mxn, b is an element of R-m. We present an fully polynomial time approximation scheme (FPTAS) for this problem by reformulating the QP (Pi) as a parameterized LP and rounding the optimal solution. Furthermore, our algorithm returns an extreme point solution of the polytope. Therefore, our results apply directly to 0-1 p...
-
作者：Ge, Dongdong; Jiang, Xiaoye; Ye, Yinyu
作者单位：Shanghai Jiao Tong University; Stanford University; Stanford University
摘要：We discuss the L-p (0 <= p < 1) minimization problem arising from sparse solution construction and compressed sensing. For any fixed 0 < p < 1, we prove that finding the global minimal value of the problem is strongly NP-Hard, but computing a local minimizer of the problem can be done in polynomial time. We also develop an interior-point potential reduction algorithm with a provable complexity bound and demonstrate preliminary computational results of effectiveness of the algorithm.
-
作者：Averkov, Gennadiy; Henk, Martin
作者单位：Otto von Guericke University
摘要：A polynomial representation of a convex d-polytope P is a finite set {p(1)(x), ... , p(n)(x)} of polynomials over R-d such that P = {x is an element of R-d : p(i)(x) >= 0 for every 1 <= i <= n}. Let s(d, P) be the least possible n as above. It is conjectured that s(d, P) = d for all convex d-polytopes P. We confirm this conjecture for simple d-polytopes by providing an explicit construction of d polynomials that represent a given simple d-polytope P.
