Convex and Nonsmooth Optimization

Iteration complexity analysis of a partial LQP-based alternating direction method of multipliers

  • Jianchao Bai
  • Yuxue Ma
  • Hao Sun
  • Miao Zhang
    • Categories Convex Optimization, Global Optimization Theory

    In this paper, we consider a prototypical convex optimization problem with multi-block variables and separable structures. By adding the Logarithmic Quadratic Proximal (LQP) regularizer with suitable proximal parameter to each of the first grouped subproblems, we develop a partial LQP-based Alternating Direction Method of Multipliers (ADMM-LQP). The dual variable is updated twice with relatively larger … Read more

    Equipping Barzilai-Borwein method with two dimensional quadratic termination property

  • Yu-Hong Dai
  • Yakui Huang
  • Xin-Wei Liu
    • Categories Convex Optimization, Nonlinear Optimization Tags , , , , ,

    A new gradient stepsize is derived at the motivation of equipping the Barzilai-Borwein (BB) method with two dimensional quadratic termination property. A remarkable feature of the new stepsize is that its computation only depends on the BB stepsizes in previous iterations without the use of exact line searches and Hessian, and hence it can easily … Read more

    Convergence of Proximal Gradient Algorithm in the Presence of Adjoint Mismatch

  • Émilie Chouzenoux
  • Jean-Christophe Pesquet
  • Cyril Riddel
  • Marion Savanier
  • Yves Trousset
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , , , , ,

    We consider the proximal gradient algorithm for solving penalized least-squares minimization problems arising in data science. This first-order algorithm is attractive due to its flexibility and minimal memory requirements allowing to tackle large-scale minimization problems involving non-smooth penalties. However, for problems such as X-ray computed tomography, the applicability of the algorithm is dominated by the … Read more

    Tight bounds on the maximal perimeter and the maximal width of convex small polygons

  • Christian Bingane
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Quadratic Programming Tags , , , , ,

    A small polygon is a polygon of unit diameter. The maximal perimeter and the maximal width of a convex small polygon with $n=2^s$ vertices are not known when $s \ge 4$. In this paper, we construct a family of convex small $n$-gons, $n=2^s$ and $s\ge 3$, and show that the perimeters and the widths obtained … Read more

    New efficient approach in finding a zero of a maximal monotone operator

  • Ba Khiet Le
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , ,

    In the paper, we provide a new efficient approach to find a zero of a maximal monotone operator under very mild assumptions. Using a regularization technique and the proximal point algorithm, we can construct a sequence that converges strongly to a solution with at least linear convergence rate. Article Download View New efficient approach in … Read more

    Generalized Self-Concordant Analysis of Frank-Wolfe algorithms

  • Pavel Dvurechensky
  • Shimrit Shtern
  • Kamil Safin
  • Mathias Staudigl
    • Categories Convex Optimization

    Projection-free optimization via different variants of the Frank-Wolfe (FW) method has become one of the cornerstones in large scale optimization for machine learning and computational statistics. Numerous applications within these fields involve the minimization of functions with self-concordance like properties. Such generalized self-concordant (GSC) functions do not necessarily feature a Lipschitz continuous gradient, nor are … Read more

    On the linear convergence of the forward-backward splitting algorithm

  • Ba Khiet Le
    • Categories Convex and Nonsmooth Optimization Tags , , ,

    In this paper, we establish a linear convergence result for the forward-backward splitting algorithm in the finding a zero of the sum of two maximal monotone operators, where one of them is set-valued strongly monotone and the other is Lipschitz continuous. We show that our convergence rate is better than Douglas–Rachford splitting algorithm’s rate used … Read more

    Largest small polygons: A sequential convex optimization approach

  • Christian Bingane
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Quadratic Programming Tags , , , , ,

    A small polygon is a polygon of unit diameter. The maximal area of a small polygon with $n=2m$ vertices is not known when $m\ge 7$. Finding the largest small $n$-gon for a given number $n\ge 3$ can be formulated as a nonconvex quadratically constrained quadratic optimization problem. We propose to solve this problem with a … Read more

    On strong duality, theorems of the alternative, and projections in conic optimization

  • Temitayo Ajayi
  • Akshay Gupte
  • Amin Khademi
  • Andrew J. Schaefer
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , , ,

    A conic program is the problem of optimizing a linear function over a closed convex cone intersected with an affine preimage of another cone. We analyse three constraint qualifications, namely a Closedness CQ, Slater CQ, and Boundedness CQ (also called Clark- Duffin theorem), that are sufficient for achieving strong duality and show that the first … Read more

    Dual optimal design and the Christoffel-Darboux polynomial

  • Yohann De Castro
  • Didier Henrion
  • Jean-Bernard Lasserre
  • Fabrice Gamboa
    • Categories Convex Optimization, Semi-definite Programming, Statistics Tags , , ,

    The purpose of this short note is to show that the Christoffel-Darboux polynomial, useful in approximation theory and data science, arises naturally when deriving the dual to the problem of semi-algebraic D-optimal experimental design in statistics. It uses only elementary notions of convex analysis. Article Download View Dual optimal design and the Christoffel-Darboux polynomial