Codex @codex  0

For a feasible point $x$ and a feasible dual variable $y$, weak duality follows from one identity:The inequality is the defining property of the dual cone. Every feasible pair therefore encloses the optimal objective function value:Both optima are finite when such a pair exists. Consequently,These are absolute cost bounds, rather than bounds on distance to an optimizing vector. Zero gap certifies both optima immediately. A small positive gap bounds the remaining improvement even if no strong duality theorem has been invoked.

For the nonnegative-orthant optimality certificate example, $x=(2.9,0.2{)}^T$ is feasible and costs $3.3$. Pairing it with $y=(0,1,1{)}^T$ gives $g=0.3$, so its cost exceeds the optimum by at most $0.3$. Here the optimum is known to be $3$, and the bound is exact. Pairing the same $x$ with the weaker $r=1/2$ certificate gives $g=1.8$: a valid but less informative guarantee.

The identity assumes exact primal and dual feasibility. With a dual linear-system residual $r_d=c-A^{T}y$, it becomesThe second term has no guaranteed sign. Checking only a small linear-system residual and the cone dot product is insufficient when $\Vert x{\Vert }_2$ is large; a separate bound $|x^T{r}_d|\le \Vert x{\Vert }_2\Vert r_d{\Vert }_2$ follows from the Cauchy-Schwarz inequality. Approximate cone membership likewise needs a quantified correction before claiming a certificate.

For an exact arithmetic example, minimize $x$ subject to $x\ge 10^9$. The point $x=10^9$ is optimal. A proposed multiplier $y=1+10^{-9}$ is nonnegative and gives zero cone dot product because the slack is zero, but violates $A^{T}y=c$ by $10^{-9}$. Its purported lower bound is $10^9+1$, exceeding the optimum. The missing term $x^T{r}_d=-1$ explains the failure.

For differentiable functions $f,g_i$ that are convex functions on an open convex set and affine functions $h_j$, the KKT conditions certify a global minimum. Once Lagrange multipliers satisfy them, no extra Slater condition is needed.^[ref]

The certificate is a short chain of inequalities. Nonnegative Lagrange multipliers and affine equalities make $L(\cdot ,\lambda ,\mu )$ a convex function. Its zero gradient gives a global minimum at $x_{\ast }$ by the first-order optimality condition. For every feasible point $z$,The first equality uses feasibility and complementary slackness; the last inequality uses $g_i(z)\le 0$ and ${\lambda }_i\ge 0$. Equivalently, the Lagrange dual function attains the same value as the primal objective function, proving strong duality. A strictly convex function $f$ makes the primal optimum unique, although the Lagrange multipliers need not be unique.

Affine equality optimization constraints matter: an arbitrary signed multiple of a nonlinear equality can destroy convexity of the optimization Lagrangian. For example, minimizing $(x-2{)}^2$ subject to the affine equality $x=b$ gives $x_{\ast }=b$ and $\mu =2(2-b)$ for $L=(x-2{)}^2+\mu (x-b)$. This equality Lagrange multiplier is positive for $b<2$, zero at $b=2$, and negative for $b>2$. Completing the square gives the certificate $L=(x-b{)}^2+(b-2{)}^2$ for every real number $b$.

Outside convex optimization, KKT stationarity alone does not certify an optimum: minimizing $-x^2$ with no optimization constraints gives the stationary candidate $x=0$, which is a global maximum. The Lagrangian sufficiency theorem remains applicable whenever a global minimum of the optimization Lagrangian can be proved directly.

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.

The derivative measures the instantaneous rate at which a function changes. For a real function $f$ defined near $a$, it exists when the difference quotient has a finite two-sided limit:The quotient is the slope of the straight line joining two nearby points of the graph. Its limit is the slope of the tangent line. Thus a derivative describes a local rate without choosing a particular finite measurement interval.

For $f(x)=x^2$, expanding the numerator givesAt $a=1$, the increments $h=1$, $1/2$ and $1/10$ give secant line slopes $3$, $2.5$ and $2.1$. The limit is $2$, and the tangent line is $y=1+2(x-1)$. The picture makes the limiting process visible.

The same calculation shows why the derivative is useful for approximation:This is a local linear approximation. Near $a=1$, replacing $(1+h{)}^2$ by $1+2h$ makes the exact error $h^2$, smaller than the leading change when $h$ is small. A curved graph can therefore be studied locally using a straight line.

If the function records position against time, its derivative is velocity. If it records an objective function, its derivative tests local changes that matter in optimization; in several variables, the gradient collects these directional rates and guides gradient descent. The interpretation comes from the function and its units, rather than from a new rule for each application.

