Search

We have developed novel algorithms for optimizing nonsmooth, nonconvex functions in which the nonsmoothness is caused by nonsmooth operators presented in the analytical form of the objective. The algorithms are based on encoding the active branch of each nonsmooth operator such that the active smooth component function and its code can be extracted at any given point, and the transition of the solution from one smooth piece to another can be detected via tracking the change of active branches of all the operators. This mechanism enables the possibility of collecting the information about the sequence of active component functions encountered in the previous iterations (i.e., the component transition information), and using it in the construction of a current local model or identification of a descent direction in a very economic and effective manner. Based on this novel idea, we have developed a trust-region method and a joint gradient descent method driven by the component information for optimizing the encodable piecewise-smooth, nonconvex functions. It has further been shown that the joint gradient descent method using a technique called proactive component function accessing can achieve a linear rate of convergence if a so-called multi-component Polyak-Lojasiewicz inequality and some other regularity conditions hold at a neighborhood of a local minimizer.

We investigate an empirical quantile estimation approach to solve chance-constrained nonlinear optimization problems. Our approach is based on the reformulation of the chance constraint as an equivalent quantile constraint to provide stronger signals on the gradient. In this approach, the value of the quantile function is estimated empirically from samples drawn from the random parameters, and the gradient of the quantile function is estimated via a finite-difference approximation on top of the quantile-function-value estimation. We establish a convergence theory of this approach within the framework of an augmented Lagrangian method for solving general nonlinear constrained optimization problems. The foundation of the convergence analysis is a concentration property of the empirical quantile process, and the analysis is divided based on whether or not the quantile function is differentiable. In contrast to the sampling-and-smoothing approach used in the literature, the method developed in this paper does not involve any smoothing function and hence the quantile-function gradient approximation is easier to implement and there are less accuracy-control parameters to tune. We demonstrate the effectiveness of this approach and compare it with a smoothing method for the quantile-gradient estimation. Numerical investigation shows that the two approaches are competitive for certain problem instances.

We consider the coordinated vehicle platooning problem over a road network with time constraints while the routes of vehicles are given. The problem is to coordinate the departure time of each vehicle to enable platoon formation hence maximizing the total fuel saving. All problem instances can be divided into two categories: the tree instances and the cycle-containing instances based on the graph formed by the routes of all vehicles in the system using a preprocessing algorithm. For tree instances, relative time windows can be defined for all vehicles to which an efficient time discretization can be applied. This property leads to a tight mixed-integer linear program reformulation as compared to the continuous-time formulation involving big-M coefficients proposed in our previous work. This formulation approach has been extended to cycle-containing instances, and the validness of the extension is characterized by the pattern of lattice groups. As an independent interest, two approximation algorithms have been derived with provable competitive ratios under certain regularity conditions for tree instances, which is for the first time on this discrete optimization problem. It is demonstrated by systematic numerical experiments that the reformulation outperforms the continuous-time formulation, and the effectiveness of the approximation algorithms is tested in additional numerical experiments., Comment: 69 pages, 12 figures

The polytope from a service center location problem with a special location-dependent demand has been investigated in this paper. The location-dependent demand is defined based on a maximum-attraction-principle assumption. Along this direction, the intersection polytope of the capacity constraints and demand constraints yields a novel polyhedral structure. The structure is investigated in this paper via a family of valid and facet-defining inequalities that can reflect the change of demand fulfillment in a neighborhood., Comment: arXiv admin note: substantial text overlap with arXiv:2011.12514

We present a finitely convergent cutting-plane algorithm for solving a general mixed-integer convex programs given an oracle for solving general convex programs. This method is extended to solve a family of two-stage mixed-integer convex programs using cutting planes, with applications to solving distributionally-robust two-stage stochastic mixed-integer convex programs. Since algorithms purely using cutting planes are not very practical for implementation, we combined the cut generation with a branch-and-union scheme to develop a more practical algorithm. Analysis is also given for the case where convex programming oracle provides an $\epsilon-$optimal solution. Computational results on generated test problems show the practicality of our algorithm. Specifically, results show that addition of cuts speed up solution times by nearly 10-fold on the largest test problems that are solved., Comment: 50 pages, 2 tables and 1 figure

We establish and analyze a service center location model with a simple but novel decision-dependent demand induced from a maximum attraction principle. The model formulations are investigated in the distributionally-robust optimization framework. A statistical model that is based on the maximum attraction principle for estimating customer demand and utility gain from service is established and analyzed. The numerical experiments show that the model admits high computational efficiency in solving mid-size instances., Comment: 27 pages, 3 figures

Platooning of vehicles is a promising approach for reducing fuel consumption, increasing vehicle safety, and using road space more efficiently. We consider the important but difficult problem of assigning optimal routes and departure schedules to a collection of vehicles. We propose an iterative route-then-schedule heuristic for centralized planning that quickly converges to high-quality solutions. We also propose and analyze a collection of valid inequalities for the individual problems of assigning vehicles to routes and scheduling the times that vehicles traverse their routes. These inequalities are shown to reduce the computational time or optimality gap of solving the routing and scheduling problem instances. Our approach uses the valid inequalities in both the routing and scheduling portions of each iteration; numerical experiments highlight the speed of the approach for routing vehicles on a real-world road network., Comment: 61 pages, 7 figures

