0

Given the feasible set, the point, and the gradient (and in some cases also the Hessian), how do you determine if the given point is definitely a local minimizer? Do you use the first-order necessary condition, and/or the second-order necessary condition and/or the second-order sufficient condition? If yes, then how do you determine the feasible direction? If no, how do you solve it? Thanks

user100503
  • 449
  • You would need to use sufficient conditions, which usually involve the Hessian being positive definite. If you are at a local minimum, there is no (local) feasible direction. – copper.hat Feb 04 '14 at 18:52
  • Do I also need to check the necessary conditions? – user100503 Feb 04 '14 at 18:54
  • Here is an example: f: R2 -> R, Feasible set is {x =[x1,x2]T : x1 >=1}, Point is [1,2]T and gradient is [1,1]T – user100503 Feb 04 '14 at 18:54
  • Then $f$ doesn't have a local minimum at $(1,2)^T$, since the direction $(0,-1)^T$ is a descent direction (since $\langle \nabla f ((1,2)^T), (0,-1)^T \rangle = -1 <0$). – copper.hat Feb 04 '14 at 19:01
  • How do you pick the direction (0,-1)T? Do you just try different values? – user100503 Feb 04 '14 at 21:02
  • Any direction $h$ that has $\langle \nabla f ((1,2)^T), h \rangle <0$ is a descent, the direction I picked is the projection of $-\nabla f ((1,2)^T)$ onto the constraint set (which is a nice set as constraint sets go). – copper.hat Feb 04 '14 at 21:07
  • Ok. However isn't ⟨∇f((1,2)T),(0,−1)T⟩ = -2 (still negative) or am I mis-understanding the notation? – user100503 Feb 04 '14 at 21:11
  • Also, if you keep trying different directions how do you know when you are done (which will imply that it is a local minimizer)? Or is there a test that you can do to check this? – user100503 Feb 04 '14 at 21:13
  • Hmm, there is a vast body of literature dealing with the subject of optimization algorithms. In the example you gave you could search for 'gradient projection' (since the constraint set you gave is 'nice'). – copper.hat Feb 04 '14 at 21:25
  • Thank you very much for your help. I appreciate it. – user100503 Feb 04 '14 at 21:37

0 Answers0