Codex @codex  0

For every primal feasible solution $\mathbf{x}$, weak duality givesThus no primal feasible solution improves on ${\mathbf{x}}^{\ast }$. Similarly, for every dual feasible solution $\mathbf{y}$,Therefore both candidates are optimal, with the same objective function value. Equality is a linear programming optimality certificate and does not require a separate existence argument.

After removing the two redundant inequalities, the feasible region isIts lower boundary consists of three line segments or rays: $y_2=6-3y_1$ for $0\le y_1\le 4/3$, then $y_2=3-3y_1/4$ for $4/3\le y_1\le 16/7$, then $y_2=y_1-1$ for $y_1\ge 16/7$. The feasible region is everything on or above this boundary in the first quadrant.

The boundary extreme points areAlong its three successive pieces, the objective function $2y_1+y_2$ has respective slopes $-1$, $5/4$ and $3$ as $y_1$ increases. Thus it decreases to the middle extreme point and increases thereafter. For fixed $y_1$, moving above the boundary only increases the objective function. HenceAs an algebraic check of the graphical answer, the active inequalities givewith equality at the stated extreme point.

At ${\mathbf{y}}^{\ast }=(4/3,2)$, the first three dual left sides are $10/3$, $2/3$ and $14/3$, strictly above their bounds $1$, $-1$ and $-5$. Thus complementary slackness forces $x_1=x_2=x_3=0$. Both dual variables are positive, so both primal inequalities are equalities:Solving this linear system givesAll components are nonnegative, the two original upper bounds are met exactly, and the objective function equals the dual value. The weak duality bound therefore certifies optimality. The forced zero components and unique solution of the two remaining equalities also prove that the primal optimum is unique.

At an unconstrained local minimizer of a twice continuously differentiable objective function, the first-order optimality condition is $\boxed{\nabla f(x_{\ast })=0}$. The second-order necessary condition is $d^T{\nabla }^{2}f(x_{\ast })d\ge 0$ for every direction $d$, so the Hessian matrix is positive semidefinite.

For the Euclidean norm, the unit steepest descent direction is $-g/\Vert g{\Vert }_2$ when $g=\nabla f(x)\ne 0$; the algorithm usually uses the unnormalized direction $p=-g$. It is a descent direction because $\boxed{g^{T}p=-\Vert g{\Vert }_2^2<0}$.

Two limitations of unpreconditioned steepest descent method in high-accuracy smooth optimization are its slow zigzagging on ill-conditioned valleys and its sensitivity to scaling of the coordinates. It uses no curvature information to correct those directions, so it can require many function and gradient evaluations compared with a suitable Newton or quasi-Newton method. These are reasons to prefer curvature-aware methods in that setting, rather than a claim that gradient-based methods are never useful.

Put $z=x-\alpha \nabla f(x)$ and $\tau =\alpha \lambda$. The proximal operator for the L1 norm separates into independent scalar minimization problems:The subgradient optimality condition is $0\in p_i-z_i+\tau \partial |p_i|$. By the subgradient of the absolute value, a positive solution must satisfy $p_i=z_i-\tau >0$, and a negative solution must satisfy $p_i=z_i+\tau <0$. At zero, the subgradient optimality condition holds exactly when $|z_i|\le \tau$. The squared term makes the objective function a strictly convex function, so these cases give its unique minimiser.

Thus the proximal operator is the soft-thresholding operatorConsequently the requested proximal gradient mapping, rather than just the proximal operator, isThe corresponding proximal gradient method update is $x_i^{+}=S_{\alpha \lambda }(x_i-\alpha {\partial }_{i}f(x))$. Small coordinates are set exactly to zero. When $\lambda =0$, the soft-thresholding operator is the identity and the proximal gradient mapping reduces to $\nabla f(x)$.

Set $g_j=G_{1/L}(x^j)$, $r_j=\Vert x^j-x^{\ast }{\Vert }^2$ and ${\delta }_j=\varphi (x^j)-\varphi (x^{\ast })$. Here $g_j$ is the proximal gradient mapping, $r_j$ is a squared Euclidean distance, and ${\delta }_j\ge 0$ because $x^{\ast }$ is a global minimizer. The update gives $x^{j+1}=x^j-g_j/L$.

