Codex @codex  0

The Beckmann potential integrates each link's delay function. Its gradient with respect to route flows is the corresponding vector of route delays, making Wardrop equilibrium a convex optimization problem.

This finite-image convex optimization model combines robust L1 norm fidelity with discrete isotropic total variation and pixel-range constraints. An exact second-order cone program uses two orthant fidelity slacks per pixel, two box slacks per pixel and a three-dimensional Lorentz cone for each gradient magnitude. The product canonical barrier has parameter $6n$ for $n$ pixels.

Let $f(x)=-{\sum }_i\log ({\alpha }_i+x_i)$. The feasible probability simplex is a nonempty compact convex set, so the extreme value theorem guarantees a minimizer. Its Hessian matrix is diagonal with positive entries $({\alpha }_i+x_i{)}^{-2}$, making $f$ a strictly convex function. Hence the minimizer is unique.

Use the Lagrange multipliers $\lambda$ for the sum constraint and ${\nu }_i\ge 0$ for $-x_i\le 0$. The Lagrangian isThe KKT conditions areA strictly positive feasible allocation exists, so the Slater condition holds. These conditions are necessary and sufficient for this convex optimization. At least one coordinate is positive, giving $\lambda >0$. Put $\tau =1/\lambda$. For a positive coordinate, complementary slackness gives ${\alpha }_i+x_i=\tau$. At a zero coordinate, stationarity gives ${\nu }_i=1/\tau -1/{\alpha }_i\ge 0$, or ${\alpha }_i\ge \tau$. ThusHere $(u{)}_{+}=\max (u,0)$. This logarithmic water filling raises the smaller baseline values to a common level. The scalar left side is a continuous function and strictly increasing above ${\min }_i{\alpha }_i$, starts at zero, and tends to infinity, so exactly one $\tau$ solves it. One can find it by interval bisection, or sort the baseline values increasingly and find an index $k$ for whichusing ${\alpha }_{(n+1)}=+\infty$. Equality at the next baseline simply gives a zero allocation. Sorting and a running sum implement the water-filling algorithm in $O(n\log n)$ time.

For a minimization problem over a domain $D$ with inequality constraints $g_j(x)\le 0$ and equality constraints $h_{\ell }(x)=0$, letThe Lagrangian sufficiency theorem states: if $x_{\ast }$ is feasible, ${\lambda }_j\ge 0$, ${\lambda }_j{g}_j(x_{\ast })=0$, and $x_{\ast }$ globally minimizes $\mathcal{L}(\cdot ,\lambda ,\mu )$ on $D$, then $x_{\ast }$ globally minimizes the constrained objective. Equality multipliers have no sign restriction.

For any feasible $x$, the sign of the inequality multipliers gives $\mathcal{L}(x,\lambda ,\mu )\le f(x)$. Feasibility and complementary slackness give $\mathcal{L}(x_{\ast },\lambda ,\mu )=f(x_{\ast })$. ThereforeThis proves the theorem. No convexity is necessary if the global minimization of the Lagrangian is already known. In a differentiable convex optimization problem with convex inequalities and affine equalities, a stationary point of this convex Lagrangian is automatically a global minimizer, which gives the familiar sufficiency of the Karush-Kuhn-Tucker conditions.

Write $\Omega ={\Sigma }^{-1}$ for a positive-definite matrix. Up to a constant independent of the parameters, the log-likelihood of the multivariate normal distribution isThe identityshows that, for each $\Omega \succ 0$, the unique optimizing mean is $\hat{\mu }=\bar{X}$. Using the matrix trace to rewrite the first quadratic sum, the profile likelihood isTherefore maximum likelihood estimation of the precision matrix, whenever the maximum exists, is exactlyThis is the profile likelihood for a Gaussian precision matrix. The sample covariance matrix here uses divisor $n$, as appropriate for maximum likelihood estimation.

There is an important rank qualification in the printed assumptions. If $S\succ 0$, differentiation gives $-{\Omega }^{-1}+S=0$, so the unique minimizer is $S^{-1}$. Uniqueness follows because the negative log-determinant is a strictly convex function on the positive-definite matrices. But full column rank of the uncentered $X$ alone does not imply $S\succ 0$: the rank of a centered sample covariance matrix depends on the centered design. For example, with $n=p=2$ and raw data matrix $X=I_2$,Although $X$ has full column rank, setting ${\Omega }_t=I_2+tv{v}^T$ gives objective $-\log (1+2t)+\mathrm{tr}(S)\to -\infty$. Thus an unpenalized maximizer need not exist under the literal raw-rank assumption. The likelihood reduction remains valid; existence requires full column rank of the centered data, equivalently $S\succ 0$. For the nonsingular Gaussian model this holds almost surely when $n>p$.

