CS Paper Radar

Weight Certificates for Convex Multi-Objective MPC: Geometric Characterization, $\ell^1$ Construction, and $\ell^2$ Foreclosure

Hadi Hajieghrary, Benedikt Walter, Chaitanya Shinde, Miguel Hurtadoand Jerry Lopez

eess.SY math.OCmath.AG ·submitted 2026-08-12 18:53 UTC · v1

Abstract

Automated-driving rulebooks rank rule violations lexicographically, and model predictive control enforces that ranking either exactly, through $L{+}1$ sequential programs per tick, or approximately, through a weighted sum tuned by the separation heuristic $w_1\gg w_2\gg\cdots\gg w_L$. We show the heuristic answers the wrong question. For a convex priority-ordered program, a weighted sum reproduces the lexicographic optimum precisely when its weight, augmented by a unit performance coefficient, supports the upper image of the achievement map at the lexicographic point; the admissible weights form the unit-performance slice of an outward normal cone. Under hinge penalties this slice is a polyhedron obtained by projecting a scaled-KKT system, and a linear program returns an interior weight with a certified margin; under squared-hinge penalties no finite weight is exact whenever the limiting multiplier is nonzero, with violation along the local minimizer branch decaying as $O(1/w)$. Calibrated on held-out logs, the resulting weights have near-equal tier components in nine of eleven calibration-eligible scenario classes and roughly double legal-tier event precision against a matched heuristic weight in closed-loop nuPlan experiments on a 25-rule rulebook. The certificate is, however, pointwise: no single weight is valid across the sampled ticks of an episode, the median lifetime is one sampling interval (zero subsequent ticks at the native rate), and persistence tracks active-set stability. These findings motivate monitored weighted solves with selective cascade fallback, although the compliance-pattern monitor detects only a subset of measured lapses.

Closest papers

Nearest neighbours by meaning across the whole index.

From Outranking Flow Scores to Linear Programs: Group Decision Making in PROMETHEE II

cs.AI ·2026-10-25 ·Alexandre Flachs, Yves De Smet
published similarity 0.58
Abstract · 15 pages; 1 figure; to be published in Algorithmic Decision Theory, 9th International Conference, ADT 2026, Lecture Notes in Computer Scienc…

We study inverse and consensus analysis for PROMETHEE II ranking problems when the performance table is fixed. Existing approaches in PROMETHEE-based sensitivity and consensus analysis usually focus on deviations of criteria weights while treating preference functions as fixed. Nevertheless both sets of parameters jointly determine the outranking flow scores. We introduce a linear reparametrization of the PROMETHEE II net flow scores based on weighted preference increments over the observed differences of performances. This representation yields a linear expression of the net flows and clarifies how weights and preference functions interact. Building on this result, we derive linear optimization models for three settings: minimizing weight deviations while allowing preference functions to vary; minimizing deviations over the full set of preference parameters; and multiple decision-maker consensus analysis (with objectives based either on total deviation or on the maximal individual deviation to promote fairness). An illustrative example shows that allowing preference functions to vary can dramatically change the inverse-analysis conclusions obtained from weight-only models, and that the proposed group formulations distinguish efficient consensuses from fairer ones.

0.36

Condorcet-type properties of the linear ordering problem with ties

cs.GT math.COmath.OC ·2026-09-17 ·Daichi Kawashima, Noriyoshi Sukegawa
similarity 0.58
Abstract

The Kemeny rule aggregates multiple strict rankings into a single strict ranking that minimizes the sum of its distances from the input rankings. The resulting optimization problem, called the Kemeny problem (\texttt{KP}), is a special case of the linear ordering problem (\texttt{LOP}). The Kemeny rule satisfies several desirable properties in social choice theory, including the extended Condorcet criterion (\texttt{XCC}). Ando et al. strengthened this result by introducing the strong Condorcet criterion (\texttt{SCC}) and showing that it holds for every optimal solution to an arbitrary \texttt{LOP} instance. Yoo and Escobedo extended the Kemeny rule to rankings with ties and showed that the resulting rule satisfies the non-strict extended Condorcet criterion (\texttt{NXCC}). This criterion gives a condition under which one candidate must be ranked strictly above another in every optimal solution. In this paper, we introduce the non-strict strong Condorcet criterion (\texttt{NSCC}), a counterpart of the \texttt{SCC} for rankings with ties, and show that it holds for every optimal solution to an arbitrary instance of the linear ordering problem with ties (\texttt{LOPT}). We also establish a complementary structural property that gives conditions under which two candidates must be tied in every optimal solution to an arbitrary \texttt{LOPT} instance.

