On Nonlinear Optimization and Multiobjective Optimization

Lectures at the University of Pavia, April 21-23, 2004, Pavia, Italy
by Prof. Kaisa Miettinen, PhD


Lecturer

Prof. Kaisa Miettinen, Helsinki School of Economics, P.O. Box 1210, FIN-00101 Helsinki, Finland and University of Jyväskylä, Department of Mathematical Information Technology, P.O. Box 35 (Agora), FIN-40014 University of Jyväskylä, Finland

Readings

Contents

Exercises

  1. Is function f(x) = 3x^4 + 4x^3 + 1 convex? Find all of its locally minimal solutions. Does it have a global minimum?
  2. Let f: R^n -> R be a differentiable function. Its linear approximation at the point x* is of the form f(x*) + Delta f(x*)^T (x-x*) (where Delta f stands for the gradient of f). If the function is twice differentiable at x*, its quadratic approximation at x* is
    f(x*) + Delta f(x*)^T (x-x*) + 0.5 (x-x*)^T H(x*) (x-x*)
    (where H stands for the Hessian of f). Let f(x,y)= exp(x^2+y^2) - 5x + 10 y. Formulate linear and quadratic approximations for it at (0,1)^T. Are the approximations convex or concave or neither. Justify.
  3. If H(x) = I for all x in R^n, what can you say about the Newton method?
  4. Let us study the problem
    minimize (x - 9/4)^2 + (y-2)^2
    subject to y - x^2 >= 0
    x + y <= 6
    x, y >= 0.
    Formulate the Karuch-Kuhn-Tucker optimality conditions and show that they are valid at the point X*=(3/2 , 9/4)^T.
    Extra: Illustrate the Karush-Kuhn-Tucker optimality conditions graphically at X*.
  5. Let us study the problem
    minimize x
    subject to (x - 1)^2 + (y - 1)^2 <= 1
    (x - 1)^2 + (y + 1)^2 <= 1.
    The only feasible point (1,0)^T is naturally the optimal solutions. However, it does not satisfy the necessary Karush-Kuhn-Tucker optimality conditions. Show this. What is the explanation?
  6. Find the globally minimal solution of
    minimize x^2 + y^2
    subject to -x - y <= -1
    using the Karush-Kuhn-Tucker optimality conditions.
  7. Minimize f(x,y) = (1-x)^2 + 100 (y-x^2)^2 and try at least three different algorithms. Use the starting point (-1.2, 1.0)^T. (Compare the effect of analytical and numerical gradients on the convergence.)
  8. Solve the problem
    minimize f(x,y) = x sin(xy) cos y
    in the region [-2,2] x [-2,2] when the variables are integer-valued.
  9. You must solve a problem
    minimize {f(x,y), g(x,y)}
    subject to x + y <= 3
    ln x^3 + 2 y^2 = 1
    x, y > 0,
    where f(x,y) = 4x^2 - 2y + 2 and g(x,y)= 2y^2+4xy + 2x. How do you use a software that can solve problems of the form
    minimize 0.5 x^T G x + c^T x
    subject to Ax = b
    g_i(x) >= 0 for i=1,...,m
    x^l <= x <= x^u
    where x, c, x^l and x^u belong to R^n, G is n x n -matrix, A is l x n -matrix, b belongs to R^l and g_i: ^R^n -> R.
  10. Solve the problem
    minimize {(x-1)^2 + y^2 + (w-2)^2, (x-2)^2 + (y-1)^2 + w^2}
    subject to x + y + w <= 6
    x, y, w >= 0
    if you have available a value function
    U(z_, z_2)= -z_1 - sqrt(z_2).
  11. Find at least four different Pareto optimal solutions to the problem
    minimize {-x, -y, -z}
    subject to 3x + 2y + 3z <= 18
    x + 2y + z <= 10
    9x + 20y + 7z <= 96
    7x + 20y + 9z <=96
    x, y, z >= 0.
  12. Search for nonlinear optimization problems on the Internet and write down brief descriptions of them.
  13. Solve graphically using the lexicographic approach
    minimize {-x, -y}
    subject to 2x + 5y <= 40
    2x + 3y <= 28
    x <= 11
    x, y >= 0.
  14. Use WWW-NIMBUS and solve the nutrition problem (saved in the system for guest users). Use different scalar solvers.
  15. Input some multiobjective optimization problem in WWW-NIMBUS and use different scalarizing functions, the solution database and visualizations. Which type of visualization do you prefer?
  16. Use both the symbolic and graphical classification in WWW-NIMBUS. Which one do you prefer? Why?

Further material on the Internet

Further printed material

Software operating on the Internet - free for academic purposes

WWW-NIMBUS WWW-NIMBUS for interactive multiobjective optimization

Further links

Keywords for search engines

Transparencies

Optimization logo at the University of Jyväskylä



April 19, 2004 Kaisa Miettinen, miettine@mit.jyu.fi