Optimization and Control (math.OC)

Abstract: End-stage renal disease patients face a complicated sociomedical situation and rely on various forms of infrastructure for life-sustaining treatment. Disruption of these infrastructures during disasters poses a major threat to their lives. To improve patient access to dialysis treatment, there is a need to assess the potential threat to critical care facilities from hazardous events. In this study, we propose optimization models to solve critical care system resilience problems including patient and medical resource allocation. We use human mobility data in the context of Harris County (Texas) to assess patient access to critical care facilities, dialysis centers in this study, under the simulated hazard impacts, and we propose models for patient re-allocation and temporary medical facility placement to improve critical care system resilience in an equitable manner. The results show (1) the capability of the optimization model in efficient patient re-allocation to alleviate disrupted access to dialysis facilities; (2) the importance of large facilities in maintaining the functioning of the system. The critical care system, particularly the network of dialysis centers, is heavily reliant on a few larger facilities, making it susceptible to targeted disruption. (3) The consideration of equity in the optimization model formulation reduces access loss for vulnerable populations in the simulated scenarios. (4) The proposed temporary facilities placement could improve access for the vulnerable population, thereby improving the equity of access to critical care facilities in disaster. The proposed patient re-allocation model and temporary facilities placement can serve as a data-driven and analytic-based decision support tool for public health and emergency management plans to reduce the loss of access and disrupted access to critical care facilities and would reduce the dire social costs.

Abstract: Hyperbolic polynomials is a class of real-roots polynomials that has wide range of applications in theoretical computer science. Each hyperbolic polynomial also induces a hyperbolic cone that is of particular interest in optimization due to its generality, as by choosing the polynomial properly, one can easily recover the classic optimization problems such as linear programming and semidefinite programming. In this work, we develop efficient algorithms for hyperbolic programming, the problem in each one wants to minimize a linear objective, under a system of linear constraints and the solution must be in the hyperbolic cone induced by the hyperbolic polynomial. Our algorithm is an instance of interior point method (IPM) that, instead of following the central path, it follows the central Swath, which is a generalization of central path. To implement the IPM efficiently, we utilize a relaxation of the hyperbolic program to a quadratic program, coupled with the first four moments of the hyperbolic eigenvalues that are crucial to update the optimization direction. We further show that, given an evaluation oracle of the polynomial, our algorithm only requires $O(n^2d^{2.5})$ oracle calls, where $n$ is the number of variables and $d$ is the degree of the polynomial, with extra $O((n+m)^3 d^{0.5})$ arithmetic operations, where $m$ is the number of constraints.

Abstract: In this paper, we study an algorithm for solving a class of nonconvex and nonsmooth nonseparable optimization problems. Based on proximal alternating linearized minimization (PALM), we propose a new iterative algorithm which combines two-step inertial extrapolation and Bregman distance. By constructing appropriate benefit function, with the help of Kurdyka--{\L}ojasiewicz property we establish the convergence of the whole sequence generated by proposed algorithm. We apply the algorithm to signal recovery, quadratic fractional programming problem and show the effectiveness of proposed algorithm.

Abstract: In this paper, we analyze a Hegselmann-Krause opinion formation model with attractive-lacking interaction. More precisely, we investigate the situation in which the individuals involved in an opinion formation process interact among themselves but can eventually suspend the exchange of information among each other at some times. Under quite general assumptions, we prove the exponential convergence to consensus for the Hegselmann-Krause model in presence of possible lack of interaction. We then extend the analysis to an analogous model in presence of time delays.

Abstract: Motivated by multiple emerging applications in machine learning, we consider an optimization problem in a general form where the gradient of the objective is only available through a biased stochastic oracle. We assume the bias magnitude can be controlled by a parameter, however, lower bias requires more computation/samples. For instance, for two applications on stochastic composition optimization and policy optimization for infinite-horizon Markov decision processes, we show that the bias follows a power law and exponential decay, respectively, as functions of their corresponding bias control parameters. For problems with such gradient oracles, the paper proposes two stochastic algorithms that adaptively adjust the bias control parameter throughout the iterations. We analyze the nonasymptotic performance of the proposed algorithms in the nonconvex regime and establish $\mathcal{O}(\epsilon^{-4})$ and (optimal) $\mathcal{O}(\epsilon^{-3})$ sample complexity to obtain an $\epsilon$-stationary point. Finally, we numerically evaluate the performance of the proposed algorithms over the two applications.

Abstract: In this paper, we develop the Galerkin-like method to deal with first-order integro-differential inclusions. Under compactness or monotonicity conditions, we obtain new results for the existence of solutions for this class of problems, which generalize existing results in the literature and give new insights for differential inclusions with an unbounded right-hand side. The effectiveness of the proposed approach is illustrated by providing new results for nonconvex state-dependent integro-differential sweeping processes, where the right-hand side is unbounded, and the classical theory of differential inclusions is not applicable. It is the first result of this kind. The paper ends with an application to the existence of an optimal control problem governed by an integro-differential inclusion in finite dimensions.

Abstract: Homotopy methods are attractive due to their capability of solving difficult optimization and optimal control problems. The underlying idea is to construct a homotopy, which may be considered as a continuous (zero) curve between the difficult original problem and a related, comparatively-easy one. Then, the solution of the easier one is continuously perturbed along the zero curve towards the desired solution of the difficult problem. We propose a methodology for the systematic construction of such zero curves for discrete-time optimal control problems drawing upon the theory of globally-convergent homotopies for nonlinear programs. This framework ensures that for almost every easy solution there exists a suitable homotopy path that is, in addition, numerically tractable. We demonstrate the results by solving a difficult path planning problem.

Abstract: We consider the non-convex optimization problem associated with the decomposition of a real symmetric tensor into a sum of rank one terms. Use is made of the rich symmetry structure to derive Puiseux series representations of families of critical points, and so obtain precise analytic estimates on the critical values and the Hessian spectrum. The sharp results make possible an analytic characterization of various geometric obstructions to local optimization methods, revealing in particular a complex array of saddles and local minima which differ by their symmetry, structure and analytic properties. A desirable phenomenon, occurring for all critical points considered, concerns the index of a point, i.e., the number of negative Hessian eigenvalues, increasing with the value of the objective function. Lastly, a Newton polytope argument is used to give a complete enumeration of all critical points of fixed symmetry, and it is shown that contrarily to the set of global minima which remains invariant under different choices of tensor norms, certain families of non-global minima emerge, others disappear.