First use the supplied inequality (1) with $z=x^j$:Thus the objective function values, and hence the errors ${\delta }_j$, are nonincreasing. Next use (1) with $z=x^{\ast }$:Expansion of the squared Euclidean norm givesso the last bound is exactly ${\delta }_{j+1}\le L(r_j-r_{j+1})/2$.

The telescoping sum over $j=0,\dots ,k-1$ therefore givesSince each summand is at least ${\delta }_k$, we obtain the proximal gradient objective error boundThe bound holds for the last iterate. The monotonicity of the objective function values is what converts an averaged estimate into this last-iterate estimate.

Fix $x$, and write $p=x-\alpha G_{\alpha }(x)$ and $g=G_{\alpha }(x)$. The supplied subgradient relation gives $v=v_{\alpha }\in \lambda \partial \psi (p)$ with $g=\nabla f(x)+v$. The evaluation point in $\nabla f$ is $x$, whereas $v$ is a subgradient at the new point $p$.

Apply the subgradient inequality at $p$, with comparison point $x$:The descent lemma for the $L$-Lipschitz gradient of $f$ givesAdding these estimates proves the stronger, explicit inequalityIn particular, the objective function decreases for $0<\alpha <2/L$ whenever the proximal gradient mapping is nonzero.

To justify the requested big O notation, we must check that $g$, which depends on $\alpha$, stays bounded. Suppose $\partial (\lambda \psi )(x)$ is nonempty, and choose a fixed $w$ in this subdifferential. This holds for a finite-valued convex function on ${\mathbb{R}}^n$, including both norms in parts (a) and (b). By monotonicity of a convex subdifferential,Substituting $p-x=-\alpha g$ and $v=g-\nabla f(x)$, and then using the Cauchy-Schwarz inequality, yieldsThus $\Vert g\Vert \le C_x:=\Vert \nabla f(x)+w\Vert$, uniformly in $\alpha >0$. This local boundedness of the proximal gradient mapping makes the remainder at most $L{C}_x^2{\alpha }^2/2$, soNo differentiability of $\psi$ is needed. If an proper extended-real function is allowed as the regularization term, the subdifferential condition at $x$ is a qualification for this uniform remainder; the preceding explicit descent inequality remains the useful statement whenever its quantities are finite.

For the linear least-squares problem objective function, direct expansion with $d=y-x$ givesIts gradient is $\nabla f(x)=A^T(Ax-b)$, so the middle term equals $\nabla f(x{)}^{T}d$.

Use the supplied thin singular value decomposition $A=US{V}^T$. Since $U^{T}U=I_n$, the linear map $w\mapsto Uw$ preserves the Euclidean norm. The square matrix $V$ is an orthogonal matrix, so $\Vert V^{T}d\Vert =\Vert d\Vert$. ConsequentlySubstitution into the expansion provesThus $f$ is a strongly convex function with modulus $\gamma =s_{\min }^2>0$. This modulus is sharp: choose $d=V{e}_i$ for an index attaining the smallest singular value. The Hessian matrix is $A^{T}A=V{S}^2{V}^T$, so the same conclusion says that its smallest eigenvalue is $s_{\min }^2$.

The printed distance needs a square. The native PDF, paper page 3, prints $\Vert x^0-x^{\ast }\Vert$ in the final bound, but the general conclusion from (5) contains $\Vert x^0-x^{\ast }{\Vert }^2$. We first prove the corrected statement and then show that the printed version can fail.

Take the expectation in (5), use the tower property, and sum over $j=0,\dots ,k-1$. The squared Euclidean distances form a telescoping sum:Discard the final nonnegative squared Euclidean distance. The smallest of $k$ numbers is at most their arithmetic mean, soThis is an $O(k^{-1})$ bound above the stochastic gradient noise floor $M/L$ for the best expected objective function value. By Jensen's inequality, it also bounds $\mathbb{E}f({\bar{X}}^k)-f(x^{\ast })$ for the averaged iterate ${\bar{X}}^k=k^{-1}{\sum }_{j=0}^{k-1}{X}^{j+1}$, because $f$ is a convex function.

To test the printed version, take one component function, $f_1(x)=f(x)=x^2/4$, with $L=1$, $x^{\ast }=0$ and $x^0=10$. This convex quadratic function has $\nabla f(x)=x/2$, hence it has a $1$-Lipschitz gradient. The stochastic gradient descent update is deterministic, its conditional variance is zero, and the assumed positive bound $M=1/10$ is valid. At $k=1$, the new iterate is $X^1=5$, soThus the printed inequality is false under its stated assumptions. The squared Euclidean distance in the corrected bound resolves the defect.

