https://optimization.cbe.cornell.edu/api.php?action=feedcontributions&user=Asa273&feedformat=atomCornell University Computational Optimization Open Textbook - Optimization Wiki - User contributions [en]2021-12-03T01:15:16ZUser contributionsMediaWiki 1.35.0https://optimization.cbe.cornell.edu/index.php?title=Duality&diff=2744Duality2021-09-04T14:44:25Z<p>Asa273: /* Duality Interpretation */ Fixed typos</p>
<hr />
<div>Author: Claire Gauthier, Trent Melsheimer, Alexa Piper, Nicholas Chung, Michael Kulbacki (SysEn 6800 Fall 2020)<br />
<br />
== Introduction ==<br />
Every optimization problem may be viewed either from the primal or the dual, this is the principle of '''duality'''. Duality develops the relationships between one optimization problem and another related optimization problem. If the primal optimization problem is a maximization problem, the dual can be used to find upper bounds on its optimal value. If the primal problem is a minimization problem, the dual can be used to find the lower bounds. <br />
<br />
According to the American mathematical scientist George Dantzig, Duality for Linear Optimization was conjectured by Jon von Neumann after Dantzig presented a problem for Linear Optimization. Von Neumann determined that two person zero sum matrix game (from Game Theory) was equivalent to Linear Programming. Proofs of the Duality theory were published by Canadian Mathematician Albert W. Tucker and his group in 1948. <ref name=":0"> Duality (Optimization). (2020, July 12). ''In Wikipedia. ''https://en.wikipedia.org/wiki/Duality_(optimization)#:~:text=In%20mathematical%20optimization%20theory%2C%20duality,the%20primal%20(minimization)%20problem.</ref><br />
<br />
== Theory, methodology, and/or algorithmic discussions ==<br />
<br />
=== Definition ===<br />
<br />
'''Primal'''<blockquote>Maximize <math>z=\textstyle \sum_{j=1}^n \displaystyle c_j x_j</math> </blockquote><blockquote>subject to:<br />
<br />
</blockquote><blockquote><blockquote><math>\textstyle \sum_{j=1}^n \displaystyle a_{i,j} x_j\lneq b_i \qquad (i=1, 2, ... ,m) </math></blockquote></blockquote><blockquote><blockquote><math>x_j\gneq 0 \qquad (j=1, 2, ... ,n) </math></blockquote></blockquote><blockquote><br />
<br />
<br />
</blockquote>'''Dual'''<blockquote><br />
Minimize <math>v=\textstyle \sum_{i=1}^m \displaystyle b_i y_i</math><br />
<br />
subject to:<blockquote><math>\textstyle \sum_{i=1}^m \displaystyle y_ia_{i,j}\gneq c_j \qquad (j=1, 2, ... , n) </math></blockquote><blockquote><math>y_j\gneq 0 \qquad (i=1, 2, ... , m)</math></blockquote></blockquote>Between the primal and the dual, the variables <math>c</math> and <math>b</math> switch places with each other. The coefficient (<math>c_j</math>) of the primal becomes the right-hand side (RHS) of the dual. The RHS of the primal (<math>b_j</math>) becomes the coefficient of the dual. The less than or equal to constraints in the primal become greater than or equal to in the dual problem. <ref name=":1"> Ferguson, Thomas S. ''A Concise Introduction to Linear Programming.'' University of California Los Angeles. https://www.math.ucla.edu/~tom/LP.pdf </ref><br />
<br />
=== Constructing a Dual ===<br />
<math>\begin{matrix} \max(c^Tx) \\ \ s.t. Ax\leq b \\ x \geq 0 \end{matrix}</math> <math> \quad \longrightarrow \quad</math><math>\begin{matrix} \min(b^Ty) \\ \ s.t. A^Tx\geq c \\ y \geq 0 \end{matrix}</math><br />
<br />
=== Duality Properties ===<br />
The following duality properties hold if the primal problem is a maximization problem as considered above. This especially holds for weak duality.<br />
<br />
==== Weak Duality ====<br />
<br />
* Let <math>x=[x_1, ... , x_n] </math> be any feasible solution to the primal<br />
* Let <math>y = [y_1, ... , y_m] </math>be any feasible solution to the dual<br />
* <math>\therefore </math>(z value for x) <math>\leq </math>(v value for y)<br />
<br />
The weak duality theorem says that the z value for x in the primal is always less than or equal to the v value of y in the dual. <br />
<br />
The difference between (v value for y) and (z value for x) is called the optimal ''duality gap'', which is always nonnegative. <ref> Bradley, Hax, and Magnanti. (1977). ''Applied Mathematical Programming.'' Addison-Wesley. http://web.mit.edu/15.053/www/AMP-Chapter-04.pdf </ref><br />
<br />
==== Strong Duality Lemma ====<br />
<br />
* Let <math>x=[x_1, ... , x_n] </math> be any feasible solution to the primal<br />
* Let <math>y = [y_1, ... , y_m] </math>be any feasible solution to the dual<br />
* If (z value for x) <math>= </math> (v value for y), then '''x''' is optimal for the primal and '''y''' is optimal for the dual<br />
<br />
'''Graphical Explanation'''<br />
<br />
Essentially, as you choose values of x or y that come closer to the optimal solution, the value of z for the primal, and v for the dual will converge towards the optimal solution. On a number line, the value of z which is being maximized will approach from the left side of the optimum value while the value of v which is being minimized will approach from the right-hand side. <br />
[[File:Duality numberline .png|thumb| '''Figure 1: Graphical Representation of Duality''']]<br />
<br />
* If the primal is unbounded, then the dual is infeasible<br />
* If the dual is unbounded, then the primal is infeasible<br />
<br />
==== Strong Duality Theorem ====<br />
If the primal solution has an optimal solution <math>x^*</math> then the dual problem has an optimal solution <math>y^*</math> such that<br />
<br />
<math>\textstyle \sum_{j=1}^n \displaystyle c_j x_j^* = \textstyle \sum_{i=1}^m \displaystyle b_i y_i^*</math><br />
<br />
Dual problems and their solutions are used in connection with the following optimization topics:<br />
<br />
'''Karush-Kuhn-Tucker (KKT) Variables'''<br />
<br />
* The optimal solution to the dual problem is a vector of the KKT multipliers. Consider we have a convex optimization problem where <math>f(x), g_1(x),...,g_m(x) </math> are convex differentiable functions. Suppose the pair <math>(\bar{x},\bar{u}) </math> is a saddlepoint of the Lagrangian and that <math>\bar{x} </math> together with <math>\bar{u} </math> satisfy the KKT conditions. The optimal solutions of this optimization problem are then <math>\bar{x} </math> and <math>\bar{u} </math> with no duality gap. <ref> ''KKT Conditions and Duality.'' (2018, February 18). Dartmouth College. https://math.dartmouth.edu/~m126w18/pdf/part4.pdf </ref><br />
* To have strong duality as described above, you must meet the KKT conditions. <br />
* <br />
<br />
'''Dual Simplex Method''' <br />
<br />
* Solving a Linear Programming problem by the Simplex Method gives you a solution of its dual as a by-product. This simplex algorithm tries to reduce the infeasibility of the dual problem. The dual simplex method can be thought of as a disguised simplex method working on the dual. The dual simplex method is when we maintain dual feasibility by imposing the condition that the objective function includes every variable with a nonpositive coefficient, and terminating when the primal feasibility conditions are satisfied. <ref name=":3"> Chvatal, Vasek. (1977). ''The Dual Simplex Method.'' W.H. Freeman and Co. http://cgm.cs.mcgill.ca/~avis/courses/567/notes/ch10.pdf </ref><br />
<br />
=== Duality Interpretation ===<br />
<br />
* Duality can be leveraged in a multitude of interpretations. The following example includes an economic optimization problem that leverages duality: <br />
<br />
'''Economic Interpretation Example''' <br />
<br />
* A rancher is preparing for a flea market sale in which he intends to sell three types of clothing that are all comprised of wool from his sheep: peacoats, hats, and scarves. With locals socializing the high quality of his clothing, the rancher plans to sell out of all of his products each time he opens up a store at the flea market. The following shows the rancher's materials, time, and profits received for his peacoats, hats, and scarves, respectively.<br />
{| class="wikitable"<br />
|+<br />
!Clothing<br />
!Wool (ft^2)<br />
!Sewing Material (in)<br />
!Production Time (hrs)<br />
!Profit ($)<br />
|-<br />
|Peacoat<br />
|12<br />
|80<br />
|7<br />
|175<br />
|-<br />
|Hat<br />
|2<br />
|40<br />
|3<br />
|25<br />
|-<br />
|Scarf<br />
|4<br />
|20<br />
|1<br />
|21<br />
|}<br />
* With limited materials and time for an upcoming flea market event in which the rancher will once again sell his products, the rancher needs to determine how he can make best use of his time and materials to ultimately maximize his profits. The rancher is running lower than usual on wool supply; he only has 50 square feet of wool sheets to be made for his clothing this week. Furthermore, the rancher only has 460 inches of sewing materials left. Lastly, with the rancher has a limited time of 25 hours to produce his clothing line.<br />
* <br />
* <br />
* With the above information the rancher creates the following linear program:<br />
<br />
<br />
'''maximize''' <math>z=175x_1+25x_2+21x_3</math><br />
<br />
'''subject to:'''<br />
<br />
<math>12x_1+2x_2+4x_3\leq 50</math><br />
<br />
<math>80x_1+40x_2+20x_3\leq 460</math><br />
<br />
<math>7x_1+3x_2+1x_3\leq 25</math><br />
<br />
<math>x_1,x_2,x_3\geq 0</math><br />
<br />
* Before the rancher finds the optimal number of peacoats, hats, and scarves to produce, a local clothing store owner approaches him and asks if she can purchase his labor and materials for her store. Unsure of what is a fair purchase price to ask for these services, the clothing store owner decides to create a dual of the original primal:<br />
<br />
<br />
'''minimize''' <math>v=50y_1+460y_2+25y_3</math><br />
<br />
'''subject to:'''<br />
<br />
<math>12y_1+80y_2+7y_3\geq 175</math><br />
<br />
<math>2y_1+40y_2+3y_3\geq 25</math><br />
<br />
<math>4y_1+20y_2+1y_3\geq 21</math><br />
<br />
<math>y_1,y_2,y_3\geq 0</math><br />
<br />
* By leveraging the above dual, the clothing store owner is able to determine the asking price for the rancher's materials and labor. In the dual, the clothing store owner's objective is now to minimize the asking price, where <math>y_1</math> represents the the amount of wool, <math>y_2</math> represents the amount of sewing material, and <math>y_3</math> represents the rancher's labor.<br />
* <br />
<br />
== Numerical Example ==<br />
<br />
=== Construct the Dual for the following maximization problem: ===<br />
'''maximize''' <math>z=6x_1+14x_2+13x_3</math><br />
<br />
'''subject to:'''<br />
<br />
<math>\tfrac{1}{2}x_1+2x_2+x_3\leq 24</math><br />
<br />
<math>x_1+2x_2+4x_3\leq 60</math><br />
<br />
<math>3x_1+5x_3\leq 12</math><br />
<br />
For the problem above, form augmented matrix A. The first two rows represent constraints one and two respectively. The last row represents the objective function. <br />
<br />
<math>A =\begin{bmatrix} \tfrac{1}{2} & 2 & 1\\ 1 & 2 & 4 \\ 3 & 0 & 5 \end{bmatrix}</math><br />
<br />
Find the transpose of matrix A<br />
<br />
<math>A^T=\begin{bmatrix} \tfrac{1}{2} & 1 & 3 \\ 2 & 2 & 0 \\ 1 & 4 & 5 \end{bmatrix}</math><br />
<br />
From the last row of the transpose of matrix A, we can derive the objective function of the dual. Each of the preceding rows represents a constraint. Note that the original maximization problem had three variables and two constraints. The dual problem has two variables and three constraints.<br />
<br />
'''minimize''' <math>v=24y_1+60y_2+12y_3<br />
</math><br />
<br />
'''subject to:'''<br />
<br />
<math>\tfrac{1}{2}y_1+y_2+3y_3 \geq 6</math><br />
<br />
<math>2y_1+2y_2\geq 14</math><br />
<br />
<math>y_1+4y_2+5y_3\geq 13</math><br />
<br />
== Applications ==<br />
Duality appears in many linear and nonlinear optimization models. In many of these applications we can solve the dual in cases when solving the primal is more difficult. If for example, there are more constraints than there are variables ''(m >> n)'', it may be easier to solve the dual. A few of these applications are presented and described in more detail below. <ref name=":2"> R.J. Vanderbei. (2008). ''Linear Programming: Foundations and Extensions.'' Springer. http://link.springer.com/book/10.1007/978-0-387-74388-2. </ref><br />
<br />
'''Economics'''<br />
<br />
* When calculating optimal product to yield the highest profit, duality can be used. For instance, the primal could be to maximize the profit, but by taking the dual the problem can be reframed into minimizing the cost. By transitioning the problem to set the raw material prices one can determine the price that the owner is willing to accept for the raw material. These dual variables are related to the values of resources available, and are often referred to as resource shadow prices. <ref> Alaouze, C.M. (1996). ''Shadow Prices in Linear Programming Problems.'' New South Wales - School of Economics. https://ideas.repec.org/p/fth/nesowa/96-18.html#:~:text=In%20linear%20programming%20problems%20the,is%20increased%20by%20one%20unit. </ref><br />
<br />
'''Structural Design'''<br />
<br />
* An example of this is in a structural design model, the tension on the beams are the primal variables, and the displacements on the nodes are the dual variables. <ref> Freund, Robert M. (2004, February 10). ''Applied Language Duality for Constrained Optimization.'' Massachusetts Institute of Technology. https://ocw.mit.edu/courses/sloan-school-of-management/15-094j-systems-optimization-models-and-computation-sma-5223-spring-2004/lecture-notes/duality_article.pdf </ref><br />
<br />
'''Electrical Networks'''<br />
<br />
*When modeling electrical networks the current flows can be modeled as the primal variables, and the voltage differences are the dual variables. <ref> Freund, Robert M. (2004, March). ''Duality Theory of Constrained Optimization.'' Massachusetts Institute of Technology. https://ocw.mit.edu/courses/sloan-school-of-management/15-084j-nonlinear-programming-spring-2004/lecture-notes/lec18_duality_thy.pdf </ref><br />
<br />
'''Game Theory'''<br />
<br />
* Duality theory is closely related to game theory. Game theory is an approach used to deal with multi-person decision problems. The game is the decision-making problem, and the players are the decision-makers. Each player chooses a strategy or an action to be taken. Each player will then receive a payoff when each player has selected a strategy. The zero sum game that Von Neumann conjectured was the same as linear programming, is when the gain of one player results in the loss of another. This general situation of a zero sum game has similar characteristics to duality. <ref> Stolee, Derrick. (2013). ''Game Theory and Duality.'' University of Illinois at Urbana-Champaigna. https://faculty.math.illinois.edu/~stolee/Teaching/13-482/gametheory.pdf </ref><br />
<br />
'''Support Vector Machines''' <br />
<br />
* Support Vector Machines (SVM) is a popular machine learning algorithm for classification. The concept of SVM can be broken down into three parts, the first two being Linear SVM and the last being Non-Linear SVM. There are many other concepts to SVM including hyperplanes, functional and geometric margins, and quadratic programming <ref> Jana, Abhisek. (2020, April). ''Support Vector Machines for Beginners - Linear SVM.'' http://www.adeveloperdiary.com/data-science/machine-learning/support-vector-machines-for-beginners-linear-svm/ </ref>. In relation to Duality, the primal problem is helpful in solving Linear SVM, but in order to get to the goal of solving Non-Linear SVM, the primal problem is not useful. This is where we need Duality to look at the dual problem to solve the Non-Linear SVM <ref> Jana, Abhisek. (2020, April 5). ''Support Vector Machines for Beginners - Duality Problem.'' https://www.adeveloperdiary.com/data-science/machine-learning/support-vector-machines-for-beginners-duality-problem/. </ref>.<br />
<br />
== Conclusion ==<br />
Since proofs of Duality theory were published in 1948 <ref name=":0" /> duality has been such an important technique in solving linear and nonlinear optimization problems. This theory provides the idea that the dual of a standard maximum problem is defined to be the standard minimum problem <ref name=":1" />. This technique allows for every feasible solution for one side of the optimization problem to give a bound on the optimal objective function value for the other <ref name=":2" />. This technique can be applied to situations such as solving for economic constraints, resource allocation, game theory and bounding optimization problems. By developing an understanding of the dual of a linear program one can gain many important insights on nearly any algorithm or optimization of data.<br />
<br />
== References ==</div>Asa273https://optimization.cbe.cornell.edu/index.php?title=2020_Cornell_Optimization_Open_Textbook_Feedback&diff=26722020 Cornell Optimization Open Textbook Feedback2020-12-15T06:31:20Z<p>Asa273: /* Convex generalized disjunctive programming (GDP) */</p>
<hr />
<div>==[[Duality]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Remove colon in the subsection title<br />
<br />
==[[Simplex algorithm]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
* References<br />
<br />
==[[Computational complexity]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
* At least one numerical example<br />
*# Finding subsets of a set is NOT O(2^n).<br />
* A section to discuss and/or illustrate the applications<br />
*# The applications mentioned need to be discussed further. <br />
<br />
==[[Network flow problem]]==<br />
<br />
* At least one numerical example<br />
*# There is NO need to include code. Simply mention how the problem was coded along with details on the LP solver used.<br />
*# The subsection title style should be consistent.<br />
<br />
==[[Interior-point method for LP]]==<br />
<br />
* An introduction of the topic<br />
*# Fix typos “where A ε R”<br />
*# Please type “minimize” and “subject to” in formal optimization problem form throughout the whole page.<br />
* A section to discuss and/or illustrate the applications<br />
*# Please type optimization problem in the formal form.<br />
*# Please double check typos and extra spaces.<br />
<br />
==[[Optimization with absolute values]]==<br />
<br />
* An introduction of the topic<br />
*# Add few sentences on how absolute values convert optimization problem into a nonlinear optimization problem<br />
* A section to discuss and/or illustrate the applications<br />
*# Inline equations at the beginning of this section are not formatted properly. Please fix the notation for expected return throughout the section.<br />
<br />
==[[Matrix game (LP for game theory)]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# aij are not defined in this section.<br />
<br />
==[[Quasi-Newton methods]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Please ensure that few spaces are kept between the equations and equation numbers.<br />
<br />
== [[Markov decision process]] ==<br />
<br />
* An introduction of the topic<br />
*# Please fix typos such as “discreet”.<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# If abbreviations are defined like MDP, use the abbreviations throughout the Wiki<br />
<br />
==[[Eight step procedures]]==<br />
<br />
* At least one numerical example<br />
*# Data for the example Knapsack problem (b,w) are missing.<br />
*# How to arrive at optimal solutions is missing.<br />
<br />
==[[Facility location problem]]==<br />
<br />
* At least one numerical example<br />
*# Mention how the formulated problem is coded and solved. No need to provide GAMS code.<br />
<br />
==[[Set covering problem]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Use proper math notations for “greater than equal to”.<br />
* At least one numerical example<br />
*# Please leave some space between equation and equation number.<br />
<br />
==[[Quadratic assignment problem]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Discuss dynamic programming and cutting plane solution techniques briefly.<br />
* A section to discuss and/or illustrate the applications<br />
<br />
==[[Newsvendor problem]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# A math programming formulation of the optimization problem with objective function and constraints is expected for the formulation. Please add any variant of the newsvendor problem along with some operational constraints.<br />
*# A mathematical presentation of the solution technique is expected. Please consider any distribution for R and present a solution technique for that specific problem. <br />
<br />
==[[Mixed-integer cuts]]==<br />
<br />
* A section to discuss and/or illustrate the applications<br />
*# MILP and their solution techniques involving cuts are extremely versatile. Yet, only two sentences are added to describe their applications. Please discuss their applications, preferably real-world applications, in brief. Example Wikis provided on the website could be used as a reference to do so.<br />
<br />
==[[Column generation algorithms]]==<br />
<br />
* An introduction of the topic<br />
*# References at the end of the sentence should be placed after the period.<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Some minor typos/article agreement issues exist “is not partical in real-world”.<br />
<br />
==[[Heuristic algorithms]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Please use proper symbol for "greater than or equal to".<br />
*# Greedy method to solve minimum spanning tree seems to be missing.<br />
<br />
==[[Branch and cut]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Equation in most infeasible branching section is not properly formatted, please fix the same.<br />
*# Step 2 appears abruptly in the algorithm and does not explain much. Please add more information regarding the same.<br />
*# Step 5 contains latex code terms that are not properly formatted. Please fix the same.<br />
*# Fix typos: e.g., repeated “for the current”, men Problem can viewed as partially” ..<br />
<br />
== [[Mixed-integer linear fractional programming (MILFP)]] ==<br />
<br />
* At least one numerical example<br />
*# Please check the index notation in Mass Balance Constraint<br />
<br />
==[[Convex generalized disjunctive programming (GDP)]]==<br />
<br />
* An introduction of the topic<br />
*# Please refrain from defining the same abbreviations multiple times.<br />
*# Please use abbreviations throughout the page if they have been defined.<br />
* At least one numerical example<br />
*# There is a duplicate figure 3.<br />
<br />
==[[Fuzzy programming]]==<br />
<br />
* A section to discuss and/or illustrate the applications<br />
*# Applications of fuzzy programming are quite versatile. Please discuss few of the mentioned applications briefly. The provided example Wikis can be used as a reference to write this section.T<br />
<br />
==[[Adaptive robust optimization]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Please check typos such as "Let ''u'' bee a vector".<br />
*# The abbreviation KKT is not previously defined.<br />
<br />
== [[Stochastic gradient descent]] ==<br />
* At least one numerical example<br />
*# Amount of whitespace can be reduced by changing orientation of example dataset by converting it into a table containing 3 rows and 6 columns.<br />
* A section to discuss and/or illustrate the applications<br />
*# Deep learning can become a subsection on its own.<br />
<br />
==[[RMSProp]]==<br />
<br />
* An introduction of the topic<br />
*# References at the end of the sentence should be placed after the period.<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Please check grammar in this section.<br />
* A section to discuss and/or illustrate the applications<br />
*# The applications section does not contain any discussion on applications. Please mention a few applications of the widely used RMSprop and discuss them briefly.<br />
<br />
==[[Adam]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# References at the end of the sentence should be placed after the period.</div>Asa273https://optimization.cbe.cornell.edu/index.php?title=2020_Cornell_Optimization_Open_Textbook_Feedback&diff=26712020 Cornell Optimization Open Textbook Feedback2020-12-15T06:21:57Z<p>Asa273: /* Set covering problem */</p>
<hr />
<div>==[[Duality]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Remove colon in the subsection title<br />
<br />
==[[Simplex algorithm]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
* References<br />
<br />
==[[Computational complexity]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
* At least one numerical example<br />
*# Finding subsets of a set is NOT O(2^n).<br />
* A section to discuss and/or illustrate the applications<br />
*# The applications mentioned need to be discussed further. <br />
<br />
==[[Network flow problem]]==<br />
<br />
* At least one numerical example<br />
*# There is NO need to include code. Simply mention how the problem was coded along with details on the LP solver used.<br />
*# The subsection title style should be consistent.<br />
<br />
==[[Interior-point method for LP]]==<br />
<br />
* An introduction of the topic<br />
*# Fix typos “where A ε R”<br />
*# Please type “minimize” and “subject to” in formal optimization problem form throughout the whole page.<br />
* A section to discuss and/or illustrate the applications<br />
*# Please type optimization problem in the formal form.<br />
*# Please double check typos and extra spaces.<br />
<br />
==[[Optimization with absolute values]]==<br />
<br />
* An introduction of the topic<br />
*# Add few sentences on how absolute values convert optimization problem into a nonlinear optimization problem<br />
* A section to discuss and/or illustrate the applications<br />
*# Inline equations at the beginning of this section are not formatted properly. Please fix the notation for expected return throughout the section.<br />
<br />
==[[Matrix game (LP for game theory)]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# aij are not defined in this section.<br />
<br />
==[[Quasi-Newton methods]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Please ensure that few spaces are kept between the equations and equation numbers.<br />
<br />
== [[Markov decision process]] ==<br />
<br />
* An introduction of the topic<br />
*# Please fix typos such as “discreet”.<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# If abbreviations are defined like MDP, use the abbreviations throughout the Wiki<br />
<br />
==[[Eight step procedures]]==<br />
<br />
* At least one numerical example<br />
*# Data for the example Knapsack problem (b,w) are missing.<br />
*# How to arrive at optimal solutions is missing.<br />
<br />
==[[Facility location problem]]==<br />
<br />
* At least one numerical example<br />
*# Mention how the formulated problem is coded and solved. No need to provide GAMS code.<br />
<br />
==[[Set covering problem]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Use proper math notations for “greater than equal to”.<br />
* At least one numerical example<br />
*# Please leave some space between equation and equation number.<br />
<br />
==[[Quadratic assignment problem]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Discuss dynamic programming and cutting plane solution techniques briefly.<br />
* A section to discuss and/or illustrate the applications<br />
<br />
==[[Newsvendor problem]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# A math programming formulation of the optimization problem with objective function and constraints is expected for the formulation. Please add any variant of the newsvendor problem along with some operational constraints.<br />
*# A mathematical presentation of the solution technique is expected. Please consider any distribution for R and present a solution technique for that specific problem. <br />
<br />
==[[Mixed-integer cuts]]==<br />
<br />
* A section to discuss and/or illustrate the applications<br />
*# MILP and their solution techniques involving cuts are extremely versatile. Yet, only two sentences are added to describe their applications. Please discuss their applications, preferably real-world applications, in brief. Example Wikis provided on the website could be used as a reference to do so.<br />
<br />
==[[Column generation algorithms]]==<br />
<br />
* An introduction of the topic<br />
*# References at the end of the sentence should be placed after the period.<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Some minor typos/article agreement issues exist “is not partical in real-world”.<br />
<br />
==[[Heuristic algorithms]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Please use proper symbol for "greater than or equal to".<br />
*# Greedy method to solve minimum spanning tree seems to be missing.<br />
<br />
==[[Branch and cut]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Equation in most infeasible branching section is not properly formatted, please fix the same.<br />
*# Step 2 appears abruptly in the algorithm and does not explain much. Please add more information regarding the same.<br />
*# Step 5 contains latex code terms that are not properly formatted. Please fix the same.<br />
*# Fix typos: e.g., repeated “for the current”, men Problem can viewed as partially” ..<br />
<br />
== [[Mixed-integer linear fractional programming (MILFP)]] ==<br />
<br />
* At least one numerical example<br />
*# Please check the index notation in Mass Balance Constraint<br />
<br />
==[[Convex generalized disjunctive programming (GDP)]]==<br />
<br />
* An introduction of the topic<br />
*# Please refrain from defining the same abbreviations multiple times.<br />
*# Please use abbreviations throughout the page if they have been defined.<br />
* At least one numerical example<br />
*# There is a duplicate figure. <br />
<br />
==[[Fuzzy programming]]==<br />
<br />
* An introduction of the topic<br />
*# References at the end of the sentence should be placed after the period.<br />
* At least one numerical example<br />
*# The numeric example should be before the applications section.<br />
* A section to discuss and/or illustrate the applications<br />
*# Applications of fuzzy programming are quite versatile. Please discuss few of the mentioned applications briefly. The provided example Wikis can be used as a reference to write this section.<br />
* References<br />
*# Please consider linking the references by using this as Wiki template, [[Quantum computing for optimization|https://optimization.cbe.cornell.edu/index.php?title=Quantum_computing_for_optimization]]<br />
<br />
==[[Adaptive robust optimization]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Please check typos such as "Let ''u'' bee a vector".<br />
*# The abbreviation KKT is not previously defined.<br />
<br />
== [[Stochastic gradient descent]] ==<br />
* At least one numerical example<br />
*# Amount of whitespace can be reduced by changing orientation of example dataset by converting it into a table containing 3 rows and 6 columns.<br />
* A section to discuss and/or illustrate the applications<br />
*# Deep learning can become a subsection on its own.<br />
<br />
==[[RMSProp]]==<br />
<br />
* An introduction of the topic<br />
*# References at the end of the sentence should be placed after the period.<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Please check grammar in this section.<br />
* A section to discuss and/or illustrate the applications<br />
*# The applications section does not contain any discussion on applications. Please mention a few applications of the widely used RMSprop and discuss them briefly.<br />
*# Please check grammar in this section.<br />
* References<br />
*# Please refer to the example Wikis provided to use proper citation style.<br />
*# Please consider linking the references by using this as Wiki template, [[Quantum computing for optimization|https://optimization.cbe.cornell.edu/index.php?title=Quantum_computing_for_optimization]]<br />
<br />
==[[Adam]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# References at the end of the sentence should be placed after the period.</div>Asa273https://optimization.cbe.cornell.edu/index.php?title=2020_Cornell_Optimization_Open_Textbook_Feedback&diff=26702020 Cornell Optimization Open Textbook Feedback2020-12-15T05:49:04Z<p>Asa273: /* Optimization with absolute values */</p>
<hr />
<div>==[[Duality]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Remove colon in the subsection title<br />
<br />
==[[Simplex algorithm]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
* References<br />
<br />
==[[Computational complexity]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
* At least one numerical example<br />
*# Finding subsets of a set is NOT O(2^n).<br />
* A section to discuss and/or illustrate the applications<br />
*# The applications mentioned need to be discussed further. <br />
<br />
==[[Network flow problem]]==<br />
<br />
* At least one numerical example<br />
*# There is NO need to include code. Simply mention how the problem was coded along with details on the LP solver used.<br />
*# The subsection title style should be consistent.<br />
<br />
==[[Interior-point method for LP]]==<br />
<br />
* An introduction of the topic<br />
*# Fix typos “where A ε R”<br />
*# Please type “minimize” and “subject to” in formal optimization problem form throughout the whole page.<br />
* A section to discuss and/or illustrate the applications<br />
*# Please type optimization problem in the formal form.<br />
*# Please double check typos and extra spaces.<br />
<br />
==[[Optimization with absolute values]]==<br />
<br />
* An introduction of the topic<br />
*# Add few sentences on how absolute values convert optimization problem into a nonlinear optimization problem<br />
* A section to discuss and/or illustrate the applications<br />
*# Inline equations at the beginning of this section are not formatted properly. Please fix the notation for expected return throughout the section.<br />
<br />
==[[Matrix game (LP for game theory)]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# aij are not defined in this section.<br />
<br />
==[[Quasi-Newton methods]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Please ensure that few spaces are kept between the equations and equation numbers.<br />
<br />
== [[Markov decision process]] ==<br />
<br />
* An introduction of the topic<br />
*# Please fix typos such as “discreet”.<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# If abbreviations are defined like MDP, use the abbreviations throughout the Wiki<br />
<br />
==[[Eight step procedures]]==<br />
<br />
* At least one numerical example<br />
*# Data for the example Knapsack problem (b,w) are missing.<br />
*# How to arrive at optimal solutions is missing.<br />
<br />
==[[Facility location problem]]==<br />
<br />
* At least one numerical example<br />
*# Mention how the formulated problem is coded and solved. No need to provide GAMS code.<br />
<br />
==[[Set covering problem]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Use proper math notations for “greater than equal to”.<br />
* At least one numerical example<br />
*# Since Table 3 provides information on aij required to formulate the constraints, Table 2 serves no purpose and should be removed from the Wiki. Table 3 can be directly generated from Table 1.<br />
*# The numerical example is solved manually without using greedy method nor LP solution method. Please solve this example both by the presented greedy algorithm and the newly added LP-based method and finally compare solutions.<br />
*# Please leave some space between equation and equation number.<br />
<br />
==[[Quadratic assignment problem]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Discuss dynamic programming and cutting plane solution techniques briefly.<br />
* A section to discuss and/or illustrate the applications<br />
*# Please format the equation for definition of yij in the hospital layout subsection.<br />
<br />
==[[Newsvendor problem]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# A math programming formulation of the optimization problem with objective function and constraints is expected for the formulation. Please add any variant of the newsvendor problem along with some operational constraints.<br />
*# A mathematical presentation of the solution technique is expected. Please consider any distribution for R and present a solution technique for that specific problem. <br />
<br />
==[[Mixed-integer cuts]]==<br />
<br />
* A section to discuss and/or illustrate the applications<br />
*# MILP and their solution techniques involving cuts are extremely versatile. Yet, only two sentences are added to describe their applications. Please discuss their applications, preferably real-world applications, in brief. Example Wikis provided on the website could be used as a reference to do so.<br />
<br />
==[[Column generation algorithms]]==<br />
<br />
* An introduction of the topic<br />
*# References at the end of the sentence should be placed after the period.<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Some minor typos/article agreement issues exist “is not partical in real-world”.<br />
*# Referencing subtitle "Methodology" is not a formal way. <br />
<br />
==[[Heuristic algorithms]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Please use proper symbol for "greater than or equal to".<br />
*# Greedy method to solve minimum spanning tree seems to be missing.<br />
<br />
==[[Branch and cut]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Equation in most infeasible branching section is not properly formatted, please fix the same.<br />
*# Step 2 appears abruptly in the algorithm and does not explain much. Please add more information regarding the same.<br />
*# Step 5 contains latex code terms that are not properly formatted. Please fix the same.<br />
*# Fix typos: e.g., repeated “for the current”, men Problem can viewed as partially” ..<br />
<br />
== [[Mixed-integer linear fractional programming (MILFP)]] ==<br />
<br />
* At least one numerical example<br />
*# Please check the index notation in Mass Balance Constraints.<br />
* References<br />
*# Please consider linking the citations to references in the reference list by using this as Wiki template, rather than using website links. [[Quantum computing for optimization|https://optimization.cbe.cornell.edu/index.php?title=Quantum_computing_for_optimization]]<br />
<br />
==[[Convex generalized disjunctive programming (GDP)]]==<br />
<br />
* An introduction of the topic<br />
*# Please refrain from defining the same abbreviations multiple times.<br />
*# Please use abbreviations throughout the page if they have been defined.<br />
* At least one numerical example<br />
*# There is a duplicate figure. <br />
<br />
==[[Fuzzy programming]]==<br />
<br />
* An introduction of the topic<br />
*# References at the end of the sentence should be placed after the period.<br />
* At least one numerical example<br />
*# The numeric example should be before the applications section.<br />
* A section to discuss and/or illustrate the applications<br />
*# Applications of fuzzy programming are quite versatile. Please discuss few of the mentioned applications briefly. The provided example Wikis can be used as a reference to write this section.<br />
* References<br />
*# Please consider linking the references by using this as Wiki template, [[Quantum computing for optimization|https://optimization.cbe.cornell.edu/index.php?title=Quantum_computing_for_optimization]]<br />
<br />
==[[Adaptive robust optimization]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Please check typos such as "Let ''u'' bee a vector".<br />
*# The abbreviation KKT is not previously defined.<br />
<br />
== [[Stochastic gradient descent]] ==<br />
* At least one numerical example<br />
*# Amount of whitespace can be reduced by changing orientation of example dataset by converting it into a table containing 3 rows and 6 columns.<br />
* A section to discuss and/or illustrate the applications<br />
*# Deep learning can become a subsection on its own.<br />
<br />
==[[RMSProp]]==<br />
<br />
* An introduction of the topic<br />
*# References at the end of the sentence should be placed after the period.<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Please check grammar in this section.<br />
* A section to discuss and/or illustrate the applications<br />
*# The applications section does not contain any discussion on applications. Please mention a few applications of the widely used RMSprop and discuss them briefly.<br />
*# Please check grammar in this section.<br />
* References<br />
*# Please refer to the example Wikis provided to use proper citation style.<br />
*# Please consider linking the references by using this as Wiki template, [[Quantum computing for optimization|https://optimization.cbe.cornell.edu/index.php?title=Quantum_computing_for_optimization]]<br />
<br />
==[[Adam]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# References at the end of the sentence should be placed after the period.</div>Asa273https://optimization.cbe.cornell.edu/index.php?title=2020_Cornell_Optimization_Open_Textbook_Feedback&diff=26692020 Cornell Optimization Open Textbook Feedback2020-12-15T05:19:27Z<p>Asa273: /* Interior-point method for LP */</p>
<hr />
<div>==[[Duality]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Remove colon in the subsection title<br />
<br />
==[[Simplex algorithm]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
* References<br />
<br />
==[[Computational complexity]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
* At least one numerical example<br />
*# Finding subsets of a set is NOT O(2^n).<br />
* A section to discuss and/or illustrate the applications<br />
*# The applications mentioned need to be discussed further. <br />
<br />
==[[Network flow problem]]==<br />
<br />
* At least one numerical example<br />
*# There is NO need to include code. Simply mention how the problem was coded along with details on the LP solver used.<br />
*# The subsection title style should be consistent.<br />
<br />
==[[Interior-point method for LP]]==<br />
<br />
* An introduction of the topic<br />
*# Fix typos “where A ε R”<br />
*# Please type “minimize” and “subject to” in formal optimization problem form throughout the whole page.<br />
* A section to discuss and/or illustrate the applications<br />
*# Please type optimization problem in the formal form.<br />
*# Please double check typos and extra spaces.<br />
<br />
==[[Optimization with absolute values]]==<br />
<br />
* An introduction of the topic<br />
*# Add few sentences on how absolute values convert optimization problem into a nonlinear optimization problem.<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Please add more details to absolute values in nonlinear optimization. (very important!)<br />
* A section to discuss and/or illustrate the applications<br />
*# Inline equations at the beginning of this section are not formatted properly. Please fix the notation for expected return throughout the section.<br />
<br />
==[[Matrix game (LP for game theory)]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# aij are not defined in this section.<br />
* References<br />
*# Please consider linking the references by using this as Wiki template, [[Quantum computing for optimization|https://optimization.cbe.cornell.edu/index.php?title=Quantum_computing_for_optimization]]<br />
<br />
==[[Quasi-Newton methods]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Please ensure that few spaces are kept between the equations and equation numbers.<br />
*# Step 6 of DFP algorithm should use the same variable M as in equation 1.14.<br />
<br />
== [[Markov decision process]] ==<br />
<br />
* An introduction of the topic<br />
*# Please fix typos such as “discreet”.<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# If abbreviations are defined like MDP, use the abbreviations throughout the Wiki.<br />
* References<br />
*# Please consider linking the references by using this as Wiki template, [[Quantum computing for optimization|https://optimization.cbe.cornell.edu/index.php?title=Quantum_computing_for_optimization]]<br />
<br />
==[[Eight step procedures]]==<br />
<br />
* At least one numerical example<br />
*# Please be consistent in the formatting of mathematical notations and equations.<br />
* References<br />
*# Lecture notes may not be a credible reference. Please find the original source.<br />
<br />
==[[Facility location problem]]==<br />
<br />
* At least one numerical example<br />
*# Mention how the formulated problem is coded and solved. No need to provide GAMS code.<br />
* References<br />
*# Please consider linking the references by using this as Wiki template, [[Quantum computing for optimization|https://optimization.cbe.cornell.edu/index.php?title=Quantum_computing_for_optimization]]<br />
<br />
==[[Set covering problem]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Use proper math notations for “greater than equal to”.<br />
* At least one numerical example<br />
*# Since Table 3 provides information on aij required to formulate the constraints, Table 2 serves no purpose and should be removed from the Wiki. Table 3 can be directly generated from Table 1.<br />
*# The numerical example is solved manually without using greedy method nor LP solution method. Please solve this example both by the presented greedy algorithm and the newly added LP-based method and finally compare solutions.<br />
*# Please leave some space between equation and equation number.<br />
<br />
==[[Quadratic assignment problem]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Discuss dynamic programming and cutting plane solution techniques briefly.<br />
* A section to discuss and/or illustrate the applications<br />
*# Please format the equation for definition of yij in the hospital layout subsection.<br />
<br />
==[[Newsvendor problem]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# A math programming formulation of the optimization problem with objective function and constraints is expected for the formulation. Please add any variant of the newsvendor problem along with some operational constraints.<br />
*# A mathematical presentation of the solution technique is expected. Please consider any distribution for R and present a solution technique for that specific problem. <br />
<br />
==[[Mixed-integer cuts]]==<br />
<br />
* A section to discuss and/or illustrate the applications<br />
*# MILP and their solution techniques involving cuts are extremely versatile. Yet, only two sentences are added to describe their applications. Please discuss their applications, preferably real-world applications, in brief. Example Wikis provided on the website could be used as a reference to do so.<br />
<br />
==[[Column generation algorithms]]==<br />
<br />
* An introduction of the topic<br />
*# References at the end of the sentence should be placed after the period.<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Some minor typos/article agreement issues exist “is not partical in real-world”.<br />
*# Referencing subtitle "Methodology" is not a formal way. <br />
<br />
==[[Heuristic algorithms]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Please use proper symbol for "greater than or equal to".<br />
*# Greedy method to solve minimum spanning tree seems to be missing.<br />
<br />
==[[Branch and cut]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Equation in most infeasible branching section is not properly formatted, please fix the same.<br />
*# Step 2 appears abruptly in the algorithm and does not explain much. Please add more information regarding the same.<br />
*# Step 5 contains latex code terms that are not properly formatted. Please fix the same.<br />
*# Fix typos: e.g., repeated “for the current”, men Problem can viewed as partially” ..<br />
<br />
== [[Mixed-integer linear fractional programming (MILFP)]] ==<br />
<br />
* At least one numerical example<br />
*# Please check the index notation in Mass Balance Constraints.<br />
* References<br />
*# Please consider linking the citations to references in the reference list by using this as Wiki template, rather than using website links. [[Quantum computing for optimization|https://optimization.cbe.cornell.edu/index.php?title=Quantum_computing_for_optimization]]<br />
<br />
==[[Convex generalized disjunctive programming (GDP)]]==<br />
<br />
* An introduction of the topic<br />
*# Please refrain from defining the same abbreviations multiple times.<br />
*# Please use abbreviations throughout the page if they have been defined.<br />
* At least one numerical example<br />
*# There is a duplicate figure. <br />
<br />
==[[Fuzzy programming]]==<br />
<br />
* An introduction of the topic<br />
*# References at the end of the sentence should be placed after the period.<br />
* At least one numerical example<br />
*# The numeric example should be before the applications section.<br />
* A section to discuss and/or illustrate the applications<br />
*# Applications of fuzzy programming are quite versatile. Please discuss few of the mentioned applications briefly. The provided example Wikis can be used as a reference to write this section.<br />
* References<br />
*# Please consider linking the references by using this as Wiki template, [[Quantum computing for optimization|https://optimization.cbe.cornell.edu/index.php?title=Quantum_computing_for_optimization]]<br />
<br />
==[[Adaptive robust optimization]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Please check typos such as "Let ''u'' bee a vector".<br />
*# The abbreviation KKT is not previously defined.<br />
<br />
== [[Stochastic gradient descent]] ==<br />
* At least one numerical example<br />
*# Amount of whitespace can be reduced by changing orientation of example dataset by converting it into a table containing 3 rows and 6 columns.<br />
* A section to discuss and/or illustrate the applications<br />
*# Deep learning can become a subsection on its own.<br />
<br />
==[[RMSProp]]==<br />
<br />
* An introduction of the topic<br />
*# References at the end of the sentence should be placed after the period.<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Please check grammar in this section.<br />
* A section to discuss and/or illustrate the applications<br />
*# The applications section does not contain any discussion on applications. Please mention a few applications of the widely used RMSprop and discuss them briefly.<br />
*# Please check grammar in this section.<br />
* References<br />
*# Please refer to the example Wikis provided to use proper citation style.<br />
*# Please consider linking the references by using this as Wiki template, [[Quantum computing for optimization|https://optimization.cbe.cornell.edu/index.php?title=Quantum_computing_for_optimization]]<br />
<br />
==[[Adam]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# References at the end of the sentence should be placed after the period.</div>Asa273https://optimization.cbe.cornell.edu/index.php?title=2020_Cornell_Optimization_Open_Textbook_Feedback&diff=26682020 Cornell Optimization Open Textbook Feedback2020-12-15T05:08:50Z<p>Asa273: /* Computational complexity */</p>
<hr />
<div>==[[Duality]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Remove colon in the subsection title<br />
<br />
==[[Simplex algorithm]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
* References<br />
<br />
==[[Computational complexity]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
* At least one numerical example<br />
*# Finding subsets of a set is NOT O(2^n).<br />
* A section to discuss and/or illustrate the applications<br />
*# The applications mentioned need to be discussed further. <br />
<br />
==[[Network flow problem]]==<br />
<br />
* At least one numerical example<br />
*# There is NO need to include code. Simply mention how the problem was coded along with details on the LP solver used.<br />
*# The subsection title style should be consistent.<br />
<br />
==[[Interior-point method for LP]]==<br />
<br />
* An introduction of the topic<br />
*# Fix typos “where A ε R”<br />
*# Please type “minimize” and “subject to” in formal optimization problem form throughout the whole page.<br />
* At least one numerical example<br />
*# The numerical example does not use any Newton’s method iterations that are presented in the above section. Please consider using a complicated example that actually uses Newton’s iterations.<br />
*# Please type the maximization problem in LaTex form.<br />
* A section to discuss and/or illustrate the applications<br />
*# Please double check typos and extra spaces.<br />
<br />
==[[Optimization with absolute values]]==<br />
<br />
* An introduction of the topic<br />
*# Add few sentences on how absolute values convert optimization problem into a nonlinear optimization problem.<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Please add more details to absolute values in nonlinear optimization. (very important!)<br />
* A section to discuss and/or illustrate the applications<br />
*# Inline equations at the beginning of this section are not formatted properly. Please fix the notation for expected return throughout the section.<br />
<br />
==[[Matrix game (LP for game theory)]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# aij are not defined in this section.<br />
* References<br />
*# Please consider linking the references by using this as Wiki template, [[Quantum computing for optimization|https://optimization.cbe.cornell.edu/index.php?title=Quantum_computing_for_optimization]]<br />
<br />
==[[Quasi-Newton methods]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Please ensure that few spaces are kept between the equations and equation numbers.<br />
*# Step 6 of DFP algorithm should use the same variable M as in equation 1.14.<br />
<br />
== [[Markov decision process]] ==<br />
<br />
* An introduction of the topic<br />
*# Please fix typos such as “discreet”.<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# If abbreviations are defined like MDP, use the abbreviations throughout the Wiki.<br />
* References<br />
*# Please consider linking the references by using this as Wiki template, [[Quantum computing for optimization|https://optimization.cbe.cornell.edu/index.php?title=Quantum_computing_for_optimization]]<br />
<br />
==[[Eight step procedures]]==<br />
<br />
* At least one numerical example<br />
*# Please be consistent in the formatting of mathematical notations and equations.<br />
* References<br />
*# Lecture notes may not be a credible reference. Please find the original source.<br />
<br />
==[[Facility location problem]]==<br />
<br />
* At least one numerical example<br />
*# Mention how the formulated problem is coded and solved. No need to provide GAMS code.<br />
* References<br />
*# Please consider linking the references by using this as Wiki template, [[Quantum computing for optimization|https://optimization.cbe.cornell.edu/index.php?title=Quantum_computing_for_optimization]]<br />
<br />
==[[Set covering problem]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Use proper math notations for “greater than equal to”.<br />
* At least one numerical example<br />
*# Since Table 3 provides information on aij required to formulate the constraints, Table 2 serves no purpose and should be removed from the Wiki. Table 3 can be directly generated from Table 1.<br />
*# The numerical example is solved manually without using greedy method nor LP solution method. Please solve this example both by the presented greedy algorithm and the newly added LP-based method and finally compare solutions.<br />
*# Please leave some space between equation and equation number.<br />
<br />
==[[Quadratic assignment problem]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Discuss dynamic programming and cutting plane solution techniques briefly.<br />
* A section to discuss and/or illustrate the applications<br />
*# Please format the equation for definition of yij in the hospital layout subsection.<br />
<br />
==[[Newsvendor problem]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# A math programming formulation of the optimization problem with objective function and constraints is expected for the formulation. Please add any variant of the newsvendor problem along with some operational constraints.<br />
*# A mathematical presentation of the solution technique is expected. Please consider any distribution for R and present a solution technique for that specific problem. <br />
<br />
==[[Mixed-integer cuts]]==<br />
<br />
* A section to discuss and/or illustrate the applications<br />
*# MILP and their solution techniques involving cuts are extremely versatile. Yet, only two sentences are added to describe their applications. Please discuss their applications, preferably real-world applications, in brief. Example Wikis provided on the website could be used as a reference to do so.<br />
<br />
==[[Column generation algorithms]]==<br />
<br />
* An introduction of the topic<br />
*# References at the end of the sentence should be placed after the period.<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Some minor typos/article agreement issues exist “is not partical in real-world”.<br />
*# Referencing subtitle "Methodology" is not a formal way. <br />
<br />
==[[Heuristic algorithms]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Please use proper symbol for "greater than or equal to".<br />
*# Greedy method to solve minimum spanning tree seems to be missing.<br />
<br />
==[[Branch and cut]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Equation in most infeasible branching section is not properly formatted, please fix the same.<br />
*# Step 2 appears abruptly in the algorithm and does not explain much. Please add more information regarding the same.<br />
*# Step 5 contains latex code terms that are not properly formatted. Please fix the same.<br />
*# Fix typos: e.g., repeated “for the current”, men Problem can viewed as partially” ..<br />
<br />
== [[Mixed-integer linear fractional programming (MILFP)]] ==<br />
<br />
* At least one numerical example<br />
*# Please check the index notation in Mass Balance Constraints.<br />
* References<br />
*# Please consider linking the citations to references in the reference list by using this as Wiki template, rather than using website links. [[Quantum computing for optimization|https://optimization.cbe.cornell.edu/index.php?title=Quantum_computing_for_optimization]]<br />
<br />
==[[Convex generalized disjunctive programming (GDP)]]==<br />
<br />
* An introduction of the topic<br />
*# Please refrain from defining the same abbreviations multiple times.<br />
*# Please use abbreviations throughout the page if they have been defined.<br />
* At least one numerical example<br />
*# There is a duplicate figure. <br />
<br />
==[[Fuzzy programming]]==<br />
<br />
* An introduction of the topic<br />
*# References at the end of the sentence should be placed after the period.<br />
* At least one numerical example<br />
*# The numeric example should be before the applications section.<br />
* A section to discuss and/or illustrate the applications<br />
*# Applications of fuzzy programming are quite versatile. Please discuss few of the mentioned applications briefly. The provided example Wikis can be used as a reference to write this section.<br />
* References<br />
*# Please consider linking the references by using this as Wiki template, [[Quantum computing for optimization|https://optimization.cbe.cornell.edu/index.php?title=Quantum_computing_for_optimization]]<br />
<br />
==[[Adaptive robust optimization]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Please check typos such as "Let ''u'' bee a vector".<br />
*# The abbreviation KKT is not previously defined.<br />
<br />
== [[Stochastic gradient descent]] ==<br />
* At least one numerical example<br />
*# Amount of whitespace can be reduced by changing orientation of example dataset by converting it into a table containing 3 rows and 6 columns.<br />
* A section to discuss and/or illustrate the applications<br />
*# Deep learning can become a subsection on its own.<br />
<br />
==[[RMSProp]]==<br />
<br />
* An introduction of the topic<br />
*# References at the end of the sentence should be placed after the period.<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Please check grammar in this section.<br />
* A section to discuss and/or illustrate the applications<br />
*# The applications section does not contain any discussion on applications. Please mention a few applications of the widely used RMSprop and discuss them briefly.<br />
*# Please check grammar in this section.<br />
* References<br />
*# Please refer to the example Wikis provided to use proper citation style.<br />
*# Please consider linking the references by using this as Wiki template, [[Quantum computing for optimization|https://optimization.cbe.cornell.edu/index.php?title=Quantum_computing_for_optimization]]<br />
<br />
==[[Adam]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# References at the end of the sentence should be placed after the period.</div>Asa273https://optimization.cbe.cornell.edu/index.php?title=2020_Cornell_Optimization_Open_Textbook_Feedback&diff=26412020 Cornell Optimization Open Textbook Feedback2020-12-15T03:54:45Z<p>Asa273: /* Duality */</p>
<hr />
<div>==[[Duality]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Remove colon in the subsection title<br />
<br />
==[[Simplex algorithm]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
* References<br />
<br />
==[[Computational complexity]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
* At least one numerical example<br />
*# Finding subsets of a set is not O(2^n).<br />
* A section to discuss and/or illustrate the applications<br />
*# The applications mentioned need to be discussed further. <br />
<br />
==[[Network flow problem]]==<br />
<br />
* At least one numerical example<br />
*# There is NO need to include code. Simply mention how the problem was coded along with details on the LP solver used.<br />
*# The subsection title style should be consistent.<br />
<br />
==[[Interior-point method for LP]]==<br />
<br />
* An introduction of the topic<br />
*# Fix typos “where A ε R”<br />
*# Please type “minimize” and “subject to” in formal optimization problem form throughout the whole page.<br />
* At least one numerical example<br />
*# The numerical example does not use any Newton’s method iterations that are presented in the above section. Please consider using a complicated example that actually uses Newton’s iterations.<br />
*# Please type the maximization problem in LaTex form.<br />
* A section to discuss and/or illustrate the applications<br />
*# Please double check typos and extra spaces.<br />
<br />
==[[Optimization with absolute values]]==<br />
<br />
* An introduction of the topic<br />
*# Add few sentences on how absolute values convert optimization problem into a nonlinear optimization problem.<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Please add more details to absolute values in nonlinear optimization. (very important!)<br />
* A section to discuss and/or illustrate the applications<br />
*# Inline equations at the beginning of this section are not formatted properly. Please fix the notation for expected return throughout the section.<br />
<br />
==[[Matrix game (LP for game theory)]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# aij are not defined in this section.<br />
* References<br />
*# Please consider linking the references by using this as Wiki template, [[Quantum computing for optimization|https://optimization.cbe.cornell.edu/index.php?title=Quantum_computing_for_optimization]]<br />
<br />
==[[Quasi-Newton methods]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Please ensure that few spaces are kept between the equations and equation numbers.<br />
*# Step 6 of DFP algorithm should use the same variable M as in equation 1.14.<br />
<br />
== [[Markov decision process]] ==<br />
<br />
* An introduction of the topic<br />
*# Please fix typos such as “discreet”.<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# If abbreviations are defined like MDP, use the abbreviations throughout the Wiki.<br />
* References<br />
*# Please consider linking the references by using this as Wiki template, [[Quantum computing for optimization|https://optimization.cbe.cornell.edu/index.php?title=Quantum_computing_for_optimization]]<br />
<br />
==[[Eight step procedures]]==<br />
<br />
* At least one numerical example<br />
*# Please be consistent in the formatting of mathematical notations and equations.<br />
* References<br />
*# Lecture notes may not be a credible reference. Please find the original source.<br />
<br />
==[[Facility location problem]]==<br />
<br />
* At least one numerical example<br />
*# Mention how the formulated problem is coded and solved. No need to provide GAMS code.<br />
* References<br />
*# Please consider linking the references by using this as Wiki template, [[Quantum computing for optimization|https://optimization.cbe.cornell.edu/index.php?title=Quantum_computing_for_optimization]]<br />
<br />
==[[Set covering problem]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Use proper math notations for “greater than equal to”.<br />
* At least one numerical example<br />
*# Since Table 3 provides information on aij required to formulate the constraints, Table 2 serves no purpose and should be removed from the Wiki. Table 3 can be directly generated from Table 1.<br />
*# The numerical example is solved manually without using greedy method nor LP solution method. Please solve this example both by the presented greedy algorithm and the newly added LP-based method and finally compare solutions.<br />
*# Please leave some space between equation and equation number.<br />
<br />
==[[Quadratic assignment problem]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Discuss dynamic programming and cutting plane solution techniques briefly.<br />
* A section to discuss and/or illustrate the applications<br />
*# Please format the equation for definition of yij in the hospital layout subsection.<br />
<br />
==[[Newsvendor problem]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# A math programming formulation of the optimization problem with objective function and constraints is expected for the formulation. Please add any variant of the newsvendor problem along with some operational constraints.<br />
*# A mathematical presentation of the solution technique is expected. Please consider any distribution for R and present a solution technique for that specific problem. <br />
<br />
==[[Mixed-integer cuts]]==<br />
<br />
* A section to discuss and/or illustrate the applications<br />
*# MILP and their solution techniques involving cuts are extremely versatile. Yet, only two sentences are added to describe their applications. Please discuss their applications, preferably real-world applications, in brief. Example Wikis provided on the website could be used as a reference to do so.<br />
<br />
==[[Column generation algorithms]]==<br />
<br />
* An introduction of the topic<br />
*# References at the end of the sentence should be placed after the period.<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Some minor typos/article agreement issues exist “is not partical in real-world”.<br />
*# Referencing subtitle "Methodology" is not a formal way. <br />
<br />
==[[Heuristic algorithms]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Please use proper symbol for "greater than or equal to".<br />
*# Greedy method to solve minimum spanning tree seems to be missing.<br />
<br />
==[[Branch and cut]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Equation in most infeasible branching section is not properly formatted, please fix the same.<br />
*# Step 2 appears abruptly in the algorithm and does not explain much. Please add more information regarding the same.<br />
*# Step 5 contains latex code terms that are not properly formatted. Please fix the same.<br />
*# Fix typos: e.g., repeated “for the current”, men Problem can viewed as partially” ..<br />
<br />
== [[Mixed-integer linear fractional programming (MILFP)]] ==<br />
<br />
* At least one numerical example<br />
*# Please check the index notation in Mass Balance Constraints.<br />
* References<br />
*# Please consider linking the citations to references in the reference list by using this as Wiki template, rather than using website links. [[Quantum computing for optimization|https://optimization.cbe.cornell.edu/index.php?title=Quantum_computing_for_optimization]]<br />
<br />
==[[Convex generalized disjunctive programming (GDP)]]==<br />
<br />
* An introduction of the topic<br />
*# Please refrain from defining the same abbreviations multiple times.<br />
*# Please use abbreviations throughout the page if they have been defined.<br />
* At least one numerical example<br />
*# There is a duplicate figure. <br />
<br />
==[[Fuzzy programming]]==<br />
<br />
* An introduction of the topic<br />
*# References at the end of the sentence should be placed after the period.<br />
* At least one numerical example<br />
*# The numeric example should be before the applications section.<br />
* A section to discuss and/or illustrate the applications<br />
*# Applications of fuzzy programming are quite versatile. Please discuss few of the mentioned applications briefly. The provided example Wikis can be used as a reference to write this section.<br />
* References<br />
*# Please consider linking the references by using this as Wiki template, [[Quantum computing for optimization|https://optimization.cbe.cornell.edu/index.php?title=Quantum_computing_for_optimization]]<br />
<br />
==[[Adaptive robust optimization]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Please check typos such as "Let ''u'' bee a vector".<br />
*# The abbreviation KKT is not previously defined.<br />
<br />
== [[Stochastic gradient descent]] ==<br />
* At least one numerical example<br />
*# Amount of whitespace can be reduced by changing orientation of example dataset by converting it into a table containing 3 rows and 6 columns.<br />
* A section to discuss and/or illustrate the applications<br />
*# Deep learning can become a subsection on its own.<br />
<br />
==[[RMSProp]]==<br />
<br />
* An introduction of the topic<br />
*# References at the end of the sentence should be placed after the period.<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# Please check grammar in this section.<br />
* A section to discuss and/or illustrate the applications<br />
*# The applications section does not contain any discussion on applications. Please mention a few applications of the widely used RMSprop and discuss them briefly.<br />
*# Please check grammar in this section.<br />
* References<br />
*# Please refer to the example Wikis provided to use proper citation style.<br />
*# Please consider linking the references by using this as Wiki template, [[Quantum computing for optimization|https://optimization.cbe.cornell.edu/index.php?title=Quantum_computing_for_optimization]]<br />
<br />
==[[Adam]]==<br />
<br />
* Theory, methodology, and/or algorithmic discussions<br />
*# References at the end of the sentence should be placed after the period.</div>Asa273https://optimization.cbe.cornell.edu/index.php?title=Quantum_computing_for_optimization&diff=1679Quantum computing for optimization2020-11-23T17:22:59Z<p>Asa273: </p>
<hr />
<div>== Introduction ==<br />
<br />
Quantum computing (QC) is the next frontier in computation and has attracted a lot of attention from the scientific community in recent years. QC provides a novel approach to help solve some of the most complex optimization problems while offering an essential speed advantage over classical methods. <ref> M. A. Nielsen and I. L. Chuang, ''Quantum Computation and Quantum Information'' Cambridge University Press, 2010, p. 702.</ref> This is evident from QC techniques like Shor’s algorithm for integer factorization, <ref> P. W. Shor, "Algorithms for quantum computation: discrete logarithms and factoring," presented at the Proceedings 35th Annual Symposium on ''Foundations of Computer Science'', 1994. </ref> and Grover's search algorithm for unstructured databases. <ref> L. K. Grover, [https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.79.325 "Quantum Mechanics Helps in Searching for a Needle in a Haystack]," ''Physical Review Letters'', vol. 79, pp. 325-328, 1997. </ref> Quantum adiabatic algorithms too are efficient optimization strategies that quickly search over the solution space. Quantum computers perform computation by inducing quantum speedups whose scaling far exceeds the capability of the most powerful classical computers. QC’s major applications can be perceived in areas of optimization, machine learning, cryptography, and quantum chemistry. <ref> J. Preskill, [https://ui.adsabs.harvard.edu/abs/2018arXiv180100862P "Quantum Computing in the NISQ era and beyond"] </ref> Despite the contrasting views on QC’s viability and performance, there is no doubt that QC holds great promise to open up a new era of computing. <br />
<br />
<br />
== References ==<br />
<references /></div>Asa273https://optimization.cbe.cornell.edu/index.php?title=Quantum_computing_for_optimization&diff=1677Quantum computing for optimization2020-11-23T17:16:15Z<p>Asa273: Created page with "Quantum computing (QC) is the next frontier in computation and has attracted a lot of attention from the scientific community in recent years. QC provides a novel approach to..."</p>
<hr />
<div>Quantum computing (QC) is the next frontier in computation and has attracted a lot of attention from the scientific community in recent years. QC provides a novel approach to help solve some of the most complex optimization problems while offering an essential speed advantage over classical methods. <ref> M. A. Nielsen and I. L. Chuang, ''Quantum Computation and Quantum Information'' Cambridge University Press, 2010, p. 702.</ref> This is evident from QC techniques like Shor’s algorithm for integer factorization, <ref> P. W. Shor, "Algorithms for quantum computation: discrete logarithms and factoring," presented at the Proceedings 35th Annual Symposium on ''Foundations of Computer Science'', 1994. </ref> and Grover's search algorithm for unstructured databases. <ref> L. K. Grover, [https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.79.325 "Quantum Mechanics Helps in Searching for a Needle in a Haystack]," ''Physical Review Letters'', vol. 79, pp. 325-328, 1997. </ref> Quantum adiabatic algorithms too are efficient optimization strategies that quickly search over the solution space. Quantum computers perform computation by inducing quantum speedups whose scaling far exceeds the capability of the most powerful classical computers. QC’s major applications can be perceived in areas of optimization, machine learning, cryptography, and quantum chemistry. <ref> J. Preskill, [https://ui.adsabs.harvard.edu/abs/2018arXiv180100862P "Quantum Computing in the NISQ era and beyond"] </ref> Despite the contrasting views on QC’s viability and performance, there is no doubt that QC holds great promise to open up a new era of computing. <br />
<br />
<br />
== References ==<br />
<references /></div>Asa273