This paper presents a stochastic optimization model for allocating and sharing a critical resource in the case of a pandemic. The demand for different entities peaks at different times, and an initial inventory from a central agency is to be allocated. The entities (states) may share the critical resource with a different state under a risk-averse condition. The model is applied to study the allocation of ventilator inventory in the COVID-19 pandemic by the Federal Emergency Management Agency of the US Department of Homeland Security (FEMA) to different states in the US. Findings suggest that if less than 60% of the ventilator inventory is available for non-COVID-19 patients, FEMA's stockpile of 20,000 ventilators (as of 03/23/2020) would be nearly adequate to meet the projected needs. However, when more than 75% of the available ventilator inventory must be reserved for non-COVID-19 patients, various degrees of shortfall are expected. In an extreme case, where the demand is assumed to be concentrated in the top-most quartile of the forecast confidence interval, the total shortfall over the planning horizon (till 05/31/20) is about 28,500 ventilator days, with a peak shortfall of 2,700 ventilators on 04/12/20. The results also suggest that in the worse-than-average to severe demand scenario cases, NY requires between 7,600-9,200 additional ventilators for COVID-19 patients during its peak demand. However, between 400 to 2,000 of these ventilators can be given to a different state after the peak demand in NY has subsided.

We investigate robust optimization problems defined for maximizing convex functions. For finite uncertainty set, we develop a geometric branch-and-bound algorithmic approach to solve this problem. The geometric branch-and-bound algorithm performs sequential piecewise-linear approximations of the convex objective, and solves linear programs to determine lower and upper bounds of nodes specified by the active linear pieces. Finite convergence of the algorithm to an $\epsilon-$optimal solution is proved. Numerical results are used to discuss the performance of the developed algorithm. The algorithm developed in this paper can be used as an oracle in the cutting surface method for solving robust optimization problems with compact ambiguity sets., Comment: 23 pages, 3 figures, 2 tables

We develop a decomposition algorithm for distributionally-robust two-stage stochastic mixed-integer convex cone programs, and its important special case of distributionally-robust two-stage stochastic mixed-integer second order cone programs. This generalizes the algorithm proposed by Sen and Sherali~[Mathematical Programming 106(2): 203-223, 2006]. We show that the proposed algorithm is finitely convergent if the second-stage problems are solved to optimality at incumbent first stage solutions, and solution to an optimization problem to identify worst-case probability distribution is available. The second stage problems can be solved using a branch-and-cut algorithm. The decomposition algorithm is illustrated with an example. Computational results on a stochastic programming generalization of a facility location problem show significant solution time improvements from the proposed approach. Solutions for many models that are intractable for an extensive form formulation become possible. Computational results suggest that solution time requirement does not increase significantly when considering distributional robust counterparts to the stochastic programming models., Comment: 28 pages

We study a service center location problem with ambiguous utility gains upon receiving service. The model is motivated by the problem of deciding medical clinic/service centers, possibly in rural communities, where residents need to visit the clinics to receive health services. A resident gains his utility based on travel distance, waiting time, and service features of the facility that depend on the clinic location. The elicited location-dependent utilities are assumed to be ambiguously described by an expected value and variance constraint. We show that despite a non-convex nonlinearity, given by a constraint specified by a maximum of two second-order conic functions, the model admits a mixed 0-1 second-order cone (MISOCP) formulation. We study the non-convex substructure of the problem, and present methods for developing its strengthened formulations by using valid tangent inequalities. Computational study shows the effectiveness of solving the strengthened formulations. Examples are used to illustrate the importance of including decision dependent ambiguity. An illustrative example to identify locations for Covid-19 testing and vaccination is used to further illustrate the model and its properties., Comment: 39 pages

We study decision dependent distributionally robust optimization models, where the ambiguity sets of probability distributions can depend on the decision variables. These models arise in situations with endogenous uncertainty. The developed framework includes two-stage decision dependent distributionally robust stochastic programming as a special case. Decision dependent generalizations of five types of ambiguity sets are considered. These sets are based on bounds on moments, Wasserstein metric, $\phi$-divergence and Kolmogorov-Smirnov test. For the finite support case, we use linear, conic or Lagrangian duality to give reformulations of the models with a finite number of constraints. These reformulations allow solutions of such problems using global optimization techniques. Certain reformulations give rise to non-convex semi-infinite programs. Techniques from global optimization and semi-infinite programming can be used to solve these reformulations.

Estimation of the $\phi$-divergence between two unknown probability distributions using empirical data is a fundamental problem in information theory and statistical learning. We consider a multi-variate generalization of the data dependent partitioning method for estimating divergence between the two unknown distributions. Under the assumption that the distribution satisfies a power law of decay, we provide a convergence rate result for this method on the number of samples and hyper-rectangles required to ensure the estimation error is bounded by a given level with a given probability., Comment: 15 pages

We study distributionally robust optimization (DRO) problems where the ambiguity set is defined using the Wasserstein metric. We show that this class of DRO problems can be reformulated as semi-infinite programs. We give an exchange method to solve the reformulated problem for the general nonlinear model, and a central cutting-surface method for the convex case, assuming that we have a separation oracle. We used a distributionally robust generalization of the logistic regression model to test our algorithm. Numerical experiments on the distributionally robust logistic regression models show that the number of oracle calls are typically 20 ? 50 to achieve 5-digit precision. The solution found by the model is generally better in its ability to predict with a smaller standard error., Comment: 25 pages