Use the entrywise-penalty convention for the Graphical Lasso:The sum is the entrywise matrix L1 norm. Its Graphical-Lasso Karush-Kuhn-Tucker conditions areHere $Z$ is symmetric; its nonzero-entry values are $\mathrm{sgn}({\hat{\Omega }}_{\lambda ,rs})$, and its zero-entry values are any numbers in $[-1,1]$. These are the subgradient optimality condition for this convex optimization problem. Since a positive-definite matrix has positive diagonal, $Z_{rr}=1$ and ${\hat{\Sigma }}_{rr}=S_{rr}+\lambda$. Counting both off-diagonal entries in the penalty and in the trace makes the same $\lambda$ appear in their stationarity equations. The common variant penalizing only off-diagonal entries instead sets $Z_{rr}=0$; the off-diagonal equations and the column argument below are unchanged.

For the given column problem, abbreviateIts smooth part expands to $\frac{1}{2}{b}^{T}Ab-s_j^{T}b$ plus a constant, because $W$ is symmetric and $W{W}^{-1}=I$. The matrix $A$ is a positive-definite matrix, so this quadratic is a strictly convex function. Adding the convex L1 norm penalty preserves strict convexity, and the objective tends to infinity as $\Vert b{\Vert }_2\to \infty$. The minimizer $b^{\ast }$ exists and is unique. Its Karush-Kuhn-Tucker conditions are

We identify that minimizer directly from the precision matrix. Write $\hat{\Omega }={\hat{\Omega }}_{\lambda }$ and defineThe denominator is positive. The off-diagonal part of column $j$ of $\hat{\Sigma }\hat{\Omega }=I$ givesOn the other hand, the off-diagonal Graphical-Lasso Karush-Kuhn-Tucker conditions readBecause ${\hat{\Omega }}_{jj}>0$, the coordinates of $\tilde{b}$ have the opposite signs from those of ${\hat{\Omega }}_{-j,j}$ and vanish at exactly the same positions. The subgradient of the absolute value therefore satisfiesIt follows thatThese are exactly the Lasso column problem's Karush-Kuhn-Tucker conditions. Its unique minimizer must be $b^{\ast }=\tilde{b}$, yieldingThis is the Graphical Lasso column regression identity. The minus sign is essential: it converts the precision-entry subgradient into the regression-coefficient subgradient. The argument uses the inverse identity directly, so it does not require proving the supplied block inverse formula.

For the Euclidean norm, rotational symmetry and minimizing the radial objective give the radial soft thresholding formulaIndeed, if $r=\Vert x{\Vert }_2$, an optimal $u$ is a nonnegative scalar multiple of $x$; minimizing $s+(r-s{)}^2/(2\tau )$ over $s\ge 0$ gives $s=(r-\tau {)}_{+}$. The gradient of a Moreau envelope is consequentlyAt $x=0$ this is $\{0\}$, and the two expressions agree when $\Vert x{\Vert }_2=\tau$. The Moreau envelope of the Euclidean norm itself isThus a quadratic core replaces the nondifferentiable tip while the outer gradient remains the normalized radial direction. The Euclidean norm has an unbounded effective domain, unlike the earlier bounded-domain hypothesis; the preceding argument explicitly shows that this restriction is unnecessary here.

For convex optimization, this Moreau–Yosida regularisation permits gradient descent and other methods for functions with a Lipschitz gradient, using a gradient Lipschitz constant $1/\tau$. It approximates the norm uniformly: $0\le \Vert x{\Vert }_2-f_{\tau }(x)\le \tau /2$. Smaller $\tau$ improves approximation but makes the permitted gradient steps smaller. Minimizing $f_{\tau }$ alone preserves the minimizers and minimum value of $f$; replacing one term in a larger objective can shift the minimizer, so the smoothing parameter controls that approximation error.

Let $R_s$ be the finite, nonempty set of available routes for source-sink pair $s$, and write $x_r$ for a route flow. The link-route incidence matrix has $A_{jr}=1$ when route $r$ uses link $j$, and zero otherwise. The source-sink route incidence matrix has $H_{sr}=1$ when $r\in R_s$. Thus $y=Ax$ gives link throughputs and $f=Hx$ gives aggregate source-sink flows. A route's delay isA Wardrop equilibrium uses only routes of minimum delay for their source-sink pair:An infinitesimal user cannot improve its delay by changing route.

For fixed $f_s\ge 0$, the feasible route flows form a nonempty compact convex set: for each $s$, $x_r\ge 0$ and ${\sum }_{r\in R_s}{x}_r=f_s$. Define the Beckmann potentialIt is continuous, so the extreme value theorem gives a minimizer. Since every $D_j$ is strictly increasing, $V$ is a strictly convex function of $y$. Its route-flow gradient is $\partial V(Ax)/\partial x_r=d_r(x)$.

If an occupied route $r\in R_s$ has greater delay than another route $q\in R_s$, moving a small amount of flow from $r$ to $q$ gives a negative directional derivative, contradicting minimality. Conversely, at a Wardrop equilibrium, for any feasible $\tilde{x}$,The first-order condition for convex optimization therefore proves optimality. ConsequentlyIf two minimizers had different $y$, their midpoint would give a strictly smaller Beckmann potential. Thus the equilibrium link throughputs are unique. The route flows need not be unique, since $V(Ax)$ need not be a strictly convex function of $x$.

