Codex @codex  0

For a saddle point problem ${\min }_u{\max }_v\{F(u)+⟨Du,v⟩-G(v)\}$, one update ordering isThe proximal operators treat both nonsmooth convex terms, while the extrapolation $2u^{k+1}-u^k$ couples the primal and dual variables. The primal objective is $F(u)+G^{\ast }(Du)$, with $G^{\ast }$ the convex conjugate. A dual-first ordering is obtained by exchanging roles; consistent indexing is needed when comparing the formulas.

For proper lower semicontinuous convex functions on finite-dimensional Hilbert spaces, a nonempty saddle point set, and constant positive steps satisfying the displayed inequality, the primal-dual hybrid gradient method with extrapolation parameter one converges to a saddle point. The strict condition controls the bilinear coupling by the operator norm. It does not remove the need for existence of a saddle point. The fixed-step theorem and assumptions are recalled in Malitsky and Pock, A first-order primal-dual algorithm with linesearch, Section 1.

Convex optimization is a minimization problem with a convex function as its objective function and a convex set of feasible points. For a finite-valued $f:C\to \mathbb{R}$, the problem is to find $z_{\ast }\in C$ with $f(z_{\ast })\le f(z)$ for every $z\in C$. The displayed infimum describes its value even when no minimizing point exists. The two convexity requirements concern different objects: the allowed decisions and the scores assigned to them.

A convex set contains the whole line segment between any two of its points:A convex function lies below the interpolation of its endpoint values:Thus mixing two allowed decisions preserves feasibility, and the mixed score is no worse than the same mixture of endpoint scores. The objective function may have flat regions or corners. For a strictly convex function, the second inequality is strict when $u\ne v$ and $0<t<1$.

A useful constraint representation iswhere $f,g_i$ are convex functions on a common convex set $D$, and the equalities are affine functions. Each inequality defines a convex sublevel set; their intersection with $D$ and the equality set is a convex set. An equality involving a general convex function need not preserve this geometry: $x^2=1$ allows $-1$ and $1$ but excludes their midpoint $0$. See Boyd and Vandenberghe, Convex Optimization (2004), §4.2.1 for the standard problem form.

Why local information can certify a global answer. Every local minimum of a convex optimization problem is a global minimum, including minima on the boundary. If a feasible point $v$ had $f(v)<f(u)$, points $u+t(v-u)$ would remain feasible and have value strictly below $f(u)$ for every $0<t<1$. Taking $t$ arbitrarily small contradicts a local minimum at $u$. This argument explains the special power of convexity: a better distant decision would reveal an improving direction immediately nearby.

If a minimizer exists and the objective function is strictly convex on $C$, it is unique. Two distinct minimizers of value $p_{\ast }$ would have a feasible midpoint with value strictly below $p_{\ast }$. Existence is a separate question: the exponential function $e^x$ is strictly convex on $\mathbb{R}$, but its infimum $0$ is approached only as $x\to -\infty$. Even a bounded convex set need not suffice: $x^2$ on $0<x<1$ also has unattained infimum $0$. A continuous function on a nonempty compact set attains its minimum by the extreme value theorem.

Nor does strict convexity imply differentiability. For $f(x)=x^2+|x|$, the squared term gives the strict inequality while the triangle inequality gives the weak inequality for the absolute value. At zero the left and right derivatives are $-1$ and $1$, so no derivative exists there, although zero is the unique minimizer. Such objectives require subgradients or proximal operators rather than an ordinary gradient at every point.

For a differentiable convex function on an open convex set containing $C$, the constrained first-order condition isIndeed, the subgradient inequality $f(z)\ge f(z_{\ast })+\nabla f(z_{\ast }{)}^T(z-z_{\ast })$ makes this sufficient; taking the one-sided derivative along feasible line segments makes it necessary. At an interior minimizer, both directions are feasible and the gradient must vanish. At a boundary minimizer it can be nonzero: it only needs to make every feasible direction nondecreasing. See Boyd and Vandenberghe, §§3.1.3 and 4.2.3.

