Convexity and Global Optimization

Y. Eddie Lu, Summer 2026

ECON 8001 course index · Chapter 5, Sections 5.1–5.3

Orientation

What problem does convexity solve?

Calculus finds candidates near one point. Convexity compares every point on a line segment. That simple geometric restriction turns a local first-order condition into a global conclusion, rules out multiple strict optima, and makes many economic choice problems tractable.

The chapter has three layers:

1. Section 5.1: convex sets contain mixtures of feasible points, and hyperplanes describe their boundaries and separation.
2. Section 5.2: concave and convex functions turn chord geometry into global tangent and Hessian inequalities.
3. Section 5.3: convex feasibility plus a concave objective turns local and KKT conditions into global certificates.

The final extension treats quasiconcavity. It only requires convex upper level sets, so it is weaker and does not carry the same curvature conclusions.

This page follows the convex-set material in Nachbar, *Convexity in \(\mathbb R^N\), the function results in Nachbar, Concave and Convex Functions, and the level-set treatment in Nachbar, Quasi-concavity.

Course map

1. Begin with line segments in feasible sets.

2. Extend two-point mixtures to finite convex combinations.

3. Study two distinct consequences:

   • concavity or convexity leads to tangent inequalities, global first-order conditions, and Hessian tests under \(C^2\) smoothness;
   • convex level sets lead to quasiconcavity or quasiconvexity.

Before this page: Linear algebra: matrices for quadratic forms, Differentiation for gradients and Hessians, and Optimization for local first- and second-order conditions. Next step: return to the course map and use the retrieval route to connect global shape conditions to the preceding optimization results.

Prerequisite retrieval

For a scalar \(f:\mathbb R^N\to\mathbb R\), \(\nabla f(x)\in\mathbb R^N\) is a column vector and \(D^2f(x)\) is an \(N\times N\) Hessian. If \(v\in\mathbb R^N\), then \(v^{\mathsf{T}}D^2f(x)v\) is a scalar.

Retrieval check. Why must a theorem about concavity name a convex domain?

Show answer

The defining inequality evaluates the function at mixtures \(\theta x+(1-\theta)y\). A convex domain guarantees those mixtures remain in the domain. Without it, the statement may not even be well-defined.

5.1 Convex sets

Definition 5.1.1: convex combinations and convex sets

A set \(C\subseteq\mathbb R^N\) is convex if, for every \(x,y\in C\) and every \(\theta\in[0,1]\),

\[ \theta x+(1-\theta)y\in C. \]

The point \(\theta x+(1-\theta)y\) is a convex combination of \(x\) and \(y\). More generally, if \(x_1,\ldots,x_m\in C\) and the weights satisfy \(\theta_i\ge0\) and \(\sum_{i=1}^m\theta_i=1\), then \(\sum_{i=1}^m\theta_i x_i\) is a finite convex combination.

The geometry is direct: \(C\) is convex exactly when it contains the complete line segment joining every two of its points. By induction, the two-point definition implies that every finite convex combination stays in \(C\).

Examples and nonexamples

• Every affine set \(\{x:Ax=b\}\), half-space \(\{x:a^{\mathsf{T}}x\le b\}\), Euclidean ball, and interval is convex.
• Intersections of any collection of convex sets are convex.
• The union of two convex sets need not be convex. For example, \([-2,-1]\cup[1,2]\subset\mathbb R\) misses the midpoint of \(-1\) and \(1\).
• In \(\mathbb R\), a set is convex exactly when it is an interval, with any combination of included or excluded endpoints.

Convexity is not connectedness in higher dimensions

Every convex set is connected, but the converse fails in \(\mathbb R^N\) for \(N\ge2\). An annulus is connected but its straight chord between two points can pass through the missing center.

Finite mixtures are the operational form

The finite-mixture statement is the one used in probability, diversification, and mixed strategies. For a portfolio interpretation, \(x_i\) can be feasible portfolios and \(\theta_i\) their mixing weights. Convex feasibility means the weighted average portfolio is still available.

Show proof

Proof strategy. The case \(m=2\) is the definition. Assume the claim for \(m-1\) points. If \(\theta_m<1\), write

\[ \begin{aligned} \sum_{i=1}^m\theta_i x_i &=(1-\theta_m) \left( \sum_{i=1}^{m-1} \frac{\theta_i}{1-\theta_m}x_i \right)\\ &\quad+\theta_mx_m. \end{aligned} \]

The parenthesized term is a convex combination of the first \(m-1\) points, so it belongs to \(C\) by induction. One more two-point combination keeps the result in \(C\).

The remaining case must be handled separately. If \(\theta_m=1\), every other nonnegative weight is zero, so the mixture is \(x_m\in C\). If \(\theta_m<1\), the normalized weights \(\theta_i/(1-\theta_m)\) are nonnegative and sum to one, as required in the induction step.

Separation and support

A hyperplane is a level set of a nonconstant affine function:

\[ H(a,b) =\{z\in\mathbb R^N:a^{\mathsf T}z=b\}. \]

