On the Resolution of Ties in Fair Convex Allocation Problems

  • Bismark Singh
    • Categories Convex and Nonsmooth Optimization, Convex Optimization Tags , , , ,

    We study the emergence of indistinguishable, but structurally distinct, allocation outcomes in convex resource allocation models. Such outcomes occur when different users receive proportionally identical allocations despite differences in initial conditions, eligibility sets, or priority weights. We formalize this behavior and analyze the structural conditions under which it arises, with a focus on fairness-oriented objectives. … Read more

    Recoverable Robust Cardinality Constrained Maximization with Commitment of a Submodular Function

  • Sabine Münch
  • Sven de Vries
    • Categories Approximation Algorithms, Combinatorial Optimization Tags , , ,

    We consider a game-theoretic variant of maximizing a monotone increasing, submodular function under a cardinality constraint. Initially, a solution to this classical problem is determined. Subsequently, a predetermined number of elements from the ground set, not necessarily contained in the initial solution, are deleted, potentially reducing the solution’s cardinality. If any deleted elements were part … Read more

    Pareto-optimal trees and Pareto forest: a bi-objective optimization model for binary classification

  • Marianna De Santis
  • Daniele Patria
  • Justo Puerto
    • Categories Data Science Applications, Multi-Criteria Optimization, Optimization in Data Science Tags , ,

    As inherently transparent models, classification trees play a central role in interpretable machine learning by providing easily traceable decision paths that allow users to understand how input features contribute to specific predictions. In this work, we introduce a new class of interpretable binary classification models, named Pareto-optimal trees, which aim at combining the complementary strengths … Read more

    Primal-dual global convergence of an augmented Lagrangian method under the error bound condition

  • Roberto Andreani
  • Gabriel Haeser
  • Renan W. Prado
  • Leonardo D. Secchin
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , ,

    This work investigates global convergence properties of a safeguarded augmented Lagrangian method applied to nonlinear programming problems, with an emphasis on the role of constraint qualifications in ensuring boundedness of the Lagrange multiplier estimates, also known as dual sequences. When functions with locally Lipschitz continuous derivatives define the constraint set, we prove that the Error … Read more

    Second order directional derivative of optimal solution function in parametric programming problem

  • Bhuvnesh Khatana
    • Categories Bilevel Optimization, Complementarity and Variational Inequalities, Nonsmooth Optimization

    In this paper, the second-order directional derivative of the optimal value function and the optimal solution function are obtained for a strongly stable parametric problem with non-unique Lagrange multipliers. Some properties of the Lagrange multipliers are proved. It is justified that the second-order directional derivative of the optimal solution function for the parametric problem can … Read more

    A Primal Approach to Facial Reduction for SDP Relaxations of Combinatorial Optimization Problems

  • Hao Hu
    • Categories (Mixed) Integer Linear Programming, Convex Optimization

    We propose a novel facial reduction algorithm tailored to semidefinite programming relaxations of combinatorial optimization problems with quadratic objective functions. Our method leverages the specific structure of these relaxations, particularly the availability of feasible solutions that can often be generated efficiently in practice. By incorporating such solutions into the facial reduction process, we substantially simplify … Read more

    On the Convergence and Complexity of Proximal Gradient and Accelerated Proximal Gradient Methods under Adaptive Gradient Estimation

  • Raghu Bollapragada
  • Shagun Gupta
    • Categories Nonlinear Optimization, Optimization in Data Science, Stochastic Programming Tags , , , ,

    In this paper, we propose a proximal gradient method and an accelerated proximal gradient method for solving composite optimization problems, where the objective function is the sum of a smooth and a convex, possibly nonsmooth, function. We consider settings where the smooth component is either a finite-sum function or an expectation of a stochastic function, … Read more

    Faster stochastic cubic regularized Newton methods with momentum

  • Yiming Yang
    • Categories Nonlinear Optimization, Optimization in Data Science, Unconstrained Optimization Tags , , ,

    Cubic regularized Newton (CRN) methods have attracted significant research interest because they offer stronger solution guarantees and lower iteration complexity. With the rise of the big-data era, there is growing interest in developing stochastic cubic regularized Newton (SCRN) methods that do not require exact gradient and Hessian evaluations. In this paper, we propose faster SCRN … Read more

    Sub-sampled Trust-Region Methods with Deterministic Worst-Case Complexity Guarantees

  • Max L. N. Gonçalves
  • Geovani Nunes Grapiglia
    • Categories Unconstrained Optimization Tags , , ,

    In this paper, we develop and analyze sub-sampled trust-region methods for solving finite-sum optimization problems. These methods employ subsampling strategies to approximate the gradient and Hessian of the objective function, significantly reducing the overall computational cost. We propose a novel adaptive procedure for deterministically adjusting the sample size used for gradient (or gradient and Hessian) … Read more

    The complete edge relaxation for binary polynomial optimization

  • Alberto Del Pia
  • Aida Khajavirad
    • Categories 0-1 Programming, Global Optimization, Integer Programming Tags , , , , ,

    We consider the multilinear polytope defined as the convex hull of the feasible region of a linearized binary polynomial optimization problem. We define a relaxation in an extended space for this polytope, which we refer to as the complete edge relaxation. The complete edge relaxation is stronger than several well-known relaxations of the multilinear polytope, … Read more