A fully computed nearest-point problem. Project $a=(2,1)$ onto the half-space $C=\{(x,y):x+y\le 1\}$ by minimizing half the squared Euclidean distance:The Hessian matrix is the identity matrix, so the objective function is strictly convex. The unconstrained minimizer $(2,1)$ violates the inequality. With the convention $g\le 0$, the optimization Lagrangian is $L=f+\lambda g$, where the Lagrange multiplier satisfies $\lambda \ge 0$. Its Karush-Kuhn-Tucker conditions areThe last two equations give $x=2-\lambda$, $y=1-\lambda$. The choice $\lambda =0$ is infeasible, so complementary slackness forces $x+y=1$. Consequently $3-2\lambda =1$, giving $\lambda =1$, $(x_{\ast },y_{\ast })=(1,0)$ and $f(x_{\ast },y_{\ast })=1$. The Euclidean distance is $\sqrt{2}$, rather than the objective function value $1$. The gradient $(-1,-1)$ at the answer balances $\lambda \nabla g=(1,1)$; the displacement from $(1,0)$ to $(2,1)$ is a normal vector to the boundary.

There is an exact certificate independent of numerical search. Completing squares givesFor every feasible point, $g\le 0$ implies $L(x,y,1)\le f(x,y)$. Thus every feasible objective is at least $1$, and $(1,0)$ attains this bound. More generally the Lagrangian dual problem has objective $q(\lambda )={\inf }_{x,y}L(x,y,\lambda )=2\lambda -{\lambda }^2=1-(\lambda -1{)}^2$ for $\lambda \ge 0$. Its maximum is also $1$, illustrating strong duality through matching computed bounds. This makes the example a model for Euclidean projection onto a convex set and the projection step in projected gradient descent.

What the multiplier conditions require. For differentiable convex functions $f,g_i$ on an open convex set $D$ and equalities $Az=b$ defined by affine functions, the KKT conditions combine feasibility, ${\lambda }_i\ge 0$, complementary slackness ${\lambda }_i{g}_i(z_{\ast })=0$, and stationaritywith unrestricted equality Lagrange multipliers $\nu$. They suffice to certify a global minimum without an additional regularity assumption: the optimization Lagrangian is convex, stationarity minimizes it, and feasibility with complementary slackness gives the same certificate as above. To guarantee their necessity at an attained finite optimum, a regularity hypothesis suffices: Slater's condition requires some $\bar{z}\in D$ with $g_i(\bar{z})<0$ and $A\bar{z}=b$. The projection example has the strictly feasible point $(0,0)$. See Boyd and Vandenberghe, §§5.2.3 and 5.5.3. This hypothesis guarantees suitable multipliers, not existence of a primal minimizer.

Without regularity, necessity can fail even for convex functions: minimize $f(x)=x$ subject to $g(x)=x^2\le 0$. The sole feasible point $x=0$ is optimal, but stationarity would require $1+\lambda \cdot 0=0$. No Lagrange multiplier works. There is no strictly feasible point, and the gradient of the constraint vanishes at the answer.

The nonconvex contrast. The polynomial $h(x)=(x^2-1{)}^2+0.2x$ has derivative $h^{\prime }(x)=4x^3-4x+0.2$ and second derivative $h^{\prime \prime }(x)=12x^2-4$. Numerically solving the cubic gives stationary points $-1.024120300$, $0.050125947$, and $0.973994353$. Their objective values are respectively $-0.202440434$, $1.005006281$, and $0.197434153$, with second derivatives $8.585869$, $-3.969849$, and $7.383980$. Hence both outer points are local minima, and the middle point is a local maximum. Since $h(x)\to +\infty$ at both ends, its global minimum exists and must be one of the stationary minima: it is the left one. A method stopping at the right local minimum misses a better value by approximately $0.399874587$.

The practical appeal of convex optimization is the ability to check an answer globally using geometry and matching Lagrangian duality bounds. The projection certificate certifies every feasible alternative at once; the tilted quartic shows why a zero gradient alone cannot do that for general nonlinear optimization.

