MATP6600/DSES6780 Nonlinear Programming, Homework 3.

Due: Friday, October 9, 2009, in class.

Let f : IRⁿ→IR be a convex function. The convex conjugate function of f is the function f^* : IRⁿ→IR given by $* * T * f (x ) := supx{x x - f(x)}.$
Show that x^* is a subgradient of f at if and only if f() = ^Tx^*- f^*(x^*).
Consider the standard form linear programming problem (P) and its dual (D): $T T min c x max bTy s.t. Ax = b (P ) s.t. A y ≤ c (D) x ≥ 0.$
Assume both (P) and (D) are feasible. Define K^P := {x ≥ 0 : Ax = b} and K^D := {y : A^Ty ≤ c}, the feasible regions of (P) and (D), respectively. Show that either K^P or K^D is unbounded. (Hint: Consider the problem min{-e^Td : Ad = 0,d ≥ 0}. where e is the vector of ones. It is possible that both K^P and K^D are unbounded.)
Show that a feasible quadratic programming problem of the form $T 1 T min c x + 2x Qx s.t. Ax ≤ b$
is unbounded if there exists a feasible point and a direction d satisfying (c + Q)^Td < 0, Ad ≤ 0, d^TQd ≤ 0.
Find all the KKT points for the following quadratic programming problem: $min x1x2 subject to - x1 ≤ 1 - x2 ≤ 1$
Use the result of Question 3 to show that this quadratic program has an unbounded optimal value.
Let y denote the KKT multipliers for the constraints of the quadratic program $min cTx + 12xTQx s.t. Ax ≤ b.$
Assume the feasible region is bounded. Show that the optimal solution can be obtained by solving the following linear program with complementarity constraints, LPCC:
$min cTx - bTy s.t. c+ Qx + AT y = 0 0 ≤ y ⊥ b - Ax ≥ 0$
Use the first order optimality conditions to find the global minimizer for the problem

min-x₁x₂x₃, subject to x₁ + 2x₂ + 4x₃ ≤ 48, x₁,x₂,x₃ ≥ 0.

(Note that this problem is nonconvex — prove that the solution you obtain is the global minimizer, without considering the second order conditions.)

John Mitchell

Amos Eaton 325

x6915.

mitchj at rpi dot edu

Office hours: Tuesday 2.0 – 3.0, Wednesday 11.0 – 12.0.