Convex and Nonsmooth Optimization

Strong convergence, perturbation resilience and superiorization of Generalized Modular String-Averaging with infinitely many input operators

  • Kay Barshad
  • Yair Censor
    • Categories Constrained Nonlinear Optimization, Convex Optimization Tags , , , , , , , , ,

    We study the strong convergence and bounded perturbation resilience of iterative algorithms based on the Generalized Modular String-Averaging (GMSA) procedure for infinite sequences of input operators under a general admissible control. These methods address a variety of feasibility-seeking problems in real Hilbert spaces, including the common fixed point problem and the convex feasibility problem. In … Read more

    On the Complexity of Subgradient Methods for Trilevel Hierarchical Generalized Variational Inequalities

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

    We study generalized variational inequalities with a three-level hierarchical structure. This setting extends nested GVI models beyond the bilevel case, for which $\mathcal{O}(\delta^{-4})$ complexity bounds are known for any prescribed positive tolerance $\delta$, to a fully three-level hierarchical structure. We analyze a projected averaged subgradient method combined with a Tikhonov-like regularization scheme. Under compactness, maximal … Read more

    A Modified Projected Gradient Algorithm for Solving Quasiconvex Programming with Applications

  • Pham Thi Hoai
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Nonlinear Optimization Tags , , , ,

    In this manuscript, we introduce a novel projected gradient algorithm for solving quasiconvex optimization problems over closed convex sets. The key innovation of our new algorithm is an adaptive, parameter-free stepsize rule that requires no line search and avoids estimating constants, such as Lipschitz modulus. Unlike recent self-adaptive approach given in [17] which typically produce … Read more

    Copositive and completely positive cones over symmetric cones of rank at least 5

  • Mitsuhiro Nishijima
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    We study copositive and completely positive cones over symmetric cones of rank at least $5$, with particular emphasis on whether these cones are spectrahedral shadows and on the behavior of a sum-of-squares inner-approximation hierarchy. We examine to what extent known results for nonnegative orthants of dimension at least $5$ carry over to general symmetric cones … Read more

    Lower Bounds for Linear Minimization Oracle Methods Optimizing over Strongly Convex Sets

  • Benjamin Grimmer
  • Ning Liu
    • Categories Convex Optimization Tags , , ,

    We consider the oracle complexity of constrained convex optimization given access to a Linear Minimization Oracle (LMO) for the constraint set and a gradient oracle for the $L$-smooth, strongly convex objective. This model includes Frank-Wolfe methods and their many variants. Over the problem class of strongly convex constraint sets $S$, our main result proves that … Read more

    Improved Analysis of Restarted Accelerated Gradient and Augmented Lagrangian Methods via Inexact Proximal Point Frameworks

  • Matthew X. Burns
  • Jiaming Liang
    • Categories Constrained Nonlinear Optimization, Convex and Nonsmooth Optimization, Convex Optimization Tags , , , ,

    This paper studies a class of double-loop (inner-outer) algorithms for convex composite optimization. For unconstrained problems, we develop a restarted accelerated composite gradient method that attains the optimal first-order complexity in both the convex and strongly convex settings. For linearly constrained problems, we introduce inexact augmented Lagrangian methods, including a basic method and an outer-accelerated … Read more

    Convex analysis for composite functions without K-convexity

  • Juan Pablo Vielma
    • Categories Convex Optimization, Generalized Convexity/Monoticity

    Composite functions have been studied for over 40 years and appear in a wide range of optimization problems. Convex analysis of these functions focuses on (i) conditions for convexity of the function based on properties of its components, (ii) formulas for the convex conjugate of the function based on those of its components and (iii) … Read more

    Convex duality contracts for production-grade mathematical optimization

  • Juan Pablo Vielma
  • Ross Anderson
  • Joey Huchette
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming, Modeling Languages and Systems

    Deploying mathematical optimization in autonomous production systems requires precise contracts for objects returned by an optimization solver. Unfortunately, conventions on dual solution and infeasibility certificates (rays) vary widely across solvers and classes of problems. This paper presents the theoretical framework used by MathOpt (a domain-specific language developed and used at Google) to unify these notions. … Read more

    Revisiting Superlinear Convergence of Proximal Newton-Like Methods to Degenerate Solutions

  • Ching-pei Lee
  • Stephen Wright
    • Categories Nonsmooth Optimization Tags , , , , ,

    We describe inexact proximal Newton-like methods for solving degenerate regularized optimization problems and for the broader problem of finding a zero of a generalized equation that is the sum of a continuous map and a maximal monotone operator. Superlinear convergence for both the distance to the solution set and a certain measure of first-order optimality … Read more

    Asymptotically tight Lagrangian dual of smooth nonconvex problems via improved error bound of Shapley-Folkman Lemma

  • Jingye Xu
    • Categories Convex Optimization, Nonlinear Optimization Tags , ,

    In convex geometry, the Shapley–Folkman Lemma asserts that the nonconvexity of a Minkowski sum of $n$-dimensional bounded nonconvex sets does not accumulate once the number of summands exceeds the dimension $n$, and thus the sum becomes approximately convex. Originally published by Starr in the context of quasi-equilibrium in nonconvex market models in economics, the lemma … Read more