Optimization and Control
Multi-Objective Enterprise Green Supply Chain Network Design
Felix Reichelk
This paper introduces and studies the Multi-Objective Enterprise Green Supply Chain Network Design problem (MOEDGSCND) an extension of the well known Multi-Objective Supply Chain Network Design (MO-SCND), in this case a three-objective combinatorial optimisation problem that simultaneously minimises total cost f1, carbon dioxide emissions f2, and customer dissatisfaction f3 over binary decisions on which distribution centres to open and how to assign customer zones to open facilities. The problem generalises capacitated facility location and is known to be NP-hard. Furthermore this paper lays out a formal specification of decision variables, objective functions, all constraints and then investigates and compares three solution approaches using a single numerical instance: (A) exact weighted-sum integer linear programming solved via PuLP, (B) three Fully
Polynomial-Time Approximation Schemes (FPTAS) providing (.94 + $\epsilon$)-guarantee approximations for $\epsilon$ := 0.15, and (C) two baseline heuristics for comparison. On an eight-customer, five-candidate-DC instance the exact solver certifies the optimal Pareto front across eight weight combinations, and all three FPTAS variants achieve their approximation guarantees, finishing within milliseconds compared to centiseconds for the exact ILP using the PuLP solver on this scale.
Read the full abstract ▾
Optimization and Control · Cross-listed from cs.DS
Dense Weak Hiding: Closing Complexity Gaps in Nonconvex and PL Finite-Sum Optimization under Individual Smoothness
Yuxing Peng, Zhiqing Tang and Weijia Jia
Under individual smoothness, known
algorithms for nonconvex finite-sum optimization use $O(n+\sqrt n\Delta L_{\max}/\varepsilon^2)$ incremental first-order oracle (IFO) calls, while existing lower bounds miss the factor $\sqrt n$ in the second term. We prove the matching lower bound $\Omega(n+\sqrt n\Delta L_{\max}/\varepsilon^2)$ for randomized IFO
algorithms, allowing component indices and query points to depend on the complete preceding history. Thus PAGE and SPIDER are minimax optimal up to universal constants under individual and mean-squared smoothness. Under the global Polyak-Lojasiewicz (PL) condition, prior lower bounds did not capture the correct dependence on $n$ under individual smoothness, and the regime of small $\kappa$ remained open for randomized IFO
algorithms. We prove an $\Omega(n+\kappa_{\max}\sqrt n\log(\Delta/\varepsilon))$ lower bound for $\kappa_{\max}\ge\sqrt n$, and an $\Omega(n+n\log(\Delta/\varepsilon)/(1+\log(\sqrt n/\kappa_{\max})))$ lower bound for $3\le\kappa_{\max}\le\sqrt n$. Restarted PAGE attains matching upper bounds under mean-squared smoothness in terms of $\kappa_{\rm ms}=L_{\rm ms}/\mu$. Our lower bounds use dense weak hiding. Each hidden direction is spread across all components, making individual queries weakly informative while preserving the direction in the average. A sufficiently large dimension makes premature activation of future stages unlikely within the query budget. Balancing the cost of revealing a stage against the number of stages permitted by individual smoothness yields the missing $\sqrt n$ factor.
Read the full abstract ▾
Optimization and Control · Cross-listed from cs.CC
A note on the $\Sigma_2^P$-completeness of the Frobenius number
Thomas Rothvoss
Given a finite set $A$ of natural numbers whose greatest common divisor is one, the Frobenius number $g(A)$ is the largest integer that is not a non-negative integer combination of the numbers in $A$. In a 2016 preprint, Matsubara states that given $A$ and $k$, deciding if $g(A) \geq k$ is $\Sigma_2^P$-complete. A decade has passed since without peer-reviewed publication of this result. At the same time, the community has found it difficult to verify this result. In this note, we give a write-up of the completeness proof based on Matsubara (2016).
Read the full abstract ▾
Optimization and Control
On the suboptimality of stochastic MPC with varying constraint horizon
Allan Andre Do Nascimento, Andre Bertolace, Antonis Papachristodoulou et al. (+1 more)
Enforcing
stochastic state constraints over the full prediction horizon in Model Predictive Control (MPC) can be computationally demanding. Here we study
stochastic MPC without terminal ingredients in which chance constraints are enforced only over a shorter constraint horizon. Using
stochastic relaxed dynamic programming, we derive an explicit upper bound on the average expected closed-loop cost that depends on both prediction and constraint horizons. For linear quadratic problems with affine chance constraints and bounded uniform disturbances, we provide a deterministic reformulation via coordinate transformation and constraint tightening. Simulations illustrate the trade-off between computational effort and performance.
Read the full abstract ▾
All authors Allan Andre Do Nascimento, Andre Bertolace, Antonis Papachristodoulou, Kostas Margellos
Optimization and Control
Sharp Singularity-Degree Bounds for Equality-Generated SDP-RLT Relaxations of Binary Programs
Hao Hu
Singularity degree is an important measure of semidefinite programming (SDP) degeneracy, but it is generally unavailable a priori from the problem data. We augment the Shor relaxation of nonempty binary sets $\{x\in\{0,1\}^n:Ax=b\}$ with the first-level Reformulation-Linearization Technique (RLT) equations generated by the defining linear equalities. For the resulting equality-generated SDP-RLT relaxation, we determine the exact worst-case singularity degree. If $\operatorname{rank}(A)=m$ and $0<m<n$, then the associated relaxation has singularity degree at most $\min\{m,n-m\}$, and this rank-nullity bound is attained for every possible rank in this range. Consequently, the worst-case singularity degree over this class is $\lfloor n/2\rfloor$ for $n\geq 2$. This is strikingly smaller than the sharp general bound $n$ for feasible SDP systems with
matrix variables of order $n+1$ (Sturm, 2000, Example 2). Thus, for individual relaxations, rank and nullity provide an a priori bound on the otherwise inaccessible singularity degree and on the Hölder exponent in error bounds estimating distance to feasibility from constraint residuals.
Read the full abstract ▾
Optimization and Control · Cross-listed from eess.SY
Finite Sample Identification of Analytic Nonlinear Systems
Negin Musavi, Ziyao Guo, Geir E. Dullerud et al. (+1 more)
This paper studies the identification of linearly parameterized nonlinear (LPN) systems. Although LPN systems share the same linear parameterization structure as linear systems, they are more challenging to identify. In particular, previous work has shown, through a counterexample based on a piecewise-affine system, that non-active exploration is generally insufficient for LPN system identification. In this paper, we consider LPN systems with real-analytic feature functions. We show that non-active exploration is sufficient for the identification of this class of systems by establishing non-asymptotic convergence rates of least-squares estimation and set-membership estimation. In addition, we provide counterexamples to show that non-active exploration may not be sufficient for system identification for non-real-analytic systems, even if those systems are infinitely differentiable. We present numerical experiments to further support and validate our theoretical results.
Read the full abstract ▾
All authors Negin Musavi, Ziyao Guo, Geir E. Dullerud, Yingying Li
Optimization and Control
Quiver Semistability and Structured Kalman Decompositions for Networked Linear Dynamical Systems
Kazuo Murota and Tasuku Soma
We introduce new notions of controllability and observability for networked linear time-invariant (LTI) systems based on $\sigma$-semistability of quiver representations. Utilizing King's criterion for $\sigma$-semistability, we define a network generalization of the Kalman decomposition for networked LTI systems, which systematically decomposes the local and interconnection dynamics while respecting the underlying network structure. Furthermore, we present efficient
algorithms for deciding the proposed controllability and observability of a given networked LTI system and for finding the Kalman-type decomposition. We also show efficient
algorithms for deciding the $\sigma$-semistability of representations of acyclic quivers with self-loops if the weight $\sigma$ has the same sign for all vertices with self-loops. Such quiver representations and weights arise from networked LTI systems.
Read the full abstract ▾
Optimization and Control
A Unified Perspective on Conformal Prediction and Wasserstein Distributionally Robust Optimization for Uncertainty Quantification
Kehan Long, Yiqi Zhao, Pol Mestres et al. (+3 more)
Uncertainty quantification from finite data is central to machine learning, optimization, and automation systems, where decisions must remain reliable under limited samples and test-time distribution shift. Conformal prediction (CP) and distributionally robust optimization (DRO) offer two complementary approaches: CP constructs data-dependent prediction sets with distribution-free finite-sample validity under exchangeability, while DRO optimizes worst-case performance over an ambiguity set around an empirical distribution. We develop a unified probabilistic perspective on CP and DRO by viewing both as ways to turn finite calibration data into a data-dependent
quantile estimator that a test score falls below with high probability. From this perspective, CP and DRO correct the empirical
quantile along two coordinates of the same family of
estimators: CP inflates the
quantile level, whereas DRO shifts the
quantile value through an ambiguity radius. Both methods provide the same calibration-conditional guarantee for the true distribution, requiring the target coverage to hold with high probability over the calibration sample. Their constructions differ, however: CP uses a closed-form, distribution-free level correction, while DRO uses a value-space correction whose certified radius depends on properties of the unknown distribution and additionally guarantees coverage uniformly over the ambiguity set. This distinction emerges in the tails of the score distribution. Because CP relies on sparse upper-tail order statistics of the calibration samples, its level inflation barely moves the
estimator when those samples are dense near the target
quantile but overshoots when they are sparse, whereas a well-chosen DRO radius corrects in value space and may avoid this overshoot.
Read the full abstract ▾
All authors Kehan Long, Yiqi Zhao, Pol Mestres, Lars Lindemann, Nikolay Atanasov, Jorge Cortés
Optimization and Control
Successive design of backstepping observers for parabolic PDE-ODE systems and its duality to state feedback stabilization
Nicole Gehring
The paper introduces a successive backstepping observer design for strictly feedforward parabolic PDE-ODE systems, in which the coupling structure determines the order of error stabilization and the corresponding transformations. First, a transformation based on a virtual measurement stabilizes the ODE observer error subsystem, which is most distal from the measurement, while decoupling it from the PDE error state. Second, a Volterra integral transformation is employed to stabilize the PDE error subsystem and to map the overall error dynamics into a cascade of exponentially stable ODE and PDE subsystems. The design is shown to be dual to a recently proposed multi-step state feedback design for parabolic PDE-ODE systems in strict feedback form, thus explaining the structure of the presented observer design.
Read the full abstract ▾
Optimization and Control
Transformer-Based Flow Shop Scheduling Using MILP-Generated Training Data
Roderich Wallrath
Advances in machine learning (ML) have created new opportunities to complement traditional operations research (OR) methods. In particular,
transformer models can capture complex interactions in
token sequences by mapping
tokens into a high-dimensional
embedding space and propagating contextual information via
attention. This makes them a candidate to model non-permutation flow shop scheduling with secondary resources as a next-
token prediction task, where
tokens represent job-machine-secondary resource tuples. For training, mixed-integer linear programming (MILP)-generated schedules are tokenized and used as next-
token prediction data. During inference, partial
token sequences (prefixes) are randomly generated and completed by the trained
transformer through constrained decoding. A computational study is conducted on a flow shop with 8 jobs, 4 machines, and 3 secondary resources, where jobs are selected from a fixed pool of 20 jobs that is sampled during training and provides the candidates during prefix completion. The
transformer achieves better solution quality (smaller makespans) compared to a genetic
algorithm (GA), the NEH heuristic, and random search. It is outperformed only by the MILP model and the iterated greedy (IG) heuristic. The study concludes that
transformer models can, to some extent, learn patterns from MILP-optimized non-permutation flow shop schedules and that
transformer-based scheduling represents an interesting direction for future research, particularly in settings with a fixed, recurring job set.
Read the full abstract ▾
Optimization and Control
Reciprocal-Manifold Annealed KKT Flows for Constrained Optimization: Application to the Nonconvex AC Optimal Power Flow
M Parimi, Aditi Ramteke, Rachit Mehra et al. (+2 more)
Safety-critical optimization applications, such as real-time power system operation, maintain feasibility at every intermediate step, not merely at convergence. Existing approaches either violate constraints mid-solve (interior-point methods) or enforce feasibility through per-instant quadratic programming subproblems with cubic computational cost and unbounded worst-case execution time. We propose a continuous-time optimization framework for smooth constrained nonlinear problems that preserves feasibility throughout the optimization process without requiring projection operators, quadratic programming subproblems, or other per-iteration optimization routines. The method is built around a reciprocal multiplier
manifold, which establishes an explicit relationship between inequality constraints and their associated Lagrange multipliers. By designing a continuous multiplier update law, the
manifold is shown to remain forward invariant, while the resulting dynamics are equivalent to continuous-time logarithmic barrier gradient descent. The proposed framework naturally extends to multiple inequality constraints, equality constraints, nonconvex feasible sets, and infeasible initial conditions. The method is further enhanced through an augmented Uzawa flow that eliminates oscillatory transients commonly observed in classical primal-dual saddle-point dynamics. The effectiveness of the proposed approach is applied to the AC Optimal Power Flow problem of IEEE 9-bus and IEEE 57-bus systems. Numerical results show convergence to solutions within 0.4% of the
benchmark optimum while maintaining strict feasibility of all constraints. A computational complexity analysis shows that the proposed dynamics reduce the per-step computational cost from cubic to linear complexity. Finally, dynamic tracking studies under time-varying operating conditions demonstrate reliable feasibility preservation.
Read the full abstract ▾
All authors M Parimi, Aditi Ramteke, Rachit Mehra, Arun Mahindrakar, Navdeep Singh
Optimization and Control · Cross-listed from math.PR
Central limit theorem for Wasserstein projection - the case of convex order
Yuanlong Ruan
The main focuses of the article are limit
theorems of Wasserstein projection in the convex order which are useful for inference tasks. The main results rely on the establishment of dual attainment, stability and several useful observations. The first is a clean criterion to invoke the Wasserstein projection dualities on the classical cost $c=h(x-y)$. A new strategy was introduced to establish the dual attainment. Backward and forward dual transport are proved to enjoy a conjugate relationship. Sufficient conditions are given that ensure uniqueness of the optimal dual potential. These ingredients laid the groundwork for the proof of optimal dual potential stability, thereby permitting us to prove the central limit
theorems under mild moment assumptions. Additional discussions show that the moment assumptions are sharp. These results also answered several open questions raised by Professor Benjamin Jourdain.
Read the full abstract ▾
Optimization and Control · Cross-listed from cs.LG
Which LLM for Which Work? Budgeted Model Allocation under Uncertain Evaluation
Hamed Khosravi and Xiaoming Huo
A company with a fixed artificial intelligence (AI) budget must decide which large
language model (LLM) handles each recurring workload. What it lacks is the quality table, how well each model performs on each workload. Given that table, the decision is a multiple-choice knapsack problem and is routine to solve, so estimating it is the difficulty, and that estimation fails in two ways. Models are rarely compared on the same work, and the recorded score is usually a proxy rather than the outcome the company values. Causal and off-policy methods repair the first but condition on the second, while evaluator-validation methods estimate the second but stop short of the decision. Worse, buying more re-evaluation cannot settle the second: randomization governs which requests are scored, not how a score is produced, so the table stays uncertain however much evaluation is purchased. Yet the deployment decision may still be determined even when the table is not. We therefore ask whether one assignment stays optimal across every quality table consistent with the evidence. For the fixed-budget problem, this admits an exact two-solve certificate: solve once at the estimated table and once at a least-favourable table. Agreement certifies the assignment; disagreement identifies the model-workload pairs where further evidence can matter. We propose CASE (causal active sequential experimentation), which targets evaluation to those pairs and repeats the test as evidence accumulates. On a production log, the measurement failure is the larger of the two: correcting assignment exactly still leaves most of the loss, and randomized re-evaluation does not remove it. In our experiments, the available evidence often does not determine the assignment. On paid software tasks, better information about model quality yields more savings than further optimization of the assignment on the same estimates.
Read the full abstract ▾
Optimization and Control
Online Gate-Driven Flow Control in Resin Transfer Moulding Using a Neural-Network Surrogate
Nicholas Wright, Oliver Maclaren, Piaras Kelly et al. (+2 more)
In resin transfer moulding, complete saturation of the fibre preform is necessary before the resin front reaches the outlet vent(s), to prevent dry-spot formation. In practice, the flow front rarely advances uniformly due to race-tracking effects. We propose a combined estimation and control strategy to address this issue. We use pressure-sensor data collected during filling to estimate the unknown race-tracking strengths via an iterated extended Kalman filter, and to simultaneously optimise auxiliary gate pressures to prevent the resin from arriving at the vent before complete saturation occurs. To make this approach feasible in real time, we replace the expensive finite element-control volume model with neural network surrogate models. The
Bayesian approximation error framework is used to account for the discrepancy between the surrogates and the original model. To make the training of the surrogates feasible with time-dependent control actions, we prove that the flow-front geometry depends only on the time-averaged gate pressures. We demonstrate the methodology on a representative forked geometry, showing that the combined estimation-and-control framework can substantially reduce the number of unfilled nodes at the end of filling compared with an uncontrolled baseline. However, the level of improvement depends strongly on the location and number of auxiliary gates.
Read the full abstract ▾
All authors Nicholas Wright, Oliver Maclaren, Piaras Kelly, Suresh Advani, Ruanui Nicholson
Optimization and Control · Cross-listed from cs.IT
Linear Coding of LTI Sources Over Vector Gaussian Channels: A Majorization Approach
Shihao Jin, Junhui Li, Shinji Hara et al. (+1 more)
We study the design of linear time-invariant (LTI) encoder-decoder pairs for transmitting the state of a discrete-time LTI vector source over power-constrained parallel Gaussian channels with feedback. Two types of power constraints are considered. Under individual subchannel power constraints, a necessary and sufficient condition for designing an encoder-decoder pair that achieves bounded estimation error covariance (EEC) is established via two coupled majorization inequalities involving the subchannel signal-to-noise ratios and the antistable poles of the source. Under total channel power constraint, we derive the minimum total power required for a feasible encoder-decoder design by exploiting partial-order progamming under majorization order. An analytical optimal power allocation is obtained for the case of equal noise variances, which admits a water-filling interpretation; for general noise case, a sequential water-filling
algorithm is developed. Our results reveal that the difficulty of transmitting a discrete-time LTI source via LTI coding is governed not only by its topological
entropy, but also by the evenness of the log-magnitudes of its antistable poles. The design methods for feasible encoder-decoder pairs are also provided.
Read the full abstract ▾
All authors Shihao Jin, Junhui Li, Shinji Hara, Wei Chen
Optimization and Control · Cross-listed from cs.LG
Denoising as Projection: Constrained Optimization with Gradient-Guided Diffusion
Runyu Zhang, Jiawei Zhang, Gioele Zardini et al. (+2 more)
Diffusion models are increasingly used not only for sampling from learned data distributions, but also for generating samples that optimize task-specific objectives. A common approach is to guide the reverse
diffusion process using gradients of an external objective. However, when the data distribution is supported on a structured feasible set, such as a
manifold or a constraint set, gradient guidance can move samples away from the learned data geometry. In this paper, we study a simple projected-gradient-guided
diffusion update based on the observation that the Stein denoising operator can act as an approximate projection onto the data geometry. The proposed update incorporates the objective gradient inside the denoising step, yielding an inference-time method that uses only a pretrained denoiser and gradient evaluations. We analyze this update as an inexact projected-gradient method for constrained optimization over learned feasible geometries. Our theory covers three settings: linear
manifolds, compact convex feasible sets, and compact Riemannian submanifolds. In all these settings, we prove descent and finite-time convergence guarantees. Numerical experiments support the theoretical interpretation and illustrate how the proposed update balances objective descent with preservation of the learned geometry.
Read the full abstract ▾
All authors Runyu Zhang, Jiawei Zhang, Gioele Zardini, Saurabh Amin, Asuman Ozdaglar
Optimization and Control
The De Cock–De Moor Conjecture: Proof, Normal Form, and Indefinite Angles
Jeffrey Humpherys
De Cock and De Moor conjectured that two
matrices built from the solutions of three coupled Lyapunov equations always share their
eigenvalues, an identity linking principal angles between model subspaces with the canonical correlations between the past and future of a
stochastic process. The
conjecture was recorded as Problem 9.1 of Unsolved Problems in Mathematical Systems and Control Theory. We prove it under the natural nonresonance condition, without stability or diagonalizability, and show that the two
matrices are similar. The proof exposes a Cauchy-
matrix structure created by the rank-one perturbation and reduces the problem to rational interpolation, and the main
theorem has also been verified in the Lean~4 proof assistant. The same structure gives a normal form that depends only on the poles and zeros of the model. Off the stable set the
eigenvalues become squared cosines of angles in an indefinite metric. We prove an inertia
theorem for them and show that reflecting a pole or a zero across the unit circle acts on the angles by a principal pivot transform. For several inputs and outputs, where the
conjecture fails, we identify the subspaces whose angles do give the canonical correlations. We also relate our approach to the independent proof of Gillberg and Löfberg.
Read the full abstract ▾
Optimization and Control
Stochastic Optimal Control of Hawkes Jump-Diffusion Systems
Daria Sakhanda and Joshué Helí Ricalde-Guerrero
This paper is devoted to developing a framework for
stochastic growth models with environmental risk, in which rare but catastrophic shocks interact with capital accumulation and pollution. Building on the Poisson point process formulation studied in arXiv:2511.13568, we extend the model to disasters driven by a marked Hawkes process, allowing past disasters to temporarily increase the likelihood of subsequent shocks. Our work focuses on a subcritical Markovian Hawkes specification, in which the state space is augmented by the self-excitation component of disaster risk. We establish the well-posedness and nonexplosion of the resulting controlled Hawkes dynamics. Using the Hamilton-Jacobi-Bellman characterization of the corresponding Poisson control problem, we obtain quantitative estimates for the Hawkes excitation process and prove, under a small-excitation scaling, that the Hawkes value function converges to its Poisson counterpart as the magnitude of self-excitation vanishes. This provides a rigorous Poisson approximation of the
stochastic control problem and quantifies the effect of self-excitation on optimal growth under environmental disaster risk.
Read the full abstract ▾