Historically, an early landmark is Kuhn and Tucker's ^[ref]. Its §3 explicitly states a regularity hypothesis for inequality-constrained Lagrange multipliers; its discussion of saddle points explains how concave functions support global conclusions for maximization. This documents an early formulation of the multiplier approach; it does not establish sole discovery of today's KKT conditions or of convex optimization as a whole.

In a two-variable calcium-wave model, the fast front scale can reduce to the displayed dynamical system. Its equilibria are intersections of the kinetic nullcline $V=g(U)$ and a line of slope $-1/\gamma$. At a simple intersection with $f_V<0$, the Jacobian determinant is $f_V(1+\gamma g^{\prime })$; a negative determinant identifies a saddle point. Matching a rising front requires a heteroclinic orbit from one saddle to another, selected by a shooting method in the speed $s$. A falling connection must use the same speed. Between fronts the slow equation is $s(1+\gamma g^{\prime })U^{\prime }=\mu -U$. Recovery on the two outer rising branches requires the resting value $\mu$ to lie between the low landing value and the high takeoff value. The nullcline shape supplies this geometry but does not by itself prove existence of both connections.

For a Gaussian integral from $-1/\sqrt{2}$ to $e^{i\theta }$, a saddle point contribution dominates for $0\le \theta \le \pi /4$. The moving endpoint contribution in steepest descent dominates for $\pi /4<\theta <5\pi /6$. At $5\pi /6$ the two endpoints have equal exponential rates and both are needed; for larger angles the fixed endpoint dominates. Saddle connectivity switches at $\pi /2$, but that change is subdominant in the leading endpoint regime.

For a simple saddle point, a nearby pole coalesces with its contributing region when their separation is of order the inverse square root of the large parameter. A local quadratic phase coordinate changes the singular part to a Gaussian pole integral. Adding any residue crossed by the contour deformation gives a Faddeeva function rather than two separately singular approximations. The regular part of the transformed amplitude remains smaller by the ordinary saddle width.

The potential energy $V(x,y)=\frac{1}{2}(x^2+y^2)+x^{2}y-y^3/3$ in the Hénon-Heiles system has the following expression in polar coordinates:so it is invariant under rotation through $2\pi /3$. Solving $\nabla V=0$ gives a strict local minimum at the origin and three saddle points, at $(0,1)$ and $(\pm \sqrt{3}/2,-1/2)$. All three saddle points have value $1/6$. Their common level set factors exactly:Thus this level set is the union of the three lines $y=-1/2$ and $y=1\pm \sqrt{3}x$. They bound an equilateral triangle containing the local minimum. The Hessian matrix is the identity at the origin; at each of the other three stationary points it has eigenvalues $3$ and $-1$. For energies $0\le E<1/6$, the central accessible region is bounded; above that value the three saddle passages allow paths from the centre to arbitrarily large radius. This follows directly from the radial potential: in each direction with $\sin (3\theta )<0$, its radial maximum occurs at $r=-1/\sin (3\theta )$, with value $1/[6{\sin }^2(3\theta )]\ge 1/6$.

The determinant of the Hessian matrix. For a twice continuously differentiable function of two variables, it is $f_{xx}{f}_{yy}-f_{xy}^2$. A negative value at a critical point implies a saddle point; a positive value combines with the sign of $f_{xx}$ in the second-derivative test. A zero value is inconclusive.

The finite-dimensional Newton root-finding iteration for a vector equation $G(x)=0$. At a point with invertible Jacobian matrix, solve the displayed linear system. For $G=\nabla F$, its Jacobian matrix is the Hessian matrix, giving Newton's method in optimization. The update solves the affine first-order approximation $G(x_k)+DG(x_k)s_k=0$; it can converge to any nondegenerate critical point, including a saddle point.

