Convex and Nonsmooth Optimization

The convergence rate of the Sandwiching algorithm for convex bounded multiobjective optimization

  • Ina Lammel
  • Karl-Heinz Küfer
    • Categories Convex Optimization, Multi-Criteria Optimization Tags , , ,

    Sandwiching algorithms, also known as Benson-type algorithms, approximate the nondominated set of convex bounded multiobjective optimization problems by constructing and iteratively improving polyhedral inner and outer approximations. Using a set-valued metric, an estimate of the approximation quality is determined as the distance between the inner and outer approximation. The convergence of the algorithm is evaluated … Read more

    Singular value half thresholding algorithm for lp regularized matrix optimization problems

  • Peng Dingtao
    • Categories Nonsmooth Optimization, Unconstrained Optimization Tags , , , ,

    In this paper, we study the low-rank matrix optimization problem, where the penalty term is the $\ell_p~(0<p<1)$ regularization. Inspired by the good performance of half thresholding function in sparse/low-rank recovery problems, we propose a singular value half thresholding (SVHT) algorithm to solve the $\ell_p$ regularized matrix optimization problem. The main iteration in SVHT algorithm makes … Read more

    Accelerated Gradient Dynamics on Riemannian Manifolds: Faster Rate and Trajectory Convergence

  • Tejas Natu
  • Camille Castera
  • Jalal Fadili
  • Peter Ochs
    • Categories Convex Optimization, Optimization in Data Science Tags , , ,

    In order to minimize a differentiable geodesically convex function, we study a second-order dynamical system on Riemannian manifolds with an asymptotically vanishing damping term of the form \(\alpha/t\). For positive values of \(\alpha\), convergence rates for the objective values and convergence of trajectory is derived. We emphasize the crucial role of the curvature of the … Read more

    Near-optimal closed-loop method via Lyapunov damping for convex optimization

  • Camille Castera
  • Peter Ochs
    • Categories Convex Optimization, Systems governed by Differential Equations Optimization, Unconstrained Optimization Tags , , ,

    We introduce an autonomous system with closed-loop damping for first-order convex optimization. While, to this day, optimal rates of convergence are only achieved by non-autonomous methods via open-loop damping (e.g., Nesterov’s algorithm), we show that our system is the first one featuring a closed-loop damping while exhibiting a rate arbitrarily close to the optimal one. … Read more

    Distributionally robust optimization through the lens of submodularity

  • Karthik Natarajan
  • Divya Padmanabhan
  • Arjun Ramachandra
    • Categories Convex Optimization, Linear Programming, Linear, Cone and Semidefinite Programming Tags , , , ,

    Distributionally robust optimization is used to solve decision making problems under adversarial uncertainty where the distribution of the uncertainty is itself ambiguous. In this paper, we identify a class of these instances that is solvable in polynomial time by viewing it through the lens of submodularity. We show that the sharpest upper bound on the … Read more

    Addressing Hierarchical Jointly-Convex Generalized Nash Equilibrium Problems with Nonsmooth Payoffs

  • Lorenzo Lampariello
  • Simone Sagratella
  • Valerio Giuseppe Sasso
    • Categories Convex and Nonsmooth Optimization Tags , , , , ,

    We consider a Generalized Nash Equilibrium Problem whose joint feasible region is implicitly defined as the solution set of another Nash game. This structure arises e.g. in multi-portfolio selection contexts, whenever agents interact at different hierarchical levels. We consider nonsmooth terms in all players’ objectives, to promote, for example, sparsity in the solution. Under standard … Read more

    Local Convergence Analysis of an Inexact Trust-Region Method for Nonsmooth Optimization

  • Robert Baraldi
  • Drew P. Kouri
    • Categories Infinite Dimensional Optimization, Nonlinear Optimization, Nonsmooth Optimization Tags , , , , ,

    In [R. J. Baraldi and D. P. Kouri, Mathematical Programming, (2022), pp. 1–40], we introduced an inexact trust-region algorithm for minimizing the sum of a smooth nonconvex function and a nonsmooth convex function in Hilbert space—a class of problems that is ubiquitous in data science, learning, optimal control, and inverse problems. This algorithm has demonstrated … Read more

    Efficient Proximal Subproblem Solvers for a Nonsmooth Trust-Region Method

  • Robert Baraldi
  • Drew P. Kouri
    • Categories Infinite Dimensional Optimization, Nonlinear Optimization, Nonsmooth Optimization Tags , , , ,

    In [R. J. Baraldi and D. P. Kouri, Mathematical Programming, (2022), pp. 1-40], we introduced an inexact trust-region algorithm for minimizing the sum of a smooth nonconvex and nonsmooth convex function. The principle expense of this method is in computing a trial iterate that satisfies the so-called fraction of Cauchy decrease condition—a bound that ensures … Read more

    From Optimization to Control: Quasi Policy Iteration

  • Mohamad Amin Sharifi Kolarijani
  • Peyman Mohajerin Esfahani
    • Categories Convex Optimization, Dynamic Programming Tags , , , ,

    Recent control algorithms for Markov decision processes (MDPs) have been designed using an implicit analogy with well-established optimization algorithms. In this paper, we adopt the quasi-Newton method (QNM) from convex optimization to introduce a novel control algorithm coined as quasi-policy iteration (QPI). In particular, QPI is based on a novel approximation of the “Hessian” matrix … Read more

    Exact Matrix Completion via High-Rank Matrices in Sum-of-Squares Relaxations

  • Sunyoung Kim
  • Godai Azuma
  • Makoto Yamashita
    • Categories Convex Optimization, Global Optimization Theory, Semi-definite Programming Tags , , , ,

    We study exact matrix completion from partially available data with hidden connectivity patterns. Exact matrix completion was shown to be possible recently by Cosse and Demanet in 2021 with Lasserre’s relaxation using the trace of the variable matrix as the objective function with given data structured in a chain format. In this study, we introduce … Read more