Here \(a\ne0\). The vector \(a\) is normal to the hyperplane. Changing \(b\) slides the hyperplane without rotating it.

Theorem 5.1.3: separating hyperplane theorem

Let \(C,D\subseteq\mathbb R^N\) be nonempty, disjoint, and convex. Then there are \(a\in\mathbb R^N\setminus\{0\}\) and \(b\in\mathbb R\) such that

\[ a^{\mathsf T}x\ge b \qquad\text{for every }x\in C, \]

and

\[ a^{\mathsf T}y\le b \qquad\text{for every }y\in D. \]

What separation means

Project every point onto the one-dimensional axis \(a\). The theorem says that the projected values from \(C\) lie on one side of \(b\), while those from \(D\) lie on the other. The inequalities may be equal at limit points. Strict separation needs stronger hypotheses, such as positive distance between the sets.

Example: separating two disks

Let

\[ C=\{z\in\mathbb R^2:\|z\|\le1\}, \]

and

\[ D=\{z\in\mathbb R^2:\|z-(3,0)\|\le1\}. \]

Choose \(a=(-1,0)^{\mathsf T}\) and \(b=-3/2\). Then every \(x\in C\) satisfies \(a^{\mathsf T}x\ge-1\ge b\), while every \(y\in D\) satisfies \(a^{\mathsf T}y\le-2\le b\). The vertical line \(z_1=3/2\) lies between the two disks.

Theorem 5.1.4: supporting hyperplane theorem

Let \(C\subseteq\mathbb R^N\) be nonempty and convex, and let \(x_0\) be a boundary point of \(C\). Then there are \(a\in\mathbb R^N\setminus\{0\}\) and \(b\in\mathbb R\) such that

\[ a^{\mathsf T}x_0=b, \]

and

\[ a^{\mathsf T}x\ge b \qquad\text{for every }x\in C. \]

The hyperplane touches \(C\) at \(x_0\) and leaves the whole set in one closed half-space. For the unit ball and \(x_0=(1,0)\), take \(a=(-1,0)^{\mathsf T}\) and \(b=-1\). The supporting line is \(z_1=1\).

Show proof strategy

For the full separation theorem, pass to relative interiors and separate the origin from the appropriate open convex difference set. The separating linear functional supplies \(a\), and its offset supplies \(b\). The familiar closest-pair proof is a useful special case when the distance between the sets is attained, but it is not the general proof for arbitrary nonclosed or unbounded convex sets.

For support at \(x_0\), separate \(C\) from a sequence of exterior points tending to \(x_0\), normalize the separating normals, and take a convergent subsequence. The limiting hyperplane passes through \(x_0\).

Retrieval check. What is the difference between a separating hyperplane and a supporting hyperplane?

Show answer

A separating hyperplane puts two disjoint convex sets in opposite closed half-spaces. A supporting hyperplane passes through a specified boundary point of one convex set and leaves that set in one closed half-space.

5.2 Concave and convex functions

Definition 5.2.1: convexity, concavity, and strictness

Let \(C\subseteq\mathbb R^N\) be nonempty and convex, and let \(f:C\to\mathbb R\).

• \(f\) is convex if, for all \(x,y\in C\) and \(\theta\in[0,1]\),

  \[ \begin{gathered} f(\theta x+(1-\theta)y)\\ \le\\ \theta f(x)+(1-\theta)f(y). \end{gathered} \]

• \(f\) is concave if the inequality reverses.

• \(f\) is strictly convex or strictly concave if the respective inequality is strict whenever \(x\ne y\) and \(\theta\in(0,1)\).

For a convex function, the graph lies weakly below its chord. For a concave function, it lies weakly above its chord. An affine function has equality in both directions, so every affine function is both convex and concave.

Basic examples

• \(x\mapsto x^2\) is strictly convex on \(\mathbb R\).
• \(x\mapsto\log x\) is strictly concave on \(\mathbb R_{++}\).
• \(x\mapsto -\|x\|^2\) is strictly concave on \(\mathbb R^N\).
• Every linear or affine function is both convex and concave, but neither strictly so on a domain containing two distinct points.

Jensen’s inequality for finite mixtures

Jensen’s inequality, finite form

Let \(f:C\to\mathbb R\) be convex. For \(x_1,\ldots,x_m\in C\) and weights \(\theta_i\ge0\) satisfying \(\sum_{i=1}^m\theta_i=1\),

\[ f\left(\sum_{i=1}^m\theta_i x_i\right) \le\sum_{i=1}^m\theta_i f(x_i). \]

For a concave function, the inequality reverses. If \(f\) is strictly convex and all positive-weight points are not identical, the convex inequality is strict; analogously for strict concavity.

The theorem is just the finite-mixture induction again, now applying the two-point function inequality at each step. It is the deterministic ancestor of the probabilistic Jensen inequality \(f(\mathbb E[X])\le\mathbb E[f(X)]\). The random-variable form needs integrability and is an ECON 8002 result.

Diversification calculation

Let \(f(x)=-x^2\), which is concave. For \(x_1=-1\), \(x_2=3\), and equal weights,

