A class of diagonal quasi-Newton penalty decomposition algorithms for sparse bound-constrained nonconvex optimization

  • Ahmad Mousavi
  • Morteza Kimiaei
  • Saman Babaie-Kafaki
  • Vyacheslav Kungurtsev
    • Categories Bound-constrained Optimization, Constrained Nonlinear Optimization, Quadratic Programming Tags , , ,

    This paper discusses an improved quasi-Newton penalty decomposition algorithm for the cardinality bound-constrained optimization problems whose simple bounds on the variables are assumed to be finite. Until an approximate stationary point is found, this algorithm approximates the solutions of a sequence of penalty subproblems by a two-block decomposition scheme. This scheme finds an approximate solution … Read more

    Mixed Integer Linear Programming Formulations for Robust Surgery Scheduling

  • Ankit Bansal
    • Categories (Mixed) Integer Linear Programming, Robust Optimization, Scheduling

    We introduce Mixed Integer Linear Programming (MILP) formulations for the two-stage robust surgery scheduling problem (2SRSSP). We derive these formulations by modeling the second-stage problem as a longest path problem on a layered acyclic graph and subsequently converting it into a linear program. This linear program is then dualized and integrated with the first-stage, resulting … Read more

    Stable Set Polytopes with Rank |V(G)|/3 for the Lovász-Schrijver SDP Operator

  • Yu Hin (Gary) Au
    • Categories Combinatorial Optimization, Convex Optimization, Semi-definite Programming Tags , , , ,

    We study the lift-and-project rank of the stable set polytope of graphs with respect to the Lovász–Schrijver SDP operator \( \text{LS}_+ \) applied to the fractional stable set polytope. In particular, we show that for every positive integer \( \ell \), the smallest possible graph with \( \text{LS}_+ \)-rank \( \ell \) contains \( 3\ell … Read more

    Extended Triangle Inequalities for Nonconvex Box-Constrained Quadratic Programming

  • Kurt M. Anstreicher
  • Diane Puges
    • Categories Bound-constrained Optimization, Global Optimization Theory, Quadratic Programming Tags , ,

    Let Box_n = {x in R^n : 0<= x <= e }, and let QPB_n denote the convex hull of {(1, x’)'(1, x’) : x  in Box_n}. The quadratic programming problem min{x’Q x + q’x : x in Box_n} where Q is not positive semidefinite (PSD), is equivalent to a linear optimization problem over QPB_n … Read more

    SMOP: Stochastic trust region method for multi-objective problems

  • Nataša Krejić
  • Nataša Krklec Jerinkić
  • Luka Rutešić
    • Categories Multi-Criteria Optimization, Nonlinear Optimization Tags , , , ,

    The problem considered is a multi-objective optimization problem, in which the goal is to find an optimal value of a vector function representing various criteria. The aim of this work is to develop an algorithm which utilizes the trust region framework with probabilistic model functions, able to cope with noisy problems, using inaccurate functions and … Read more

    A new constant-rank-type condition related to MFCQ and local error bounds

  • Roberto Andreani
  • Mariana da Rosa
  • Leonardo D. Secchin
    • Categories Nonlinear Optimization

    Constraint qualifications (CQs) are fundamental for understanding the geometry of feasible sets and for ensuring the validity of optimality conditions in nonlinear programming. A known idea is that constant-rank type CQs allow one to modify the description feasible set, by eliminating redundant constraints, so that the Mangasarian-Fromovitz CQ (MFCQ) holds. Traditionally, such modifications, called reductions … Read more

    Projected proximal gradient trust-region algorithm for nonsmooth optimization

  • Lindon Roberts
  • Minh N. Dao
  • Hung M. Phan
    • Categories Nonlinear Optimization, Nonsmooth Optimization Tags , , ,

    We consider trust-region methods for solving optimization problems where the objective is the sum of a smooth, nonconvex function and a nonsmooth, convex regularizer. We extend the global convergence theory of such methods to include worst-case complexity bounds in the case of unbounded model Hessian growth, and introduce a new, simple nonsmooth trust-region subproblem solver … Read more

    Smoothing l1-exact penalty method for intrinsically constrained Riemannian optimization problems

  • Ernesto G. Birgin
  • Orizon Pereira Ferreira
  • Gabriel Haeser
  • Nelson Maculan
  • Lennin Mallma Ramirez
  • Leandro Fonseca Prudente
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization

    This paper deals with the Constrained Riemannian Optimization (CRO) problem, which involves minimizing a function subject to equality and inequality constraints on Riemannian manifolds. The study aims to advance optimization theory in the Riemannian setting by presenting and analyzing a penalty-type method for solving CRO problems. The proposed approach is based on techniques that involve … Read more

    Unifying restart accelerated gradient and proximal bundle methods

  • Jiaming Liang
    • Categories Convex and Nonsmooth Optimization, Convex Optimization Tags , , , ,

    This paper presents a novel restarted version of Nesterov’s accelerated gradient method and establishes its optimal iteration-complexity for solving convex smooth composite optimization problems. The proposed restart accelerated gradient method is shown to be a specific instance of the accelerated inexact proximal point framework introduced in “An accelerated hybrid proximal extragradient method for convex optimization … Read more

    Efficient LP warmstarting for linear modifications of the constraint matrix

  • Guillaume Derval
  • Bardhyl Miftari
  • Quentin Louveaux
    • Categories Linear Programming, Robust Optimization

    We consider the problem of computing the optimal solution and objective of a linear program under linearly changing linear constraints. The problem studied is given by $\min c^t x \text{ s.t } Ax + \lambda Dx \leq b$ where $\lambda$ belongs to a set of predefined values $\Lambda$. Based on the information given by a … Read more