For a planar harmonic function, $u_{yy}=-u_{xx}$. Its Hessian matrix is therefore $\left(\begin{array}{cc}a& b\\ b& -a\end{array}\right)$, with eigenvalues $\pm \sqrt{a^2+b^2}$. At a stationary point with nonzero Hessian matrix determinant, both signs occur, so the point is a saddle point. A zero determinant requires separate treatment and is not covered by this nondegenerate test. The result is the local quadratic counterpart of the maximum principle for harmonic functions.

For one acoustic half-space and vacuum on the other side, a harmonic point force gives displacement amplitude $F\gamma /D$ and fluid acoustic velocity potential amplitude $i\omega F{e}^{-\gamma y}/D$. For time dependence $e^{-i\omega t}$, the outgoing acoustic square-root branch has $\gamma >0$ for $|k|>k_0$ and $\gamma =-i\sqrt{k_0^2-k^2}$ for $|k|<k_0$. The causal limit $\omega \mapsto \omega +i0$ places the positive guided-mode pole above the inversion contour and the negative pole below. The saddle point generates cylindrical radiation, whereas guided residues decay normally to the membrane.

For a real symmetric invertible matrix $H$, the full undamped Newton step for the displayed quadratic function sends every starting point to the unique stationary point:This follows because the gradient is affine and its first-order expansion is exact. If $H$ is a positive-definite matrix the result is the unique global minimum; a negative-definite matrix gives a global maximum, and an indefinite matrix $H$ gives a saddle point. Thus exact arrival does not by itself show that a minimization method has minimized anything. A line search, damping, or a positive-definite matrix replacing the Hessian matrix changes this exact one-step assertion.

Optimal truncation chooses how many terms to retain for a useful finite approximation. In a divergent asymptotic expansion, increasing the truncation order eventually makes the terms larger rather than smaller. Stopping near a smallest term often gives the best direct approximation, but the actual remainder must be checked. A small last term alone is not a universal error bound.^[ref]

For a divergent factorial series can approximate a convergent integral, $T_k=k!/z^k$ decreases while $k+1<z$ and increases while $k+1>z$. Thus the useful cutoff is near $k=z$, rather than at arbitrarily large order. At $z=10$, $T_9=T_{10}=0.00036288$ are the two smallest terms. Retaining $N=10$ terms givesThe actual error is about $0.0001770$. Retaining twenty terms instead gives $S_{20}(10)\approx 0.9076137084$, with error about $0.008020$: more work produces a worse answer.

For this example the bound $N!/z^N$ is explicit, so a requested tolerance can be tested before using a truncation. For a different integral, a nearby saddle point or simple pole can change the relevant remainder scale. This is why the smallest-term rule is a useful guide, rather than a replacement for remainder analysis.

The cutoff for factorial terms $n!z^{-n}$ has $n=|z|+O(1)$. Better analysis can expose contributions smaller than every retained inverse power, linking optimal truncation to the Stokes phenomenon. Such contributions can be important even when many asymptotic coefficients agree. Directly summing ever more terms does not automatically recover them.

A parabola is a plane curve whose points are equally distant from a focus and a directrix. In suitable coordinates it has equation $y=a{x}^2$, with $a\ne 0$. Its quadratic geometry can also describe a contour deformation through a saddle point.

For example, take a focus of a conic at $(1,0)$ and a directrix of a conic $x=-1$. Equality of squared Euclidean distances gives $(x-1{)}^2+y^2=(x+1{)}^2$, hence $y^2=4x$. The point $(1,2)$ has distance $2$ to both the focus and the directrix. Its eccentricity of a conic is one. Unlike an ellipse, a parabola is unbounded and has only one matched focus-directrix description.

For $x,y>0$, the signs needed for the phase portrait follow directly from the factorizations:The coordinate axes are invariant sets. On $y=0$, the logistic differential equation $\dot{x}=x(1-x)$ directs positive states toward the boundary saddle point $(1,0)$. On $x=0$, $\dot{y}=2y$ directs positive states upward. At the three equilibria, use the local directions found in part (ii); interior sample trajectories near $(2,1)$ spiral clockwise inward.

