Talk:Duality (optimization)

not just linear programming

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)[reply]

--> 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).[reply]

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

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[reply]

Proposed merger

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)[reply]

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)[reply]

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

Text and/or other creative content from this version of Lagrange multiplier was copied or moved into Dual problem with this edit on 13 May 2011. The former page's history now serves to provide attribution for that content in the latter page, and it must not be deleted as long as the latter page exists.

lower bound! not upper bound

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

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)[reply]

expression within parentheses is not the Lagrangian dual function

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

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)[reply]

Requested move

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

New Organization

Here are my thoughts for the organization:

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

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

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)[reply]

Proposed merge with strong/weak duality + duality gap

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)[reply]

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)[reply]

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)[reply]

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Duality (optimization). Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

Added archive https://web.archive.org/web/20110724151508/http://or.journal.informs.org/cgi/reprint/11/3/399 to http://or.journal.informs.org/cgi/reprint/11/3/399

When you have finished reviewing my changes, please set the checked parameter below to true or failed to let others know (documentation at {{Sourcecheck}}).

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 07:47, 17 December 2016 (UTC)[reply]

Constraint qualification and strong duality

The article currently states that "If a constraint qualification such as Slater's condition holds and the original problem is convex, then we have strong duality".

While it is true that Slater's condition implies strong duality, "constraint qualification" is not concerned with duality. Constraint qualification provides circumstances under which KKT conditions (or other first order conditions) are necessary for a primal solution to be a local minima.

To give a concrete example, I cannot find any primary source stating that even LICQ (one of the strongest forms of constraint qualification) implies strong duality. This could be because constraint qualification statements do not always assume that the problem is convex, while Slater's condition does assume that the primal problem is convex (at least, this is the convention in Stephen Boyd's book). However, I cannot find any source which states that LICQ for a convex problem implies strong duality.

The most general conditions for strong duality rely on compactness of at least one of the primal feasible region and the dual feasible region. See: https://en.wikipedia.org/wiki/Minimax_theorem.

I propose that the article be amended to remove reference to constraint qualification implying strong duality (Slater's condition can stay, as that claim is true). I think some additional discussion could be included near this statement the describe the general conditions for strong duality, but I am not sure if that discussion is better placed in the dedicated Strong Duality wikipedia article. — Preceding unsigned comment added by Rileyjmurray (talk • contribs) 02:03, 2 April 2017 (UTC)[reply]