0.13

Linear Objective Problems: A Complexity Framework for Bilevel Optimization

cs.CC cs.DMmath.COmath.OC ·2026-11-08 ·Christoph Grüne, James B. Orlin, Lasse Wulf
theory similarity 0.57
Abstract

Many bilevel and robust optimization problems are complete for the second level of the polynomial hierarchy, but such results are usually proven one problem at a time with problem-specific reductions. A recurring obstacle is that the lower level must select an optimal solution rather than merely a feasible one, whereas standard reductions preserve only whether a solution exists, not which solutions are optimal. We introduce linear objective problems (LOP), a framework for optimization problems whose solutions are explicit subsets of a ground set and whose objective is linear in these elements. We define tight solution-embedding reductions, which map the optimal solutions of one problem element by element onto the optimal solutions of another, without having to recognize optimal solutions, which is coNP-hard in general. This gives a notion of LOP-completeness, with Satisfiability as the canonical complete problem, even with unit weights. We show that many classical problems are LOP-complete, including Vertex Cover, Dominating Set, TSP, Knapsack, and Steiner Tree, and we introduce a duality that transfers LOP-completeness between minimization and maximization problems. As our main application, we prove a meta-theorem for min-max regret optimization under interval uncertainty: for every LOP-complete problem, the min-max regret version is $Σ_2^p$-complete. Instead of a separate proof for each nominal problem, it suffices to show that the nominal problem is LOP-complete. This recovers known results for the interval min-max regret versions of Knapsack and Maximum Benefit Set Cover and yields completeness for over 50 further problems.

0.24

Extending Tardos's Theorem to Separable Convex Quadratic Programming

cs.DS ·2026-10-05 ·Bin Cui, Hanqing Li, Xupeng Miao
theory similarity 0.57
Abstract · 13 pages, no figures. Substantially revised with a simplified algorithm and proofs. Title and author list updated

For an integer equality matrix $A\in\mathbb{Z}^{r\times m}$ of binary encoding length $\langle A\rangle$, Tardos's theorem solves linear programs using $\operatorname{poly}(r,m,\langle A\rangle)$ rational arithmetic operations and comparisons, independently of the right-hand side and objective coefficients. We extend this guarantee to continuous separable convex quadratic programming over $Ax=b$, $x\ge0$: the operation count is independent of the right-hand side, linear costs, and all nonnegative quadratic weights. The algorithm returns an exact optimal primal-dual pair or a certificate of infeasibility or unboundedness. All intermediate rational numbers have encoding lengths polynomial in the total input length. As an application, we obtain a strongly polynomial algorithm for continuous multicommodity flow with shared capacities and quadratic costs of aggregate arc flow, independently of demands, capacities, and cost coefficients. Objective compression and continuous-integer proximity yield a local solver returning a point close to an optimum. We relax nonnegativity on coordinates with zero optimal dual slack, minimize the largest remaining coordinate, and optimize over the relaxed coordinates. A descent LP over the recession cone provides a complementary bound. Circuit decomposition combines these bounds into a scale ensuring that each local call reveals a new coordinate. At most $m$ calls, followed by two LPs, recover an exact optimum and its dual certificate.

0.20

Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights

cs.DS stat.MLcs.LG ·2026-09-22 ·Shinsaku Sakaue
theory similarity 0.56
Abstract

We study online inverse linear optimization with a fixed unknown linear utility: in each round, an environment presents a compact action set, the learner recommends an action from it, and the environment returns an action that maximizes the utility over the same set. When the utility vector and the actions lie in the $d$-dimensional Euclidean unit ball, we give a randomized algorithm whose regret---the cumulative utility shortfall relative to optimal actions---is $O(\sqrt d)$ in expectation for every time horizon, without knowledge of the horizon. The dependence on $d$ is optimal up to a constant factor by the known $Ω(\sqrt d)$ lower bound for horizons $T\ge d$. Our algorithm maintains matrix multiplicative weights on polynomial feature spaces at geometrically spaced scales. It selects a recommendation distribution by solving a linear program and updates its score matrices by comparing the available actions with the feedback action. With rational oracle outputs and feedback actions, an implementation computable relative to a linear-optimization oracle preserves the $O(\sqrt d)$ regret bound. Whether the same rate is attainable with running time polynomial in the dimension, horizon, and input length remains open.

