Optimization and Control (math.OC)

Abstract: The robust multi-product pricing problem is to determine the prices of a collection of products so as to maximize the worst-case revenue, where the worst case is taken over an uncertainty set of demand models that the firm expects could be realized in practice. A tacit assumption in this approach is that the pricing decision is a deterministic decision: the prices of the products are fixed and do not vary. In this paper, we consider a randomized approach to robust pricing, where a decision maker specifies a distribution over potential price vectors so as to maximize its worst-case revenue over an uncertainty set of demand models. We formally define this problem -- the randomized robust price optimization problem -- and analyze when a randomized price scheme performs as well as a deterministic price vector, and identify cases in which it can yield a benefit. We also propose two solution methods for obtaining an optimal randomization scheme over a discrete set of candidate price vectors based on constraint generation and double column generation, respectively, and show how these methods are applicable for common demand models, such as the linear, semi-log and log-log demand models. We numerically compare the randomized approach against the deterministic approach on a variety of synthetic and real problem instances; on synthetic instances, we show that the improvement in worst-case revenue can be as much as 1300%, while on real data instances derived from a grocery retail scanner dataset, the improvement can be as high as 92%.

Abstract: For modern gradient-based optimization, a developmental landmark is Nesterov's accelerated gradient descent method, which is proposed in [Nesterov, 1983], so shorten as Nesterov-1983. Afterward, one of the important progresses is its proximal generalization, named the fast iterative shrinkage-thresholding algorithm (FISTA), which is widely used in image science and engineering. However, it is unknown whether both Nesterov-1983 and FISTA converge linearly on the strongly convex function, which has been listed as the open problem in the comprehensive review [Chambolle and Pock, 2016, Appendix B]. In this paper, we answer this question by the use of the high-resolution differential equation framework. Along with the phase-space representation previously adopted, the key difference here in constructing the Lyapunov function is that the coefficient of the kinetic energy varies with the iteration. Furthermore, we point out that the linear convergence of both the two algorithms above has no dependence on the parameter $r$ on the strongly convex function. Meanwhile, it is also obtained that the proximal subgradient norm converges linearly.

Abstract: We study the asymptotic behaviour of the well-known Dykstra's algorithm through the lens of proof-theoretical techniques. We provide an elementary proof for the convergence of Dykstra's algorithm in which the standard argument is stripped to its central features and where the original compactness principles are circumvented, additionally providing highly uniform primitive recursive rates of metastability in a full general setting. Moreover, under an additional assumption, we are even able to obtain effective general rates of convergence. We argue that such additional condition is actually necessary for the existence of general uniform rates of convergence.

Abstract: Over the past two decades, multiobejective gradient descent methods have received increasing attention due to the seminal work of Fliege and Svaiter. Recently, Chen et al. pointed out that imbalances among objective functions can lead to a small stepsize in Fliege and Svaiter's method, which significantly decelerates the convergence. To address the issue, Chen et al. propose the Barzilai-Borwein descent method for multiobjective optimization (BBDMO). Their work demonstrated that BBDMO achieves better stepsize and performance compared to Fliege and Svaiter's method. However, a theoretical explanation for the superiority of BBDMO over the previous method has been open. In this paper, we extend Chen et al.'s method to composite cases and propose two types of Barzilai-Borwein proximal gradient methods (BBPGMO). Moreover, we prove that the convergence rates of BBPGMO are $O(\frac{1}{\sqrt{k}})$, $O(\frac{1}{k})$, and $O(r^{k})(0<r<1)$ for non-convex, convex, and strongly convex problems, respectively. Notably, the linear rate $r$ in our proposed method is smaller than the previous rates of first-order methods for multiobjective optimization, which directly indicates its improved performance. We further validate these theoretical results through numerical experiments.

Abstract: In this paper, we present version 2.0 of cashocs. Our software automates the solution of PDE constrained optimization problems for design optimization and optimal control. Since its inception, many new features and useful tools have been added to cashocs, making it even more flexible and efficient. The most significant additions are a framework for space mapping, the ability to solve topology optimization problems with a level-set approach, the support for parallelism via MPI, and the ability to handle additional (state) constraints. In this software update, we describe the key additions to cashocs, which is now even better-suited for solving complex PDE constrained optimization problems.

Abstract: The airport ground holding problem seeks to minimize flight delay costs due to reductions in the capacity of airports. However, the critical input of future airport capacities is often difficult to predict, presenting a challenging yet realistic setting. Even when capacity predictions provide a distribution of possible capacity scenarios, such distributions may themselves be uncertain (e.g., distribution shifts). To address the problem of designing airport ground holding policies under distributional uncertainty, we formulate and solve the airport ground holding problem using distributionally robust optimization (DRO). We address the uncertainty in the airport capacity distribution by defining ambiguity sets based on the Wasserstein distance metric. We propose reformulations which integrate the ambiguity sets into the airport ground holding problem structure, and discuss dicretization properties of the proposed model. We discuss comparisons (via numerical experiments) between ground holding policies and optimized costs derived through the deterministic, stochastic, and distributionally robust airport ground holding problems. Our experiments show that the DRO model outperforms the stochastic models when there is a significant difference between the empirical airport capacity distribution and the realized airport capacity distribution. We note that DRO can be a valuable tool for decision-makers seeking to design airport ground holding policies, particularly when the available data regarding future airport capacities are highly uncertain.

Abstract: It is well-known that by adding integrality constraints to the semidefinite programming (SDP) relaxation of the max-cut problem, the resulting integer semidefinite program is an exact formulation of the problem. In this paper we show similar results for a wide variety of discrete optimization problems for which SDP relaxations have been derived. Based on a comprehensive study on discrete positive semidefinite matrices, we follow a generic approach to derive mixed-integer semidefinite programming (MISDP) formulations of binary quadratically constrained quadratic programs and binary quadratic matrix programs. Applying a problem-specific approach, we derive more compact MISDP formulations of several problems, such as the quadratic assignment problem, the graph partition problem and the integer matrix completion problem. We also show that several structured problems allow for novel compact MISDP formulations through the notion of association schemes. Complementary to the recent advances on algorithmic aspects related to MISDP, this work opens new perspectives on solution approaches for the here considered problems.

Abstract: Increased variability of electricity generation due to renewable sources requires either large amounts of stand-by production capacity or some form of demand response. For residential loads, space heating and cooling, water heating, electric vehicle charging, and routine appliances make up the bulk of the electricity consumption. Controlling these loads can reduce the peak load of a residential neighborhood and facilitate matching supply with demand. However, maintaining user comfort is important for ensuring user participation to such a program. This paper formulates a novel mixed integer linear programming problem to control the overall electricity consumption of a residential neighborhood by considering the users' comfort. To efficiently solve the problem for communities involving a large number of homes, a distributed optimization framework based on the Dantzig-Wolfe decomposition technique is developed. We demonstrate the load shaping capacity and the computational performance of the proposed optimization framework in a simulated environment.