Optimization and Control (math.OC)

Abstract: We discuss, on finite and infinite dimensional normed vector spaces, some versions of Radstr\"{o}m cancellation law (or lemma) that are suited for applications to set optimization problems. In this sense, we call our results "conic" variants of the celebrated result of Radstr\"{o}m, since they involve the presence of an ordering cone on the underlying space. Several adaptations to this context of some topological properties of sets are studied and some applications to subdifferential calculus associated to set-valued maps and to necessary optimality conditions for constrained set optimization problems are given. Finally, a stability problem is considered.

Abstract: This paper is devoted to prove that any domain satisfying a $(\delta_0,r_0)-$capacity condition of first order is automatically $(m,p)-$stable for all $m\geqslant 1$ and $p\geqslant 1$, and for any dimension $N\geqslant 1$. In particular, this includes regular enough domains such as $\mathscr{C}^1-$domains, Lipchitz domains, Reifenberg flat domains, but is weak enough to also includes cusp points. Our result extends some of the results of Hayouni and Pierre valid only for $N=2,3$, and extends also the results of Bucur and Zolesio for higher order operators, with a different and simpler proof.

Abstract: This paper focuses on the stability of solutions for a velocity-tracking problem associated with the two-dimensional Navier-Stokes equations. The considered optimal control problem does not possess any regularizer in the cost, and hence bang-bang solutions can be expected. We investigate perturbations that account for uncertainty in the tracking data and the initial condition of the state, and analyze the convergence rate of solutions when the original problem is regularized by the Tikhonov term. The stability analysis relies on the H\"older subregularity of the optimality mapping, which stems from the necessary conditions of the problem.

Abstract: This paper establishes a closed-form expression for projecting onto a capped rotated second-order cone. This special object is a convex set that arises as a part of the feasible region of the perspective relaxation of mixed-integer nonlinear programs (MINLP) with binary indicator variables. The rapid computation of the projection onto this convex set enables the development of effective methods for solving the continuous relaxation of MINLPs whose feasible region may involve a Cartesian product of a large number of such sets. As a proof of concept for the applicability of our projection method, we develop a projected gradient method and specialize a general form of FISTA to use our projection technique in order to effectively solve the continuous perspective relaxation of a sparse regression problem with $L_0$ and $L_2$ penalties. We also generalize the basic sparse regression formulation and solution method to support group sparsity. In experiments we first demonstrate that the projection problem is solved faster and more accurately with our closed-form than with an interior-point solver, and also when solving sparse regression problems our methods that applies our projection formula can outperform a state-of-the-art interior point solver while nearly matching its solution accuracy.

Abstract: This paper develops a unified distributed method for solving two classes of constrained networked optimization problems, i.e., optimal consensus problem and resource allocation problem with non-identical set constraints. We first transform these two constrained networked optimization problems into a unified saddle-point problem framework with set constraints. Subsequently, two projection-based primal-dual algorithms via Optimistic Gradient Descent Ascent (OGDA) method and Extra-gradient (EG) method are developed for solving constrained saddle-point problems. It is shown that the developed algorithms achieve exact convergence to a saddle point with an ergodic convergence rate $O(1/k)$ for general convex-concave functions. Based on the proposed primal-dual algorithms via saddle-point dynamics, we develop unified distributed algorithm design and convergence analysis for these two networked optimization problems. Finally, two numerical examples are presented to demonstrate the theoretical results.

Abstract: The current cut selection algorithm used in mixed-integer programming solvers has remained largely unchanged since its creation. In this paper, we propose a set of new cut scoring measures, cut filtering techniques, and stopping criteria, extending the current state-of-the-art algorithm and obtaining a 4\% performance improvement for SCIP over the MIPLIB 2017 benchmark set.

Abstract: We give properties of strict pseudocontractions and demicontractions defined on a Hilbert space, which constitute wide classes of operators that arise in iterative methods for solving fixed point problems. In particular, we give necessary and sufficient conditions under which a convex combination and composition of strict pseudocontractions as well as demicontractions that share a common fixed point is again a strict pseudocontraction or a demicontraction, respectively. Moreover, we introduce a generalized relaxation of composition of demicontraction and give its properties. We apply these properties to prove the weak convergence of a class of algorithms that is wider than the Douglas-Rachford algorithm and projected Landweber algorithms. We have also presented two numerical examples, where we compare the behavior of the presented methods with the Douglas-Rachford method.

Abstract: We propose a method for learning decision-makers' behavior in routing problems using Inverse Optimization (IO). The IO framework falls into the supervised learning category and builds on the premise that the target behavior is an optimizer of an unknown cost function. This cost function is to be learned through historical data, and in the context of routing problems, can be interpreted as the routing preferences of the decision-makers. In this view, the main contributions of this study are to propose an IO methodology with a hypothesis function, loss function, and stochastic first-order algorithm tailored to routing problems. We further test our IO approach in the Amazon Last Mile Routing Research Challenge, where the goal is to learn models that replicate the routing preferences of human drivers, using thousands of real-world routing examples. Our final IO-learned routing model achieves a score that ranks 2nd compared with the 48 models that qualified for the final round of the challenge. Our results showcase the flexibility and real-world potential of the proposed IO methodology to learn from decision-makers' decisions in routing problems.