-
作者：Liang, Wei; Tang, Shaojie; Zhang, Zhao
作者单位：Zhejiang Normal University
摘要：In this paper, we introduce a polynomial-time 2-approximation algorithm for the Unrooted Prize-Collecting Forest with K Components (URPCFK\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hbox {URPCF}_K$$\end{document}) problem. Given a graph G and an integer K, URPCFK\documentclass[12pt]{minimal} \usepackage{amsmat...
-
作者：Andreani, Roberto; Haeser, Gabriel; Mito, Leonardo M.; Ramirez, Hector
作者单位：Universidade Estadual de Campinas; Universidade de Sao Paulo; Universidad de Chile; Universidad de Chile
摘要：In a previous paper [Andreani et al, Math. Prog. 202, p. 473-514, 2023] we introduced a constant rank constraint qualification for nonlinear semidefinite and second-order cone programming by considering all faces of the underlying cone. This condition is independent of Robinson's condition and it implies a strong second-order necessary optimality condition which depends on a single Lagrange multiplier instead of the full set of Lagrange multipliers. In this paper we expand on this result in se...
-
作者：Bhathena, Aaresh; Fattahi, Salar; Gomez, Andres; Kucukyavuz, Simge
作者单位：University of Michigan System; University of Michigan; University of Southern California; Northwestern University
摘要：This paper investigates convex quadratic optimization problems involving n indicator variables, each associated with a continuous variable, particularly focusing on scenarios where the matrix Q defining the quadratic term is positive definite and its sparsity pattern corresponds to the adjacency matrix of a tree graph. We introduce a graph-based dynamic programming algorithm that solves this problem in time and memory complexity of O(n2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepa...
-
作者：Andrews, Roland; Carpentier, Justin; Taylor, Adrien
作者单位：Inria; Universite PSL; Ecole Normale Superieure (ENS); Communaute Universite Grenoble Alpes; Centre National de la Recherche Scientifique (CNRS); Universite Grenoble Alpes (UGA); Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble
摘要：This work investigates the convergence behavior of augmented Lagrangian methods (ALMs) when applied to convex optimization problems that may be infeasible. ALMs are a popular class of algorithms for solving constrained optimization problems. We demonstrate that, under mild assumptions, the sequences of iterates generated by ALMs converge to solutions of the closest feasible problem. We establish progressively stronger convergence results, ranging from basic sequence convergence to more precise...
-
作者：Curtis, Frank E.; Jiang, Xin; Wang, Qi
作者单位：Lehigh University
摘要：An interior-point algorithm framework is proposed, analyzed, and tested for solving nonlinearly constrained continuous optimization problems. The main setting of interest is when the objective and inequality constraint functions may be nonlinear and/or nonconvex, and when constraint values and derivatives are tractable to compute, but objective function values and derivatives can only be estimated. The algorithm is intended primarily for a setting that is similar for stochastic-gradient method...
-
作者：Chen, Liang; Chen, Ruoning; Sun, Defeng; Zhang, Liping
作者单位：Hunan University; Tsinghua University; Hong Kong Polytechnic University
摘要：In this paper, we study the Aubin property of the Karush-Kuhn-Tucker solution mapping for the nonlinear semidefinite programming (NLSDP) problem at a locally optimal solution. In the literature, it is known that the Aubin property implies the constraint nondegeneracy by Fusek (SIAM J. Optim. 23:1041-1061, 2013) and the second-order sufficient condition by Ding et al. (SIAM J. Optim. 27:67-90, 2017). Based on the Mordukhovich criterion, here we further prove that the strong second-order suffici...
-
作者：Ma, Wentao; Chen, Zhiping; Xu, Huifu
作者单位：Xi'an Jiaotong University; Chinese University of Hong Kong
摘要：Inspired by Shapiro et al. [], we consider a stochastic optimal control (SOC) and Markov decision process (MDP) under simultaneous epistemic and aleatoric uncertainties using Bayesian composite risk (BCR) measures. The proposed BCR-SOC/MDP model evaluates the risk of stagewise cost via a two-layer framework: the inner risk measure tackles aleatoric uncertainty conditional on a latent environment parameter, while the outer risk measure deals with the epistemic uncertainty of the inner risk unde...
-
作者：Traub, Vera; Koch, Laura Vargas; Zenklusen, Rico
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; RWTH Aachen University; Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：The single-source unsplittable flow (SSUF) problem asks to send flow from a common source to terminals with unrelated demands, each terminal being served through a single path. The classical SSUF objective is to minimize the violation of some given arc capacities. A seminal result of Dinitz, Garg, and Goemans showed that, whenever a fractional flow exists respecting the capacities, then there is an unsplittable one violating the capacities by at most the maximum demand. Goemans conjectured a n...
-
作者：Der Hulst, Rolf van; Walter, Matthias
作者单位：University of Twente
摘要：Implied-integer detection is a well-known presolving technique that is used by many Mixed-Integer Linear Programming solvers. Informally, a variable is said to be implied integer if its integrality is enforced implicitly by integrality of other variables and the constraints of a problem. In this case, algorithms used in MILP software can choose whether they treat it as an integer or continuous variable. In this work we formalize the definition of implied integrality by taking a polyhedral pers...
-
作者：Homem-de-Mello, Tito; Valencia, Juan; Lagos, Felipe; Lagos, Guido
作者单位：Universidad Adolfo Ibanez; Universidad Adolfo Ibanez; Universidad Adolfo Ibanez
摘要：We study a class of two-stage stochastic programs, namely, those with fixed recourse matrix and fixed costs, and linear second stage. We show that, under mild assumptions, the problem can be solved with just one scenario, which we call an optimal scenario. Such a scenario does not have to be unique and may fall outside the support of the underlying distribution. Although finding an optimal scenario in general might be hard, we show that the result can be particularly useful in the case of stoc...