\[ \begin{aligned} f\left(\frac{x_1+x_2}{2}\right) &=f(1)=-1,\\ \frac{f(-1)+f(3)}2&=-5. \end{aligned} \]

Therefore \(-1>-5\): the concave payoff of the average exceeds the average payoff. The inequality is strict because the two choices differ and \(f\) is strictly concave.

Epigraphs and hypographs

Definition 5.2.2: epigraph and hypograph

For \(f:C\to\mathbb R\), define subsets of \(\mathbb R^{N+1}\) by

\[ \operatorname{epi}f =\{(x,r)\in C\times\mathbb R:r\ge f(x)\}, \]

\[ \operatorname{hypo}f =\{(x,r)\in C\times\mathbb R:r\le f(x)\}. \]

The epigraph is the region on or above the graph; the hypograph is the region on or below it.

Theorem 5.2.3: epigraph and hypograph characterization

For a function on a convex domain \(C\), \(f\) is convex if and only if

\[ \operatorname{epi}f\text{ is convex}. \]

\(f\) is concave if and only if

\[ \operatorname{hypo}f\text{ is convex}. \]

Show proof

Proof strategy. For concavity, take two points \((x,r)\) and \((y,s)\) in the hypograph. Thus \(r\le f(x)\) and \(s\le f(y)\). Concavity gives

\[ \theta r+(1-\theta)s \le\theta f(x)+(1-\theta)f(y) \le f(\theta x+(1-\theta)y), \]

so their mixture remains in the hypograph. Conversely, put two graph points \((x,f(x))\) and \((y,f(y))\) in a convex hypograph. Membership of their mixture is exactly the concavity inequality. Reverse all vertical inequalities for the epigraph and convexity.

The graph itself is usually not convex

For a nonaffine function, the line segment between two graph points generally lies above or below the graph rather than on it. Convexity concerns the epigraph or hypograph, not usually the graph.

First-order characterization

The chord definition does not require derivatives. When derivatives exist, it has an equivalent tangent-plane form.

Theorem 5.2.4: supporting inequalities

Assumptions. \(C\subseteq\mathbb R^N\) is nonempty, open, and convex, and \(f:C\to\mathbb R\) is differentiable.

Concavity. The function \(f\) is concave if and only if, for every \(x,y\in C\),

\[ f(y)\le f(x)+\nabla f(x)^{\mathsf{T}}(y-x). \]

Convexity. The function \(f\) is convex if and only if, for every \(x,y\in C\),

\[ f(y)\ge f(x)+\nabla f(x)^{\mathsf{T}}(y-x). \]

Strict versions. The function is strictly concave if and only if the concave supporting inequality is strict whenever \(x\ne y\). It is strictly convex if and only if the convex supporting inequality is strict whenever \(x\ne y\).

For concavity, every tangent plane lies weakly above the graph. For convexity, every tangent plane lies weakly below it. These are global inequalities for every pair \((x,y)\), not merely local Taylor approximations.

Show proof

Proof strategy for concavity. Let \(g(t)=f(x+t(y-x))\) for \(t\in[0,1]\). Concavity of \(f\) gives a chord inequality for \(g\). Divide by \(t>0\) and take \(t\downarrow0\) to obtain the tangent inequality. Conversely, set \(z=\theta x+(1-\theta)y\) and apply the supporting inequality at \(z\):

\[ \begin{aligned} f(x) &\le f(z) +(1-\theta)\nabla f(z)^{\mathsf{T}}(x-y),\\ f(y) &\le f(z) -\theta\nabla f(z)^{\mathsf{T}}(x-y). \end{aligned} \]

Multiply the first inequality by \(\theta\) and the second by \(1-\theta\). The gradient terms cancel, so

\[ \theta f(x)+(1-\theta)f(y)\le f(z), \]

which is the concavity inequality. The convex proof reverses every inequality.

Retrieval check. In the converse proof, why are the multipliers on the two displayed inequalities \(\theta\) and \(1-\theta\), rather than the other way around?

Show answer

They are the weights in the desired chord expression \(\theta f(x)+(1-\theta)f(y)\). With these weights, the two gradient terms are \(\theta(1-\theta)\nabla f(z)^{\mathsf{T}}(x-y)\) and its negative, so they cancel.

A stationary point alone is not a global certificate