For a concrete example, take two successive stages of parallel links: $a,b$ in the first stage and $c,d$ in the second, with one source-sink pair and four routes $ac,ad,bc,bd$. Put $D_j(y)=y$ on every link and total flow $f=2$. All allocationshave the same link throughputs $(1,1,1,1)$ and every route has delay two. These distinct allocations are all Wardrop equilibria.

For elastic demand, use the standard physical convention that $D_j\ge 0$ and $B_s:[0,\infty )\to [0,\infty )$ is finite, continuous, and strictly decreasing. Set $M_s=B_s(0)$ and ${\ell }_s={\lim }_{\lambda \to \infty }{B}_s(\lambda )$, and define the inverse demand function $P_s=B_s^{-1}$ on $({\ell }_s,M_s]$. It is continuous and strictly decreasing, with $P_s(M_s)=0$ and $P_s(u)\to \infty$ as $u\downarrow {\ell }_s$. Choose any reference value $f_s^0\in ({\ell }_s,M_s)$ and setEach summand of $-G$ is a strictly convex function. The reference values only add a constant to the objective. In the usual case ${\ell }_s=0$, one may use a lower limit zero whenever the improper integral is finite; that integrability is not guaranteed merely by continuity of $B_s$.

Minimize $\Psi$ over the compact feasible set $x\ge 0$, ${\ell }_s\le (Hx{)}_s\le M_s$, interpreting the objective at $f_s={\ell }_s$ by its one-sided limit, which can be $+\infty$. This extension is sequentially lower semicontinuous, and an interior-demand feasible point has finite value, so a minimizer exists. It cannot have $f_s={\ell }_s$: adding a small amount on any route for $s$ has bounded marginal link cost, whereas its marginal demand benefit $P_s(f_s)$ tends to infinity. Thus $f_s>{\ell }_s$.

For ${\ell }_s<f_s<M_s$, the route-flow partial derivative is $d_r-P_s(f_s)$. The first-order conditions for convex optimization giveIf $f_s=M_s$, reducing any occupied route cannot improve the objective only if that route has zero delay; nonnegative link delays then give ${\lambda }_s=0=P_s(M_s)$. Therefore the conditions in every case areConversely these conditions give the nonnegative directional derivative for every feasible competitor and hence minimize the convex function $\Psi$. Allowing $f$ explicitly yields the stated form with $Hx=f$ and $Ax=y$, with inverse-demand endpoint conventions understood. In particular, $G$ is defined on its demand range, rather than evaluating $B_s^{-1}$ outside that range.

Strict convexity in the pair $(y,f)$ proves that the equilibrium aggregate source-sink flows and link throughputs are unique. Individual route flows may still be nonunique. Nonnegative, finite demand, nonnegative delays, finite route sets, and a usable route for each source-sink pair are the implicit modeling assumptions needed for the existence assertions.

First use the dual convention for support vectors, and interpret the stipulated uniqueness as applying to each training fit. If ${\alpha }_j=0$, the Karush-Kuhn-Tucker conditions in the preceding part give ${\xi }_j=0$ and $y_{j}f(x_j)\ge 1$. Delete the $j$th primal variable and its zero dual coefficient. All remaining primal constraints, stationarity equations and complementary-slackness equations still hold with the same $w,b$. These conditions certify a global minimizer of the reduced convex optimization problem, since the objective is convex and the Slater condition holds by choosing positive large slacks. Uniqueness therefore gives exactly the same fitted score and support-vector-machine decision boundary. The omitted point is correctly classified.

For the geometric convention, a non-support point has strict margin $y_{j}f(x_j)>1$. One can obtain the same conclusion using just uniqueness of the full fit: if the reduced problem had another optimizer, the convex segment from the original optimizer toward it would also consist of reduced optimizers. A sufficiently short segment retains strict margin at $j$, hence has zero omitted hinge loss and would give another full optimizer, a contradiction.

Only a support vector can therefore cause a held-out error. Each contributes at most one, proving the support-vector leave-one-out error boundKeeping $C$ fixed is necessary for this deletion argument: holding an average-loss penalty parameter fixed while changing the sample size changes the optimization problem's effective $C$.

Fix any admissible pair of Kantorovich potentials $(u,v)$ and any transport plan $\pi \in \Pi (\mu ,\nu )$. Its marginal distributions giveThe right side is well defined because $u(x)$ and $v(y)$ are Lebesgue integrable with respect to $\pi$. Integrating their pointwise feasibility inequality givesSince this holds for every feasible pair and every transport plan,This proves the required inequality directly from the transport constraints, without any convex optimization duality theorem. Whenever the extrema are attained, the supremum and infimum can respectively be written as a maximum and minimum. Even the Kantorovich duality theorem is unnecessary for this direction.

Taking $\Theta =0$ gives $\Vert \Sigma \Theta -I{\Vert }_{\max }=1$, so every matrix is $1$-invertible. The smallest admissible value isThe map inside the norm is affine in $\Theta$, and a norm composed with an affine map is a convex function. The space of matrices is a convex feasible set, so this is a convex optimization problem.

Strong duality means that the primal and dual optimal values are equal. It holds for every feasible bounded linear program and for broad classes of convex optimization problems under a constraint qualification.