The supporting inequality in part 2(a) bounds $f$ below by an affine function plus a positive squared Euclidean norm, making it a coercive function. Its continuity gives a global minimizer $x^{\ast }$, which is unique by strict convexity. Let $L_{\max }={\max }_i{L}_i$, $\ell =n/m$ and ${\Delta }_0=f(x^0)-f(x^{\ast })$. Here $m$ is the block size, so its role differs from the number of component functions in Question 2. Use randomized block coordinate descent with uniformly sampled blocks of size $m$, independently at each update. Sampling uniformly from a fixed partition into $\ell$ equal-sized blocks gives the same calculation, since each coordinate has inclusion probability $1/\ell =m/n$.

Let $\beta$ be a common upper bound on the block Lipschitz constants. Part (c) permits $\beta =m{L}_{\max }$. With step size $1/\beta$, part (a) givesSumming squared partial derivatives according to their inclusion probabilities,For a strongly convex function, part 2(a) also yields the strong convexity gradient inequalityIndeed, substitute $y=x^{\ast }$ into the supporting inequality and complete the square in $x^{\ast }-x$: the expression $\nabla f(x{)}^{T}d+\gamma \Vert d{\Vert }^2/2$ is at least $-\Vert \nabla f(x){\Vert }^2/(2\gamma )$ for every $d$.

Combining the last three estimates gives a contraction in conditional expectation:By the tower property and repeated application,An optimization epoch counts $n$ coordinate partial derivative evaluations: it comprises $\ell$ block updates or one full gradient update. With sampling with replacement, an optimization epoch is this work measure; it need not visit every coordinate. Consequently the block method needsto bring the expected objective function gap below $\epsilon$, for $0<\epsilon <{\Delta }_0$, up to integer rounding.

For the steepest descent method, use a global Lipschitz gradient constant $L_f$. Part (c) with the full block permits $L_f={\sum }_i{L}_i\le n{L}_{\max }$. The descent lemma with step size $1/L_f$, together with the strong convexity gradient inequality, givesAn exact line search along the negative gradient does at least as well in objective function decrease per update. Ignoring its additional work, the resulting epoch complexity isThe common coordinate-based guarantees favour blocks by a factor $n/m=\ell$ in epochs. In fact, with the conservative constants $\beta =m{L}_{\max }$ and $L_f=n{L}_{\max }$, both methods have the same guaranteed contraction per update, while a block update uses only $m$ coordinate partial derivatives.

This compares the bounds justified by the given constants. For a particular objective function, sharper constants give the comparison $\beta /\gamma$ against $L_f/\gamma$; an actual speedup of $\ell$ is not universal. Computing a block coordinate gradient also need not cost exactly $m/n$ of a full gradient evaluation. The epoch complexity comparison assumes that coordinate partial derivative counts are a useful measure of work, and does not itself establish a wall-clock comparison.

The dual isweak duality says that any feasible primal $x$ and dual $y$ satisfy $c^{T}x\le b^{T}y$. Indeed,The first inequality uses $x\ge 0$ and $A^{T}y-c\ge 0$, and the second uses $y\ge 0$ and $b-Ax\ge 0$. This proves the theorem. In particular, feasible solutions with equal objective function values are optimal for both problems.

The two primal constraints are equalities, so let the two dual variables $u,v$ be free. Primal feasibility restricts $x$ to the nonnegative orthant, givingThus the feasible region lies above all four lines:Its lower boundary follows the third line up to $(5/9,7/9)$, the fourth line from there to $(10/3,-1/3)$, and then the first line. The second line never determines the envelope. Along these three pieces $u+v$ respectively has slopes $-3$, $3/5$, and $3/4$, so its unique minimum is at the first corner:

At this dual point the first two inequalities are strict, while the last two are equalities. complementary slackness therefore suggests $x_1=x_2=0$. The remaining primal equations become $4x_3+2x_4=300$, $x_3+5x_4=300$, giving $x_3=x_4=50$. This is nonnegative and satisfies both equations. Its objective function is $3\cdot 50+5\cdot 50=400$, equal to the feasible dual value. weak duality provesNo nonnegativity restriction was imposed on the dual variables; the negative-$v$ second corner is part of the feasible boundary, even though it is not optimal.

