Discretization methods are commonly used for solving standard semi-infinite optimization (SIP) problems. The transfer of these methods to the case of general semi-infinite optimization (GSIP) problems is difficult due to the $x$-dependence of the infinite index set. On the other hand, under suitable conditions, a GSIP problem can be transformed into a SIP problem. In … Read more
The dual form of convex quadratic semidefinite programming (CQSDP) problem, with nonnegative constraints, is a 4-block separable convex optimization problem. It is known that,the directly extended 4-block alternating direction method of multipliers (ADMM4d) is very efficient to solve the dual, but its convergence is not guaranteed. In this paper, we reformulate the dual as a … Read more
The analysis of infeasibility plays an important role in solving satisfiability problems (SAT) and mixed integer programs (MIPs). In mixed integer programming, this procedure is called conflict analysis. So far, modern MIP solvers use conflict analysis only for propagation and improving the dual bound, i.e., fathoming nodes that cannot contain feasible solutions. In this short … Read more
We consider a bound for the maximum-entropy sampling problem (MESP) that is based on solving a max-det problem over a relaxation of the Boolean Quadric Polytope (BQP). This approach to MESP was first suggested by Christoph Helmberg over 15 years ago, but has apparently never been further elaborated or computationally investigated. We find that the … Read more
We describe a long-step path-following algorithm for a class of symmetric programming problems with nonlinear convex objective functions. The complexity estimates similar to the case of a linear-quadratic objective function are established. The results of numerical experiments for the class of optimization problems involving quantum entropy are presented. CitationPreprint, University of Notre Dame, December 2017ArticleDownload … Read more
We study a deterministic technique to check the existence of feasible points for mixed-integer nonlinear optimization problems which satisfy a structural requirement that we call granularity. We show that solving certain purely continuous optimization problems and rounding their optimal points leads to feasible points of the original mixed-integer problem, as long as the latter is … Read more
In this paper we consider uncertain second-order cone (SOC) and semidefinite programming (SDP) constraints with polyhedral uncertainty, which are in general computationally intractable. We propose to reformulate an uncertain SOC or SDP constraint as a set of adjustable robust linear optimization constraints with an ellipsoidal or semidefinite representable uncertainty set, respectively. The resulting adjustable problem … Read more
The Traveling Salesman Problem with Pickup and Delivery (TSPPD) describes the problem of finding a minimum cost path in which pickups precede their associated deliveries. The TSPPD is particularly important in the growing field of Dynamic Pickup and Delivery Problems (DPDP). These include the many-to-many Dial-A-Ride Problems (DARP) of companies such as Uber and Lyft, … Read more
We generalize the classic convergence rate theory for subgradient methods to apply to non-Lipschitz functions via a new measure of steepness. For the deterministic projected subgradient method, we derive a global $O(1/\sqrt{T})$ convergence rate for any function with at most exponential growth. Our approach implies generalizations of the standard convergence rates for gradient descent on … Read more
Proximal gradient methods have been found to be highly effective for solving minimization problems with non-negative constraints or L1-regularization. Under suitable nondegeneracy conditions, it is known that these algorithms identify the optimal sparsity pattern for these types of problems in a finite number of iterations. However, it is not known how many iterations this may … Read more