Use the optimization LagrangianSymmetry gives the gradient equations $2Ax=\lambda 1$ and $2By=\lambda 1$. The positive-definite matrices are invertible, so defineThe affine constraint gives $\lambda =2/D$, henceFor a global certificate, write any other feasible point as $(x_{\ast }+u,y_{\ast }+v)$. Feasibility implies $1^{T}u+1^{T}v=0$. Expansion cancels the cross terms and leavesBy positive definiteness this is positive unless $u=v=0$. Thus the solution is the unique global minimum, not merely a stationary point. This is a two-block instance of positive quadratic minimization under one affine constraint.

The objective is continuous on the compact disk, so a global maximum exists. Its gradient is $(e^x,2e^{2y})$, which is never zero, so a maximum cannot lie in the interior. It must have $x^2+y^2=1$.

Both coordinates of a maximizing point are positive. Reflecting a negative coordinate to its positive counterpart strictly increases the objective without changing the constraint; at an endpoint with one coordinate zero, a small move along the circle into the positive quadrant also increases the objective to first order. Thus it suffices to consider $x>0,y>0$.

The boundary Lagrange multiplier equations are $e^x=2\lambda x$ and $2e^{2y}=2\lambda y$. Eliminate $\lambda$ to obtain the two-dimensional nonlinear system of equationsKeeping this quadrant restriction excludes the boundary minimum that an unconstrained elimination could also produce. Under the stated uniqueness assumption for the admissible solution, the global maximum must be that solution. Approximate it with multivariable Newton iteration, solving $J_F(z_n){\Delta }_n=-F(z_n)$ and setting $z_{n+1}=z_n+{\Delta }_n$, with a suitable safeguard if needed. For example its explicit Jacobian matrix isNo numerical solution of the system is required.

Complete the square to write the objective asLet $z=(x,y)$ and $a=(1,2)$, so $\Vert a\Vert =\sqrt{5}$ while feasibility requires $\Vert z\Vert \ge \sqrt{20}=2\sqrt{5}$. The reverse triangle inequality givesThe objective is therefore at least zero. Equality is attained by $z=2a=(2,4)$, which lies on the boundary. Equality requires the vectors to have the same direction and $\Vert z\Vert =2\sqrt{5}$, so this minimizer is unique. HenceIt also satisfies the Karush-Kuhn-Tucker conditions with $\lambda =1/2$. The direct distance argument proves global optimality even though the exterior of a disk is not a convex set; this is nearest-point minimization outside a Euclidean ball.

Separate inactive and active optimization constraints. At an interior feasible point with $h>0$, a differentiable local minimum must satisfy $\nabla f=0$. Retain only solutions lying in the interior.

On the boundary $h=0$, if $\nabla h\ne 0$, apply the Lagrange multiplier condition. Using the optimization Lagrangian $L=f-\lambda h$, the Karush-Kuhn-Tucker conditions areThe sign follows from feasible motion into $h>0$: the directional derivative along $\nabla h$ at a minimum cannot be negative. Thus a boundary candidate has $h=0$ and a nonnegative Lagrange multiplier. Boundary points with $\nabla h=0$ must be examined separately, because the usual constraint qualification fails there.

Solve the interior and boundary systems, check membership in the feasible set, and establish which candidates are minima using second-order tests or a direct global comparison. The Karush-Kuhn-Tucker conditions alone are not sufficient for general nonconvex functions or feasible sets. On an unbounded feasible set, also check whether an infimum is attained and whether escaping sequences can improve the objective.

For negative $x$, the mean value theorem gives $f^{\prime }(x)=3+x{f}^{\prime \prime }({\xi }_x)$. In particular,Since $f^{\prime }$ is continuous and strictly increasing, it vanishes at exactly one point $x_m\in (-2,-1)$. The positive second derivative makes $f$ a strictly convex function on the entire real line. Its derivative changes from negative to positive at $x_m$, so $x_m$ is the unique global minimum. One may also use $f(x)\ge x^2+3x-5\to \infty$ to verify coercivity.

In the endpoint-bracketing form of golden-section search, begin with $[-2,-1]$, a width-one interval known to contain this unique minimum, and place the two standard interior probes. The attainable position accuracy is different from that for a simple root. Around $x_m$, Taylor's theorem givesHere the minimum value is nonzero and of order one: the lower quadratic bound gives $f(x_m)\ge -29/4$, while $f(x_m)\le f(-1)<-13/2$. Ordinary relative round-off error in these function values therefore hides changes of order $ϵ$, once $h^2$ has that size. The function-value resolution near a nondegenerate minimum is consequently of orderEach golden-section search contraction multiplies the bracket width by $\rho =(\sqrt{5}-1)/2$. Using $2^{-20}$ as the nominal target width givesUnknown evaluation-error constants can change the actual stopping point; $29$ is the standard scale-based count. Requiring $2^{-40}$ position accuracy from these function-value comparisons would disregard the quadratic flatness of the minimum. The same precision effect is documented for one-dimensional numerical minimization.^[ref]

Apply the mean value theorem, the first-order case of Taylor's theorem, to $f^{\prime }$ between $0$ and $x>1$. It yieldsAlso $f(3/2)\ge -5+9/2+9/4=7/4>0$, so the initial point is to the right of the root $x^{\ast }$. For an increasing strictly convex function, its tangent at a point to the right of a root meets the axis between that root and the point. Hence the exact Newton root-finding iteration remains in $[x^{\ast },3/2]$ and decreases towards $x^{\ast }$.