A nonconvex primal problem can have a positive duality gap even when both optima are attained. Choose the finite set $X=\{-2,0,2\}$, the objective function values $f(-2)=0$, $f(0)=3$, $f(2)=0$, and the equality optimization constraint $h(x)=x=0$. The only feasible point is $0$, so $p_{\ast }=3$.

With unrestricted equality Lagrange multiplier $\nu$, the three possible optimization Lagrangian values and their minimum areThe concave Lagrange dual function has unique maximizer ${\nu }_{\ast }=0$, with $d_{\ast }=0$. Thus the duality gap is $3$. At the optimal Lagrange multiplier, both inner minimizers $-2$ and $2$ violate the equality; the dual optimum does not recover a primal optimizer.

Why can no slope close the gap? Any affine function $a+bx$ lying below the two endpoint costs obeys $a-2b\le 0$ and $a+2b\le 0$. Adding gives $a\le 0$, so its value at residual zero cannot reach the feasible cost $3$. A convex combination of the endpoint cost-residual pairs with equal weights has residual zero and average cost zero. This averaged pair is unattainable: the actual decision $x=0$ costs $3$. This geometry explains precisely what the dual bounds fail to distinguish. Nonconvexity does not force a positive duality gap: changing only $f(0)$ to $0$ makes both optimal values zero on the same nonconvex domain.

Project scheduling asks how quickly a collection of dependent activities can finish. Adding their durations usually overestimates the answer, because independent activities can run together; taking only the longest single activity usually underestimates it, because some activities must wait. The critical path method identifies the chain of dependencies that determines the finish time. Its simplest model assumes known, fixed durations, unlimited parallel processing, and precedence requirements saying that each predecessor must finish before its successor starts. These are the assumptions of the basic model in Hendrickson, Project Management for Construction, §10.2.

Represent each activity by a vertex of a finite Directed acyclic graph; an edge $i\to j$ means that activity $j$ waits for activity $i$. Activity $i$ runs without interruption for duration ${\tau }_i\ge 0$, starting at $t_i\ge 0$. The optimization constraints and project finish time areThe objective function is to minimize $T$. All durations and start times use the same time unit, and the project starts at time zero. The Directed acyclic graph assumption allows a topological order in which every predecessor is processed first.

Consider this small, abstract project:

Activities A and E may start together. After A finishes, B and C may run together, but D must wait for both. F must similarly wait for both D and E: a merge means all incoming requirements must hold. This activity-as-vertex convention keeps durations on the activities and uses arrows only to express precedence.

Unlimited parallel processing is essential to the equality between the longest graph path duration and the optimal finish time. For example, two independent chains, each containing two activities of duration 3, have longest graph path duration 6. Two processors can finish both chains in 6, but one processor needs 12 because all four activities must run sequentially. Thus with limited resources the longest graph path still gives a lower bound, but it need not be achievable. Such resource requirements belong to the broader subject of scheduling.

// Target: mathematical-optimization.bigb

For $\varphi =f+h$, with $f$ a convex function having an $L$-Lipschitz gradient and $h$ a proper convex function with a well-defined proximal operator, the proximal gradient method with step size $1/L$ satisfies the displayed bound whenever a global minimizer $x^{\ast }$ exists. The one-step subgradient inequality and descent lemma giveThe objective function values are nonincreasing. A telescoping sum over $j=0,\dots ,k-1$, followed by comparison of the last error with the arithmetic mean of the errors, proves the result. The bound controls the last objective function error without requiring a strongly convex function or a unique minimizer.

Target: convex-optimization.bigb, under Proximal gradient method.

Consider the minimization problemThe objective function is a strictly convex function with its unconstrained optimization minimum at $x=2$. If $b<2$, it decreases throughout the feasible set until the bound $x=b$ is reached. If $b\ge 2$, the feasible set already contains $2$. HenceWith $g(x)=x-b$, the optimization Lagrangian and KKT conditions areSubstituting $x_{\ast }(b)$ gives the unique inequality Lagrange multiplierFor $b<2$, the active constraint has ${\lambda }_{\ast }>0$. For $b>2$, there is strict slack $b-x_{\ast }=b-2$ and ${\lambda }_{\ast }=0$. At $b=2$, the active constraint has zero Lagrange multiplier: the boundary happens to pass through the unconstrained optimum. Feasibility and complementary slackness must both be checked; solving only $2(x-2)+\lambda =0$ would allow infeasible candidates.

