This work considers solving an optimization instance in which the objective is quadratic and where the decision variable is a probability measure, and proposes a hierarchy of convex relaxations based on searching over probability measures over products of the base space that converges to the globally optimal solution.
Abstract
We consider solving an optimization instance in which the objective is quadratic and where the decision variable is a probability measure. Our class of problems are motivated by applications arising from optimal transport (with the Gromov-Wasserstein problem being a prominent example) as well as energy landscape minimization. Because the objective depends quadratically on the decision variable, our class of problems fall outside the standard modeling framework of the Generalized Moment Problems (which requires the objective to be linear). To this end, we propose a hierarchy of convex relaxations based on searching over probability measures over products of the base space. These have a natural interpretation with the moment Sum-of-squares hierarchy-a prominent framework for solving polynomial optimization instances, which we adapt to accommodate probability measures. A key conceptual contribution is to introduce a notion of positive-semidefiniteness that extends the usual notion over matrices. Under the assumption that the decision variables satisfy certain marginal constraints (as in the Kantorovich formulation of the optimal transport problem), we establish convergence of our hierarchy towards the globally optimal solution. Under the additional assumption that the objective is a polynomial, we propose a moment-SOS type hierarchy of finite dimensional semidefinite programs whose optimal solution converges to that of the original quadratic optimization over measures. We demonstrate our framework with numerical experiments. More generally, optimization over measures where the objective and/or constraint depends on the decision in a polynomial way is a fundamental problem. It is hoped that our work provides a road-map as to how the ideas of the SOS-ordinarily developed for polynomial optimization-may be applied to a broader class of non-linear problems involving measures.
We show that a class of binary optimization problems with complex non-quadratic objectives or constraints can be reformulated as multi-objective quadratic unconstrained binary optimization problems. When the objective and constraints depend on a small number of quadratic features and are monotone with respect to their preferred directions, at least one globally optimal solution lies in the Pareto set of the associated MO-QUBO. This enables the constraints to be evaluated classically on Pareto-optimal candidates rather than encoded as penalties. We demonstrate the approach for binary portfolio optimization under a Conditional Value-at-Risk constraint. Using Quantum Approximate Multi-Objective Optimization on an illustrative 100-asset instance, we approximate the mean-variance Pareto front using an IBM Quantum computer and derive mean-CVaR fronts through classical post-processing. The hardware results recover the overall structure of the classical front and yield near-optimal feasible portfolios for different risk bounds.
Andres D. Ruiz, Soumyadip Ghosh, S. Woerner· 0 citations
A unified framework, based on decision diagrams, is proposed that serves both to solve the associated optimization problems and to construct ideal conic quadratic extended formulations of the closure of the convex hull of the underlying mixed-integer set.
Soobin Choi, S. Fattahi, Andrés Gómez et al.· 1 citation
We consider the minimization of the expectation of piecewise (not necessarily convex) quadratic function over Wasserstein balls. This expectation problem often appears as a key sub-problem of distributionally robust optimization problems. We present a computationally accessible semidefinite program (SDP)-based characterization for the optimal distribution of this problem, requiring only the optimal solution of a single SDP. We show that strong duality holds between the expectation problem and its SDP dual problem. We then provide a constructive characterization of the associated optimal distributions and prove that they can be explicitly recovered from an optimal solution of the dual of the dual SDP. This result enables the direct computation of the optimal distributions of the expectation problem. Furthermore, we demonstrate through a numerical study on a distributionally robust mean-risk portfolio optimization problem using simulated data that the worst-case distributions can be computed efficiently and utilized to obtain probabilistic interpretation of worst-case solutions.
N. Dizon, V. Jeyakumar· Optimization Letters· 0 citations
This paper presents a new algorithm addressing the problem of stochastic optimization where the cost function depends on a vector of uncertain parameters with known statistics. The algorithm is parameterized so as to address various stochastic formulations spanning from Expectation-focused to Value-at-Risk (VaR) as well as Conditional-Value-at-Risk (CVaR)-focused formulations. The algorithm leverages a recently proposed gradient-based Search&Accelerate algorithm which is originally dedicated to deterministic optimization problems. The approach is based on a sequence of warm-started solutions of instances of the problem. These solutions together with a samples of other solutions belonging to the convex hull of the first ones constitute the set of admissible candidates. Among this discrete set of candidates, the optimal solution is selected with regards to a sample-based approximation of the targeted criterion. The relevance of the algorithm and its efficiency are discussed and shown using a tailored illustrative example.
Maximum likelihood (ML) estimation is a principled and statistically efficient approach for learning probabilistic models. However, for unnormalized models, ML estimation requires evaluating the partition function and differentiating through it, which may not always be tractable. Score matching provides a practically viable alternative that circumvents this obstacle by fitting the score in a way that eliminates dependence on the normalizing constant. We derive the generalized score matching objective on a convex subset of $\mathbb{R}^{d}$ constructively starting from Minimum Probability Flow (MPF) learning, and show how classical score matching as well as domain-adapted variants for non-negative data arise naturally within the proposed framework. We show that the resulting objective is a {\it proper local scoring rule} of second-order, which provides the theoretical guarantee that the true density is recovered when the objective is minimized. Furthermore, for a model belonging to the exponential family, we establish convexity of the objective together with consistency of the finite-sample estimator under standard regularity conditions. Our derivation sheds new light on the scope and applicability of generalized score matching in various problem settings. We compare generalized score matching-based estimators on constrained domains, where the partition function is analytically intractable. We provide experimental results on parameter estimation for model densities belonging to the exponential family defined over convex subsets of $\mathbb{R}^{d}$, and a generative modeling use-case to demonstrate broader applicability of the proposed generalized score matching framework.
Nishanth Shetty, Saisuchith Mahajan, C. Seelamantula· 0 citations
A shrinkage path heuristic is proposed that reduces the solution of a DRO problem to a one-dimensional search over the line segment connecting the sample average approximation (SAA) and the (more demanding but practically solvable) classical robust optimization solution.
Ling-Jun Meng, Ryan Cory-Wright, W. Wiesemann· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