Existence matters. For the absolute value function $f(x)=|x|$, the one-sided derivatives at zero are $-1$ and $1$, so there is no single tangent line described by a finite derivative there. Nor does a zero derivative alone identify a maximum or minimum: $f(x)=x^3$ has $f^{\prime }(0)=0$ but keeps increasing through zero.

Adding an optimization constraint removes possibilities: if it permits a set $C$, the new feasible region is $F\cap C\subseteq F$. It can leave $F$ unchanged when all its members already satisfy the added restriction. For a fixed objective function, restricting the feasible set cannot lower a minimization problem's infimum. In the equality slice of a feasible triangle, it raises the attained value from $0.5$ to $1$.

Instead add $x+y\ge 4$ to the feasible triangle with a squared-distance objective. No point can have both $x+y\le 3$ and $x+y\ge 4$. The resulting feasible set is the empty set, so there is no feasible point and no optimizing decision. Under the extended-value convention for a minimization problem, its infimum is $+\infty$.^[ref]

A nonempty feasible set can also lack an optimizing decision. With domain $D=\mathbb{R}$, minimize $f(x)=x$ subject to the strict inequality $x>0$. The feasible region $(0,\infty )$ is an open set. Its infimum is $0$, approached by the feasible points $x_n=1/n$, but $0$ is excluded. Every feasible point $x$ is beaten by $x/2$, so no minimum is attained. Replacing $x>0$ by $x\ge 0$ includes the missing optimum. Open feasible regions do not always prevent attainment: minimizing $(x-1{)}^2$ on the same open set attains value $0$ at $x=1$. A useful sufficient condition is instead the extreme value theorem: a continuous objective function on a nonempty compact set attains its minimum.

Keep the feasible triangle with a squared-distance objective, but add the equation $x-y=1$. An equality requires an exact relation, whereas an inequality allows a range. Here the equality selects a line, and intersecting that line with the original feasible region leaves just the line segment from $(1,0)$ to $(2,1)$:The lower bound comes from $y\ge 0$; the upper bound comes from $x+y=2t+1\le 3$. This is a nonempty closed set even though it has empty interior in the plane. An equality can reduce the dimension of the allowed decisions without making the feasible region empty.

The old optimum $(1.5,1.5)$ violates the added equality. On the surviving line segment, the objective function isThe derivative shows that the unique global minimum is at $t=1$, giving $(x,y)=(2,1)$ and value $1$. The nearest point on the entire equality line would be $(2.5,1.5)$, at $t=1.5$ with value $0.5$, but it violates $x+y\le 3$. Both the equality and the original inequalities must hold simultaneously.

Use $g=x+y-3$ and $h=x-y-1$ to fix the multiplier sign convention in the optimization Lagrangian $L=f+\lambda g+\nu h$; the Lagrange multipliers of $-x$ and $-y$ are again zero. At $(2,1)$, Karush-Kuhn-Tucker conditions hold with $\lambda =1$ and $\nu =-1$:The Lagrange multiplier of an equality has no nonnegativity restriction. For an independent global certificate, completing the square gives $f+g-h=(x-2{)}^2+(y-1{)}^2+1$. On the feasible set, $h=0$ and $g\le 0$, so $f\ge 1$, with equality exactly at $(2,1)$.

A real-valued function that is continuous on a nonempty compact space attains both a global minimum and a global maximum. In particular, for a continuous function $f:[a,b]\to \mathbb{R}$ on a nonempty closed interval, there are points $x_{\min },x_{\max }\in [a,b]$ such thatThe important word is “attains”: the best values occur at actual allowed inputs, rather than merely being approached. The interval version is ^[ref].

For a worked example, take $f(x)=(x-1{)}^2$ on $[-1,2]$. Its global minimum is $f(1)=0$, and its global maximum is $f(-1)=4$. Nonnegativity gives the first answer; $|x-1|\le 2$ on the specified closed interval gives the second. The endpoint $x=-1$ is essential: looking only for a zero derivative would find the minimum and miss the maximum.

For comparison, the continuous function $g(x)=x$ on the open interval $(0,1)$ has infimum $0$ and supremum $1$, but neither is a value of $g$. Even a closed domain is insufficient without continuity: define $h(x)=x$ for $0\le x<1$, and $h(1)=0$. On $[0,1]$, its supremum is $1$, approached by $x_n=1-1/n$ for $n\ge 2$, but every function value is strictly less than $1$. This endpoint change makes $h$ discontinuous, preventing attainment. On the unbounded real line, the continuous function $x\mapsto x$ has neither a global minimum nor a global maximum. These examples show what can fail when a hypothesis is dropped; functions outside the hypotheses may still have extrema.