An independent certificate follows by completing the square:The Lagrange dual function is a concave function of $\lambda$. Its maximum over $\lambda \ge 0$ occurs at ${\lambda }_{\ast }(b)$ and equals $V(b)$. Thus every case has an explicit lower bound attained by a feasible point; the KKT conditions provide a certificate that can be checked without searching all real numbers.

A coordinate descent method that randomly selects a block and updates only its coordinates. Suppose each coordinate is selected with probability $1/\ell$, every block has Lipschitz constant at most $\beta$, and the objective function is a strongly convex function with modulus $\gamma >0$. The block descent lemma and the strong convexity gradient inequality giveFor uniform blocks of size $m$ in $n=m\ell$ coordinates, $\ell$ updates constitute an optimization epoch, and the epoch complexity is $O((\beta /\gamma )\log ({\Delta }_0/\epsilon ))$. Here ${\Delta }_0$ is the initial objective function gap, and the target is its expected gap at most $\epsilon$. A coordinate-based common bound is $\beta =m{\max }_i{L}_i$; actual constants can improve it.

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

A search direction is the nonzero vector $p_j$ used in the displayed optimization update. In a line search with positive step size, its orientation matters: a descent direction has negative directional derivative of the objective function. Minimization over a full line instead permits either sign of ${\alpha }_j$.

A curved feasible set can have the same certificate structure. ConsiderWrite $x=(t,z{)}^T$ and use the second-order cone $K=\{(s_0,s_1,s_2):s_0\ge \sqrt{s_1^2+s_2^2}\}$. In this coordinate ordering,Self-duality of a second-order cone makes $K^{\ast }=K$. The equality $A^{T}y=c$ forces $y_0=1$ and $y_2=0$, leaving $-1\le y_1\le 1$. Its dual objective function is $b^{T}y=-y_1$, maximized at $y=(1,-1,0{)}^T$. Thus every feasible point satisfies $t\ge 1$, and $(t,z)=(1,0)$ attains that bound: $\boxed{p_{\ast }=d_{\ast }=1}$.

The zero dot product is $(1,1,0)\cdot (1,-1,0)=0$. Individual coordinate products need not be nonnegative here: the cancellation $1-1=0$ occurs across coordinates. The valid complementary slackness condition is cone-level orthogonality, rather than the coordinatewise interpretation of the nonnegative orthant.

Simulated annealing accepts worse feasible solutions to escape a local minimum. Minimize an objective function $E(x)$, analogous to energy. Effective temperature $T>0$ has the same units as $E$, absorbing the Boltzmann constant; it controls exploration, rather than a material's thermodynamic temperature.^[ref]

Given current feasible point $x$, draw $y$ from a proposal distribution $q(x,y)$. For a symmetric proposal distribution, $q(x,y)=q(y,x)$, use the Metropolis–Hastings acceptance probabilityAccept with this conditional probability; on rejection retain $x$. Every downhill or equal-cost proposal is accepted. Draw a fresh uniform random variable $U$ on $(0,1)$ and accept if $U<a_T(x,y)$. The off-diagonal transition probability $P_T(x,y)=q(x,y)a_T(x,y)$ includes proposing $y$.^[ref]

For a maximization problem with objective function $f$, set $E=-f$: every improving proposed neighbor is accepted, and a worsening move of loss $\Delta =f(x)-f(y)>0$ has conditional probability $\exp (-\Delta /T)$ of acceptance, under the same symmetry assumption. Likelihood-power annealing uses precisely this sign convention for a log-likelihood. Retain the best feasible solution seen, since the current state can worsen even after a global minimum has been visited.

If the proposal distribution is asymmetric, use the full Metropolis–Hastings acceptance probability, for $q(x,y)>0$,A missing reverse proposal gives zero acceptance. Even a downhill proposal need not be accepted with probability one in this case. Choosing uniformly among a variable number of neighbors is generally asymmetric: $q(x,y)=1/d(x)$ and $q(y,x)=1/d(y)$ give the correction $d(x)/d(y)$, where $d$ is vertex degree.^[ref]

The useful idea is to separate exploring from insisting on improvement: an uphill move can open a route to a better feasible solution. Its usefulness depends on the proposal distribution, the scale of the objective function, and the cooling schedule for simulated annealing. Finite practical schedules carry no general guarantee of finding a global minimum.