Example 1.6 ended badly for calculus: a point with zero slope and positive curvature turned out to be far from optimal. Local tests see only a neighbourhood, and the function \(x^3-3x\) does something in the distance that no neighbourhood of \(x=1\) reveals. What property of a problem would make such surprises impossible, so that looking near a point tells the truth about every point?
The property is convexity. For sets it says that the segment between two members stays inside; for functions, that the chord between two points of the graph lies on or above the graph. From these two modest requirements follow the three facts on which the rest of the book leans: a tangent plane to a convex function is a lower bound everywhere, not just nearby; a local minimizer of a convex function over a convex set is a global one; and convexity can be verified, by curvature or by a short calculus of construction rules, without examining every pair of points.
2.1 Sets that contain their segments
Definition 2.1 (convex set, convex combination). A set \(C\subseteq\mathbb R^n\) is convex if for all \(x,y\in C\) and all \(\theta\in[0,1]\) ,
A convex combination of points \(x_1,\dots,x_k\) is a point \(\theta_1x_1+\dots+\theta_kx_k\) with every \(\theta_i\ge 0\) and \(\theta_1+\dots+\theta_k=1\) . The convex hull of a set is the set of all convex combinations of its points.
The point \(\theta x+(1-\theta)y\) traces the segment from \(y\) (at \(\theta=0\) ) to \(x\) (at \(\theta=1\) ). The empty set and single points are convex because the condition has nothing to violate. An induction on \(k\) shows that a convex set contains every convex combination of its points, not only those of two points; this is Exercise 13 in the function setting.
Proposition 2.2 (basic convex sets). (a) Every halfspace \(\{x:a^{\top}x\le\beta\}\) and every hyperplane \(\{x:a^{\top}x=\beta\}\) is convex. (b) Every affine set \(\{x:Ax=b\}\) is convex. (c) Every ball \(\{x:\lVert x-x_c\rVert\le r\}\) , in any norm, is convex. (d) The intersection of any family of convex sets is convex. Consequently every polyhedron \(\{x:Ax\le b,\ Cx=d\}\) is convex.
Proof. (a) If \(a^{\top}x\le\beta\) and \(a^{\top}y\le\beta\) and \(0\le\theta\le 1\) , then \(a^{\top}(\theta x+(1-\theta)y)=\theta a^{\top}x+(1-\theta)a^{\top}y\le\theta\beta+(1-\theta)\beta=\beta\) , where the inequality uses \(\theta\ge 0\) and \(1-\theta\ge 0\) . With equalities in place of inequalities the same line handles hyperplanes.
(b) If \(Ax=b\) and \(Ay=b\) , then \(A(\theta x+(1-\theta)y)=\theta b+(1-\theta)b=b\) .
(c) If \(\lVert x-x_c\rVert\le r\) and \(\lVert y-x_c\rVert\le r\) , write \(\theta x+(1-\theta)y-x_c=\theta(x-x_c)+(1-\theta)(y-x_c)\) . The triangle inequality and homogeneity of the norm give \(\lVert\theta x+(1-\theta)y-x_c\rVert\le\theta\lVert x-x_c\rVert+(1-\theta)\lVert y-x_c\rVert\le r\) .
(d) If \(x\) and \(y\) belong to every set of the family, then so does each point of the segment between them, because each set is convex. A polyhedron is an intersection of finitely many halfspaces and hyperplanes.
Part (d) is the workhorse. It says that each additional convex constraint keeps the feasible set convex, so the feasible set of a problem is convex whenever each constraint, taken alone, defines a convex set. Unions behave differently: the union of the two points \(\{0\}\) and \(\{1\}\) on the real line is not convex.
Example 2.1: Three sets tested from the definition
A set bounded by a hyperbola. Let \(C=\{x\in\mathbb R^2: x_1>0,\ x_2>0,\ x_1x_2\ge 1\}\) . Take \(x,y\in C\) and \(0\le\theta\le 1\) , and set \(z=\theta x+(1-\theta)y\) . Both coordinates of \(z\) are positive. Expanding,
The first two products are at least \(1\) . For the cross term, the inequality between arithmetic and geometric means gives \(x_1y_2+y_1x_2\ge 2\sqrt{x_1x_2\,y_1y_2}\ge 2\) . Hence \(z_1z_2\ge\theta^2+(1-\theta)^2+2\theta(1-\theta)=1\) , so \(z\in C\) and \(C\) is convex.
The same inequality without the sign conditions. The set \(\{x\in\mathbb R^2:x_1x_2\ge 1\}\) contains \((1,1)\) and \((-1,-1)\) but not their midpoint \((0,0)\) , where the product is \(0\) . It is not convex. It is the union of \(C\) and its reflection through the origin, two convex pieces that do not form a convex whole.
An annulus. The set \(\{x\in\mathbb R^2:1\le\lVert x\rVert\le 2\}\) contains \((1.5,0)\) and \((-1.5,0)\) , whose midpoint is the origin, which has norm \(0\) . It is not convex. The constraint \(\lVert x\rVert\le 2\) defines a convex set; the constraint \(\lVert x\rVert\ge 1\) does not.
One violating pair settles nonconvexity. Convexity needs an argument covering all pairs, which is why the rest of this chapter develops tests that avoid pairs altogether.
2.2 Functions whose chords lie above their graphs
Definition 2.3 (convex function). Let \(C\subseteq\mathbb R^n\) be convex. A function \(f:C\to\mathbb R\) is convex if for all \(x,y\in C\) and all \(\theta\in[0,1]\) ,
It is strictly convex if the inequality is strict whenever \(x\ne y\) and \(0<\theta<1\) . It is concave if \(-f\) is convex.
The domain must be convex for the left side to make sense. Affine functions \(a^{\top}x+\beta\) satisfy the condition with equality, so they are both convex and concave, and they are the only functions that are both. Every norm is convex: by the triangle inequality and homogeneity, \(\lVert\theta x+(1-\theta)y\rVert\le\theta\lVert x\rVert+(1-\theta)\lVert y\rVert\) .
The definition for functions is tied to the definition for sets through two associated sets. The epigraph of \(f\) is the set of points on or above its graph,
Proposition 2.4 (epigraph and sublevel sets). (a) A function \(f\) on a convex set \(C\) is convex if and only if \(\operatorname{epi}f\) is a convex set. (b) If \(f\) is convex, every sublevel set \(\{x\in C:f(x)\le\gamma\}\) is convex.
Proof. (a) Suppose \(f\) is convex and \((x,s),(y,t)\in\operatorname{epi}f\) . Then \(f(\theta x+(1-\theta)y)\le\theta f(x)+(1-\theta)f(y)\le\theta s+(1-\theta)t\) , so the corresponding combination of the two points lies in the epigraph. Conversely, if the epigraph is convex, apply its convexity to the points \((x,f(x))\) and \((y,f(y))\) : the point \((\theta x+(1-\theta)y,\ \theta f(x)+(1-\theta)f(y))\) lies in the epigraph, which is the defining inequality of a convex function.
(b) If \(f(x)\le\gamma\) and \(f(y)\le\gamma\) , then \(f(\theta x+(1-\theta)y)\le\theta\gamma+(1-\theta)\gamma=\gamma\) .
Part (b) explains why constraints \(f_i(x)\le 0\) with convex \(f_i\) define convex feasible sets. Its converse is false: the function \(\sqrt{\lvert x\rvert}\) on \(\mathbb R\) has intervals as sublevel sets and is not convex. Part (a) explains why the epigraph reformulation of Section 1.3 loses nothing: minimizing a convex function is minimizing a linear function over a convex set.
2.3 The tangent plane as a global lower bound
For a differentiable function the chord condition can be replaced by a condition on tangents. This is the single most used fact about convex functions.
Theorem 2.5 (first-order characterization). Let \(f\) be differentiable on an open convex set \(C\subseteq\mathbb R^n\) . Then \(f\) is convex on \(C\) if and only if
Proof. Suppose first that \(f\) is convex, and fix \(x,y\in C\) . For \(0<t\le 1\) the definition gives \(f(x+t(y-x))\le(1-t)f(x)+tf(y)\) , which rearranges to
As \(t\) decreases to \(0\) , the left side tends to the directional derivative of \(f\) at \(x\) in the direction \(y-x\) , which for a differentiable function equals \(\nabla f(x)^{\top}(y-x)\) . The inequality survives the limit, and that is the claim.
Conversely, suppose the tangent inequality holds. Fix \(x,y\in C\) and \(\theta\in[0,1]\) , and let \(z=\theta x+(1-\theta)y\) , which lies in \(C\) . Apply the inequality twice with base point \(z\) :
Multiply the first by \(\theta\) , the second by \(1-\theta\) , and add. The gradient terms combine to \(\nabla f(z)^{\top}(\theta x+(1-\theta)y-z)=0\) , leaving \(\theta f(x)+(1-\theta)f(y)\ge f(z)\) .
The first-order Taylor approximation \(f(x)+\nabla f(x)^{\top}(y-x)\)
is, for any differentiable function, a good model of \(f\)
near \(x\)
; in one variable this is the linearization of calculus (math.calculus.linearization-as-local-model). The theorem says that for convex functions the model is a global underestimate. Information gathered at one point, a value and a gradient, constrains the function everywhere. In particular, if \(\nabla f(x)=0\)
the inequality reads \(f(y)\ge f(x)\)
for all \(y\)
: a stationary point of a convex function is a global minimizer. Chapter 3 builds on exactly this.
The same proof with strict inequalities shows that if \(f(y)>f(x)+\nabla f(x)^{\top}(y-x)\) whenever \(y\ne x\) , then \(f\) is strictly convex.
Example 2.2: Inequalities read off from tangents
Take \(f(x)=e^{x}\) on \(\mathbb R\) , which is convex (its second derivative is positive; see Theorem 2.6). The tangent at \(0\) is \(1+y\) , so
Take \(f(x)=x\log x\) on \(x>0\) , with \(f'(x)=\log x+1\) and \(f''(x)=1/x>0\) . At \(x=1\) we have \(f(1)=0\) and \(f'(1)=1\) , so the tangent is \(y-1\) and
At \(y=2\) the left side is \(2\log 2\approx 1.386\) and the right side is \(1\) . At \(y=1/2\) the left side is \(-\tfrac12\log 2\approx-0.347\) and the right side is \(-0.5\) . A single numerical check proves nothing, but each agrees with the theorem, and the theorem covers every \(y\) at once.
Now take the nonconvex function \(f(x)=x^3-3x\) of Example 1.6. Its tangent at \(x=1\) is the horizontal line at height \(-2\) , since \(f(1)=-2\) and \(f'(1)=0\) . If the tangent inequality held we would have \(f(y)\ge-2\) for all \(y\) , but \(f(-3)=-18\) . The tangent at a local minimizer is not a lower bound, and that is precisely how a local minimizer can fail to be global.
2.4 Curvature and the Hessian test
Checking the tangent inequality for all pairs is no easier than checking the chord inequality. For twice differentiable functions there is a test that involves one point at a time.
Theorem 2.6 (second-order characterization). Let \(f\) be twice continuously differentiable on an open convex set \(C\subseteq\mathbb R^n\) . Then \(f\) is convex on \(C\) if and only if its Hessian is positive semidefinite at every point: \(\nabla^2f(x)\succeq 0\) for all \(x\in C\) . If \(\nabla^2f(x)\succ 0\) for all \(x\in C\) , then \(f\) is strictly convex.
Proof. The argument reduces to one variable by restricting \(f\)
to a line. Fix \(x\in C\)
and a direction \(d\)
, and let \(g(t)=f(x+td)\)
for those \(t\)
with \(x+td\in C\)
. By the chain rule (math.multivariable-calculus.total-derivative-chain-rule),
We also use Taylor’s theorem in one variable with the Lagrange form of the remainder, which the Real Analysis course derives from the mean value theorem: if \(g\) is twice differentiable on an interval containing \(0\) and \(s\) , then \(g(s)=g(0)+g'(0)s+\tfrac12g''(\tau)s^2\) for some \(\tau\) between \(0\) and \(s\) .
Suppose the Hessian is positive semidefinite on \(C\) . Given \(x,y\in C\) , take \(d=y-x\) and \(s=1\) . Then \(g''(\tau)\ge 0\) , so \(g(1)\ge g(0)+g'(0)\) , which reads \(f(y)\ge f(x)+\nabla f(x)^{\top}(y-x)\) . By Theorem 2.5, \(f\) is convex. If the Hessian is positive definite and \(y\ne x\) , then \(g''(\tau)>0\) , the inequality is strict, and \(f\) is strictly convex by the remark following Theorem 2.5.
Suppose instead that \(f\) is convex but \(d^{\top}\nabla^2f(x)d<0\) for some \(x\in C\) and some \(d\) . Because the Hessian is continuous, \(g''(t)<0\) for all \(t\) in some interval \([-\varepsilon,\varepsilon]\) with \(\varepsilon>0\) . Taylor’s theorem with \(s=\varepsilon\) then gives \(g(\varepsilon)<g(0)+g'(0)\varepsilon\) , that is, \(f(x+\varepsilon d)<f(x)+\nabla f(x)^{\top}(\varepsilon d)\) . This contradicts the tangent inequality of Theorem 2.5. Hence the Hessian is positive semidefinite everywhere.
Two cautions. First, positive definiteness of the Hessian is sufficient for strict convexity and not necessary: \(f(x)=x^4\)
is strictly convex, yet \(f''(0)=0\)
. Second, for a symmetric matrix, positive semidefiniteness means \(d^{\top}Hd\ge 0\)
for every direction \(d\)
, which is equivalent to all eigenvalues being nonnegative. It is not a statement about the entries. An eigenvector is a direction along which the matrix acts as multiplication by the eigenvalue (math.linear-algebra.eigenvector-as-steady-direction), and Linear Algebra shows that a symmetric matrix has an orthonormal basis of eigenvectors; so an eigenvector with a negative eigenvalue is a direction of negative curvature.
Example 2.3: Two quadratics with positive diagonals
Let \(f(x)=x_1^2+x_1x_2+x_2^2\) . Its Hessian is constant,
with characteristic polynomial \((2-\mu)^2-1\) , so the eigenvalues are \(1\) and \(3\) . Both are positive, the Hessian is positive definite, and \(f\) is strictly convex on \(\mathbb R^2\) .
Let \(h(x)=x_1^2+4x_1x_2+x_2^2\) . Its Hessian is
with eigenvalues \(-2\) and \(6\) . The diagonal entries are positive and the function is not convex. The eigenvector for \(-2\) is \((1,-1)\) , and along it \(h(t,-t)=t^2-4t^2+t^2=-2t^2\) , a downward parabola. To exhibit the failure in the terms of Definition 2.3, take the points \((1,-1)\) and \((-1,1)\) , where \(h=-2\) ; their midpoint is the origin, where \(h=0>-2\) .
Common mistake. Testing definiteness from diagonal entries alone, or testing convexity from a plot or a few midpoint pairs. The function \(h\) of Example 2.3 has positive diagonal Hessian entries and satisfies the midpoint inequality for many pairs, for instance any two points on a coordinate axis. Convexity is a statement about every segment, and positive semidefiniteness is a statement about every direction. Compute the eigenvalues, or for a \(2\times 2\) symmetric matrix check that the trace and the determinant are both nonnegative; for larger matrices use a factorization.
Example 2.4: The log-sum-exp function
Let \(f(x)=\log(e^{x_1}+e^{x_2})\) on \(\mathbb R^2\) . Write \(p_i=e^{x_i}/(e^{x_1}+e^{x_2})\) , so that \(p_1,p_2>0\) and \(p_1+p_2=1\) . Differentiating,
For any \(v\in\mathbb R^2\) ,
This is the variance of a random variable that takes the value \(v_1\) with probability \(p_1\) and \(v_2\) with probability \(p_2\) , so it is nonnegative. Without probability language: by the Cauchy–Schwarz inequality applied to the vectors \((\sqrt{p_1}v_1,\sqrt{p_2}v_2)\) and \((\sqrt{p_1},\sqrt{p_2})\) , we get \((p_1v_1+p_2v_2)^2\le(p_1v_1^2+p_2v_2^2)(p_1+p_2)\) , and \(p_1+p_2=1\) . So the Hessian is positive semidefinite everywhere and \(f\) is convex.
It is not strictly convex. At \(x=(0,0)\) we have \(p=(1/2,1/2)\) and
with eigenvalues \(0\) and \(1/2\) . The zero eigenvalue belongs to the direction \((1,1)\) , and indeed \(f(x_1+t,x_2+t)=f(x_1,x_2)+t\) exactly: along that direction the function is affine. The Hessian test found not only that \(f\) is convex but where its convexity is weakest.
2.5 Building convex functions from simpler ones
Most convex functions met in practice are recognised not by differentiation but by the way they are assembled.
Proposition 2.7 (operations preserving convexity). Let \(f,f_1,\dots,f_k\) be convex functions on \(\mathbb R^n\) . (a) If \(w_1,\dots,w_k\ge 0\) , then \(w_1f_1+\dots+w_kf_k\) is convex. (b) For any matrix \(A\) and vector \(b\) of compatible sizes, \(x\mapsto f(Ax+b)\) is convex. (c) The pointwise maximum \(x\mapsto\max\{f_1(x),\dots,f_k(x)\}\) is convex. (d) If \(h:\mathbb R\to\mathbb R\) is convex and nondecreasing on an interval containing the range of \(f\) , then \(x\mapsto h(f(x))\) is convex.
Proof. Fix \(x,y\) and \(\theta\in[0,1]\) and write \(z=\theta x+(1-\theta)y\) . (a) Multiply each inequality \(f_i(z)\le\theta f_i(x)+(1-\theta)f_i(y)\) by \(w_i\ge 0\) and add. (b) Since \(Az+b=\theta(Ax+b)+(1-\theta)(Ay+b)\) , convexity of \(f\) gives \(f(Az+b)\le\theta f(Ax+b)+(1-\theta)f(Ay+b)\) . (c) For each \(i\) , \(f_i(z)\le\theta f_i(x)+(1-\theta)f_i(y)\le\theta\max_jf_j(x)+(1-\theta)\max_jf_j(y)\) ; the right side does not depend on \(i\) , so it also bounds \(\max_if_i(z)\) . (d) Since \(f(z)\le\theta f(x)+(1-\theta)f(y)\) and \(h\) is nondecreasing, \(h(f(z))\le h(\theta f(x)+(1-\theta)f(y))\) , and since \(h\) is convex the right side is at most \(\theta h(f(x))+(1-\theta)h(f(y))\) .
Rule (c) extends, with the same proof, to the supremum of an arbitrary family of convex functions, provided the supremum is finite. That extension is what will make every Lagrange dual function concave in Chapter 5.
Example 2.5: Convexity by construction, and a rule misapplied
A regularised least-squares objective. Let \(F(x)=\lVert Ax-b\rVert^2+\lambda\lVert x\rVert_1\) with \(\lambda\ge 0\) , where \(\lVert x\rVert_1=\lvert x_1\rvert+\dots+\lvert x_n\rvert\) . The function \(u\mapsto\lVert u\rVert^2\) is convex because its Hessian is \(2I\) . By rule (b), \(x\mapsto\lVert Ax-b\rVert^2\) is convex. Each \(\lvert x_i\rvert\) is the maximum of the two linear functions \(x_i\) and \(-x_i\) , convex by rule (c), and their sum is convex by rule (a). A final use of rule (a) with weights \(1\) and \(\lambda\) shows that \(F\) is convex. No derivative of the nondifferentiable term was needed.
A piecewise linear function. The function \(\max\{2x+1,-x+4,\tfrac12x+2\}\) of Exercise 1.8 is a maximum of affine functions, convex by rule (c).
The composition rule without monotonicity. Let \(g(x)=x^2-1\) , which is convex, and \(h(t)=t^2\) , which is convex. One might conclude that \(h(g(x))=(x^2-1)^2\) is convex. It is not: it equals \(0\) at \(x=1\) and at \(x=-1\) , and equals \(1\) at their midpoint \(0\) . Rule (d) requires \(h\) to be nondecreasing on the range of \(g\) , which is \([-1,\infty)\) , and \(t^2\) is decreasing on \([-1,0]\) . Where \(g\) is nonnegative the rule does apply: on the interval \(x\ge 1\) the composition is convex.
2.6 Strong convexity
Convexity bounds a function below by its tangent planes. For algorithms one often needs more: a guarantee that the function curves upward at a definite rate, so that being far from the minimizer forces the value to be noticeably larger.
Definition 2.8 (strong convexity). Let \(m>0\) . A function \(f\) on a convex set \(C\) is strongly convex with modulus \(m\) , or \(m\) -strongly convex, if the function \(x\mapsto f(x)-\tfrac m2\lVert x\rVert^2\) is convex on \(C\) .
Proposition 2.9 (characterizations of strong convexity). Let \(f\) be differentiable on an open convex set \(C\) . Then \(f\) is \(m\) -strongly convex on \(C\) if and only if
If \(f\) is twice continuously differentiable, this holds if and only if \(\nabla^2f(x)\succeq mI\) for all \(x\in C\) , that is, every eigenvalue of every Hessian is at least \(m\) .
Proof. Let \(g(x)=f(x)-\tfrac m2\lVert x\rVert^2\) , so \(\nabla g(x)=\nabla f(x)-mx\) . By Theorem 2.5, \(g\) is convex if and only if \(g(y)\ge g(x)+\nabla g(x)^{\top}(y-x)\) for all \(x,y\) , that is,
The bracket equals \(\lVert y\rVert^2-2x^{\top}y+\lVert x\rVert^2=\lVert y-x\rVert^2\) . For the second statement, \(\nabla^2g=\nabla^2f-mI\) , and by Theorem 2.6 \(g\) is convex if and only if this matrix is positive semidefinite everywhere.
Strong convexity implies strict convexity, which implies convexity, and neither implication reverses.
Example 2.6: Convex, strictly convex, strongly convex
The function \(f(x)=x^4\) has \(f''(x)=12x^2\ge 0\) , so it is convex on \(\mathbb R\) , and it is strictly convex because the tangent inequality is strict away from the point of tangency. It is not strongly convex on \(\mathbb R\) : strong convexity with modulus \(m\) would require \(12x^2\ge m\) for every \(x\) , which fails near \(0\) , where the curvature vanishes. On the half-line \(x\ge 1\) the same function is strongly convex with modulus \(12\) , since \(12x^2\ge 12\) there. Strong convexity is a property of a function on a set.
The quadratic \(f(x)=x_1^2+x_1x_2+x_2^2\) of Example 2.3 has constant Hessian with eigenvalues \(1\) and \(3\) , so it is strongly convex with modulus \(m=1\) , the smallest eigenvalue. The log-sum-exp function of Example 2.4 has a zero eigenvalue at every point, in the direction \((1,1)\) , so it is convex and not even strictly convex.
An affine function is convex with zero curvature in every direction; it has no minimizer on \(\mathbb R^n\) unless it is constant. A strongly convex function is at the opposite extreme, as the last result of the chapter shows.
2.7 What convexity buys
Theorem 2.10 (local minimizers are global). Let \(f\) be convex on a convex set \(C\) . (a) Every local minimizer of \(f\) over \(C\) is a global minimizer. (b) The set of global minimizers is convex. (c) If \(f\) is strictly convex, there is at most one global minimizer.
Proof. (a) Let \(\bar x\) be a local minimizer and suppose some \(y\in C\) has \(f(y)<f(\bar x)\) . For \(0<t\le 1\) the point \(z_t=\bar x+t(y-\bar x)\) lies in \(C\) , and by convexity
As \(t\to 0\) the points \(z_t\) approach \(\bar x\) , so every neighbourhood of \(\bar x\) contains feasible points with smaller value. This contradicts local minimality.
(b) The set of global minimizers is the sublevel set \(\{x\in C:f(x)\le p^\star\}\) , which is convex by Proposition 2.4.
(c) If \(x\ne y\) were both global minimizers, strict convexity would give \(f(\tfrac12x+\tfrac12y)<\tfrac12f(x)+\tfrac12f(y)=p^\star\) , which is impossible.
The theorem says nothing about existence. The strictly convex function \(e^{x}\) has no minimizer on \(\mathbb R\) , as Example 1.2 showed. Existence still comes from Theorem 1.4, and strong convexity supplies its hypothesis: by Proposition 2.9, a differentiable \(m\) -strongly convex function on \(\mathbb R^n\) satisfies \(f(y)\ge f(0)+\nabla f(0)^{\top}y+\tfrac m2\lVert y\rVert^2\) , and the right side tends to \(+\infty\) as \(\lVert y\rVert\to\infty\) . So the function is coercive, has a minimizer, and by part (c) has exactly one.
We can now say precisely what a convex optimization problem is: in the standard form of Definition 1.1, the objective \(f_0\) and the inequality constraint functions \(f_1,\dots,f_m\) are convex and the equality constraint functions \(h_j\) are affine. The feasible set is then convex, as an intersection of sublevel sets of convex functions and hyperplanes, and Theorem 2.10 applies. Equality constraints must be affine, not merely convex: the set \(\{x:x_1^2+x_2^2=1\}\) is a level set of a convex function, not a sublevel set, and it is not convex.
The next chapter asks how to recognise a minimizer when no constraint interferes. For a convex function the answer will be one line, and it is the tangent inequality of Theorem 2.5 that makes it so.
Exercises
-
Decide which of these subsets of \(\mathbb R^2\) are convex, giving a proof or a violating pair of points for each: (a) \(\{x:x_1^2+4x_2^2\le 4\}\) ; (b) \(\{x:x_1^2-x_2^2\le 1\}\) ; (c) \(\{x:x_2\ge\lvert x_1\rvert\}\) ; (d) \(\{x:x_1x_2\le 1\}\) .
Answer
(a) Convex: it is the sublevel set \(\{x:x_1^2+4x_2^2\le 4\}\) of a convex quadratic (Proposition 2.4). (b) Not convex: \((2,2)\) and \((2,-2)\) satisfy \(x_1^2-x_2^2=0\le 1\) , but their midpoint \((2,0)\) gives \(4>1\) . (c) Convex: it is the intersection of the halfspaces \(x_1-x_2\le 0\) and \(-x_1-x_2\le 0\) . (d) Not convex: \((3,0)\) and \((0,3)\) have product \(0\) , but their midpoint \((1.5,1.5)\) has product \(2.25>1\) .
-
Let \(C\subseteq\mathbb R^n\) be convex, \(A\) an \(m\times n\) matrix and \(b\in\mathbb R^m\) . Prove that the image \(\{Ax+b:x\in C\}\) is convex, and that for a convex set \(D\subseteq\mathbb R^m\) the inverse image \(\{x:Ax+b\in D\}\) is convex.
Solution
Image. Take two points of the image, \(u=Ax+b\) and \(v=Ay+b\) with \(x,y\in C\) , and \(\theta\in[0,1]\) . Then
\[ \theta u+(1-\theta)v=\theta(Ax+b)+(1-\theta)(Ay+b)=A(\theta x+(1-\theta)y)+b, \]because the coefficients \(\theta\) and \(1-\theta\) sum to \(1\) , so the two copies of \(b\) combine into one. Since \(C\) is convex, \(\theta x+(1-\theta)y\in C\) , and therefore \(\theta u+(1-\theta)v\) is the image of a point of \(C\) .
Inverse image. Let \(x,y\) satisfy \(Ax+b\in D\) and \(Ay+b\in D\) . By the same identity, \(A(\theta x+(1-\theta)y)+b=\theta(Ax+b)+(1-\theta)(Ay+b)\) , which is a convex combination of two points of \(D\) and so lies in \(D\) because \(D\) is convex. Hence \(\theta x+(1-\theta)y\) belongs to the inverse image. Both arguments use only that an affine map commutes with convex combinations; projections, scalings, translations, and sums of sets are all covered as special cases.
-
Decide whether the point \((1,1)\) lies in the convex hull of \((0,0),(3,0),(0,3)\) , and whether it lies in the convex hull of \((0,0),(2,0),(0,1)\) ; when it does, write it as an explicit convex combination.
Answer
Yes for the first triangle: \((1,1)=\tfrac13(0,0)+\tfrac13(3,0)+\tfrac13(0,3)\) . No for the second: that hull is \(\{x\ge 0:\tfrac12x_1+x_2\le 1\}\) , and \(\tfrac12+1=1.5>1\) .
-
Using only Definition 2.3 and no derivatives, prove that \(\lvert x\rvert\) and \(x^2\) are convex on \(\mathbb R\) , and exhibit two points and a value of \(\theta\) showing that \(x^3\) is not convex on \(\mathbb R\) .
Hint
For \(\lvert x\rvert\) use the triangle inequality on \(\theta x+(1-\theta)y\) . For \(x^2\) verify the identity \(\theta x^2+(1-\theta)y^2-(\theta x+(1-\theta)y)^2=\theta(1-\theta)(x-y)^2\) . For \(x^3\) try \(x=-2\) , \(y=0\) , \(\theta=\tfrac12\) : the midpoint value is \(-1\) and the chord value is \(-4\) .
-
Apply Theorem 2.5 to the convex function \(-\log x\) on \(x>0\) to prove that \(\log y\le y-1\) for all \(y>0\) , and then use concavity of the logarithm to prove that \(\sqrt{ab}\le\tfrac12(a+b)\) for all \(a,b>0\) .
Solution
Let \(f(x)=-\log x\) on \(x>0\) . Then \(f''(x)=1/x^2>0\) , so \(f\) is convex by Theorem 2.6, and \(f'(x)=-1/x\) . Theorem 2.5 with base point \(x=1\) gives, for every \(y>0\) ,
\[ -\log y\ \ge\ -\log 1+(-1)(y-1)=-(y-1), \]which is \(\log y\le y-1\) . Equality holds only at \(y=1\) because \(f\) is strictly convex.
For the second claim, concavity of \(\log\) is convexity of \(-\log\) . Definition 2.3 applied to \(-\log\) at the points \(a,b>0\) with \(\theta=\tfrac12\) gives \(-\log\bigl(\tfrac12a+\tfrac12b\bigr)\le-\tfrac12\log a-\tfrac12\log b\) , that is,
\[ \log\frac{a+b}{2}\ \ge\ \tfrac12\log a+\tfrac12\log b=\log\sqrt{ab}. \]The exponential function is strictly increasing, so applying it to both sides preserves the inequality and yields \(\sqrt{ab}\le\tfrac12(a+b)\) . This is the inequality between geometric and arithmetic means that was used, without proof, in Example 2.1; it is now a consequence of convexity.
-
For which values of the real parameter \(c\) is \(f(x_1,x_2)=x_1^2+cx_1x_2+x_2^2\) convex on \(\mathbb R^2\) , for which is it strictly convex, and for which is it strongly convex? Give the strong convexity modulus as a function of \(c\) when it exists.
Solution
The Hessian is constant:
\[ \nabla^2f=\begin{pmatrix}2&c\\c&2\end{pmatrix}, \]with characteristic polynomial \((2-\mu)^2-c^2\) and eigenvalues \(2-c\) and \(2+c\) . By Theorem 2.6, \(f\) is convex exactly when both eigenvalues are nonnegative, that is, when \(\lvert c\rvert\le 2\) .
If \(\lvert c\rvert<2\) both eigenvalues are positive, the Hessian is positive definite, and \(f\) is strictly convex. If \(\lvert c\rvert=2\) one eigenvalue is zero; for \(c=2\) the function is \((x_1+x_2)^2\) , which vanishes on the whole line \(x_1+x_2=0\) , so it is constant along a segment and cannot be strictly convex, and \(c=-2\) is the same with \(x_1-x_2\) . So \(f\) is strictly convex exactly when \(\lvert c\rvert<2\) .
By Proposition 2.9, \(f\) is \(m\) -strongly convex exactly when both eigenvalues are at least \(m\) . The best modulus is the smaller eigenvalue, \(m=2-\lvert c\rvert\) , which is positive exactly when \(\lvert c\rvert<2\) . For a quadratic, then, strict and strong convexity coincide; the distinction between them needs non-quadratic functions such as \(x^4\) .
-
Show that \(f(x_1,x_2)=x_1^2/x_2\) is convex on the open halfplane \(x_2>0\) by computing its Hessian and writing it as a nonnegative multiple of \(vv^{\top}\) for a suitable vector \(v\) .
Solution
Differentiate \(f(x_1,x_2)=x_1^2/x_2\) twice:
\[ \frac{\partial^2f}{\partial x_1^2}=\frac{2}{x_2},\qquad \frac{\partial^2f}{\partial x_1\partial x_2}=-\frac{2x_1}{x_2^2},\qquad \frac{\partial^2f}{\partial x_2^2}=\frac{2x_1^2}{x_2^3}. \]Factor out \(2/x_2^3\) :
\[ \nabla^2f(x)=\frac{2}{x_2^3}\begin{pmatrix}x_2^2&-x_1x_2\\-x_1x_2&x_1^2\end{pmatrix}=\frac{2}{x_2^3}\,vv^{\top},\qquad v=\begin{pmatrix}x_2\\-x_1\end{pmatrix}. \]For any direction \(d\) we get \(d^{\top}\nabla^2f(x)d=\tfrac{2}{x_2^3}(v^{\top}d)^2\) , which is nonnegative because \(x_2>0\) on the domain. The domain \(\{x_2>0\}\) is open and convex, so Theorem 2.6 applies and \(f\) is convex there. The Hessian has rank one: the curvature is zero in the direction \(d=(x_1,x_2)\) perpendicular to \(v\) , which reflects the identity \(f(sx_1,sx_2)=sf(x_1,x_2)\) for \(s>0\) . The function is linear along rays from the origin, so it is convex and not strictly convex.
-
A student claims that \(f(x_1,x_2)=x_1^2+3x_1x_2+x_2^2\) is convex because its Hessian has positive diagonal entries and \(f\) is nonnegative at six points tested on the axes. Find the error, a direction of negative curvature, and two points whose midpoint violates the inequality of Definition 2.3.
Solution
The Hessian is
\[ \nabla^2f=\begin{pmatrix}2&3\\3&2\end{pmatrix}, \]with eigenvalues \(2-3=-1\) and \(2+3=5\) . A negative eigenvalue means the Hessian is not positive semidefinite, so by Theorem 2.6 \(f\) is not convex. The student’s first error is reading definiteness from the diagonal: the diagonal entries are the curvatures along the coordinate axes only, and here the off-diagonal entry dominates. The second error is the choice of test points: on the axes one of \(x_1,x_2\) is zero, the cross term vanishes, and \(f\) reduces to a square, which cannot reveal anything about the mixed direction.
The eigenvector for \(-1\) is \((1,-1)\) , and \(f(t,-t)=t^2-3t^2+t^2=-t^2\) , so this is a direction of negative curvature. For a violating pair take \(x=(1,-1)\) and \(y=(-1,1)\) , where \(f=-1\) . Their midpoint is \((0,0)\) with \(f=0\) , and \(0>-1=\tfrac12f(x)+\tfrac12f(y)\) , contradicting Definition 2.3.
-
For each function name the rule of Proposition 2.7 that proves convexity, or show that convexity fails: (a) \(e^{x_1^2+x_2^2}\) ; (b) \(\max\{x_1,x_2,0\}\) ; (c) \(\lVert Ax-b\rVert+2\lVert x\rVert_1\) ; (d) \((x_1^2+x_2^2-1)^2\) ; (e) \(1/(1-x_1^2-x_2^2)\) on the open unit disc.
Answer
(a) Convex by rule (d): \(e^{t}\) is convex and nondecreasing, composed with the convex function \(x_1^2+x_2^2\) . (b) Convex by rule (c): a maximum of three affine functions. (c) Convex by rules (b) and (a): a norm composed with an affine map, plus a nonnegative multiple of a norm. (d) Not convex: the value is \(0\) at \((1,0)\) and \((-1,0)\) and \(1\) at their midpoint. (e) Convex by rule (d): \(h(t)=1/(1-t)\) is convex and increasing on \(t<1\) , and the inner function \(x_1^2+x_2^2\) is convex with range \([0,1)\) on the open disc.
-
Prove that a function all of whose sublevel sets are convex need not be convex, by analysing \(f(x)=\sqrt{\lvert x\rvert}\) on \(\mathbb R\) : describe its sublevel sets and find a chord that lies below the graph.
Hint
The sublevel set for level \(\gamma\ge 0\) is the interval \([-\gamma^2,\gamma^2]\) . For the chord, compare the value at the midpoint of \(0\) and \(4\) with the average of the values at \(0\) and \(4\) .
-
Classify each function on \(\mathbb R\) as strongly convex (with the best modulus), strictly but not strongly convex, or convex but not strictly convex: (a) \(x^2+\cos x\) ; (b) \(\sqrt{1+x^2}\) ; (c) \(\max\{\lvert x\rvert-1,0\}\) .
Answer
(a) \(f''(x)=2-\cos x\in[1,3]\) , so strongly convex with best modulus \(1\) . (b) \(f''(x)=(1+x^2)^{-3/2}>0\) with infimum \(0\) , so strictly convex and not strongly convex. (c) Convex as a maximum of convex functions, constant on \([-1,1]\) , so not strictly convex.
-
Prove that \(f\) is \(m\) -strongly convex on a convex set \(C\) if and only if \(f(\theta x+(1-\theta)y)\le\theta f(x)+(1-\theta)f(y)-\tfrac m2\theta(1-\theta)\lVert x-y\rVert^2\) for all \(x,y\in C\) and \(\theta\in[0,1]\) ; then deduce that a minimizer \(x^\star\) of such an \(f\) over \(C\) satisfies \(f(x)-f(x^\star)\ge\tfrac m2\lVert x-x^\star\rVert^2\) for all \(x\in C\) .
Solution
Let \(g(x)=f(x)-\tfrac m2\lVert x\rVert^2\) and \(z=\theta x+(1-\theta)y\) . By Definition 2.8, \(f\) is \(m\) -strongly convex exactly when \(g(z)\le\theta g(x)+(1-\theta)g(y)\) for all \(x,y,\theta\) . Substituting the definition of \(g\) and moving the norm terms to the right, this is
\[ f(z)\le\theta f(x)+(1-\theta)f(y)-\frac m2\Bigl(\theta\lVert x\rVert^2+(1-\theta)\lVert y\rVert^2-\lVert z\rVert^2\Bigr). \]Expand \(\lVert z\rVert^2=\theta^2\lVert x\rVert^2+2\theta(1-\theta)x^{\top}y+(1-\theta)^2\lVert y\rVert^2\) . Then the bracket equals \(\theta(1-\theta)\lVert x\rVert^2+\theta(1-\theta)\lVert y\rVert^2-2\theta(1-\theta)x^{\top}y=\theta(1-\theta)\lVert x-y\rVert^2\) . Each step is an equivalence, which proves the first claim.
For the growth bound, let \(x^\star\) minimize \(f\) over \(C\) and take any \(x\in C\) and \(\theta\in(0,1]\) . The point \(\theta x+(1-\theta)x^\star\) lies in \(C\) , so its value is at least \(f(x^\star)\) . Combining with the inequality just proved,
\[ f(x^\star)\le\theta f(x)+(1-\theta)f(x^\star)-\frac m2\theta(1-\theta)\lVert x-x^\star\rVert^2 . \]Subtract \(f(x^\star)\) and divide by \(\theta>0\) : \(0\le f(x)-f(x^\star)-\tfrac m2(1-\theta)\lVert x-x^\star\rVert^2\) . Letting \(\theta\to 0\) gives \(f(x)-f(x^\star)\ge\tfrac m2\lVert x-x^\star\rVert^2\) . No derivative was used, so the bound holds for nondifferentiable strongly convex functions and for constrained minimizers.
-
Prove Jensen’s inequality for finite combinations by induction on \(k\) : if \(f\) is convex on a convex set \(C\) , \(x_1,\dots,x_k\in C\) , and \(\theta_1,\dots,\theta_k\ge 0\) sum to \(1\) , then \(f(\theta_1x_1+\dots+\theta_kx_k)\le\theta_1f(x_1)+\dots+\theta_kf(x_k)\) .
Hint
The case \(k=2\) is Definition 2.3. For the step, assume \(\theta_k<1\) and write the combination as \((1-\theta_k)w+\theta_kx_k\) with \(w=\sum_{i<k}\frac{\theta_i}{1-\theta_k}x_i\) . Check that \(w\) is a convex combination of \(k-1\) points, so \(w\in C\) , apply the two-point inequality, and then the induction hypothesis to \(f(w)\) .
-
Show that \(f(x)=\log(1+e^{x})\) is convex on \(\mathbb R\) , find the supremum of \(f''\) , and use the tangent at \(0\) to prove \(\log(1+e^{x})\ge\log 2+\tfrac12x\) for all real \(x\) .
Answer
With \(\sigma(x)=e^{x}/(1+e^{x})\) we have \(f'=\sigma\) and \(f''=\sigma(1-\sigma)>0\) , so \(f\) is convex. Since \(\sigma\in(0,1)\) , the product \(\sigma(1-\sigma)\) is at most \(\tfrac14\) , with equality at \(\sigma=\tfrac12\) , that is, at \(x=0\) ; so \(\sup f''=\tfrac14\) . The tangent at \(0\) has value \(f(0)=\log 2\) and slope \(f'(0)=\tfrac12\) , and Theorem 2.5 gives the inequality.
-
Example 1.6 exhibited a local minimizer of \(x^3-3x\) on \([-3,3]\) that is not global. Find the largest subinterval of \([-3,3]\) containing \(x=1\) on which this function is convex, and verify the conclusion of Theorem 2.10 on that subinterval by comparing values.
Solution
Here \(f(x)=x^3-3x\) and \(f''(x)=6x\) , which is nonnegative exactly when \(x\ge 0\) . Within the feasible interval \([-3,3]\) of Example 1.6, the largest interval containing \(1\) on which \(f''\ge 0\) throughout is \([0,3]\) . An interval extending to the left of \(0\) would contain points with negative second derivative, and by Theorem 2.6 applied on its interior \(f\) would fail to be convex there.
On \([0,3]\) the function is convex, and \(x=1\) is a local minimizer because \(f'(1)=0\) and \(f''(1)=6>0\) . Theorem 2.10 then asserts that \(x=1\) is a global minimizer over \([0,3]\) . Checking directly: \(f'(x)=3(x-1)(x+1)\) is negative on \((0,1)\) and positive on \((1,3)\) , so \(f\) decreases from \(f(0)=0\) to \(f(1)=-2\) and then increases to \(f(3)=18\) . The minimum over \([0,3]\) is \(-2\) at \(x=1\) , as predicted. The global minimizer \(x=-3\) of Example 1.6 lies outside the region of convexity, which is how it escaped the local test.
-
For distinct points \(a,b\in\mathbb R^n\) show that \(\{x:\lVert x-a\rVert\le\lVert x-b\rVert\}\) is a halfspace, identifying its normal vector and offset, and decide whether \(\{x:\lVert x-a\rVert\le 2\lVert x-b\rVert\}\) is convex.
Solution
Both sides of \(\lVert x-a\rVert\le\lVert x-b\rVert\) are nonnegative, so by monotonicity of squaring on \([0,\infty)\) the condition is equivalent to \(\lVert x-a\rVert^2\le\lVert x-b\rVert^2\) . Expanding, \(\lVert x\rVert^2-2a^{\top}x+\lVert a\rVert^2\le\lVert x\rVert^2-2b^{\top}x+\lVert b\rVert^2\) . The quadratic terms cancel, leaving
\[ 2(b-a)^{\top}x\le\lVert b\rVert^2-\lVert a\rVert^2 . \]This is a halfspace with normal vector \(b-a\) and offset \(\tfrac12(\lVert b\rVert^2-\lVert a\rVert^2)\) ; its boundary is the perpendicular bisector of the segment from \(a\) to \(b\) . It is convex by Proposition 2.2.
With the factor \(2\) the quadratic terms no longer cancel. Squaring gives \(\lVert x-a\rVert^2\le 4\lVert x-b\rVert^2\) , that is, \(3\lVert x\rVert^2-2(4b-a)^{\top}x+4\lVert b\rVert^2-\lVert a\rVert^2\ge 0\) . Completing the square with \(c=\tfrac13(4b-a)\) turns this into \(\lVert x-c\rVert^2\ge r^2\) with \(r^2=\lVert c\rVert^2-\tfrac13(4\lVert b\rVert^2-\lVert a\rVert^2)=\tfrac49\lVert a-b\rVert^2\) . So the set is the complement of the open ball of radius \(r=\tfrac23\lVert a-b\rVert\) about \(c\) . It is not convex: for any unit vector \(u\) the points \(c+ru\) and \(c-ru\) belong to it and their midpoint \(c\) does not. In one dimension with \(a=0\) and \(b=3\) the set is \(\{x\le 2\}\cup\{x\ge 6\}\) .
-
Give an example of a strictly convex function on \(\mathbb R\) with no minimizer and an example of a convex function on \(\mathbb R\) with infinitely many minimizers, and say exactly what Theorem 2.10 does and does not promise in each case.
Answer
\(e^{x}\) is strictly convex with no minimizer; Theorem 2.10(c) promises at most one minimizer, and zero is consistent with that. The function \(\max\{\lvert x\rvert-1,0\}\) is convex with the whole interval \([-1,1]\) as its set of minimizers; Theorem 2.10(b) promises that this set is convex, and an interval is. Neither part of the theorem asserts existence, and uniqueness needs strict convexity.
-
Prove that the Euclidean norm \(\lVert x\rVert\) is convex but not strictly convex on \(\mathbb R^n\) , and that \(\lVert x\rVert^2\) is strongly convex with modulus \(2\) .
Hint
Convexity of the norm is the triangle inequality plus homogeneity. To see that it is not strict, take \(y=2x\) with \(x\ne 0\) and check that the inequality of Definition 2.3 holds with equality. For the square, note that \(\lVert x\rVert^2-\tfrac22\lVert x\rVert^2\) is the zero function, which is convex, and that no larger modulus works because \(\lVert x\rVert^2-\tfrac m2\lVert x\rVert^2\) is concave and not affine when \(m>2\) .