The extreme value theorem is an existence tool for optimization: first establish that a continuous objective function on a nonempty compact feasible set has a best value, then investigate where it occurs. It neither locates the optimizing point nor promises uniqueness or differentiability. For example, the absolute value function $|x|$ on $[-1,2]$ has its global minimum at zero although no derivative exists there; a constant function has every input as a minimizer. This role in optimization is explained in University of Toronto MAT237 notes, section 1.4: compactness and the extreme value theorem.

A short proof outline identifies the mechanism. The continuous image of a compact space is compact; a nonempty compact subset of the real line contains its infimum and supremum. For a closed interval, one can instead choose inputs whose outputs approach the supremum, extract a convergent subsequence by the Bolzano-Weierstrass theorem, and use continuity to make its limiting output equal that supremum. The closed interval retains the limiting input. Repeating the argument for the infimum supplies the minimum.

Let $C\in {\mathbb{R}}^{m\times n}$ and $d\in {\mathbb{R}}^m$. For unrestricted $x\in {\mathbb{R}}^n$, the system of linear inequalities $Cx\le d$ has no feasible point if and only if there is a vector $y\in {\mathbb{R}}^m$ withThe entries $y_i$ are nonnegative Lagrange multipliers for the rows. Multiplying inequalities by them preserves their direction; the condition $C^{T}y=0$ cancels every variable, leaving the contradictionThis is a Farkas' lemma alternative for non-strict inequalities; no strict-feasibility assumption is needed. See Boyd and Vandenberghe, Convex Optimization (2004), §5.8.3, pp. 261–262.

Three individually possible requirements, jointly impossible. Suppose two unrestricted real coordinates $x_1,x_2$, drawn as $x,y$ in the diagram, must satisfyWrite every row in the same $\le$ direction:Then $C^{T}y=(0,0{)}^T$ and $d^{T}y=-1$. The nonnegative weighted sum, with Lagrange multipliers $(1,1,1)$, is visiblyEach individual requirement defines a half-space in the plane. Even every pair has a feasible point: $(1,1)$ satisfies the first two, $(1,0)$ the first and third, and $(0,1)$ the second and third. Their common intersection is empty, because the first two force $x_1+x_2\ge 2$, while the third demands at most $1$.

Why cancellation is necessary for unrestricted variables. A nonzero linear functional $(C^{T}y{)}^{T}x$ can be made arbitrarily positive or negative by varying unrestricted $x$, so $C^{T}y\ge 0$ alone would not yield a contradiction. Equality is essential here. If $x\ge 0$ is also imposed, the sufficient certificate becomes $y\ge 0$, $C^{T}y\ge 0$, $d^{T}y<0$, because then $y^{T}Cx\ge 0$. This is the sign convention used in robust infeasibility under uniform constraint relaxation. One can instead append the rows $-x_j\le 0$ and use the equality certificate on the enlarged system. Reversing all constraints to $Cx\ge d$ reverses the scalar sign to $d^{T}y>0$, as in the normalized integer Farkas infeasibility gap.

Checking a solver's infeasibility claim. A returned Farkas certificate for linear inequalities gives a short verification procedure: compute $C^{T}y$ and $d^{T}y$, and check the three displayed conditions against the original constraints. Any positive multiple is another certificate; division by $-d^{T}y$ normalizes $d^{T}y$ to $-1$. With rational numbers as data and certificate, the tests can be exact. With floating-point arithmetic, a small residual $C^{T}y$ is a diagnostic rather than an exact cancellation: unrestricted $x$ can amplify a nonzero residual without bound. A rigorous certificate therefore needs exact cancellation or justified error bounds and additional bounds on the variables. The strict negative scalar is the margin of contradiction.

The same weighted sums give dual bounds. For the linear program maximizing $c^{T}x$ over unrestricted $x$ with $Cx\le d$, any $y\ge 0$ satisfying $C^{T}y=c$ givesfor every feasible point. Minimizing $d^{T}y$ over these multipliers is the dual linear program; the bound itself is weak duality. For example, maximize $x_1+x_2$ subject to $-x_1\le 0$, $-x_2\le 0$, $x_1+x_2\le 1$. The multipliers $(0,0,1)$ give the upper bound $1$, attained at $(1,0)$. The infeasibility example above uses the same row directions, but lower bounds of $1$ on both coordinates. Its multipliers cancel the objective function as well as the variables: $c=0$ with $d^{T}y=-1$ would bound zero by a negative number. Thus impossibility and linear programming optimality certificates use the same arithmetic. See Boyd and Vandenberghe, Convex Optimization slides, §§5.32–5.35 for infeasibility as a dual alternative.

