Optimization with Inexact Real-Valued Inputs

Inexact real optimization: an objective-gap bound and an exact-feasibility obstruction

Definitions and mathematical statement

Shared notation.

Standard number systems are $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$. Specialized notation and index ranges follow the cited source and the definitions below.

An optimization problem minimizes or maximizes a specified objective over a feasible set. In a finite-precision input model each real datum is represented by an approximation, interval, or oracle; the representation controls both input size and attainable accuracy.

Record scope and qualifications.

The catalogue title is retained as metadata. Named certificates, contracts, bounds or frameworks in that title are not asserted as results of the original source extract. This is a general computational direction: no particular optimization family, accuracy requirement, or real-input representation is specified.

Source-record limitation: The supplied assessment flags an indeterminate optimization prompt: no input model, optimization class, or complexity target.

Statement recorded in the supplied source.

How can optimization problems with real-valued input be solved efficiently when the input numbers cannot be represented exactly? [S2]

Source status.

The supplied catalogue labels this source record open; that metadata was checked against the supplied snapshot on 2026-10-11. The label is preserved for provenance and is not an independent verification of present open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-21.

Short English statement

Study optimization when exact real input values cannot be stored.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30000056 (OWR-730-004). Catalogue curation and metadata: CC BY 4.0. The source extract is retained; definitions, English summaries and qualifications are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Approximation Algorithms for NP-Hard Problems $2005$, Oberwolfach Reports, DOI 10.4171/owr/2004/28, pp. 1461--1540 https://doi.org/10.4171/owr/2004/28.
• Source-specific Oberwolfach Reports licences, including CC BY-SA 4.0 where applicable, are retained; see THIRD_PARTY_NOTICES.md.

Verbatim supplied catalogue question

How can optimization problems with real-valued input be solved efficiently when the input numbers cannot be represented exactly?

A specified model within the broad source direction

The source paragraph explicitly motivates stochastic gap analysis, after explaining why unqualified worst-case rounding is unreliable. The catalogue fragment is a general direction, not one formal complexity conjecture. We analyze a fixed feasible family $\mathcal F\subseteq\{0,1\}^n$ with linear objective and then contrast real-valued constraints. The following complete bounds do not purport to cover every optimization family in the question.

Deterministic objective stability.

Suppose $|c_i-\widehat c_i|\le\delta$ and let $x^*$ and $\widehat x$ minimize $c\cdot x$ and $\widehat c\cdot x$ over the same nonempty family. Every feasible vector has at most $n$ nonzero coordinates, so $|(c-\widehat c)\cdot x|\le n\delta$. Consequently \[ c\cdot\widehat x \le\widehat c\cdot\widehat x+n\delta \le\widehat c\cdot x^*+n\delta \le c\cdot x^*+2n\delta. \] If the unique optimum has a gap greater than $2n\delta$ to every other solution, the rounded objective has the same unique optimum: any competing vector's difference loses at most $2n\delta$ and remains positive. This controls rounding accuracy, not the time needed to find either optimum.

A complete stochastic isolation estimate.

Assume the coordinates $c_i$ are independent real random variables, each with a density bounded by $\phi$, and the finite feasible family is fixed independently of them. For each $i$, conditional on all other coefficients, let $a_i$ be the minimum of $\sum_{j\ne i}c_jx_j$ over feasible $x$ with $x_i=0$, and let $b_i$ be the analogous minimum with $x_i=1$. If either group is empty omit that coordinate. The two best group values are $a_i$ and $b_i+c_i$, with threshold $t_i=a_i-b_i$ depending only on the other coefficients.

If two distinct best and second-best feasible vectors have objective gap at most $\eta$, choose a coordinate where they differ. The best value in each of its two groups lies between the global best value and the second-best value: the group of the global best attains that best value, and the other group has a candidate with value at most the second-best one. Therefore $|c_i-t_i|\le\eta$. Conditional independence and the density bound give probability at most $2\phi\eta$ for this event. The union bound over $n$ coordinates proves \[ \Pr(\hbox{best-to-second-best gap}\le\eta) \le2n\phi\eta. \] Ties are included by this argument; taking $\eta\downarrow0$ shows they have probability zero. If the family has one vector, the gap is interpreted as infinity and the claim is immediate.

Combining this estimate with objective stability gives probability at most $4n^2\phi\delta$ that rounding with error at most $\delta$ changes the unique optimum. For a desired failure probability $\beta>0$, error $\delta\le\beta/(4n^2\phi)$ suffices. With coefficients in a bounded fixed interval, this asks for $O(\log(n\phi/\beta)+1)$ binary precision bits, up to the evident nonnegative cutoff when that expression is small. This is a concrete logarithmic-precision mechanism in the source's direction. It does not prove polynomial optimization time, a gap certificate computable without solving the problem, or analogous bounds for random constraint coefficients.

Why exact constraints need a different promise.

Consider minimizing $-x$ for $x\in\{0,1\}$ subject to $\theta x\le0$. At $\theta=0$, the unique optimum is $x=1$; at any $\theta>0$, the only feasible point is zero. In a bounded-error real oracle model, a query of precision $b$ returns any rational within $2^{-b}$ of $\theta$. Run a purported universally correct terminating exact algorithm on zero, with every answer zero. It must eventually output one. Let $B$ be the largest precision queried along this finite run, or zero if no query was made. Choose $0<\theta<2^{-B}$. The same all-zero answers are valid at every query, hence the adaptive transcript and output are identical, but the output is infeasible. Thus no such algorithm can guarantee termination and exact correctness for all real $\theta$ in this oracle model without additional information. Interval promises, an allowed feasibility error or a separation margin change the question and can escape this obstruction.

Audit

The primary stochastic motivation on printed pages 1523--1524 was inspected. The audit kept the feasible family fixed for objective isolation, used conditional independence exactly where needed, and distinguished precision from optimization work. No sampled experiment or general smoothed-complexity theorem is asserted. The broad source direction still needs a specified family, input model and output accuracy before a full solution can be defined.

Process and contributions

Mathematics and model-assisted adversarial self-audit: OpenAI gpt-6-astra, ultra reasoning, as dispatched for this research batch; exact serving revision not exposed. Codex (GPT-6; exact serving revision not exposed) materially assisted with orchestration and format review. No human mathematical authorship, mathematical edits, or independent human proof checking is asserted. Contribution prompt A was applied to the full definition and supplied source row, then prompt B was applied adversarially to the derived results. The item-specific audit above records the scope checks and rejected extrapolations. Local assembly and structural checks do not establish mathematical correctness. The source catalogue status is preserved in TOP_PROBLEM and is separate from this attempt status.

Integration review.

Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% The proved material is a rederivation of known or auxiliary facts rather than a substantiated new advance on the original target. A complete objective-rounding/isolation analysis is provided for a stated model, but the broad source prompt has no single specified complexity target and constraint rounding remains model-dependent.

References

The complete original Sources subsection above is retained, including catalogue attribution and licence notices. The additional list records primary sources actually consulted for this attempt on 11 October 2026; uncited source links reproduced above were not all rechecked.

• Oberwolfach Report 28/2004, Approximation Algorithms for NP-Hard Problems, original question and surrounding discussion read from the cached primary PDF text on 11 October 2026. Historical statements are not a current-status survey. https://doi.org/10.4171/owr/2004/28.

Final status

Unresolved in this attempt. A complete objective-rounding/isolation analysis is provided for a stated model, but the broad source prompt has no single specified complexity target and constraint rounding remains model-dependent.