The nullclines prescribe where arrows become vertical or horizontal; they are generally not themselves trajectories. The image samples the vector field and several solutions, rather than assuming every nullcline is an invariant set.

Intersect the two nullcline families. The axes yield $(0,0)$ and $(1,0)$, and $y=1$ with $xy=2$ yields $(2,1)$. The possible remaining intersection would have $x+y=1$ and $xy=2$, requiring $x^2-x+2=0$, whose discriminant is $-7$. Hence there are no further real equilibria.

The Jacobian matrix isEvaluate it at each equilibrium:

All three are hyperbolic equilibria, so their classifications persist for the nonlinear system. Immediately to the right of $(2,1)$ on $y=1$, the velocity is vertically downward, showing that the attracting spiral turns clockwise.

Since the exponential factor is positive, equilibria must have $y=0$ and $x^4=1$. Thus $\boxed{(x,y)=(-1,0),(1,0)}$. At either point the Jacobian matrix is $\left(\begin{array}{cc}0& 1\\ -4x^3& 0\end{array}\right)$. At $(-1,0)$ its eigenvalues are $\pm 2$, so this is a saddle point. At $(1,0)$ they are $\pm 2i$: the linearization has a centre equilibrium.

The requested first-order approximation follows by putting $x=1+u$, $y=v$: $\dot{u}=v+O(\Vert (u,v){\Vert }^2)$ and $\dot{v}=-4u+O(\Vert (u,v){\Vert }^2)$. The linearized system conserves $4u^2+v^2$, giving the approximate ellipsesHowever, the printed nonlinear system has a weak repelling focus at $(1,0)$, rather than a centre. A centre in the linearization need not be a nonlinear centre. Here that distinction can be proved explicitly, without relying on the numerical drift in the figure.

Put $X=2(x-1)$, $Y=y$, $\tau =2t$ and $r^2=X^2+Y^2$. The weak focus of an exponential polynomial planar system has the local positive functionExpanding the vector field through cubic order and differentiating givesThe cubic correction cancels the cubic terms in the derivative of $H$, and the quartic correction leaves the positive radial term $3r^4/16$. Since $H=r^2/2+O(r^3)$ is positive and the angular velocity stays near $-1$, small nonzero trajectories spiral outward. Equivalently the reversed system has a strict local Lyapunov function and an asymptotically stable equilibrium. In particular, a periodic orbit sufficiently near the equilibrium is impossible, because $H$ would have to increase strictly and return to its starting value. This proves the failure of the printed centre assertion while retaining its correct linearized ellipse calculation.

A transition structure is a saddle point on the potential-energy surface: motion along the reaction coordinate lowers energy in either direction. It has one unstable vibrational direction and no intermediate residence basin.

An intermediate is a local minimum, separated from neighboring states by barriers, with a finite lifetime. It may be short-lived, but that does not make it a transition structure. The elementary SN2 reaction step has a transition structure and no distinct bonded intermediate.

At a smooth interior stationary point, define $D=t_{11}{t}_{22}-t_{12}^2$. The second-derivative test gives a minimum for $D>0,t_{11}>0$, a maximum for $D>0,t_{11}<0$, and a saddle point for $D<0$; $D=0$ is inconclusive.

For the stated time function, putPositive physical speeds make all three coefficients positive. The positive Hessian of a layered travel-time functional here isThus the stationary path is a strict minimum, not merely a candidate of unspecified type. In fact the same positivity holds for all finite crossing positions, so the time function is strictly convex and the minimum is unique.

For a differentiable function at an interior stationary point, both first partial derivatives vanish. If the second derivatives are continuous, form the symmetric Hessian matrixThe second-derivative test gives a strict local minimum if $D>0$ and $f_{xx}>0$, a strict local maximum if $D>0$ and $f_{xx}<0$, and a saddle point if $D<0$. If $D=0$, higher-order terms must be examined. For example, $x^4+y^4$, $-x^4-y^4$ and $x^4-y^4$ all have zero Hessian matrix at the origin but respectively a minimum, maximum and saddle. These are local interior criteria; boundary extrema require separate treatment.