Nonlinear Programming Final Exam
section A
Indicate whether each statement is true (+) or false (o).
If false, briefly state why or give a
counterexample.
_____ 1. A barrier function adds a penalty to the
objective when the solution approaches a
boundary of the feasible region.
_____ 2. The number of "dependent" variables of the GRG
algorithm is equal to the number of
equality constraints.
_____ 3. The cubic interpolation procedure for
one-dimensional minimization requires the
computation of second derivatives.
_____ 4. The function xa is convex for x>0.
_____ 5. The feasible directions algorithm computes a search direction by solving an LP .
_____ 6. The Fibonacci method for one -dimensional
minimization requires the computation of
derivatives.
_____ 7. If all posynomials in a (posynomial) GP problem
are condensed into single terms,
then it is always possible to rewrite the resulting problem as an LP problem.
_____ 8. A linear function is neither convex nor concave.
_____ 9. The Gradient Projection method always follows the
boundary of the feasible region,
and never enters the interior.
_____ 10. The logarithm of the dual GP objective v(δ,λ) above is a concave function of δ and λ.
_____ 11. The logarithm of the dual GP objective v(δ,λ)
above is not a concave function of
both δ and λ, but becomes so if you eliminate
using
_____ 12. A locally optimal solution for a signomial
geometric programming problem must be
globally optimal.
_____ 13. The dual ("pseudo-dual") of a signomial GP
problem may have multiple local
maxima, but its global maximum will have the same objective value as the global
minimum of the primal signomial GP.
_____ 14. Penalty functions may be used for both equality
and inequality constraints , but barrier
functions may be used only for inequality constraints.
_____ 16. If the Lagrangian function L(x,λ) has a saddlepoint
, then
there is zero duality
gap between primal and dual optimal solutions.
_____ 17. Consider the problem: min f(x) subject to gi(x)
≤ 0, i=1,2...m, x ≥ 0
(where gi satisfy
some constraint qualification) and its Lagrangian function
Then if f and gi are convex, the partial derivative of L with respect to each xj
must be
zero at the optimum.
_____ 18. For the problem in the previous statement ,
must be zero at the
optimum.
_____ 19. For the problem in the previous statement, either xj or
(or possibly both)
must be zero at the optimum.
_____20. The limit, as w → 0, of the function (c/w)w is ∞.
_____21.
_____22. If we define the function
then
_____23. When the dual problem is solved, the primal variables of a posynomial
GP problem
are often computed by exponentiating the Lagrange multipliers of the
orthogonality
constraints.
_____24. The function f(x,y) = xy is a concave function of x and y.
_____25. If an algorithm is applied to a minimization problem with optimal value
zero, and the
objective value is approximately halved at each iteration, then we would say
that the
algorithm has a linear rate of convergence.
_____26. The Hessian matrix of (xtQx + cx) is 2Q.
_____27. In the QC/LD problem, the objective function is assumed to be quadratic.
_____28. If fi(x) is linear for i=1,2,...n, then the function F(x) defined by
F(x)= max{fi(x):
i=1,2,...n} is a convex function.
_____29. If a posynomial GP objective function continues to decrease as xj
→ 0
for some primal
variable xj, then the dual problem objective is unbounded.
_____30. If a posynomial GP objective function continues to decrease as xj
→ +∞
for some
primal variable xj, then the dual problem is infeasible.
_____ 31. Every posynomial function is convex.
_____ 32. The dual of a constrained posynomial GP problem has only linear
equality and
nonnegativity constraints.
_____ 33. If a primal GP constraint is slack, then all the weights of the terms
in that constraint
must be zero.
_____ 34. In the QC/LD problem, the variables are restricted to be integer-valued.
_____ 35. The gradient of the function f(x) = (xtQx + cx) is Qx + c.
_____ 36. Solving the QC/LD problem requires a one-dimensional search at each iteration.
_____ 37. The posynomial constraint gi(x) ≤1 has a convex feasible region.
_____ 38. It is always possible (e.g., by a change of variable ) to reformulate a
posynomial GP
problem so as to have a convex objective and convex feasible region.
_____ 39. The objective of the posynomial GP problem, i.e.,
is a concave function of δ and λ.
_____ 40. In the "Golden Section Search" method, more than one-third of the
interval of
uncertainty is eliminated at each iteration (assuming that no function values
are equal).
_____ 41. If all posynomials in a (posynomial) GP problem are condensed into
single terms,
then the resulting problem has a feasible region which includes the original
feasible
region.
_____ 42. The Hessian matrix of a quadratic function is constant.
_____ 43. In Wolfe's complementary pivoting algorithm for QP, if a single
artificial variable is
used, then the tableau does not require an objective row.
_____ 44. The gradient projection method computes Lagrange multipliers at each
iteration, and
stops when they have the appropriate sign.
_____ 45. "Quasi-Newton" search methods for unconstrained minimization require
the
computation of second partial derivatives.
_____ 46. Newton's method for unconstrained minimization requires the
computation of second
partial derivatives.
_____ 47. If you guess at the value of some primal GP variable and then fix it
at this value, the
dual GP problem becomes more difficult to solve.
_____ 48. In a "generalized linear programming" problem, the column of
coefficients of the
variables must be selected as well as the variables.
_____ 49. The function eax is convex only for a ≥ 0.
_____ 50. The Davidon-Fletcher-Powell (DFP) algorithm requires the computation
of partial
derivatives.
_____ 51 . If a posynomial function is "condensed" into a monomial, the monomial
function (if
not equal) is an overestimate of the posynomial function.
_____ 52 . Wolfe's method for quadratic programming requires a one-dimensional
search at
every iteration.
_____ 53. If a constrained nonlinear programming problem satisfies a "constraint
qualification",
then a point which satisfies the Karush-Kuhn-Tucker conditions must be an
optimal
solution.
_____ 54. A barrier function allows a constraint to be violated, but adds a
penalty if the
constraint is violated.
_____ 55. The GRG algorithm requires the use of a one-dimensional search method.
_____ 56. The Feasible Directions algorithm requires the use of a
one-dimensional search
method.
_____ 57. If a constrained nonlinear programming problem satisfies a "constraint
qualification",
then the Karush-Kuhn-Tucker conditions must be satisfied by an optimal solution.
_____ 58. The function eax is convex for all values of a.
_____ 59. In Wolfe's complementary pivoting method for quadratic programming,
the
complementary slackness conditions are satisfied after each iteration.
_____ 60 . The tableau for Wolfe's method for quadratic programming includes
columns for
both primal and dual variables.
_____ 61. The function xa is convex for a ≥ 0.
_____ 62. If a nonlinear programming problem has only linear constraints, then
any point which
satisfies the Karush-Kuhn-Tucker conditions must be optimal.
_____ 63. The Fletcher-Reeves method is also known as a "Quasi-Newton" method.
_____ 64. The quadratic interpolation procedure for one-dimensional minimization
requires the
computation of derivatives.
_____ 65. If the GRG algorithm were applied to a LP problem, it would produce,
at each
iteration, the same solution as the simplex algorithm for LP.
_____ 66. A penalty function allows a constraint to be violated, but adds a
penalty if the
constraint is violated.
_____ 67. The Lagrangian dual of a convex quadratic programming problem is a
quadratic
programming problem with only nonnegativity constraints on the dual variables.
_____ 68. Powell's algorithm for unconstrained minimization requires the
computation of partial
derivatives.
_____ 69. The Davidon-Fletcher-Powell method is also known as the "Conjugate
Gradient"
method.
_____ 70. In the QC/LD problem, the objective function is assumed to be convex.
| Prev | Next |