For \(f(x)=x^3\), \(f'(0)=0\), but \(0\) is neither a maximum nor a minimum. The tangent inequality, or concavity/convexity plus an appropriate first-order condition, is the missing global structure.

Second-order characterization

Theorem 5.2.5: Hessian characterization

Assumptions. \(C\subseteq\mathbb R^N\) is nonempty, open, and convex, and \(f:C\to\mathbb R\) is \(C^2\).

Conclusions.

• \(f\) is convex if and only if \(D^2f(x)\) is positive semidefinite for every \(x\in C\).
• \(f\) is concave if and only if \(D^2f(x)\) is negative semidefinite for every \(x\in C\).
• Positive definiteness everywhere is sufficient for strict convexity. Negative definiteness everywhere is sufficient for strict concavity.

The Hessian test works because its sign controls the curvature of every line restriction through the domain.

Show proof

For \(x,y\in C\), examine the scalar restriction

\[ h(t)=f\bigl(x+t(y-x)\bigr). \]

Put \(z(t)=x+t(y-x)\). By the chain rule,

\[ h''(t)=(y-x)^{\mathsf{T}}D^2f\bigl(z(t)\bigr)(y-x). \]

Thus a positive semidefinite Hessian makes every line restriction convex; negative semidefiniteness makes every such restriction concave.

Strict convexity does not require a positive definite Hessian everywhere

The function \(f(x)=x^4\) is strictly convex on \(\mathbb R\), yet \(f''(0)=0\). Likewise, \(-x^4\) is strictly concave, but its Hessian is zero at zero. A definite Hessian everywhere is a strong sufficient condition, not a necessary condition for strictness.

A one-point semidefinite Hessian says little

For \(f(x)=x^4\), the Hessian at zero is \(0\), which is both positive and negative semidefinite. That does not make \(f\) concave near zero. The global Hessian characterization requires the sign at every point of an open convex domain.

Affine functions and continuity

Definition 5.2.7: affine function

A function \(f:\mathbb R^N\to\mathbb R\) is affine if there are \(a\in\mathbb R^N\) and \(b\in\mathbb R\) such that

\[ f(x)=a^{\mathsf T}x+b \qquad\text{for every }x\in\mathbb R^N. \]

The constant \(b\) shifts the graph but does not change its slope. For every \(x,y\) and \(\theta\in[0,1]\),

\[ f\bigl(\theta x+(1-\theta)y\bigr) =\theta f(x)+(1-\theta)f(y). \]

Thus an affine function satisfies both chord inequalities with equality.

Theorem 5.2.8: characterization of affine functions

A function \(f:\mathbb R^N\to\mathbb R\) is affine if and only if it is both convex and concave.

Show proof

The forward direction follows from the displayed mixture equality. Conversely, convexity and concavity force equality for every two-point mixture. This gives linearity along every line segment. The finite-dimensional Jensen functional equation, together with the regularity already implied by finite-valued convexity on the open domain \(\mathbb R^N\), yields \(f(x)=a^{\mathsf T}x+b\).

Theorem 5.2.9: interior continuity

Let \(C\subseteq\mathbb R^N\) be nonempty, open, and convex. Every finite-valued convex or concave function \(f:C\to\mathbb R\) is continuous on \(C\).

Convexity bounds the slope of a chord through an interior point by slopes to nearby points in finitely many coordinate directions. Those bounds prevent a finite-valued convex function from jumping inside its domain. Apply the result to \(-f\) for concavity.

Continuity at the boundary is not automatic

The open-domain assumption matters. Define \(f:[0,1]\to\mathbb R\) by \(f(0)=1\) and \(f(x)=0\) for \(x>0\). This function is convex but discontinuous at \(0\). Convexity guarantees continuity on the relative interior, not at every included boundary point without more assumptions.

5.3 Convex optimization

In a maximization problem, the standard global-shape pair is a convex feasible set and a concave objective. The word convex optimization includes this maximization form, or equivalently minimization of the convex function \(-f\).

Theorem 5.3.1: local maxima are global

Let \(C\subseteq\mathbb R^N\) be nonempty and convex, and let \(f:C\to\mathbb R\) be concave.

1. Every local maximizer of \(f\) on \(C\) is a global maximizer.

2. The set

   \[ \operatorname*{arg\,max}_{x\in C}f(x) \]

   is convex, with the empty set counted as convex.

Why a better distant point would contradict local optimality

If \(y\) had a higher value than a local maximizer \(x^*\), every sufficiently small move from \(x^*\) toward \(y\) would remain feasible. Concavity would make that nearby mixture better than \(x^*\), contradicting local maximality.

If two points both attain the maximum, concavity says every mixture of them attains at least that same value. It cannot exceed the maximum, so the whole segment also maximizes.

Show proof

Suppose \(x^*\) is a local maximizer but \(f(y)>f(x^*)\) for some \(y\in C\). For \(t\in(0,1)\), convexity gives

\[ x_t=(1-t)x^*+ty\in C. \]

Concavity gives

\[ f(x_t) \ge(1-t)f(x^*)+tf(y) >f(x^*). \]

For small \(t\), \(x_t\) is arbitrarily close to \(x^*\), a contradiction.

For the argmax claim, take maximizers \(x\) and \(y\) with common value \(M\). Concavity gives \(f(\theta x+(1-\theta)y)\ge M\), while the definition of \(M\) gives the reverse inequality.

Theorem 5.3.2: strict concavity gives at most one maximizer

Let \(C\subseteq\mathbb R^N\) be nonempty and convex. If \(f:C\to\mathbb R\) is strictly concave, then

\[ \left| \operatorname*{arg\,max}_{x\in C}f(x) \right|\le1. \]

Show proof

If distinct \(x\) and \(y\) both maximize \(f\), their midpoint is feasible and strict concavity makes its value strictly greater than the common maximum. This is impossible.

Uniqueness is not existence

Strict concavity gives at most one maximizer. The strictly concave function \(f(x)=\log x\) on \((0,1)\) has none. A compact feasible set and a continuous objective would supply existence through Weierstrass.

The safe first-order condition

Theorem 5.3.3: variational first-order condition

Let \(C\subseteq\mathbb R^N\) be nonempty and convex. Suppose \(f\) is differentiable on an open neighborhood of \(C\), and let \(x^*\in C\).

Necessity. If \(x^*\) maximizes \(f\) on \(C\), then

\[ \nabla f(x^*)^{\mathsf T}(y-x^*)\le0 \qquad\text{for every }y\in C. \]

Sufficiency. If \(f\) is concave and the displayed inequality holds, then \(x^*\) is a global maximizer of \(f\) on \(C\).

Interior special case. If \(x^*\) is interior to \(C\), the displayed condition is equivalent to

\[ \nabla f(x^*)=0. \]

At a boundary optimum, the gradient need not vanish. It only needs to have a nonpositive inner product with every feasible displacement. For example, \(f(x)=x\) on \(C=[0,1]\) is concave and is maximized at \(x^*=1\), where \(f'(1)=1\ne0\). Yet \(f'(1)(y-1)\le0\) for every \(y\in[0,1]\).

Show proof

For necessity, fix \(y\in C\) and define \(\phi(t)=f(x^*+t(y-x^*))\) on \([0,1]\). A maximum at \(t=0\) requires \(\phi'(0^+)\le0\), which is the variational inequality.

For sufficiency, the concave supporting inequality gives

\[ f(y) \le f(x^*)+\nabla f(x^*)^{\mathsf T}(y-x^*) \le f(x^*) \]

for every feasible \(y\).

At an interior point, both \(x^*+te_j\) and \(x^*-te_j\) are feasible for small \(t>0\). Applying the variational inequality to both signs makes every component of the gradient zero.

Example 5.3.4: calculate and certify an interior maximum

Maximize

\[ f(x_1,x_2) =-(x_1-2)^2-2(x_2+1)^2 \]

over \(\mathbb R^2\). The first-order equations are

\[ -2(x_1-2)=0, \]

and

\[ -4(x_2+1)=0. \]

Thus \(x^*=(2,-1)\). Since

\[ D^2f(x)= \begin{pmatrix} -2&0\\ 0&-4 \end{pmatrix} \prec0, \]

\(f\) is strictly concave on \(\mathbb R^2\). The zero gradient is therefore a global certificate, and strict concavity gives uniqueness. The Hessian is not being used only as a local SOC here: its sign on the whole convex domain establishes global concavity.

KKT as a global certificate

Consider

\[ \max_{x\in\mathbb R^N} f(x) \]

subject to

\[ Ax=b, \]

and

\[ h_i(x)\le c_i, \qquad i=1,\ldots,m. \]

Use the maximization Lagrangian

\[ \begin{aligned} L(x;\mu,\lambda) ={}&f(x)\\ &-\mu^{\mathsf T}(Ax-b)\\ &-\sum_{i=1}^m\lambda_i\bigl(h_i(x)-c_i\bigr). \end{aligned} \]

The equality multiplier \(\mu\) is unrestricted in sign. The inequality multipliers satisfy \(\lambda_i\ge0\). Those signs follow from the displayed Lagrangian and the direction \(h_i\le c_i\).

Theorem 5.3.5: KKT sufficiency and KKT necessity under Slater

Assume \(f\) is concave and \(C^1\), each \(h_i\) is convex and \(C^1\), and the equality constraints are affine.

Suppose a feasible \(x^*\) has multipliers \(\mu^*\) and \(\lambda^*\) satisfying:

1. Stationarity

   \[ \begin{aligned} &\nabla f(x^*)-A^{\mathsf T}\mu^*\\ &\qquad-\sum_{i=1}^m \lambda_i^*\nabla h_i(x^*)=0. \end{aligned} \]

2. Dual feasibility

   \[ \lambda_i^*\ge0, \qquad i=1,\ldots,m. \]

3. Complementary slackness

   \[ \lambda_i^*\bigl(c_i-h_i(x^*)\bigr)=0. \]

   This condition holds for each \(i=1,\ldots,m\).

Then \(x^*\) is a global maximizer. This sufficiency direction does not need Slater’s condition.

Conversely, suppose \(x^*\) is a maximizer and there is a strictly feasible point \(\bar x\) such that

\[ A\bar x=b, \]

and

\[ h_i(\bar x)<c_i, \qquad i=1,\ldots,m. \]

Then suitable KKT multipliers exist. This strict-feasibility assumption is Slater’s condition; it is a constraint qualification for the necessity direction.

Do not attach a sign restriction to an equality multiplier

The equation \(Ax=b\) can be written as either \(Ax-b=0\) or \(b-Ax=0\). Reversing that normalization reverses \(\mu\) but changes no feasible point. Therefore \(\mu\) must be free in sign. Only the multiplier on the standardized inequality \(h_i(x)-c_i\le0\) is required to be nonnegative here.

Show global-certificate proof

Let \(y\) be any feasible point. Concavity gives

\[ f(y)-f(x^*) \le\nabla f(x^*)^{\mathsf T}(y-x^*). \]

Substitute stationarity. The equality term vanishes because \(Ay=Ax^*=b\). Convexity of each \(h_i\) gives

\[ \nabla h_i(x^*)^{\mathsf T}(y-x^*) \le h_i(y)-h_i(x^*) \le c_i-h_i(x^*). \]

After multiplying by \(\lambda_i^*\ge0\) and summing, complementary slackness makes the upper bound zero. Hence \(f(y)\le f(x^*)\) for every feasible \(y\).

Slater’s role is different. Strict feasibility permits a separating-hyperplane argument between attainable constraint-objective values and the set of values that would strictly improve on the optimum. The separating normal supplies the multipliers. It is not needed once multipliers satisfying KKT are already in hand.

Example 5.3.6: solve KKT and obtain a global certificate

Maximize

\[ f(x,y)=-(x-2)^2-(y-1)^2 \]

subject to

\[ x+y=1, \]

and

\[ x\le\frac12. \]

The problem has a concave objective, an affine equality, and a convex affine inequality. Use

\[ \begin{aligned} L(x,y;\mu,\lambda) ={}&f(x,y)\\ &-\mu(x+y-1)\\ &-\lambda\left(x-\frac12\right), \end{aligned} \]

with \(\mu\in\mathbb R\) and \(\lambda\ge0\). Stationarity gives

\[ -2(x-2)-\mu-\lambda=0, \]

and

\[ -2(y-1)-\mu=0. \]

The unconstrained solution on the equality has \(x=1\), so the upper bound must bind. Set \(x^*=y^*=1/2\). The second stationarity equation gives \(\mu^*=1\); the first then gives \(\lambda^*=2\). Thus

\[ (x^*,y^*;\mu^*,\lambda^*) =\left(\frac12,\frac12;1,2\right). \]

All KKT conditions hold. The theorem certifies a global maximum, and strict concavity certifies uniqueness. Slater also holds, for example at \((0,1)\), but it is only needed to guarantee that a maximizer admits multipliers.

For a direct check, substitute \(y=1-x\). For every feasible \(x\le1/2\),

\[ \begin{aligned} &f\left(\frac12,\frac12\right) -f(x,1-x)\\ &\qquad=\left(\frac12-x\right)(3-2x)\\ &\qquad\ge0. \end{aligned} \]

Example 5.3.7: inactive means zero multiplier

If the upper bound in the preceding problem changes to \(x\le2\), the equality-only solution \((1,0)\) is feasible and the inequality is slack. Complementary slackness forces \(\lambda^*=0\). Stationarity then gives the free equality multiplier \(\mu^*=2\).

Retrieval check. Which direction of Theorem 5.3.5 uses Slater’s condition?

Show answer

Slater is used to guarantee necessity: a global maximizer has KKT multipliers. It is not needed for sufficiency. Once a feasible point and multipliers satisfy KKT in a concave maximization problem with convex constraints, they already form a global certificate.

Extension: quasiconvexity and quasiconcavity

Convexity compares values to weighted averages of values. Quasiconcavity only asks whether sufficiently good choices form a convex set.

Definition: upper and lower level sets

Let \(C\subseteq\mathbb R^N\) be convex and \(f:C\to\mathbb R\). For \(a\in\mathbb R\), define

\[ \begin{aligned} U_a&=\{x\in C:f(x)\ge a\},\\ L_a&=\{x\in C:f(x)\le a\}. \end{aligned} \]

The function \(f\) is quasiconcave if every upper level set \(U_a\) is convex. It is quasiconvex if every lower level set \(L_a\) is convex. Empty level sets count as convex.

Equivalently, \(f\) is quasiconcave if

\[ f(\theta x+(1-\theta)y)\ge\min\{f(x),f(y)\} \]

for all \(x,y\in C\) and \(\theta\in[0,1]\). For quasiconvexity, replace the minimum by the maximum and reverse the inequality.

Concavity implies quasiconcavity

If \(f\) is concave on a convex set \(C\), then it is quasiconcave. If \(f\) is convex, then it is quasiconvex. The converses fail.

Show proof

If \(f(x)\ge f(y)\), concavity gives

\[ \begin{gathered} f(\theta x+(1-\theta)y) \\ \ge\theta f(x)+(1-\theta)f(y)\\ \ge f(y). \end{gathered} \]

This is exactly the convexity of the upper level set at level \(f(y)\).

Retrieval check. If \(f\) is quasiconcave and \(f(x),f(y)\ge a\), what must be true of \(f(\theta x+(1-\theta)y)\) for \(\theta\in[0,1]\)?

Show answer

It must be at least \(a\). Both endpoints lie in the upper level set \(U_a\), and quasiconcavity says \(U_a\) is convex, so their mixture remains in \(U_a\).

Examples that mark the boundary

• \(f(x)=e^x\) on \(\mathbb R\) is strictly convex and quasiconcave. It is quasiconcave because every upper level set is a ray \([\log a,\infty)\), or all of \(\mathbb R\) or empty.
• \(f(x)=x^2\) is not quasiconcave on \(\mathbb R\): for \(a>0\), the upper level set \((-\infty,-\sqrt a]\cup[\sqrt a,\infty)\) is not convex.
• Every monotone real-valued function on an interval is both quasiconcave and quasiconvex, even when it has no concavity or convexity.

Quasiconcavity is not a substitute for concavity

The function \(f(x)=x^3\) is strictly increasing, hence quasiconcave on \(\mathbb R\), but its stationary point at zero is not a maximum. Quasiconcavity alone does not make a zero gradient sufficient for a global optimum.

Extension 1: strict quasiconcavity and uniqueness

Strict quasiconcavity means that for distinct \(x,y\) with \(f(x)\ge f(y)\), every proper mixture has value strictly above \(f(y)\). It gives at most one global maximizer on a convex feasible set. The same midpoint contradiction as for strict concavity proves it.

It remains weaker than strict concavity. The function \(f(x)=e^x\) is strictly quasiconcave on \(\mathbb R\) because it is strictly increasing, while it is strictly convex rather than concave.

Extension 2: differentiated quasiconcavity

Let \(C\subseteq\mathbb R^N\) be nonempty, open, and convex, and let \(f:C\to\mathbb R\) be \(C^2\). Define the tangent space to the level set at \(x\) by

\[ T_{\nabla f(x)} =\{v\in\mathbb R^N:\nabla f(x)^{\mathsf{T}}v=0\}. \]

The test examines curvature only along directions tangent to a level set, not all directions.

Necessary tangent-curvature condition for quasiconcavity

Assumptions. \(C\subseteq\mathbb R^N\) is nonempty, open, and convex, and \(f:C\to\mathbb R\) is \(C^2\) and quasiconcave.

Conclusion. For every \(x\in C\) and every \(v\in T_{\nabla f(x)}\),

\[ v^{\mathsf{T}}D^2f(x)v\le0. \]

This is only a necessary condition. Quasiconcavity rules out positive curvature along a direction that is locally tangent to a level set, because that would create a strict local trough on the corresponding line.

Tangent-space semidefiniteness is not sufficient

The converse stated in the cited Nachbar note is incorrect. Let \(f(x)=x^4\) on the open convex domain \(\mathbb R\). If \(x\ne0\), then \(f'(x)\ne0\), so the only gradient-orthogonal direction is \(v=0\). At \(x=0\), \(f'(0)=0\) and \(f''(0)=0\). Hence \(v^{\mathsf{T}}D^2f(x)v\le0\) holds for every gradient-orthogonal \(v\) at every \(x\). Yet \(f\) is not quasiconcave: its upper level set at \(a=1\) is \((-\infty,-1]\cup[1,\infty)\), which is not convex.

Safe strict-curvature sufficient condition

Assumptions. \(C\subseteq\mathbb R^N\) is nonempty, open, and convex, and \(f:C\to\mathbb R\) is \(C^2\). Suppose that, for every \(x\in C\) and every nonzero \(v\in\mathbb R^N\) with \(\nabla f(x)^{\mathsf{T}}v=0\),

\[ v^{\mathsf{T}}D^2f(x)v<0. \]

Conclusion. \(f\) is strictly quasiconcave on \(C\).

Show proof

Why this is safe. Restrict \(f\) to any nondegenerate feasible line segment. At an interior stationary point of that restriction, the segment direction is gradient-orthogonal, so the second derivative is strictly negative. Thus a line restriction cannot have an interior local trough: it rises strictly until at most one peak and then falls strictly. This gives strict quasiconcavity on every segment, hence on \(C\). The condition is sufficient, not necessary.

The gradient-zero case is special

If \(\nabla f(x)=0\), then \(T_{\nabla f(x)}=\mathbb R^N\). The level-set tangent condition then becomes the ordinary all-directions Hessian condition. Do not apply a bordered-Hessian shortcut without checking whether the gradient is nonzero.

Assumption audit and problem blueprints

Assumption audit

1. Finite-mixture feasibility

   • Condition: \(C\) is convex.
   • Conclusion: every finite convex combination remains in \(C\).

2. Jensen inequality

   • Condition: \(f\) is convex or concave on a convex domain.
   • Conclusion: the value at a mixture is compared with the mixture of values in the appropriate direction.

3. Tangent inequality

   • Conditions: \(C\) is open and convex, and \(f\) is differentiable.
   • Conclusion: the tangent plane globally supports the graph.

4. Hessian equivalence

   • Conditions: \(C\) is open and convex, and \(f\in C^2\).
   • Conclusion: a semidefinite Hessian everywhere is equivalent to convexity or concavity in the corresponding direction.

5. Global maximization certificate

   • Conditions: \(C\) is convex, \(f\) is concave, and the variational inequality holds at \(x^*\).
   • Conclusion: \(x^*\) is a global maximizer.

6. Uniqueness

   • Conditions: \(C\) is convex and \(f\) is strictly concave, or strictly quasiconcave.
   • Conclusion: there is at most one maximizer.

7. Existence

   • Conditions: \(C\) is compact and \(f\) is continuous.
   • Conclusion: a maximizer exists.

8. KKT global certificate

   • Conditions: \(f\) is concave, the inequalities are convex, the equalities are affine, and a feasible point satisfies KKT.
   • Conclusion: that point is a global maximizer.

9. KKT necessity

   • Condition: the convex program satisfies Slater’s condition.
   • Conclusion: KKT multipliers exist at a maximizer.

10. Quasiconcavity

    • Condition: every upper level set is convex.
    • Conclusion: mixtures do not fall below the worse endpoint, but no weighted-average payoff inequality follows.

11. Strict quasiconcavity from curvature

    • Conditions: \(C\) is open and convex, \(f\in C^2\), and curvature is strictly negative in every nonzero gradient-orthogonal direction.
    • Conclusion: \(f\) is strictly quasiconcave.

Blueprint: prove a global optimum

1. State the feasible set and prove it is convex.
2. Separate existence from characterization. Use compactness and continuity if existence is needed.
3. Establish concavity for maximization or convexity for minimization, using a definition, a Hessian test on the whole domain, or a composition rule.
4. Write the correct first-order condition. At a boundary, use \(\nabla f(x^*)^{\mathsf{T}}(y-x^*)\le0\) rather than automatically setting the gradient to zero.
5. Apply the supporting inequality to every feasible \(y\).
6. Add strictness only to claim uniqueness.

Blueprint: classify quasi-shape

1. Write the upper level set for quasiconcavity or lower level set for quasiconvexity.
2. Test whether that set is convex for every level.
3. Treat tangent-space negative semidefiniteness as necessary only. The \(x^4\) counterexample shows it is not sufficient for quasiconcavity.
4. For a sufficient strict test, require strict negative curvature in every nonzero gradient-orthogonal direction, with an open convex domain and a \(C^2\) objective.
5. Do not infer concavity, a global FOC result, or Hessian definiteness merely from a quasi-shape property.

Blueprint: certify a convex program with KKT

1. Standardize every inequality as \(h_i(x)\le c_i\).
2. Write the displayed Lagrangian before assigning multiplier signs.
3. Solve primal feasibility, stationarity, dual feasibility, and complementary slackness together.
4. Check that the objective is concave, inequalities are convex, and equalities are affine. Then KKT is sufficient globally.
5. Invoke Slater only if you need to argue that a maximizer must have KKT multipliers.

Exit tickets

1. Is the union of two convex sets necessarily convex? Give a two-point test.
2. State the finite-mixture Jensen inequality for a concave function.
3. What extra conditions turn a strictly concave objective’s at-most-one result into a unique maximizer result?
4. Why does \(f'(x^*)=0\) fail to prove a maximum for a quasiconcave function?
5. In the \(C^2\) Hessian characterization, is positive definiteness everywhere necessary for strict convexity?
6. Is nonpositive curvature in every gradient-orthogonal direction sufficient for quasiconcavity?
7. In a concave maximization problem, does KKT sufficiency require Slater?

Show answer

1. No. In \([-2,-1]\cup[1,2]\), both \(-1\) and \(1\) are present but their midpoint \(0\) is absent. 2. \(f(\sum_i\theta_i x_i)\ge\sum_i\theta_i f(x_i)\). 3. A compact feasible set and a continuous objective give existence. 4. Quasiconcavity does not produce the tangent supporting inequality; \(x^3\) is a counterexample.
2. No. \(x^4\) is strictly convex although its second derivative is zero at zero.
3. No. \(x^4\) satisfies that tangent-space semidefinite condition but is not quasiconcave on \(\mathbb R\). 7. No. Slater supports necessity, meaning the existence of multipliers at an optimum.

Mastery checklist

• I can test convexity of a feasible set from the line-segment definition.
• I can move between two-point mixtures and finite convex combinations.
• I can state Jensen’s inequality with the direction appropriate to the function.
• I can recognize convexity from an epigraph and concavity from a hypograph.
• I can state the domains and differentiability assumptions of the tangent and Hessian characterizations.
• I can separate global optimality, uniqueness, and existence.
• I can use the variational inequality at a boundary rather than imposing a false zero-gradient condition.
• I can distinguish KKT sufficiency from KKT necessity and state exactly where Slater enters.
• I can define quasiconcavity from upper level sets and say why it is weaker than concavity.
• I can distinguish the necessary tangent-space semidefinite condition from the strict sufficient curvature condition for quasiconcavity.

Sources and further reading

• John Nachbar, Convexity in \(\mathbb R^N\), for convex sets, finite convex combinations, and separating geometry.
• John Nachbar, Concave and Convex Functions, for epigraphs, hypographs, tangent inequalities, and Hessian characterizations.
• John Nachbar, Quasi-concavity, for level sets. Its statement that tangent-space negative semidefiniteness is sufficient for quasiconcavity is incorrect; the \(x^4\) counterexample above shows the failure.