On every relevant interval, $|f^{\prime \prime }|<3$ and $f^{\prime }>5$, so the stated quadratic convergence bound gives, with $e_n=|x_n-x^{\ast }|$,Iterating the bound givesThus four Newton corrections suffice to reduce the exact-iteration error bound below the floating-point spacing scale. The quadratic convergence doubles the approximate number of correct digits at each late step. Beyond this point further corrections cannot reliably improve a generic floating-point answer. This is a bound on useful accuracy under the usual stable-evaluation model, not a claim that the data specify the exact iteration at which every implementation must stagnate.

At a root of size between $1$ and $2$, the spacing of floating-point numbers is $ϵ=2^{-40}$. With ordinary stable function evaluations, a sensible generic absolute position tolerance has scale $2^{-40}\approx 9.09\times 10^{-13}$; sub-spacing progress cannot generally be represented. This is a resolution estimate, not a lower bound excluding an accidentally exactly representable root.

Define one bisection method step as replacing the current bracket by the half retaining the sign change. Starting from $[1,2]$, the width after $N$ such updates is $2^{-N}$. ThereforeThe midpoint of a bracket has an exact-arithmetic error bound of half its width. If tolerance is defined instead as that midpoint error bound, $39$ updates suffice to make it at most $2^{-40}$. Stating the convention avoids an off-by-one difference; once the endpoints are adjacent floating-point numbers, their exact midpoint need not itself be representable.

The second-order remainder form of Taylor's theorem gives, for a point ${\xi }_x$ between $0$ and $x$,For $x\ne 0$, the given curvature bounds implyIn particular $f(1)<-1/2<0$ and $f(2)\ge 5>0$. Differentiability implies continuity, so the intermediate value theorem gives a root in $(1,2)$.

The mean value theorem applied to $f^{\prime }$ gives $f^{\prime }(x)=3+x{f}^{\prime \prime }({\eta }_x)\ge 3+2x>0$ for $x\in (1,2)$. Thus $f$ is strictly increasing there, and it cannot have two roots. There is exactly one root in $(1,2)$.

Use the standard spacing convention for machine epsilon: the next representable floating-point number above $1$ is $1+2^{-40}$. In a normalized binary representation this corresponds to $41$ significant binary digits, including the leading digit. The spacing throughout $[1,2)$ is therefore $2^{-40}$.

With rounding to nearest, the associated unit roundoff is half that spacing, $u=2^{-41}$; for a normal result the relative round-off error is bounded by $u$. Some texts instead call $u$ machine epsilon. Here $2^{-40}$ denotes the spacing scale, and the iteration counts below use that convention. It describes representation precision, not a guarantee that an arbitrarily evaluated function has a relative error this small.

The number isA direct search over every $q$-element subset must inspect $\left(\genfrac{}{}{0ex}{}{n}{q}\right)$ candidates. Testing one candidate by generating its subset sums creates $2^q$ values; storing previously seen sums detects a collision. Generating them incrementally needs $O(2^q)$ arithmetic operations, or $O(q{2}^q)$ for the straightforward independent calculation of each sum. Thus the simple overall search has cost on the scale of $\left(\genfrac{}{}{0ex}{}{n}{q}\right)2^q$, apart from integer-arithmetic and data-structure costs.

The important time complexity distinction is that fixed $q$ gives polynomial growth in $n$, of degree $q$, but this can still become impractically large. If $q$ increases with $n$, both the candidate count and the internal power set can grow exponentially. For example, near $q=n/2$ the binomial coefficient is already exponentially large. An exhaustive implementation can therefore encounter a combinatorial explosion; the fixed-$q$ estimate $\Theta (n^q)$ must not be described as exponential in $n$.

Fix any seven-element subset $S$. Its power set supplies $2^7=128$ pigeons. Map each subset to its integer sum. Since the elements are positive, all such sums lie between $0$ and ${\sum }_{s\in S}s$. The latter is at most the sum of the seven largest available elements,There are therefore at most $92$ possible sums, fewer than the $128$ subsets. The pigeonhole principle forces two distinct subsets to have the same sum. Every seven-element subset has the two-sum property. This is the subset-sum pigeonhole bound. The weaker estimate ${\sum }_{s\in S}s\le 7\cdot 16=112$ would also suffice, since $128>113$.

For $q=1,\dots ,5$, choose the first $q$ elements of $\{1,2,4,8,16\}$. Every sum of a subset has a unique binary representation, so distinct subsets cannot have the same sum. To see this directly, take the largest power of two belonging to exactly one of two proposed subsets. It exceeds the sum of all smaller powers, and therefore cannot be cancelled by their difference. Thus these chosen sets are dissociated sets and do not have the two-sum property.

If cardinality zero is included, the empty set has only one subset, so it cannot supply two distinct ones either. There is a counterexample at every cardinality from $0$ through $5$.

For $q\ge 1$, choose an ordered list of $q$ distinct elements: there are $n(n-1)\cdots (n-q+1)$ such lists. Every $q$-element subset occurs in exactly $q!$ orders, the number of permutations of its elements. Thus the count is the binomial coefficientFor fixed $q$ and $n\ge 2q$, every numerator factor lies between $n/2$ and $n$. ConsequentlyThe constants depend on the fixed $q$, not on $n$. These inequalities prove $\left(\genfrac{}{}{0ex}{}{n}{q}\right)=\Theta (n^q)$ in big theta notation. More precisely, dividing the product by $n^q$ gives the fixed-cardinality binomial coefficient asymptotic $\left(\genfrac{}{}{0ex}{}{n}{q}\right)\sim n^q/q!$. For $q=0$, there is exactly one empty subset, and the assertion is $1=\Theta (1)$.

A subset is determined uniquely by deciding, for each of the $n$ elements, whether to include it. Each decision has two possibilities. By the rule of product, there are $2\cdot 2\cdots 2=2^n$ decision strings. The correspondence between such binary strings and subsets is a bijection, so $|\mathcal{P}(\mathcal{U})|=2^n$. The all-zero string corresponds to the empty subset.