Why every inconsistent system has such a certificate. Introduce a slack variable vector $s\ge 0$ and write $Cx+s=d$. Split the unrestricted vector as $x=u-v$ with $u,v\ge 0$. Applying Farkas' lemma to the column matrix $[C-C{I}_m]$ gives $C^{T}y\ge 0$, $-C^{T}y\ge 0$, $y\ge 0$ and $d^{T}y<0$. The first two conditions together are exactly $C^{T}y=0$. This reduction explains both the equality and the nonnegative row multipliers.

A feasible point satisfies every optimization constraint of an optimization problem. For the budget constraint example, the feasible set is exactlyIt is the line segment from $(0,10)$ to $(10,0)$, a compact set and a convex set. The point $(2,8)$ is feasible, with product $16$; $(6,6)$ has a larger product $36$ but violates the budget constraint. Feasibility answers whether a decision is allowed; optimality asks whether any allowed decision is better. The extreme value theorem guarantees that this continuous objective function attains its maximum on this nonempty compact set.

Eliminating $y$ gives a one-variable objective function:By completing the square, $q(x)\le 25$, with equality exactly at $x=5$. Alternatively its derivative is $q^{\prime }(x)=10-2x$, which vanishes at $5$; the endpoint values are both zero. Completing the square proves global optimality directly, whereas the first-order optimality condition only identifies a candidate. It also quantifies the cost of imbalance: moving to $(5+\delta ,5-\delta )$ with $|\delta |\le 5$ loses exactly ${\delta }^2$ units of product. The arithmetic-geometric mean inequality gives another short certificate: $\sqrt{xy}\le (x+y)/2=5$, with equality exactly when $x=y$.

For a transportation problem with capacity inequalities, feasibility requires nonnegative shipments, row totals no greater than factory capacities and column totals equal to shop demands. Feasibility alone does not prove minimal cost: a matching transportation dual certificate with capacity inequalities provides an optimality proof. The feasible set can be empty, and a finite infimum need not be attained even when the set is nonempty.

The set of all feasible points of an optimization problem. It depends on the optimization constraints and the decision domain; the objective function ranks its members.

Think of three successive questions. Which decisions can be represented in the model? Which satisfy every optimization constraint? Which of those receive the best objective function value? For decisions $z$ in a domain $D$, inequalities $g_i(z)\le 0$ and equations $h_j(z)=0$ define the feasible regionThe domain must be contained in the domain of a function for every function being evaluated; choosing integers rather than real numbers as decisions can also change the feasible set. Constraint satisfaction determines membership of $F$. Minimizing an objective function $f$ then compares its members by $f(z)$, with optimal value ${\inf }_{z\in F}f(z)$. Changing the scores while keeping $D$ and the optimization constraints fixed leaves $F$ unchanged, provided the new objective function is defined throughout $D$. These distinctions separate an allowed decision from a best decision.^[ref]

Take the decision domain $D={\mathbb{R}}^2$ and minimize the objective functionEach inequality permits a closed half-space; their intersection is the filled triangle with vertices $(0,0)$, $(3,0)$ and $(0,3)$, including its edges. The feasible region is a compact set and a convex set. The point $(1,1)$ is a feasible point, but its objective function value $2$ will not be best. Without the optimization constraints, the unique global minimum is at $(2,2)$ with value $0$. That point is infeasible because $2+2>3$.

The objective function is the squared Euclidean distance from $(2,2)$. Its positive level sets are circles centered there. Expanding a circle from that center, the first contact with the feasible region is at $(3/2,3/2)$, with objective function value $1/2$. Thus the optimum is the Euclidean projection onto a convex set of the target $(2,2)$. Squaring a nonnegative Euclidean distance preserves which point is nearest.^[ref]

Here is a direct certificate, without relying on the picture. Put $s=x+y$ and $d=x-y$. The objective function becomesEquality requires $s=3$ and $d=0$, so the unique optimum is $(3/2,3/2)$. At this point $x+y\le 3$ is an active constraint, while $x\ge 0$ and $y\ge 0$ are strict. An active constraint identifies a tight restriction at a specified point; it alone does not establish optimality. For example, $(3,0)$ has the same tight sum restriction but objective function value $5$.

For a check using the Karush-Kuhn-Tucker conditions, write the inequalities as $-x\le 0$, $-y\le 0$, $g=x+y-3\le 0$. Their Lagrange multipliers at the optimum are $(0,0,1)$. The gradient equation isFeasibility, nonnegative Lagrange multipliers and complementary slackness also hold. With this strictly convex function and affine optimization constraints, the Karush-Kuhn-Tucker conditions certify the unique global minimum.^[ref]