Convex Optimization

Generalized Conjugate Gradient Methods for $\ell_1$ Regularized Convex Quadratic Programming with Finite Convergence

  • Xiaojun Chen
  • Zhaosong Lu
    • Categories Convex Optimization, Nonsmooth Optimization, Quadratic Programming Tags , , , ,

    The conjugate gradient (CG) method is an efficient iterative method for solving large-scale strongly convex quadratic programming (QP). In this paper we propose some generalized CG (GCG) methods for solving the $\ell_1$-regularized (possibly not strongly) convex QP that terminate at an optimal solution in a finite number of iterations. At each iteration, our methods first … Read more

    Acceleration of the PDHGM on strongly convex subspaces

  • Thomas Pock
  • Tuomo Valkonen
    • Categories Applications - Science and Engineering, Convex Optimization, Generalized Convexity/Monoticity Tags , , ,

    We propose several variants of the primal-dual method due to Chambolle and Pock. Without requiring full strong convexity of the objective functions, our methods are accelerated on subspaces with strong convexity. This yields mixed rates, $O(1/N^2)$ with respect to initialisation and $O(1/N)$ with respect to the dual sequence, and the residual part of the primal … Read more

    An Extended Frank-Wolfe Method with “In-Face” Directions, and its Application to Low-Rank Matrix Completion

  • Robert M. Freund
  • Rahul Mazumder
  • Paul Grigas
    • Categories Convex Optimization, Data-Mining Tags , , , , ,

    We present an extension of the Frank-Wolfe method that is designed to induce near-optimal solutions on low-dimensional faces of the feasible region. We present computational guarantees for the method that trade off efficiency in computing near-optimal solutions with upper bounds on the dimension of minimal faces of iterates. We apply our method to the low-rank … Read more

    The rate of convergence of Nesterov’s accelerated forward-backward method is actually (k^{-2})$

  • Hédy Attouch
  • Juan Peypouquet
    • Categories Convex Optimization Tags , ,

    The {\it forward-backward algorithm} is a powerful tool for solving optimization problems with a {\it additively separable} and {\it smooth} + {\it nonsmooth} structure. In the convex setting, a simple but ingenious acceleration scheme developed by Nesterov has been proved useful to improve the theoretical rate of convergence for the function values from the standard … Read more

    Fast convergence of inertial dynamics and algorithms with asymptotic vanishing damping

  • Hédy Attouch
  • Z Chbani
  • Juan Peypouquet
  • P Redont
    • Categories Convex Optimization Tags , , , , , ,

    In a Hilbert space setting $\mathcal H$, we study the fast convergence properties as $t \to + \infty$ of the trajectories of the second-order differential equation \begin{equation*} \ddot{x}(t) + \frac{\alpha}{t} \dot{x}(t) + \nabla \Phi (x(t)) = g(t), \end{equation*} where $\nabla\Phi$ is the gradient of a convex continuously differentiable function $\Phi: \mathcal H \to \mathbb R$, … Read more

    Techniques in Iterative Proton CT Image Reconstruction

  • Yair Censor
  • Scott Penfold
    • Categories Biomedical Applications, Convex Optimization Tags , , , , , ,

    This is a review paper on some of the physics, modeling, and iterative algorithms in proton computed tomography (pCT) image reconstruction. The primary challenge in pCT image reconstruction lies in the degraded spatial resolution resulting from multiple Coulomb scattering within the imaged object. Analytical models such as the most likely path (MLP) have been proposed … Read more

    An accelerated non-Euclidean hybrid proximal extragradient-type Algorithm for convex-concave saddle-point Problems

  • Oliver Kolossoski
  • Renato D.C. Monteiro
    • Categories Convex Optimization Tags , , , , , , , ,

    This paper describes an accelerated HPE-type method based on general Bregman distances for solving monotone saddle-point (SP) problems. The algorithm is a special instance of a non-Euclidean hybrid proximal extragradient framework introduced by Svaiter and Solodov [28] where the prox sub-inclusions are solved using an accelerated gradient method. It generalizes the accelerated HPE algorithm presented … Read more

    New Computational Guarantees for Solving Convex Optimization Problems with First Order Methods, via a Function Growth Condition Measure

  • Robert M. Freund
  • Haihao Lu
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , ,

    Motivated by recent work of Renegar, we present new computational methods and associated computational guarantees for solving convex optimization problems using first-order methods. Our problem of interest is the general convex optimization problem f^* = \min_{x \in Q} f(x), where we presume knowledge of a strict lower bound f_slb < f^*. [Indeed, f_slb is naturally ... Read more

    Noisy Euclidean distance realization: robust facial reduction and the Pareto frontier

  • Dmitriy Drusvyatskiy
  • Nathan Krislock
  • Henry Wolkowicz
  • Y.-L. Voronin
    • Categories Convex Optimization, Semi-definite Programming Tags , , , , ,

    We present two algorithms for large-scale low-rank Euclidean distance matrix completion problems, based on semidefinite optimization. Our first method works by relating cliques in the graph of the known distances to faces of the positive semidefinite cone, yielding a combinatorial procedure that is provably robust and parallelizable. Our second algorithm is a first order method … Read more

    Uniqueness of Market Equilibrium on a Network: A Peak-Load Pricing Approach

  • Veronika Grimm
  • Lars Schewe
  • Martin Schmidt
  • Gregor Zöttl
    • Categories Convex Optimization, Finance and Economics, Network Optimization Tags , , ,

    In this paper we establish conditions under which uniqueness of market equilibrium is obtained in a setup where prior to trading of electricity, transmission capacities between different market regions are fixed. In our setup, firms facing fluctuating demand decide on the size and location of production facilities. They make production decisions constrained by the invested … Read more