0.41

Newton Steps are Faster for Linear Complementarity Problems

cs.DS math.OC ·2026-11-05 ·Haoyuan Ma, László A. Végh, Adrian Vladu
similarity 0.56
Abstract

Linear Complementarity Problems (LCPs) with sufficient matrices form a well-studied class of problems, dating back from the foundational works of Cottle and Dantzig (1968). LCPs capture convex quadratic programs, and admit reductions from problems such as discounted stochastic games or mean-payoff games. While the original approach for solving these problems was based on pivoting methods, in their 1991 book, Kojima, Megiddo, Noma, and Yoshise introduced an interior point method (IPM) with running time that is polynomial in the input size, but which depends linearly on a certain parameter called the handicap number of the matrix. Despite the ensuing rich literature on sufficient LCP IPMs, the linear dependence on the handicap number has not been improved since then. We present an IPM whose running time depends on the square root of the handicap number. The algorithm can decrease the duality gap by a constant factor in $O\left(\min\left\{\sqrt{n} (1+κ),n^{9/8}\sqrt{1+κ}\right\}\right)$ iterations. Curiously, this can already be achieved using standard Newton updates. We analyze the IPM in a norm defined by a local weighting, where centralizing Newton steps quadratically converge to the central path, without any dependence on the handicap number. The weights arise from a characterization by Rump (Linear Algebra and Its Applications, 1997, 1998, 2003) of the sign-real spectral radius and its relation to sufficiency; another ingredient of our proof is a new operator norm characterization of the handicap number. Moreover, the connection to Rump's work also enables us to show coNP-completeness of testing sufficiency, and approximation hardness of the handicap number.

0.34

An Augmented Lagrangian Approach to Lifted Bellman Linear Programming

cs.AI ·2026-11-10 ·Jongchan Park, Hyukjun Yang, Narim Jeong, Donghwan Lee
similarity 0.55
Abstract

Temporal-difference critics regress onto a bootstrapped target and usually need a target network. Lifted Bellman Linear Programming (LBLP) instead expresses the in-sample optimal values of offline RL as the solution to a linear program over the dataset. Its neural solver ALBUM relaxes the constraints into hinge penalties with fixed coefficients, and its guarantees are conditions on coefficients chosen in advance. We solve the same program with the method of multipliers: the coefficients become multipliers learned by dual ascent, with one penalty parameter $ρ$. In the convex case the fixed points are the KKT pairs of LBLP, and at every stationary point the applied constraint weights balance the objective exactly. The critic can serve a Gaussian actor, a flow actor, and best-of-N sampling, and for the Gaussian actor we propose an advantage-normalized DDPG+BC objective. With a single $Q$ and $V$ and no target network, our AL-LBLP with best-of-N reaches 60.1\% average success on the 50 state-based OGBench tasks. On long-horizon tasks, it reaches 81.5% on humanoidmaze-giant and 79.8% on antmaze-giant. It does not collapse up to batch size 8192.

0.04

Do Language Models Know Which Constraints Belong Together?

cs.LG cs.AIcs.DSmath.OC ·2026-11-03 ·Junbo Jacob Lian, Kaixuan Chen, Hanzhang Qin, Huiling Chen, Chaoyu Zhang +1 more
benchmarktheorycode/data similarity 0.55
Abstract · 68 pages, 5 figures, 31 tables. Code and data: https://github.com/junbolian/JointDW

Dantzig--Wolfe reformulation strengthens the linear relaxation of a mixed-integer program by convexifying constraint families, and each candidate costs a column generation run. The choice is hard when families strengthen the bound only together, as in classical lot-sizing, network-design, and facility-location formulations. We prove that when an evaluation convexifies at most $s$ of $k$ families, methods that observe only bounds need of order $k^w$ evaluations to find a hidden group of $w$ families in the worst case. A prediction missing $e$ members reduces this to $Θ(k^e)$ through a staged search that need not know $e$. The orders extend to several groups, prices, and growing evaluation costs. We study two predictors: a lookahead at an optimal LP dual, which vanishes on groups whose families share no variable, and language models reading the model, verified by the staged search in JointDW. Such groups appear in three of ten MIPLIB-NL models whose bound can be improved and in all 59 benchmark instances. Given the coefficients of models with up to 16 families, one language model names a true group first in 249 of 252 answers. On the benchmark instances, decompositions chosen by language models from the text solve faster than those of GCG's detector.

0.34