1. Solving a linear program always gives its global optimum.
  2. Solving a non-linear program always gives its local optimum.

  3. Benders decomposition applied to a linear program , gives global optimum

  4. Generalized benders decomposition (i.e. the subproblem is non-linear) gives local optimum.

What are your views on the above observations?

asked 23 Jul '13, 13:33

spyimp's gravatar image

spyimp
4118
accept rate: 0%


Assuming that (a) we are only discussing feasible, bounded problems, (b) "solving" means solving with good quality software to normal termination, without bumping into time, memory or iteration limits or numerical problems and (c) "optimality" is understood to mean "within tolerances", then I agree with 1 and 3. If in 2 and 4 you mean always produces AT BEST a local optimum, I disagree because it is entirely possible to get a global optimum. If you mean always produces AT LEAST a local optimum, I disagree because things like asymptotic divergence and oscillation are possible in some cases.

link

answered 23 Jul '13, 16:03

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

2

For the nonlinear case, convexity of objective function and solution region (in case of a minimization problem) is a very important condition that can guaranty finding the optimal solution.

(23 Jul '13, 16:25) Ehsan ♦

Convexity is important, but is it sufficient? It's been a quarter century or so since I dealt with nonlinear programming, so I could be off with this comment, but it seems to me that at least some NLP algorithms are susceptible to jamming even on a convex feasible region.

(23 Jul '13, 16:41) Paul Rubin ♦♦

@Paul: In case of convex programming, a local optimum is always a global optimum (see here).

(23 Jul '13, 17:08) Ehsan ♦

@Ehsan: Yes, but that only helps if you get to a local optimum. (I hope this link works: http://tinyurl.com/mqxu6o4.)

(23 Jul '13, 17:32) Paul Rubin ♦♦

@Paul: You're right. Thanks for the link.

BTW, the link doesn't work, but the necessary discussion is on page 362.

(23 Jul '13, 17:50) Ehsan ♦

Interesting -- the link works for me. I wonder if my Google log-in is somehow embedded in it?

(23 Jul '13, 17:53) Paul Rubin ♦♦

I guess the issue is log-in via Google. When I log in to Google, the link works fine.

(23 Jul '13, 18:16) Ehsan ♦
showing 5 of 7 show 2 more comments
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×35
×6
×5
×1

Asked: 23 Jul '13, 13:33

Seen: 1,120 times

Last updated: 23 Jul '13, 18:16

OR-Exchange! Your site for questions, answers, and announcements about operations research.