-
作者：Edirisinghe, Chanaka; Jeong, Jaehwan
作者单位：Rensselaer Polytechnic Institute; Radford University
摘要：We present a global algorithm for indefinite knapsack separable quadratic programs with bound constraints. The upper bounds on variables with nonconvex terms are assumed to be infinite in the algorithmic development. By characterizing optimal solutions of the problem, we enumerate a subset of KKT points to determine a global optimum. The enumeration is made efficient by developing a theory for shrinking and partitioning the search domain of KKT multipliers. The global algorithmic procedure is ...
-
作者：Neumaier, Arnold
作者单位：University of Vienna
摘要：This paper presents an algorithm for approximately minimizing a convex function in simple, not necessarily bounded convex, finite-dimensional domains, assuming only that function values and subgradients are available. No global information about the objective function is needed apart from a strong convexity parameter (which can be put to zero if only convexity is known). The worst case number of iterations needed to achieve a given accuracy is independent of the dimension and-apart from a cons...
-
作者：Gower, R. M.; Gower, A. L.
作者单位：Heriot Watt University; University of Edinburgh; Ollscoil na Gaillimhe-University of Galway
摘要：It is commonly assumed that calculating third order information is too expensive for most applications. But we show that the directional derivative of the Hessian () can be calculated at a cost proportional to that of a state-of-the-art method for calculating the Hessian matrix. We do this by first presenting a simple procedure for designing high order reverse methods and applying it to deduce several methods including a reverse method that calculates . We have implemented this method taking i...
-
作者：Andreani, R.; Martinez, J. M.; Santos, L. T.
作者单位：Universidade Estadual de Campinas
摘要：We will show examples in which the primal sequence generated by the Newton-Lagrange method converges to a strict local minimizer of a constrained optimization problem but the gradient of the Lagrangian does not tend to zero, independently of the choice of the dual sequence.
-
作者：Chambolle, Antonin; Pock, Thomas
作者单位：Centre National de la Recherche Scientifique (CNRS); Institut Polytechnique de Paris; Ecole Polytechnique; Graz University of Technology; Austrian Institute of Technology (AIT)
摘要：We revisit the proofs of convergence for a first order primal-dual algorithm for convex optimization which we have studied a few years ago. In particular, we prove rates of convergence for a more general version, with simpler proofs and more complete results. The new results can deal with explicit terms and nonlinear proximity operators in spaces with quite general norms.
-
作者：Van Parys, Bart P. G.; Goulart, Paul J.; Kuhn, Daniel
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; University of Oxford; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：A sharp upper bound on the probability of a random vector falling outside a polytope, based solely on the first and second moments of its distribution, can be computed efficiently using semidefinite programming. However, this Chebyshev-type bound tends to be overly conservative since it is determined by a discrete worst-case distribution. In this paper we obtain a less pessimistic Gauss-type bound by imposing the additional requirement that the random vector's distribution must be unimodal. We...
-
作者：Porumbel, Daniel
作者单位：heSam Universite; Conservatoire National Arts & Metiers (CNAM)
摘要：A recurrent task in mathematical programming consists of optimizing polytopes with prohibitively many constraints, e.g., the primal polytope in cutting-planes methods or the dual polytope in column generation (CG). We present a method to optimize such polytopes using the following intersection sub-problem: given ray , find the maximum such that is feasible. We interpret as a direction of growth from the origin ; is the intersection point between and the polytope boundary. To ease the expositio...
-
作者：Hua, Xiaoqin; Yamashita, Nobuo
作者单位：Jiangsu University of Science & Technology; Kyoto University
摘要：In this paper, we propose a class of block coordinate proximal gradient (BCPG) methods for solving large-scale nonsmooth separable optimization problems. The proposed BCPG methods are based on the Bregman functions, which may vary at each iteration. These methods include many well-known optimization methods, such as the quasi-Newton method, the block coordinate descent method, and the proximal point method. For the proposed methods, we establish their global convergence properties when the blo...
-
作者：Forsgren, Anders; Gill, Philip E.; Wong, Elizabeth
作者单位：Royal Institute of Technology; University of California System; University of California San Diego
摘要：Computational methods are proposed for solving a convex quadratic program (QP). Active-set methods are defined for a particular primal and dual formulation of a QP with general equality constraints and simple lower bounds on the variables. In the first part of the paper, two methods are proposed, one primal and one dual. These methods generate a sequence of iterates that are feasible with respect to the equality constraints associated with the optimality conditions of the primal-dual form. The...
-
作者：Liang, Jingwei; Fadili, Jalal; Peyre, Gabriel
作者单位：Universite de Caen Normandie; Centre National de la Recherche Scientifique (CNRS); Centre National de la Recherche Scientifique (CNRS); Universite PSL; Universite Paris-Dauphine; Universite PSL; Universite Paris-Dauphine
摘要：In this paper, we present a convergence rate analysis for the inexact Krasnosel'skiAaEuroMann iteration built from non-expansive operators. The presented results include two main parts: we first establish the global pointwise and ergodic iteration-complexity bounds; then, under a metric sub-regularity assumption, we establish a local linear convergence for the distance of the iterates to the set of fixed points. The obtained results can be applied to analyze the convergence rate of various mon...
