We study the ternary quadratic problem (TQP), a quadratic optimization problem with linear constraints where the variables take values in {0,±1}. While semidefinite programming (SDP) techniques are well established for {0,1}- and {±1}-valued quadratic problems, no dedicated integer semidefinite programming framework exists for the ternary case. In this paper, we introduce a ternary SDP formulation … Read more
ArticleDownload View PDF
Optimization problems routinely depend on uncertain parameters that must be predicted before a decision is made. Classical robust and regret formulations are designed to handle erroneous predictions and can provide statistical error bounds in simple settings. However, when predictions lack rigorous error bounds (as is typical of modern machine learning methods) classical robust models often … Read more
In this work, we revisit binary polynomial optimization (BPO) problems with limited treewidth of the associated graph. We provide alternate proofs of the exactness of a reformulated linear program (LP) with O(n.2^d) variables, n being the number of variables and d being the treewidth of the associated graph. The first proof relies on expressing any … Read more
The representation of a function in a higher-dimensional space, often referred to as lifting, can be used to reduce complexity. We investigate how lifting affects the convergence properties of Newton-type methods. For the first time, we conduct a systematic comparison of several lifting strategies on a set of 40 optimal control problems. In addition, we … Read more
This paper proposes a context-aware multi-uncertainty-set distributionally robust chance-constrained DC optimal power flow model. Meteorological features are projected to partition the non-convex error support into a context-dependent decomposition of conditional local ambiguity sets, with conditional weights inferred via kernel regression. The minimax problem is reformulated into a finite-dimensional second-order cone program with proven asymptotic consistency. … Read more
We study time-of-use pump scheduling to deliver a required volume using a finite set of pump combinations with empirical flow–power performance, subject to per-shift caps on pump switches. We prove a structural theorem: partitioning the horizon into maximal intervals with constant tariff and shift (atoms), there always exists an optimal schedule with at most one … Read more
In this paper, we develop a stochastic set-valued optimization (SVO) framework tailored for robust machine learning. In the SVO setting, each decision variable is mapped to a set of objective values, and optimality is defined via set relations. We focus on SVO problems with hyperbox sets, which can be reformulated as multi-objective optimization (MOO) problems … Read more
Stochastic minimax problems with decision-dependent distributions (SMDD) have emerged as a crucial framework for modeling complex systems where data distributions drift in response to decision variables. Most existing methods for SMDD rely on an explicit functional relationship between the decision variables and the probability distribution. In this paper, we propose two sample-based zeroth-order algorithms, namely … Read more
We prove the NP-hardness, using Karp reductions, of some problems related to the correlation polytope and its corresponding cone, spanned by all of the n×n rank-one matrices over {0, 1}. The problems are: membership, rank of the decomposition, and a “relaxed rank” obtained from relaxing the zero-norm expression for the rank to an ℓ1 norm. … Read more