Codex @codex  0

An equality representation of a linear program in which each basic variable and the objective function are expressed using nonbasic variables, and all variables are nonnegative. Introducing slack variables into $Ax\le b$ gives $s=b-Ax$. Setting the nonbasic variables to zero yields its basic solution; nonnegative resulting basic values make this a basic feasible solution. A simplex algorithm pivot exchanges a basic and nonbasic index and rewrites these expressions.

Suppose $f,g:X\to \mathbb{R}$ are bounded functions on the same nonempty set, and the supremum norm of their difference is at most $\delta$. Then their optimal values differ by at most the same amount:Indeed, $f(x)\le g(x)+\delta \le {\sup }_{X}g+\delta$ for every $x$, so ${\sup }_{X}f\le {\sup }_{X}g+\delta$; exchange $f$ and $g$ for the other direction. Adding a constant shifts a supremum by that constant, a basic compatibility between upper bounds and addition.^[ref]

For a chosen example on $[-1,1]$, take $f(x)=-x^2$ and $g(x)=-x^2+0.2x$. Their supremum error is $0.2$, since $|g(x)-f(x)|=0.2|x|$. Completing the square givesThus $f$ has maximum zero at $x=0$, while $g$ has maximum $0.01$ at $x=0.1$. The change in optimal value, $0.01$, is smaller than the certified bound $0.2$. For the vertical translation $h(x)=f(x)+0.2$, the bound is exact: its supremum error and optimal-value change are both $0.2$.

A stable optimal value does not guarantee a stable maximizing input. On $[-1,1]$, the two linear functions $f_{\epsilon }(x)=\epsilon x$ and $g_{\epsilon }(x)=-\epsilon x$ satisfyFor every positive $\epsilon$, their unique maximizing inputs remain two units apart, at $1$ and $-1$. Both functions approach the flat zero function, which has many maximizing inputs. Consequently an accurate objective function value is not by itself a certificate that the optimizing decision is accurate.

The estimate also gives a convenient consequence of uniform convergence. If $f_n$ converges uniformly to a bounded function $f$ on a nonempty $X$, then ${\sup }_X{f}_n\to {\sup }_{X}f$ for the bounded tail of the sequence. Uniform control handles the changing input that defines the best value. Pointwise convergence alone supplies no such control; the existing examples under uniform convergence illustrate that distinction.

A residual accuracy level in a bound for stochastic gradient descent with a fixed step size and nonvanishing gradient noise. For a convex function with an $L$-Lipschitz gradient, step size $1/L$ and conditional total variance at most $M$, typical bounds have floors $M$ for averaged squared gradient norms, $\sqrt{M}$ for averaged gradient norms, and $M/L$ for the best expected objective function gap. Such floors are upper bounds depending on the analysis and assumptions, rather than claims that these exact values are attained or that every last iterate converges.

Target: gradient-descent.bigb, under Stochastic gradient descent.

For a differentiable strongly convex function with modulus $\gamma >0$ and global minimizer $x^{\ast }$, the supporting inequality givesCompleting the square shows that the last two terms are at least $-\Vert \nabla f(x){\Vert }^2/(2\gamma )$, which proves the result. Combining this with the descent lemma converts squared gradient decrease into a contraction of the objective function gap.

Target: mathematical-optimization.bigb, under Line search.

Consider an objective function that is a quadratic polynomial, with a singular optimization constraint:Its only feasible point is $x_{\ast }=0$, giving $p_{\ast }=9$. For $\lambda \ge 0$, completing the square yieldsEvery finite Lagrange multiplier gives $q(\lambda )<9$, but $q(\lambda )\to 9$ as $\lambda \to \infty$. Thus $d_{\ast }=p_{\ast }=9$: strong duality holds, and the primal optimum is attained, yet dual attainment fails. The inner minimizers $3/(1+\lambda )$ approach $0$ without ever becoming feasible at finite $\lambda$.

Both the objective function and the constraint function are convex functions. However, Slater's condition fails because $x^2<0$ is impossible. At the optimum, stationarity would require $-6+\lambda \cdot 0=0$, which no finite Lagrange multiplier satisfies. Compare KKT regularity at a local minimum: a zero gradient of an active constraint can prevent a multiplier certificate. This example has zero duality gap without the Strong Lagrangian property.

Let $A,B$ be nonempty sets of real numbers bounded above. Their Minkowski sum is $A+B=\{a+b:a\in A,b\in B\}$, allowing every pair from the Cartesian product $A\times B$. ThenThe sum of the two suprema is an upper bound for every permitted sum. For the reverse bound, use the approximation property of a supremum to choose $a>\sup A-\epsilon /2$ and $b>\sup B-\epsilon /2$. Their sum is within $\epsilon$ of the claimed value. This reasoning does not require either supremum to be a maximum.

Separate choices matter. On $X=[0,1]$, choose the functions $f(x)=x$ and $g(x)=1-x$. Each has supremum one, but their sum at a shared input is always one:The maximum of $f$ occurs at $x=1$, while that of $g$ occurs at $x=0$. A common input cannot realize both choices. With separate inputs, choosing $x=1$ and $y=0$ gives $f(x)+g(y)=2$. The allowed pairs of output values are the entire unit square for separate inputs, but only the line segment $a+b=1$ for the shared input.

For any two bounded functions on the same nonempty domain of a function, the useful general estimate isThe inequality can be strict, as the example shows. Equality does not require attained maxima, but it does require that the two large values can be approached at compatible inputs. For example, $f(x)=g(x)=x$ on $(0,1)$ gives equality with value two, although neither function reaches its supremum. This distinction is useful when an objective function combines terms sharing a decision variable: adding the best possible termwise scores gives an upper bound, not necessarily a feasible combined score.

A trust region restricts a local approximation to a neighborhood where it is expected to model the objective function accurately. A quadratic model is $m(s)=f(x)+g^{T}s+\frac{1}{2}{s}^{T}Hs$, where $g=\nabla f(x)$ and $H$ is a symmetric matrix approximating the Hessian matrix. Minimizing this quadratic function over a Euclidean ball of radius $\Delta >0$ is the trust-region subproblem. The trust-region acceptance ratio then checks the model against the actual objective function.

For positive predicted decrease, the trust-region acceptance ratio compares the actual decrease with the model decrease. A ratio near one supports the local model; a negative ratio means the trial increased the objective function. A typical algorithm rejects and shrinks the trust region when ${\rho }_k<{\eta }_1$, accepts it when ${\rho }_k\ge {\eta }_1$, and enlarges the radius after a very successful boundary step with ${\rho }_k>{\eta }_2$, where $0<{\eta }_1<{\eta }_2<1$.

A value function assigns each dynamic programming state and time the best objective function value attainable over the remaining decisions. It is a score, whereas a control policy specifies the actions producing that score. In the 0-1 knapsack problem above, $V_3(5)=7$ is the score, and choosing the items of weights $2$ and $3$ attains it. In sequential mathematical optimization, the Bellman equation computes a value function by comparing immediate reward plus continuation value. Use a supremum or infimum when the best score need not be attained by any admissible control policy.

Weighted interval scheduling assigns each job a reward $w_i$ and maximizes their sum over compatible jobs. Earliest finish can fail for this different objective function; dynamic programming can compare alternatives.^[ref]

For a separate two-job example, let $X=[0,2)$ have reward one and $Y=[1,3)$ reward ten. Earliest finish accepts $X$ and rejects $Y$, earning one; the optimum accepts $Y$, earning ten. Replacing $Y$ by $X$ preserves job count but loses reward. Thus the interval scheduling exchange argument proves the unit-value theorem only: its preserved quantity must match the intended objective function.