-
A firm chooses quantities \(x_1,x_2\ge0\) to maximize \(4x_1+3x_2\) subject to \(x_1+x_2\le5\) and \(x_1+3x_2\le9\) . Find the optimal plan and profit, the shadow prices of both resources, and a certificate that would convince a sceptic.
Solution
The feasible region has vertices \((0,0)\) , \((5,0)\) , \((3,2)\) , and \((0,3)\) , where \((3,2)\) solves \(x_1+x_2=5\) , \(x_1+3x_2=9\) . The profits are \(0\) , \(20\) , \(12+6=18\) , and \(9\) . By Theorem 4.5 an optimal solution occurs at a vertex, so the optimal plan is \(x=(5,0)\) with profit \(20\) . Only the first resource is used up: \(5\le5\) and \(5\le9\) .
The dual is: minimize \(5y_1+9y_2\) subject to \(y_1+y_2\ge4\) , \(y_1+3y_2\ge3\) , \(y\ge0\) . Complementary slackness (Theorem 4.11): the second primal constraint is slack, so \(y_2=0\) ; \(x_1>0\) , so the first dual constraint is tight, \(y_1+y_2=4\) , giving \(y=(4,0)\) . Check the remaining dual constraint: \(4+0\ge3\) . So the shadow prices are \(4\) and \(0\) .
Certificate for a sceptic: \(x=(5,0)\) satisfies all primal constraints and has value \(20\) ; \(y=(4,0)\) satisfies all dual constraints and has value \(5\cdot4+9\cdot0=20\) . By weak duality no feasible plan can earn more than any dual feasible value, in particular more than \(20\) . The second resource has price zero because it is not scarce at the optimum; an extra unit of the first is worth \(4\) .
-
Decide, with proof, whether \(f(x_1,x_2)=x_1^4+x_2^2-2x_1^2\) is convex on \(\mathbb R^2\) ; find all its stationary points and classify them; and state its global minimum value with a justification of existence.
Answer
The Hessian is diagonal with entries \(12x_1^2-4\) and \(2\) ; at the origin the first is \(-4\) , so \(f\) is not convex. Stationary points: \((0,0)\) , a saddle with \(f=0\) , and \((\pm1,0)\) , strict local minimizers with Hessian entries \(8\) and \(2\) and \(f=-1\) . Since \(f=(x_1^2-1)^2-1+x_2^2\ge-1\) and \(f\) is coercive, the global minimum value is \(-1\) , attained at \((\pm1,0)\) .
-
Minimize \((x_1-3)^2+(x_2-1)^2\) subject to \(x_1^2+x_2^2\le5\) and \(x_1\ge0\) , and give the multipliers; then say by how much, to first order, the optimal value changes if the radius constraint is relaxed to \(x_1^2+x_2^2\le5.1\) .
Solution
The unconstrained minimizer \(c=(3,1)\) has \(\lVert c\rVert^2=10>5\) , so the disc constraint is active; try it alone. With \(f_1=x_1^2+x_2^2-5\) and multiplier \(\lambda\) , stationarity is \(2(x-c)+2\lambda x=0\) , so \(x=c/(1+\lambda)\) : the solution is the point of the circle in the direction of \(c\) ,
\[ x^\star=\sqrt5\,\frac{(3,1)}{\sqrt{10}}=\frac{(3,1)}{\sqrt2}\approx(2.1213,\ 0.7071),\qquad1+\lambda=\frac{\sqrt{10}}{\sqrt5}=\sqrt2,\quad\lambda^\star=\sqrt2-1\approx0.4142 . \]The second constraint \(x_1\ge0\) is inactive, with multiplier \(0\) , and \(\lambda^\star>0\) , so all KKT conditions hold; the problem is convex, so this is the solution. The optimal value is the squared distance from \(c\) to the circle, \((\sqrt{10}-\sqrt5)^2=15-10\sqrt2\approx0.8579\) .
Relaxing the constraint to \(x_1^2+x_2^2\le5+u\) with \(u=0.1\) changes the optimal value, to first order, by \(-\lambda^\star u\approx-0.0414\) . Exactly, the new value is \((\sqrt{10}-\sqrt{5.1})^2\approx0.8171\) , a change of \(-0.0407\) , which respects the bound \(p^\star(u)\ge p^\star(0)-\lambda^\star u\) of Theorem 5.6.
-
Let \(f\) be convex and differentiable on \(\mathbb R^n\) and suppose \(\nabla f(\bar x)^{\top}(x-\bar x)\ge0\) for every \(x\) in a closed convex set \(C\) containing \(\bar x\) . Prove that \(\bar x\) minimizes \(f\) over \(C\) , and give an example in which \(\nabla f(\bar x)\ne0\) .
Hint
This is one direction of Lemma 9.1: combine the hypothesis with the tangent inequality of Theorem 2.5. For the example take \(f(x)=x\) on \(C=[0,1]\) and \(\bar x=0\) .
-
For \(f(x)=\tfrac12(x_1^2+25x_2^2)\) give \(m\) , \(L\) , and \(\kappa\) ; the number of gradient steps with \(\alpha=1/L\) that guarantee a reduction of \(\lVert x_k-x^\star\rVert\) by \(10^{-4}\) ; and the number of Newton steps needed for the same purpose.
Answer
\(m=1\) , \(L=25\) , \(\kappa=25\) . By Theorem 7.7 the squared distance contracts by \(1-1/25=0.96\) per step, so a reduction of the distance by \(10^{-4}\) is guaranteed after \(k\ge\log(10^{-8})/\log(0.96)\approx451.2\) , that is, \(452\) steps; the exact analysis of Proposition 7.8 gives \(226\) . Newton’s method needs one step, since \(f\) is quadratic.
-
Find the dual function and the dual optimal value of “minimize \(x_1^2+x_2^2\) subject to \(x_1+x_2\ge4\) and \(x_1\le1\) ”, recover the primal solution from the dual solution, and identify which constraints are active.
Solution
Write \(f_1=4-x_1-x_2\le0\) and \(f_2=x_1-1\le0\) with multipliers \(\lambda_1,\lambda_2\ge0\) . The Lagrangian \(x_1^2+x_2^2+\lambda_1(4-x_1-x_2)+\lambda_2(x_1-1)\) is minimized at \(x_1=(\lambda_1-\lambda_2)/2\) , \(x_2=\lambda_1/2\) , giving
\[ g(\lambda)=-\tfrac14(\lambda_1-\lambda_2)^2-\tfrac14\lambda_1^2+4\lambda_1-\lambda_2 . \]Maximize over \(\lambda\ge0\) . Setting the partial derivatives to zero: \(-\tfrac12(\lambda_1-\lambda_2)-\tfrac12\lambda_1+4=0\) and \(\tfrac12(\lambda_1-\lambda_2)-1=0\) . The second gives \(\lambda_1-\lambda_2=2\) ; the first then gives \(\lambda_1=6\) , so \(\lambda_2=4\) . Both are nonnegative, so this is the dual solution, with \(d^\star=-1-9+24-4=10\) .
The Lagrangian minimizer at \(\lambda^\star=(6,4)\) is \(x=(1,3)\) . It is feasible: \(1+3=4\) and \(x_1=1\) , with both constraints active, consistent with both multipliers being positive. Its objective value is \(1+9=10=d^\star\) , so by Proposition 5.7 it is optimal and strong duality holds. Without the bound \(x_1\le1\) the solution would be \((2,2)\) with value \(8\) ; the bound costs \(2\) , and its multiplier \(4\) is the initial rate at which relaxing it would lower the optimal value.
-
A student minimizing \(f(x,y)=x^2+6xy+y^2\) reports that the origin is the minimizer because the gradient vanishes there and both second partial derivatives are positive. Evaluate the claim, and determine what happens to the problem when the constraint \(x=y\) is added.
Answer
The Hessian \(\begin{pmatrix}2&6\\6&2\end{pmatrix}\) has eigenvalues \(-4\) and \(8\) , so the origin is a saddle and \(f\) is unbounded below: \(f(t,-t)=-4t^2\) . With the constraint \(x=y\) the feasible directions are multiples of \((1,1)\) , along which \(f=8x^2\) ; the quadratic form is positive definite on the null space of the constraint, so by Theorem 4.13 the origin is the unique constrained minimizer.
-
Project the point \((2,2,-1)\) onto the probability simplex in \(\mathbb R^3\) , and use the result to perform one step of the projected gradient method with \(\alpha=1\) on \(f(x)=\tfrac12\lVert x-c\rVert^2\) , \(c=(2,2,-1)\) , from any starting point.
Answer
With two positive coordinates, \(4-2\nu=1\) gives \(\nu=1.5\) and the projection \((0.5,0.5,0)\) , consistent since \(-1-1.5<0\) . With \(\alpha=1\) the gradient step from any \(x\) gives \(x-(x-c)=c\) , so the projected gradient step lands on \((0.5,0.5,0)\) , which is the solution of minimizing \(f\) over the simplex.
-
For “minimize \(e^{x}\) subject to \(x\ge0\) ” write the KKT conditions and solve them, compute the dual function, and verify strong duality; then explain what changes, and what does not, for “minimize \(e^{x}\) subject to \(x\le0\) ”.
Solution
Constraint \(x\ge0\) . With \(f_1=-x\) : stationarity \(e^{x}-\lambda=0\) , \(\lambda\ge0\) , \(\lambda x=0\) , \(x\ge0\) . Stationarity forces \(\lambda=e^{x}>0\) , so complementary slackness forces \(x=0\) , and then \(\lambda=1\) . The problem is convex, so \(x^\star=0\) , \(p^\star=1\) , \(\lambda^\star=1\) . The dual function is \(g(\lambda)=\inf_x(e^{x}-\lambda x)\) ; for \(\lambda>0\) the infimum is at \(x=\log\lambda\) and equals \(\lambda-\lambda\log\lambda\) , and \(g(0)=0\) . Since \(g'(\lambda)=-\log\lambda\) , the maximum is at \(\lambda=1\) with \(d^\star=1=p^\star\) : strong duality, with both optima attained.
Constraint \(x\le0\) . Now \(f_1=x\) and stationarity is \(e^{x}+\lambda=0\) , impossible for \(\lambda\ge0\) . There is no KKT point, and correctly so: the infimum \(p^\star=0\) is approached as \(x\to-\infty\) and not attained, so there is no minimizer for the conditions to describe. The dual function is \(g(\lambda)=\inf_x(e^{x}+\lambda x)\) , which is \(-\infty\) for \(\lambda>0\) and \(0\) for \(\lambda=0\) , so \(d^\star=0=p^\star\) , attained at \(\lambda=0\) .
What changes is attainment of the primal optimum, and with it the existence of a KKT point. What does not change is strong duality: Slater’s condition holds in both problems, and Theorem 6.6 guarantees a zero gap and an attained dual optimum whenever \(p^\star\) is finite, whether or not the primal optimum is attained.
-
Compute two iterations of Newton’s method for \(f(x)=x^2+e^{-x}\) from \(x_0=0\) , estimate the minimizer to four decimals, and explain why the iteration is guaranteed to be a descent method at every point.
Answer
\(f'(x)=2x-e^{-x}\) , \(f''(x)=2+e^{-x}\) . From \(x_0=0\) : \(x_1=0+\tfrac13\approx0.3333\) , \(x_2\approx0.3517\) , and the minimizer is \(0.3517\) to four decimals. Since \(f''>0\) everywhere, the Newton step is a descent direction at every point (Proposition 8.2(a)).
-
Solve “minimize \(\tfrac12(x-3)^2+2\lvert x\rvert\) ” exactly, verify the answer with the subgradient optimality condition, and state the proximal gradient iteration that would compute it, including its fixed point.
Answer
The solution is the soft threshold of \(3\) at level \(2\) : \(x^\star=1\) . Check: \((x-3)+2\cdot1=-2+2=0\) . With \(\alpha=1\) the proximal gradient step from any \(x\) is the soft threshold of \(x-(x-3)=3\) , namely \(1\) , which is its own image: the fixed point.
-
Without solving it, give a lower bound and an upper bound on the optimal value of “minimize \(x_1^2+2x_2^2\) subject to \(x_1+x_2\ge3\) ” using one dual point and one feasible point of your choice, and then compute the exact optimal value to see how tight your bounds were.
Solution
In standard form \(f_1=3-x_1-x_2\le0\) . The Lagrangian \(x_1^2+2x_2^2+\lambda(3-x_1-x_2)\) is minimized at \(x_1=\lambda/2\) , \(x_2=\lambda/4\) , so
\[ g(\lambda)=-\frac{\lambda^2}{4}-\frac{\lambda^2}{8}+3\lambda=3\lambda-\frac38\lambda^2 . \]A lower bound. Take \(\lambda=3\) : \(g(3)=9-3.375=5.625\) . By Theorem 5.4, \(p^\star\ge5.625\) .
An upper bound. Take the feasible point \((1.5,1.5)\) : \(f_0=2.25+4.5=6.75\) . So \(p^\star\le6.75\) .
Exact value. The unconstrained minimizer \(0\) is infeasible, so the constraint is active; stationarity gives \(x=(\lambda/2,\lambda/4)\) and \(\tfrac34\lambda=3\) gives \(\lambda^\star=4\) , \(x^\star=(2,1)\) , \(p^\star=4+2=6\) , and \(g(4)=12-6=6\) confirms it. The interval \([5.625,6.75]\) obtained without solving had width \(1.125\) and contained the answer; choosing \(\lambda\) nearer \(4\) and a point nearer \((2,1)\) would tighten it at both ends.
-
The central point of a barrier method for a problem with \(m=8\) inequality constraints at \(t=400\) has objective value \(12.37\) . Give an interval guaranteed to contain \(p^\star\) , and say what additional check on the computed point is needed before trusting that interval.
Answer
By Theorem 10.5, \(12.37-8/400\le p^\star\le12.37\) , that is, \(p^\star\in[12.35,12.37]\) . The bound holds for an exact central point, so one must check that the computed point is strictly feasible and that the centering was accurate, for instance that the gradient of \(tf_0+\phi\) there is negligible, or else evaluate the dual function at the multipliers actually obtained.
-
A linear program in standard form has an optimal basic feasible solution at which two nonbasic reduced costs are \(0\) and \(3\) . Say what this implies about uniqueness of the primal solution, and what complementary slackness then says about the dual constraints.
Answer
A zero reduced cost on a nonbasic variable means that increasing it does not change the cost, so unless the corresponding pivot is degenerate there is a whole edge of optimal solutions and the primal solution is not unique. In the dual, the constraint belonging to that variable is tight, and the constraint belonging to the variable with reduced cost \(3\) is slack by \(3\) , which forces that primal variable to be zero in every optimal solution.
-
For \(f(x)=\tfrac12x^{\top}Px+q^{\top}x\) with \(P=\begin{pmatrix}3&1\\1&3\end{pmatrix}\) and \(q=(-4,-4)\) , perform one step of the gradient method with the best constant step and one Newton step from \(x_0=(0,0)\) , and compare both with the minimizer.
Solution
The eigenvalues of \(P\) are \(3-1=2\) and \(3+1=4\) , so \(m=2\) , \(L=4\) , \(\kappa=2\) . The minimizer solves \(Px=-q\) : \(3x_1+x_2=4\) , \(x_1+3x_2=4\) , so \(x^\star=(1,1)\) .
Gradient step. The best constant step is \(2/(m+L)=\tfrac13\) (Proposition 7.8). At \(x_0=0\) the gradient is \(q=(-4,-4)\) , so \(x_1=(\tfrac43,\tfrac43)\) . The error has gone from \((-1,-1)\) to \((\tfrac13,\tfrac13)\) : its norm is multiplied by \(\tfrac13=(\kappa-1)/(\kappa+1)\) , exactly the predicted factor, and it has changed sign, an overshoot. That happens because the initial error is along the eigenvector \((1,1)\) with eigenvalue \(4\) , the direction in which the multiplier is \(1-\tfrac43=-\tfrac13\) .
Newton step. \(x_0-P^{-1}(Px_0+q)=-P^{-1}q=(1,1)\) : the minimizer, in one step, as Proposition 8.2(c) guarantees for a quadratic.
With step \(1/L=\tfrac14\) the gradient method would also have landed on \((1,1)\) at once from this particular start, because the error lies entirely in the eigendirection with eigenvalue \(L\) ; for a general start no constant step does that.
-
A colleague proposes to solve a smooth nonconvex equality-constrained problem by the quadratic penalty method with \(\rho=10^{8}\) and to accept the result if consecutive iterates agree to eight digits. List the weaknesses of this plan and propose a better one, naming the residuals you would report.
Answer
Weaknesses: \(\rho=10^{8}\) makes the penalized problem extremely ill-conditioned; the stopping rule measures stalling, not optimality; the result is infeasible by an amount of order \(1/\rho\) times the multiplier, and nothing is reported about it; and for a nonconvex problem even an accurate limit is only a stationary point. Better: use the method of multipliers with a moderate \(\rho\) , or sequential quadratic programming, from several starting points; report the primal residual \(\lVert h(x)\rVert\) , the stationarity residual, and the objective value, each relative to a stated scaling; check second-order conditions; and describe the result as a candidate.