Optimization problem: Difference between revisions

Revision as of 23:42, 13 February 2022

Revision as of 23:25, 18 February 2022

Line 9:

==Continuous optimization problem==

The ''[[Canonical form|standard form]]'' of a [[Continuity (mathematics)|continuous]] optimization problem is<ref>{{cite book|title=Convex Optimization|first1=Stephen P.|last1=Boyd|first2=Lieven|last2=Vandenberghe|page=129|year=2004|publisher=Cambridge University Press|isbn=978-0-521-83378-3|url=https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf#page=143|format=pdf}}</ref>

: <math display=block>\begin{align}

&\underset{x}{\operatorname{minimize}}& & f(x) \\

&\operatorname{subject\;to}

Line 26 ⟶ 27:

==Combinatorial optimization problem==

{{Main|Combinatorial optimization}}

Formally, a [[combinatorial optimization]] problem {{mvar|A}} is a quadruple{{Citation needed|date=January 2018}} {{math|(''I'', ''f'', ''m'', ''g'')}}, where

* {{math|I}} is a [[Set (mathematics)|set]] of instances;

Line 33 ⟶ 35:

The goal is then to find for some instance {{mvar|x}} an ''optimal solution'', that is, a feasible solution {{mvar|y}} with

: <math display=block>m(x, y) = g \biglleft\{ m(x, y') \mid: y' \in f(x) \bigrright\} .</math>

: <math>m(x, y) = g \bigl\{ m(x, y') \mid y' \in f(x) \bigr\} .</math>

For each combinatorial optimization problem, there is a corresponding [[decision problem]] that asks whether there is a feasible solution for some particular measure {{math|''m''₀}}. For example, if there is a [[Graph (discrete mathematics)|graph]] {{mvar|G}} which contains vertices {{mvar|u}} and {{mvar|v}}, an optimization problem might be "find a path from {{mvar|u}} to {{mvar|v}} that uses the fewest edges". This problem might have an answer of, say, 4. A corresponding decision problem would be "is there a path from {{mvar|u}} to {{mvar|v}} that uses 10 or fewer edges?" This problem can be answered with a simple 'yes' or 'no'.

Line 47 ⟶ 48:

|display-authors=etal}}</ref>

==See also==

*[[ {{annotated link|Counting problem (complexity)]] }}

*[[ {{annotated link|Design Optimization]] }}

*[[Function problem]]

* {{annotated link|Ekeland's variational principle}}

*[[Glove problem]]

*[[ {{annotated link|Function problem]]}}

*[[Operations research]]

*[[ {{annotated link|Glove problem]]}}

*[[Satisficing]]: the optimum need not be found, just a "good enough" solution.

*[[ {{annotated link|Operations research]] }}

*[[Search problem]]

*[[ {{annotated link|Satisficing]]:}} − the optimum need not be found, just a "good enough" solution.

*[[Semi-infinite programming]]

*[[ {{annotated link|Search problem]] }}

*[[ {{annotated link|Semi-infinite programming]]}}

==References==

{{reflist}}

==External links==

*{{cite web |title=How Traffic Shaping Optimizes Network Bandwidth |work=IPC |date=12 July 2016 |access-date=13 February 2017 |url=https://www.ipctech.com/how-traffic-shaping-optimizes-network-bandwidth }}

* {{cite web |title=How Traffic Shaping Optimizes Network Bandwidth |work=IPC |date=12 July 2016 |access-date=13 February 2017 |url=https://www.ipctech.com/how-traffic-shaping-optimizes-network-bandwidth }}

{{ConvexAnalysis}}

{{Authority control}}