Talk:Duality (optimization)

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated Start-class, Mid-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
Start Class
Mid Importance
 Field: Applied mathematics

not just linear programming[edit]

Just putting a note here, since I'm not able to deal with it now. Dual problems exist for nonlinear constrained optimization problems as well as linear programming problems. The principle is the same, although the mechanics might be different.Cretog8 (talk) 23:47, 26 June 2008 (UTC)

--> I added in the introduction the most general description of a Dual problem, since associating everything with the Lagrange dual only for linear program is completely incorrect and misleading. Not only do dual problems exist for non-linear programs, but other types of dual problems exist as well...q4444q —Preceding undated comment added 17:35, 14 October 2010 (UTC).

Could anybody help to make "Problem statement in the linear case" a bit easier[edit]

for out-siders to understand? Maybe one or two simple examples might greatly help what is actually said ... Thanks,

True bsmile (talk) 07:08, 20 October 2009 (UTC)true_bsmile

Proposed merger[edit]

I think the discussion on Lagrange duality would fit more naturally here than in the article Lagrange multiplier. Any objections? Isheden (talk) 21:06, 12 May 2011 (UTC)

Hi Isheden!
Lagrangian duality belongs here; you may also include material or consider merger with Lagrangian relaxation. The Lagrange multiplier article needs expansion to cover nonlinear programming, linear programming, and combinatorial optimization uses, rather than just smooth optimization.
IMHO, the Lagrangian duality section in this article should be roughly the same size as the linear-programming duality, and it should be larger than the sections on Fenchel duality, Wolfe duality, and surrogate duality. I assume that, similarly, the linear programming article has an expanded treatment of LP duality, including primal-dual algorithms and the dual simplex algorithm.
Best regards,  Kiefer.Wolfowitz 21:28, 12 May 2011 (UTC)

Merger performed. Isheden (talk) 13:24, 13 May 2011 (UTC)

lower bound! not upper bound[edit]

The solution to the dual problem provides a lower bound for the primal problem, not upper bound. — Preceding unsigned comment added by (talk) 05:19, 4 January 2012 (UTC)

You are correct. I updated the page in the 1 spot I noticed it said 'upper bound' in that context. Zfeinst (talk) 14:52, 4 January 2012 (UTC)

expression within parentheses is not the Lagrangian dual function[edit]

It is the whole objective function that is the Lagrangian dual function. The expression within parentheses is only the Lagrangian function. (talk) 14:04, 5 January 2012 (UTC)

Thank you for correcting this. By the way, in Boyd/Vandenberghe (chapter 5) an equality constraint is included as well. Isheden (talk) 14:40, 5 January 2012 (UTC)

Requested move[edit]

I think this article should have a broader title such as Duality (optimization) or Duality (mathematical optimization). Then it would be natural to merge the newly created articles Strong duality and Weak duality into this article, as they don't have much potential for expansion. Comments are appreciated. Isheden (talk) 21:18, 15 January 2012 (UTC)

I agree with this idea. I created the strong duality and weak duality pages earlier today because I didn't think they fit well in this page as it is currently titled/defined, but if expanded then I fully approve of of such a move. Zfeinst (talk) 21:43, 15 January 2012 (UTC)
Done. The article needs some restructuring, however. It should start explaining duality in general, including the Lagrange dual function, before introducing the dual problem. Isheden (talk) 16:33, 16 January 2012 (UTC)
Should the Lagrange dual function come before the dual problem in general? The Lagrange dual is just an example that is frequently utilized but is not "special" mathematically? Perhaps we can come up with a consensus for organization in this talk page before moving everything around. Zfeinst (talk) 19:57, 16 January 2012 (UTC)
I would suggest looking at [1], [2], and [3] for ideas how to structure the article. There are many kinds of duality, but Lagrangean and Wolfe are perhaps the most important ones. More advanced topics can be found in [4]. Isheden (talk) 21:57, 16 January 2012 (UTC)

New Organization[edit]

Here are my thoughts for the organization:

  1. Duality Principle
    1. Weak/Strong Duality
  2. Lagrangian Duality
    1. Linear (mention of strong duality)
    2. Non-Linear (mention of weak duality)
  3. Other Duality Concepts (Wolfe, Fenchel, others?)
  4. History
  5. See Also
  6. Notes
  7. References

What do you think? Zfeinst (talk) 22:58, 16 January 2012 (UTC)

I think it's basically fine. Before the general non-linear case, there should of course be a discussion of convex objective functions. See also Kiefer.Wolfowitz's comments above.Isheden (talk) 08:17, 17 January 2012 (UTC)

Proposed merge with strong/weak duality + duality gap[edit]

I support the merge with strong and weak duality since each of those topics is really inseparable from a discussion of the dual problem. However, duality gap I think is a larger topic because of its use in algorithms and not just the "principle" of it. What does everyone else think? Zfeinst (talk) 22:20, 8 March 2012 (UTC)

My proposal was based on the present article duality gap, which is a stub and also quite difficult to read without the background in this article. If it really turns out that duality gap is such a large topic that it deserves a separate article, it would not be difficult to split it out from this article later. Isheden (talk) 22:58, 8 March 2012 (UTC)
propose also to define x being Є RN, and saying explicitely that D is the domain where all constraints hold

Rramberg (talk) 23:29, 3 November 2013 (UTC)