text:
Not logged in [Login - Register]
 Sciencemadness Discussion Board » Fundamentals » Organic Chemistry » Synthesis of 3-(p-Hydroxyphenyl)-2-Butanone "raspberry ketone" Select A Forum Fundamentals   » Chemistry in General   » Organic Chemistry   » Reagents and Apparatus Acquisition   » Beginnings   » Miscellaneous   » The Wiki Special topics   » Technochemistry   » Energetic Materials   » Biochemistry   » Radiochemistry   » Computational Models and Techniques   » Prepublication Non-chemistry   » Forum Matters   » Legal and Societal Issues   » Detritus   » Test Forum

Pages:  1    3  4
Author: Subject: Synthesis of 3-(p-Hydroxyphenyl)-2-Butanone "raspberry ketone"
Klute
International Hazard

Posts: 1379
Registered: 18-10-2006
Location: France
Member Is Offline

Mood: No Mood

Synthesis of 3-(p-Hydroxyphenyl)-2-Butanone "raspberry ketone"

As a weekend distraction, I'm thinking of trying to synthesise this flavor at home.

HO-Ph-CH(CH3)-CO-CH3

(EDIT: apparently this is a isomer of the so-called "raspberry ketone". See the ohter posts. These two paths are obviously not revelant.)

Two paths came to my mind:

1°- Enolate synthesis: Forming the enolate of MEK with NaOMe, and reacting it with a protected p-halophenol. The phenol would react with the methoxide, and could/would form an ester. I'm not sure on what to use for a protection, maybe reacting the phenolate with BnX or forming another ether..
From the information available, using DMF as a solvant for the alkylation, and either FeSO4 or UV as catalyst. I'm not sure how well the reaction would proceed.

2°- Acetoacetic ester synth of the protected bromophenol, followed by alkylation with MeI of the formed ester with another equivalent of alkoxide at the benzylic carbon, followed by hydrolysis/decarboxylation.

Then of course deprotection of the formed ketone. Would the clivage of an ether with a Lewis acid damadge the ketone?

Any advice, ideas, suggestions? Any other ideas of pathways would be welcome.

[Edited on 27-12-2007 by Klute]
solo
International Hazard

Posts: 3706
Registered: 9-12-2002
Location: Estados Unidos de La Republica Mexicana
Member Is Offline

Mood: ....getting old and drowning in a sea of knowledge

Hydroxybenzaldehydes
Christian Maliverney1 and Michel Mulhauser1
Kirk‑Othmer Encyclopedia of Chemical Technology

Abstract
Among the hydroxybenzaldehydes, only mono-, di- and trihydroxybenzaldehydes are known. Salicylaldehyde (2-hydroxybenzaldehyde) and 4-hydroxybenzaldehyde represent more than 99% of the hydroxybenzaldehydes' market. The physical and chemical properties of hydroxybenzaldehydes are described. 2-Hydroxy and 4-hydroxybenzaldehydes react in a similar manner as phenol toward electrophiles. The aldehyde function can be reduced or oxidized to form a variety of compounds depending on the reagents and conditions used. Hydroxybenzaldehydes undergo the normal reactions of aromatic aldehydes.

Most industrial methods for the manufacture of hydroxybenzaldehydes are based on phenol, but other routes exist, starting from hydroxybenzoic acids, by reduction, or from cresols, by oxidation. Both p-hydroxybenzaldehyde and salicylaldehyde have a low to moderate acute oral toxicity, but salicylaldehyde is, in addition, corrosive toward skin and appreciably irritating to the eyes.

The hydroxybenzaldehydes are used primarily as chemical intermediates to a variety of products. The largest single use of salicylaldehyde is in the manufacture of coumarin. Both are used as intermediates in the synthesis of agrochemicals, pharmaceuticals, fragrances, and in electroplating. Condensation products of salicylaldehyde and diamines have important chelation properties, and have wide use in the stabilization of petroleum products, and in chemical processing, especially as oxidation catalysts. These and other applications to polymer chemistry are described.

Keywords: Hydroxybenzaldehydes; Agricultural chemicals; Disinfectants; Coumarin; Flavors; Fragrances; Salicyladehyde; Electroplating; Pharmaceutical intermediates

[Edited on 25-12-2007 by solo]

Attachment: Hydroxybenzaldehydes.pdf (160kB)

It's better to die on your feet, than live on your knees....Emiliano Zapata.
not_important
International Hazard

Posts: 3873
Registered: 21-7-2006
Member Is Offline

Mood: No Mood

Bunce, R.A., and Reeves, H.D. 1989. Synth. Comm. 19:1109-1118.

Tateiwa, J.-I., Horiuchi, H., Hashimoto, K., Yamauchi, T., and Uemura, S. 1994. Cation-exchanged montmorillonite-catalyzed facile Friedel-crafts alkylation of hydroxy and methoxy aromatics with 4-hydroxybutan-2-one to produce raspberry ketone and some pharmaceutically active compounds. J. Org. Chem. 59:5901-5904.

Halogen isn't going to come off the phenol very easily. This sounds more like the palladium catalysed reactions, you might even be able to get MVK to couple with the halo-phenol, the reduce the alkene which should happen easily as it's a,b to the keto.

[Edited on 25-12-2007 by not_important]
leu
National Hazard

Posts: 368
Registered: 13-10-2005
Member Is Offline

Mood: No Mood

Description of GB2416770

Raspberry ketone (p-hydroxyphenyl-2-butanone) is a key flavour molecule with typical raspberry flavour characteristics and a low odour threshold. Raspberry ketone is one of the most expensive flavour components used in the food industry. Up to $20,000/kg may be paid for the natural compound. Raspberry ketone can be found in raspberries and other fruits (such as peaches, grapes, apples and various berries), vegetables (e.g. rhubarb) and in the bark of tree (e.g. yew, maple and pine). Raspberry ketone can be used in the aroma formulation of, for instance, strawberry, kiwi, cherry and other berries. However none of these fruits are used to obtain the raspberry ketone as the low content of raspberry ketone in these fruits makes the extraction and purification process unprofitable. Raspberry ketone can be produced chemically via the condensation of p hydroxybenzaldehyde with acetone. However, the chemical synthesis of compounds can often result in environmentally unfriendly production processes and in undesirable racemic mixture of the compound of interest (Vandamme and Soetaert 2002; J Chem Techno Biotechnol 77:1323-1332). In raspberries, the synthesis of raspberry ketone is one part of the phenylpropanod pathway. This pathway has been described by Borejszaysocki and Hrazdina (1994). In the first step, coumaryl CoA (which Is present In many plant tissues) is condensed with one malonyl CoA into benzalacetone (p-hydroxyphenylbut 3-enc-2-one). The enzyme catalysing this step is called benzalacetone synthase (BAS). In the second step, the double bond in benzalacetone is reduced, resulting in raspberry ketone (p-hydroxyphenyl-2-butanone). The enzyme catalysing this step is called benzalacetone reductase (BAR), this enzyme requires the presence of NADPH. Benzalacetone synthase (BAS), EC 2.3.1.-., is a member of the polyketide synthase family. Benzalacetone reductase condenses one acetone unit from malonyl CoA with one p-coumaric acid to form benzalacetone. Chalcone synthase (CHS), EC 2.3.1.74, is another member of the polyketide synthase family, which condenses three acetate units from malonyl CoA with one p-coumaric acid to form chalcone. Stilbene synthase (STS), EC 2.3.1.146, is another member of the polyketide synthase family, which condenses three acetate units from malonyl CoA with one p-coumaric acid to form stilbene (Zheng et al 2001). The polyketide synthase family is described in detail in Schroder 1999 (Comprehensive natural products chemistry vol 1: polyketides and other secondary metabolites includingfatty acids and their derivatives [U. Sankawa Ed] pp 749-771). CHS is part of another part of the phenylpropanod pathway, which converts phenylalanine into naringenin chalcone and its derivatives (Weisshaar and Jenkins 1998; Hwang et al 2003). This part of the phenylpropanoid pathway involves the following enzymes: phenylalanne ammonia Iyase (PAL), cinnamate-4-hydroxylase (C4H), 4-coumarate:coenzyme A ligase (4CL) and chalcone synthase (CHS). As a first step phenylalanine Is deamnated to yield cinnamic acid by the action of PAL. Cinnamic acid is hydroxylatcd by C4H to 4-coumaric acid. 4-coumaric acid is activated to 4-coumaryl-coenzymeA (CoA) by the action of 4CL. CHS catalyses the stepwise condensation of three acetate units from malonylCoA with 4-coumaryl CoA to yield nanngenin chalcone (which is a precursor for some flavonoids). Naringenin chalcone is converted to naringenin by chalcone isomerase (CHI) or naringemn chalcone spontaneously converts to naringenn. Evidence for the relation between BAS and CHS is provided by BorejszaWysocki and Hrazdna (1994 and 1996). Borejsza-Wysocki and Hrazdina (1994) show that the timing of BAS activity parallels CHS activity. In addition, Borejsza-Wysock and Hrazdina (1996) show that CHS and BAS co-purify, and seem to react with the same antisera. However, CHS and BAS activity in the same enzyme preparation showed a different response to treatments with, for instance, 2-mercaptoethanol and ethylene glycol. Also, CHS activity and BAS activity showed different induction patterns upon treatment of raspberry cell cultures with yeast extract, suggesting that these enzymes are not one and the same molecule. Soluble enzymes catalysing the reduction of a double bond using NADPH, for example benzalacetone reductase (BAR), are classified by the International Union of Biochemistry and Molecular Biology as belonging to enzymatic class EC 1.3.1.X. For instance, an enzyme annotated as EC 1.3.1. 11 from Arthrobacter sp. was reported to remove a double bond from coumarate (Levi and Weinstein, 1964). However, no gene has been identified in connection to this enzymatic activity. Other enzymes In the enzymatic class EC 1.3.1.X are orotate reductase, 2-hexadecenal reductase, cholestenone 5 alpha-reductase etc. for which genes are known. However, none of these enzymes was reported to have benzalacetone reductase (BAR) activity. It is known from literature that 4-hydroxybenzalacetone can be transformed to raspberry ketone by fungi or yeasts such as Pichia, Saccharomyces, Beauveria, Kloeckera, Aureobasidium, Cladosporium Geotrichum, Mucor and Candida spp. (Fuganti and Zucchi, 1998). However, no gene has been identified in connection to this enzymatic activity. Also, to our knowledge, no such activity has been reported for bacteria, neither gram negative nor gram positive. Attempts to biosynthesise raspberry ketone have been described. Hugueny et al (1995, Boflavour 95 pp 269-273) teach a biotechnological method for producing raspberry ketone. This method comprises culturing a microorganism which has a secondary alcoholdehydrogenase (ADH), such as Candida boidinii, and adding the precursor betulosde to the culture medium. In this cellular environment the secondary ADH dehydrogenatates betuligenol into raspberry ketone. Various studies have been carried out to determine the role of polyketide synthase genes in the production of flavonoids using E cold transformed with a raspberry CHS gene (see Zheng et al 2001; Kumar and Ellis 2003), a Glycyrrhiza echinata CHS gene (Hwang et al, 2003) or a Arabidopsis thaliana CHS gene (Watts et al 2004). However these studies teach the in vitro or in vivo synthesis of naringenin. These studies do not teach the in vivo synthesis of benzalacetone or raspberry ketone. Abe et al (2001) teach the cloning of rhubarb BAS, expression of the gene in E colt, purification of the recombinant BAS protein and the in vitro synthesis of benzalacetone. However this study does not teach the in vivo synthesis of benzalacetone or raspberry ketone. SUMMARY OF THE INVENTION According to a first aspect of the present invention, we provide a host cell comprising a chalcone synthase (CHS) polypeptide sequence and a 4coumarate:CoA 1igase (4CL) sequence in which one or both of the CHS polypeptide sequence and the 4CL sequence is heterologous to thc host cell. Preferably, the CHS polypeptide sequence is derived from one of the following: raspberry, petunia, grape, Medicago sativa, Arabidopsis thaliana, Antirrhinum majus, Zea mais and Petroselinum crispum, preferably a raspberry CHS sequence. Preferably, the CHS sequence is selected from the group consisting of: accession number AF292367, accession number AF400567, accession number X04080, accession number X76892, accession number L02902, accession number AF112086, accession number X0371O, accession number X60204, accession number V01538, a sequence shown in SEQ ID NO: 2, and a sequence having at least 75% sequence homology thereto. Preferably, the 4CL sequence is a tobacco 4CL sequence. Preferably, the 4CL sequence is a sequence having an accession number U50846 or a sequence shown in SEQ ID NO: 3. Preferably, the host cell is transformed with an expression vector encoding the chalcone synthase (CHS) polypeptide sequence and an expression vector encoding the 4-coumarate:CoA ligase (4CL) sequence, or an expression vector encoding both sequences. Preferably, the host cell is a microbial host cell selected from the group consisting of F,scherichia spp, Saccharomyces spp, Pichia spp, Beauveria spp, Candida spp, Aspergillus spp, Bacillus spp, Pseudomonas spp, Hansenula spp, Klayveromyces spp, Schizosaccharomyces spp, Streptomyces spp, Lactococcus spp, Lactobacillus spp, Pediococcus spp, Kloeckera spp, Aureobasidium spp, and Streptococcus spp, preferably an E. colt, preferably strain BL21, or a Saccharomyces cerevisiae, preferably strain YPH 499, or a Bacillus subtilis host cell. Preferably, a polypeptide expressed from the CHS polypeptide sequence has benzal acetone synthase (B AS) acti vity. Preferably, the host cell is capable of producing benzalacetone when supplied with a precursor of benzalacetone, preferably p-coumaric acid or a source of p coumarc acid. Preferably, the host cell has benzalacetone reductase (BAR) activity, preferably inherent benzalacetone reductase (BAR) activity. Preferably, the host cell further comprises a benzalacetone reductase (BAR) sequence, preferably a heterologous BAR sequence, preferably shown as SEQ ID NO: 5. Preferably, the host cell is capable of producing raspberry ketone when supplied with a precursor of raspberry ketone, preferably benzalacetone or a source of benzalacetone. Preferably, the host cell is capable of producing raspberry ketone when supplied with a precursor of raspberry ketone, preferably p-coumaric acid or a source of p-coumaric acid. Preferably, the host cell further comprises a cinnamate-4-hydroxylase (C4H) sequence. Preferably, the host cell Is capable of producing benzalacetone or raspberry ketone, or both, when supplied with cinnamic acid or a source of cinnamic acid. Chemistry is our Covalent Bond solo International Hazard Posts: 3706 Registered: 9-12-2002 Location: Estados Unidos de La Republica Mexicana Member Is Offline Mood: ....getting old and drowning in a sea of knowledge Reference Information Cation-exchanged montmorillonite-catalyzed facile Friedel-crafts alkylation of hydroxy and methoxy aromatics with 4-hydroxybutan-2-one to produce raspberry ketone and some pharmaceutically active compounds. Tateiwa, J.-I., Horiuchi, H., Hashimoto, K., Yamauchi, T., and Uemura, S. J. Org. Chem. 59:5901-5904., 1994 Abstract The Friedel-Crafts alkylation of hydroxy and methoxy aromatics with 4-hydroxybutan-2-one (y- KB) in the presence of a cation-exchanged montmorillonite (Mn+-mont; Mn+ = Z++, N3+, Fe3+, and Zn2+) was investigated. Phenol was C-alkylated regiospecifically with y-KB in the presence of Z1A+-, A13+-, or Fe3+-mont to produce 4-(4-hydroxyphenyl)butan-2-one (raspberry ketone) in 31-35% GLC yield. Anisole, 2-methoxynaphthalene, and 1-methoxynaphthalene were regiospecifically C- alkylated to produce 4-(4-methoxyphenyl)butan-2-one, 4-(2-methoxy-l-naphthyl)butan-2-one (phar- maceutically active), and 4-(4-methoxy-l-naphthyl)butan-2-one, respectively. N3+- and Fe3+-mont were the most effective catalysts in these cases (13-58% isolated yield). y-KB could be used as an alkylating agent instead of the highly toxic 3-buten-2-one (MVK) which also polymerizes easily. Attachment: Cation-Exchanged Montmorillonite-Catalyzed Facile Friedel-Crafts Alkylation of Hydroxy and Methoxy Aromatics with 4-Hydr (553kB) This file has been downloaded 1373 times It's better to die on your feet, than live on your knees....Emiliano Zapata. solo International Hazard Posts: 3706 Registered: 9-12-2002 Location: Estados Unidos de La Republica Mexicana Member Is Offline Mood: ....getting old and drowning in a sea of knowledge Reference Information Amberlyst-15 Catalyzed Addition of Phenols to agr,b.beta-Unsaturated Ketones Richard A. Bunce a; Henry D. Reeves Synthetic Communications Volume 19, Issue 5 & 6 March 1989 , pages 1109 - 1117 Abstract Amberlyst-15 has been used to catalyze regioselective additions of phenols to agr,b.beta-unsaturated ketones in yields of 20-90%. The reaction is superior to the analogous reaction employing concentrated sulfuric acid in affording greater yields and purer products with a minimum of laboratory operations. [Edited on 25-12-2007 by solo] Attachment: Amberlyst-15 Catalyzed Addition of Phenols to agr,b.beta-Unsaturated Ketones.pdf (417kB) This file has been downloaded 1870 times It's better to die on your feet, than live on your knees....Emiliano Zapata. Klute International Hazard Posts: 1379 Registered: 18-10-2006 Location: France Member Is Offline Mood: No Mood Thanks for all thoses articles! I've just realized that there seems to be some confusion in the litterature on the exact nature of the so-called "raspberry ketone": in two of my org.chem books, and in some articles on the net, it is said to be the branched p-hydroxyphenylbutanone, the phenyl ring being attached to the third carbon of the chain, alpha to the carbonyl. See here: Smell Database But in all the articles/patents you guys have kindly provided, it is said to be the straight-chained isomer. To my eyes, the linear isomer 4-(para-hydroxyphenyl)butanone seems easier to synth, especially through the p-hydroxybenzaldehyde pathways. A crossed aldol with acetone is easy and well documented, basic conditions would be more effective here I guess, the benzalacetone should be easy to isolate and purify, and I guess a CTH could reduce the double bond, or NaBH4 even if the carbonyl gets reduced, it could easily be re-oxydized. US4414417 deals with a CTH using Rhodium and Iridium catalysts that yield the saturated ketone; this could be applied to other catalyst/donors. The FC option seems equally interesting, but not possessing any b-hydroxybutanone, it doesn't seem readily obtained from MEK or other accesible reagents. p-hydroxybenzaldehyde could be obtained through a Riemmer-Tiemann as mentionned in the review Solo provided, I remember ready about performing the reaction in alcoholic medium to preveil the para-formylation. I have ~30g of phenol left, so this could be enough on a small scale, though I want to give the o-formylation a try using Mg(OCH3)2/paraformaldehyde a try again. Maybe a bayer-villiger oxydation on benzaldehyde could give workable yields of phenol. I don't want to melt any benzenesulfonic acid with NaOH . Well, I guess I'm going to keep busy for a while thanks for the help! LSD25 Hazard to Others Posts: 239 Registered: 29-11-2007 Member Is Offline Mood: Psychotic (Who said that? I know you're there...) Klute, I just found this whilst looking for zingerone (fuck knows why I was looking for that, but...) http://www.apc.titech.ac.jp/~tikariya/mito/teaching/2005/tex... Seems like a nice, simple route I reckon I could even practice the yeast reduction on the zingerone - although that rhodium catalyst makes ones mouth water eh? Whhhoooppps, that sure didn't work solo International Hazard Posts: 3706 Registered: 9-12-2002 Location: Estados Unidos de La Republica Mexicana Member Is Offline Mood: ....getting old and drowning in a sea of knowledge Reference Information Rheosmin (“Raspberry Ketone”) and Zingerone, and Their Preparation by Crossed Aldol-Catalytic Hydrogenation Sequences LEVERETT R. SMITH THE C H EMICAL EDUCATOR VOL . 1 , N O . 3 Introduction Preparations of the two closely-related natural products rheosmin (“raspberry ketone”, 4-(4'-hydroxyphenyl)- 2-butanone) and zingerone (4-(4'-hydroxy-3'- methoxyphenyl)-2-butanone), are well-suited for the introductory organic laboratory. The crossed-aldol condensation of 4-hydroxybenzaldehyde with acetone gives an adduct (4-(4'-hydroxyphenyl)-3-buten-2-one), which is hydrogenated cleanly over rhodium on alumina to form rheosmin. Condensation of vanillin with acetone gives 4-(4'-hydroxy-3'- methoxyphenyl)-3-buten-2-one, which is hydrogenated to zingerone. The article includes background information on the target compounds and the synthetic methods used, along with experimental procedures and IR and NMR data on the compounds encountered. [Edited on 1-1-2008 by solo] Attachment: Rheosmin (“Raspberr Ketone”) and Zingerone,and Their Preparation.pdf (99kB) This file has been downloaded 1987 times It's better to die on your feet, than live on your knees....Emiliano Zapata. Klute International Hazard Posts: 1379 Registered: 18-10-2006 Location: France Member Is Offline Mood: No Mood Thanks alot for those two last papers, especially your Solo, just what I need. I think i will ratehr try a NaBH4 reduction of the unsaturated ketone though, as I don't plan on aquiring any rhodium catalyst, and Pd/C would surely give the same result as NaBH4, or a mixture of the saturated alcohol and ketone. I might try it with some recylced catalyst at a small scale, as per Solo's document. I will surely try making zingerone first, trying the aldol condensation and see how the reduction goes, I've encountered a few mishabs with the Mg(OMe)2 / (H2CO)n formylation, although the reaction seems to proceed well. Left the acidifyed mixture stir too long, resulting in a f**king polymeric sludge (excess paraformaldehdye). It's just a lot of work, along with the preparation and drying of the reagents. Does seem more interesting than the Riemmer Tiemann though. pantone159 International Hazard Posts: 523 Registered: 27-6-2006 Location: Austin, TX, USA Member Is Offline Mood: desperate for shade Thanks also to solo for the last paper... Also thanks for pointing out 'The Chemical Educator', a journal that I wasn't aware of. Perhaps this is akin to the Journal of Chemical Education(?) which I like a lot. Klute - Let us know how the NaBH4 reduction goes, that would be easier for me to try then the hydrogenation. stoichiometric_steve International Hazard Posts: 681 Registered: 14-12-2005 Member Is Offline Mood: satyric klute: Pd/C-CTH does generally NOT reduce carbonyl functions. Klute International Hazard Posts: 1379 Registered: 18-10-2006 Location: France Member Is Offline Mood: No Mood From the document Solo has just posted: "Literature reports appear of palladium and Raney nickel giving significant over-hydrogenation to give alcohols as byproducts, in 15–20% yield, which complicates cleanup and isolation of pure ketone products [30, 36, 47]. 30. Mannich, C.; Merz, K. W. Archiv d. Pharm. 1927, 265, 15. 36. Pabst, A.; Barron, D.; Adda, J.; Schreiber, P. Phytochemistry 1990, 29, 3853. 47. Banno, K.; Mukaiyama, T. Bull. Chem. Soc. Japan 1976, 49, 1453." I might try a microscale experiment with recycled Pd/C, both by CTH and catalytic hydrogenation as per the article, if I have enough time. But if NaBH4 reduction works as cleanly and effeciently as I hope it will, and oxydation with either H2O2/Fe3+ or some HOCl source works nicely, it could come out cheaper/more practical than getting some Rh/Alumina, of which I won't have any immediate use elsewhere. Klute International Hazard Posts: 1379 Registered: 18-10-2006 Location: France Member Is Offline Mood: No Mood Thanks to Nicodem, who kindly retreived European Journal of Organic Chemistry 9,(2000) 1793-1797, dealing with the use of NaBH4/CoCl2 system in either MeOH or aq. medium for reduction of 4 unsaturated ketone, including benzylideneacetone, the unsubstitued derivative of the two unsaturated ketones mentionned further up, to afford either: -the unsaturated alcohol by using straight NaBH4 in protic medium -the saturated ketone by using NaBH4/CoCl2, giving 86% of 1-phenylbutan3-one when using a Sub/NABH4/CoCl2 ratio of 1/3.5/3 -the saturated alcohol, by doing a two-step one-pot procedure, first reducing the carbonyl then the double bond, or vice versa. So this really is a key article for this synth, no need of catalytic hydrogenations, or multiple steps to obtain the ketone. Aldol, reduction, voilà. Mild conditions, easy workup. I will try out the zingerone synthesis as soon as I get my vanillin, and then start working on get that para-hydroxybenzaldehyde... Any ideas apart from the Riemmer Tiemann, which isn't really para-selective, and would yield o mixture of o- and p-isomers? BTW, NiCl2 can be used aswell with similar results. I will also report back on the Mg(OMe)2/(CH2O)n formylation once everything is done. EDIT: I read the wrong colum in the tables, actually the best yield of the 1-phenylbutan-3-one is 86%, when using a solution of Sodium Dodecylsulfate.. [Edited on 7-1-2008 by Klute] UnintentionalChaos International Hazard Posts: 1454 Registered: 9-12-2006 Location: Mars Member Is Offline Mood: Nucleophilic I don't know about purity, but to get some vanillin on the cheap, go buy the cheapest bottle of clear artificial vanilla extract that you can (essentially containing vanillin, ethanol, and water) and place it in a flask with air excluded (such as by a piece of aluminum foil with a small hole in it) and heat until ethanol stops boiling off (I did this a looooong time ago before I had much experience or a decent thermometer and remember that the solution suddenly changed boiling pattern when this happens..I was also checking the flammability of the vapors). You may have a second phase seperate. This is liquid vanillin or perhaps liquid vanillin with water dissolved in it (mp. vanillin 81-83C). Add water and heat to dissolve if this occurs. Chill the solution (which may be a pale amber color from oxidation/polymerization products. Using aluminum foil and allowing water/alcohol vapor to form a protective atmosphere minimizes this) Vanillin crystallizes out as long, thin, pale yellow/cream colored needles. I got 13g from an 8oz bottle ($7 US) I'm sure most here can improve on this method though.

[Edited on 1-6-08 by UnintentionalChaos]

Department of Redundancy Department - Now with paperwork!

'In organic synthesis, we call decomposition products "crap", however this is not a IUPAC approved nomenclature.' -Nicodem
Klute
International Hazard

Posts: 1379
Registered: 18-10-2006
Location: France
Member Is Offline

Mood: No Mood

UnintentionalChaos, thanks for the advice, but I think I will be getting my vanillin from a flavoring supplier, which offers it in >99% purity for a reasonable price. But I might give it a try with the flavorings at the local supermarket, as the minium is 500g, and I wouldn't know what to do with so much vanillin, even if using it for baking cakes and stuff

As I only screened quickly through the article yesterday, I mixed up some entries, and the fact that the only way of obtaining good yields of pure phenylbutanone is to use a 0.1mol.L solution of Sodium Dodecylsulfate (SDS), which I don't currently have at hand, as a reagent anyway. Apparently, Tetrabutylammonium Bromide can't be a good substitute as it doesn't form micellar emuslions, which apparently "protect" the ketone from reduction by BH4-; it's the formed H2 which is the true reducing agent, catalysed by the formed metal boride. I could try using benzylalkylammonium chlorides, in C10-C12, which would form micellar emuslions and might act similarily. It's starnge as they have a few entries were using MeOH and H2O as solvants give 77% et 51% yield respectively, but latter state that:

"The preparation of pure product 3c [1-PhButanone] was not possible in either MeOH or water, and only use of aqueous solutions of SDS afforded it in good yield (entry 10). It seems that this surfactant ‘‘protects’’ the micellar-bound substrate
from attack by the reactive anion BH4 –, the main reduction
pathway being, therefore, the one carried out by H2."

I guess the product is contaminated by saturated alcohol, and that the 2 must be hard to seperate. A light oxydation could convert any over-reduced material back to the ketone, but could also make more impurities, and give a complex mixture of products. Let's try it one pot.
So if the benzalkonium (pool supply) doesn't work out nicely, I was thinking about generating before-hand the metal boride with stoechimetric amounts of borohydride and the chloride, in the appropriate solvant, and then adding the substrate and performing a atmospheric catalytic hydrogenation. Wouldn't it basicly proceed the same way as in-situ formed H2? I think it is molecular hydrogen that is evolved and not nascent, but don't take my word on this. Can anyone can help me out here? This way, no need of using expensive Rhodium catalyst.

EDIT:I've been kindly given ~30g of reagent-grade vanillin, so I will be able to perform the aldol condensation this weekend.
I've decided on trying a simple atmospheric catalytic hydrogenation with preformed CoB catlyst (from CoCl2 and stoechiometric NaBH4), as I've realized I've only got a couple grams of CoCl2 and no NiCl2... We will see how it turns out. I'm still undecided concerning the amount of catalyst to use... Any advice would be welcome.

[Edited on 10-1-2008 by Klute]
Klute
International Hazard

Posts: 1379
Registered: 18-10-2006
Location: France
Member Is Offline

Mood: No Mood

Solo kindly retreived two more article on the catalytic hydrogenation of unsaturated ketones:

Colloidal nickel boride on rare earth oxides for hydrogenation of olefins
Yu-Lin Jiang, Xue-Yun Wei, Shou-Ping Tang and Liu-Bin Yuan
Catalysis Letters; 34, (1995) 19-22

This deals with the use of colloidal NiB catalyst, mixed with rare earth oxides in some cases, to afford a highly active catalyst, prepared from the metal salt, and alcoholic NaBH4 in presence of PEG. The hydrogenation of p-hydroxyphenylbut-3-en-2-one to Rheosmin "raspberry ketone" is covered. The preperation of the "simple" catalyt is straight forward. They claim a 96% isolated yield of rheosmin when using Ni2B, in 170min, and the hydrogen uptake rate and thus reaction is much quicker when the catalyst is made as described with PEG and Nd2O3.
Another particluary interesting thing is that they compared the activity of this catalyst with Pd/C, and claim a 96% isolated yield of Rheosmin in 160min! This is pretty contradictory with the Chem.Educ. article.
At first reflexion, I would rather trust the Chem. Educ. article, as the reactions were reviewed for use in academic labs by students, although it is not explicity claimed that the Pd/C hydrogenation was. But then again, when presenting a new catalyst, the authors of the Cat. Today would have highlighted the strong superiority of their catalyst towards product isolation if they had obtained bad yields when using Pd/C. Although dishonest, claiming higher yields with the object of their article would seem more logical than claiming high yields (although longer reaction times) with such a widely used catalyst. In any case, this inspires me at trying it.
The other good news is that with both catalyst atmospheric hydrogenation seems to give very good yields, so no need of pressurized hydrogen.

Selective hydrogenation of 4-(6-methoxy-2-naphtyl)-3-buten-2-one to Nabumetone®
Nicoletta Ravasio, Federica Zaccheria, Pietro Allegrini and Mauro Ercoli
Catalysis Today, Volume 121, Issues 1-2, 15 March 2007, Pages 2-5

This article describs the use of reuseable, easily prepared SiO2-supported Cu catalyst for hydrogenation of unsaturated ketones.
Highly-loaded catalyst promotes complete reduction to the saturated alcohol. But 8% Cu/SiO2 apparently gives good yields when reducing the titled compound, derivative of benzalacetone were the phenyl ring is replaced by a substitued naphtyl ring. Both compounds should behave similarily I guess.
No isolated yields are mentionned, only high selectivities, which can be unclear towards to true efficienty of the reaction. High selectivites but low conversions can be usefull for industrials when the substarte can easily be recycled.
Once again, >98% selectivites are mentionned for 5% Pd/C. It is also mentionned that adding ~5% K2CO3 to a Pd/C hydrogenation minimizes the formation of the saturated alcohol, which is a good find.
Even if the catalyst can easily be prepared before introduction of the substarte, the problem is that changes in the quality of the silica can cause drastic changes in the products, especially with aliphatic unsaturated ketones. Conjugated aromatic unsaturated ketones appear more resitant to this change in chemioselectivity. But as I personally make my silica gel from soduim silicate solution and HCl, the quality varies enormously, and I don't really have means of controlling porosity, surface/gram and other caracteristics that seem to play a important role here.
But the simplicity of the procedure still makes this a interesting experiment. Cu-based catalyst are said to be more selective to carbonyl reduction than double-bonds, and if reprocuble results can be obtained with home-made catalyst, this could have other applications for different compounds, and thus make cheap, available hydrogenation catalyts for the home chemist, compared to other mostly expensive ones.

I'm finding this subject more and more interesting. What started as a simple weekend-occupation subject is turning into my major center of interest actually. I'm very lucky that there some interesting litterature on the subject, and incredibly helpfull members here that provided these articles as I can't access any libraries at the moment. Again, thanks a million.
LSD25
Hazard to Others

Posts: 239
Registered: 29-11-2007
Member Is Offline

Mood: Psychotic (Who said that? I know you're there...)

Solo,

Thanks for J.Chem Ed article - I'd seen the abstract to that before and have long wanted to read it....

Whhhoooppps, that sure didn't work
Klute
International Hazard

Posts: 1379
Registered: 18-10-2006
Location: France
Member Is Offline

Mood: No Mood

Synthesis of 1-(4-hydroxy-3-methoxyphenyl)but-1-en-3-one by basic crossed-aldol condensation of vanillin and acetone.

Finally started this very easy reaction. I just scaled up 20x the L. R. SMITHChem. Educ. 1(3) "short" synthesis, and plan on leaving it 48h at room temp.

Synthesis

5g (33 mmol) of reagent-grade vanillin [Picture 1] were weighed, and dissolved in 20mL (~280 mmol) of technical acetone, giving a totally limpid solution, in a 100mL capped bottle containing a stir bar [picture 2].
2g (50 mmol) of technical NaOH were dissolved in 20mL dH2O (10% w/v, 2.5 mol/L), and the warm solution was cooled under a stream of cold water. Once at room temp, the solution was slowly poored into the acetone solution with steady stirring. This immediately caused the solution to turn yellow and warm up somewhat [picture 3]. The color gradually darkened, becoming dark orange after 5min, and the bottle cooled down gently [picture 4]. This will be stirred at RT for 48h, then worked up as per the article: addition of 100mL of 3M HCl, filteration and washing of the resulting solids, recrystallization with EtOH/H2O, and caracterisation of the product.
This unsaturated ketone will then be hydrogenated over 10% Pd/C to the corresponding ketone, 1-(4-hydroxy-3-methoxyphenyl)butan-3-one, or Zingerone. Hydrogenation over preformed Co2B might also be tried.

Picture 1

Picture 2

Picture 3

Picture 4

Sorry if the pics are big, I didn't find how to just post a "icon" to the large pictures for display on another window. If this causes too much problems for uploading this thread, I'll diminish the size...

EDIT:
12h later, the mixture is now dark cherry red. I will post a picture tomorow as I don't have the time right now.

[Edited on 17-1-2008 by Klute]
Klute
International Hazard

Posts: 1379
Registered: 18-10-2006
Location: France
Member Is Offline

Mood: No Mood

Synthesis of 1-(4-hydroxy-3-methoxyphenyl)but-1-en-3-one - Continued

After 48h stirring at RT [Picture 1], the dark red/black mixture was transfered to a 250mL beaker, and 100mL 10% HCl poored in with magnetic stirring. A black oil crashes out, giving a black heterogenous mixture [Picture 2]. After 2min stirring, a fine yellow solid started precipitating [Picture 3]. Black droplets were still present at the bottom.
After another 5min stirring , the suspension was filtered, care taken of decanting the heavy, dark granules present at the bottom of the beaker. The fine suspension gave a greenish crystalline powder [Picture 4], which was washed with a little water, dried with suction on the buchner, and transfered to a small beaker.
The dark crystalline granules were equally washed, filtered and dried [Picture 5]. They did not agglomerate, and were very easy to collect in a seperate beaker.

The two crops were recrystallized with hot 10mL EtOH, followed by gradual addition of 5-8mL water, and left to cool. The first crop gave a clear, greenish solution, the second gave a dark brown, but limpid solution. The first crop crystallized very quickly. It was filtered, briefly washed with water, and dried on the buchner [Picture 6], giving beautifull canary-yellow crystalline flakes [Picture 7] .
The second crop crysatllized much less, not enough water had been added. The formed crystals were filtered, the filtrate replaced in the beaker, and the cake sparingly washed with water and dried. The crystals formed, although larger than the first crop, were of a more darker yellow [Picture 8].
The two crops of crystals were left to dry in the dessicator, and finally weighed exactly 2.53g each!

The final weight was 5.06g (26.35 mmol), representing a yield of 79.86%. Not bad.

Picture 1

Picture 2

Picture 3

Picture 4

Picture 5

Picture 6

Picture 7

Picture 8

Hydrogenation will hopefully be performed next weekend.
tinydantzler
Harmless

Posts: 1
Registered: 20-1-2008
Member Is Offline

Mood: No Mood

I was wondering if someone could help me out with something regarding this synthesis of zingerone.

I am currently in a beginner-ish orgo chem lab in college, and I need to propose a 3 step synthesis of a compound of some interest. As far as I can tell, the synthesis of zingerone from vanillin is only a 2 step (the vanillin and acetone with NaOH and the hydrogenation), and I'm having trouble coming up with a possible third step either at the beginning or end.

I mean, I can sort of see some compounds I could possibly synthesize vanillin out of, but they seem to be unimportant things that would not be readily purchasable.

I read that zingerone is produced by heating gingerol through a retro aldol reaction. Now, mind me if I say something stupefying as I do not have much practical lab experience, but would an aldol reaction of zingerone and what appears would be an aldehyde be at all feasible?

If anyone could help out, I'd really appreciate it. I have a backup plan if I cannot figure something out with zingerone, but this seems more interesting.
Klute
International Hazard

Posts: 1379
Registered: 18-10-2006
Location: France
Member Is Offline

Mood: No Mood

You could make the vanillin from eugenol, that's a common academic synthesis IIRC, using KMnO4. I'll have a look to see if I can't find a protocol at home. Or there some news ways of making vanillin from lignin.
Maybe you could reduce the unsaturated ketone all the way to the saturated alcohol (NaBH4/CoCl2 2 steps-one pot, see the article mentionned earlier in the thread, or better LiAlH4 if they let you handle that) and then oxydize to the saturated ketone.

You could try the rheosmin synthesis, making the p-hydroxybenzaldehyde, although I haven't found a practical way with the chems I can acces for now. It seems the Riemmer Tiemann formylation would essentially yield salicylaldehyde, with only small amouts of p-isomer.

Good luck, please keep us posted on what you decide on doing, and how it goes.
Nicodem
Super Moderator

Posts: 4229
Registered: 28-12-2004
Member Is Offline

Mood: No Mood

@Tinydantzler: Vanillin can also be done by formylating guiacol (2-methoxyphenol) - a cheap and readily available chemical. This can be done by the Reimer Tiemann reaction in the presence of cyclodextrin or tertiary amines (they change the regioselectivity of the reaction thus allowing for the para formylation). Other published methods include the condensation with glyoxalic acid in basic media following by the oxidation of the intermediate mandelic acid to vanillin (but these are two steps). One Japonese patent also describes the Vilsmeier-Haack formylation of guiacol using DMF/POCl3 at 120°C. This last is probably the most suitable for lab scale.

@Klute: Nice work.

Edit: Wrote glycolic acid instead of glyoxalic...

[Edited on 22/1/2008 by Nicodem]
LSD25
Hazard to Others

Posts: 239
Registered: 29-11-2007
Member Is Offline

Mood: Psychotic (Who said that? I know you're there...)

Or you could oxidise the ketone to the cinnamic acid... Ferulic acid:

http://en.wikipedia.org/wiki/Ferulic_acid

Alternatively, I think Solo (here or elsewhere) came up with a 1-step procedure for benzaldehyde from phenylalanine - this might hold true for tyrosine (p-hydroxyphenylalanine) then you have the p-hydroxybenzaldehyde. From that rheosmin synthesis could be acheived in the remaining two steps.

If yields ain't important - the Strecker degradation of tyrosine with glyoxal or potassium peroxodisulfate:

Will give crap yields of the benzaldehyde, but like I said, if yield ain't important. If however you use diazomethane some very interesting methyl ketones might result.

Whhhoooppps, that sure didn't work
Klute
International Hazard

Posts: 1379
Registered: 18-10-2006
Location: France
Member Is Offline

Mood: No Mood

Nicodem: does that tertiary amine trick work in general, or is this only related to vanilin? I don't remember ready about this before, IIRC the Riemmer Tiemann review (haven't got the ref on hand, but it was made available here) doesn't mention it, but I haven't got the document at hand so can't confirm this. If you've got a ref or two, I'd be delighted to give them a look.

LSD25, smart idea from the tyrosine, but indeed seperating the vast amount of byproducts would be time-costly, and for minimal yields. But both products (tyrosine and S2O82-) are pretty available. I'll have a look for Solo's idea, or ask him directly if I can't find anything.
Pages:  1    3  4

 Sciencemadness Discussion Board » Fundamentals » Organic Chemistry » Synthesis of 3-(p-Hydroxyphenyl)-2-Butanone "raspberry ketone" Select A Forum Fundamentals   » Chemistry in General   » Organic Chemistry   » Reagents and Apparatus Acquisition   » Beginnings   » Miscellaneous   » The Wiki Special topics   » Technochemistry   » Energetic Materials   » Biochemistry   » Radiochemistry   » Computational Models and Techniques   » Prepublication Non-chemistry   » Forum Matters   » Legal and Societal Issues   » Detritus   » Test Forum


text:
# Hausdorff spaces and separated maps.

Since the definitions for a Hausdorff space and for a separated map is so similar, I wondered about the implications between them.

Suppose $X$ is a Hausdorff space, and we have a map $f:X \rightarrow Y$ to some topological space $Y$. So assuming that for two $x_1 \neq x_2 \in X$ we have that $f(x_1) = f(x_2)$, we know from the definition of a Hausdorff space that $f$ is separated.

Now onto the converse. Assuming that $f$ is separated. The Hausdorff condition on $X$ holds for all $x_1 \neq x_2 \in X$ when $f(x_1) = f(x_2)$, but since it's dependent on $f(x_1) = f(x_2)$ we cannot guarantee that the condition holds for all points $x_1 \neq x_2 \in X$. Is this correct?

Edit: Here's the definition of a separated map: A continuous map $f:X \rightarrow Y$ is called separated if any two points $x_1 \neq x_2 \in X$ with $f(x_1) = f(x_2)$ can be separated in the sense that there exists open sets $U_1, U_2 \subseteq X$ such that $x_1 \in U_1$, $x_2 \in U_2$ and $U_1 \cap U_2 = \emptyset$

• Hello, what is the definition of a separapled map?
– Paul
May 20, 2016 at 12:34
• @Paul I edited my post to include the definition. May 20, 2016 at 12:45

The notion of separated map is the relative version of the notion of a Hausdorff space. By relative one means that it's a statement about the fibers of a map $$f\colon X\rightarrow Y$$.
A continuous map $$f\colon X\rightarrow Y$$ is separated iff all fibers $$f^{-1}(y)$$ are Hausdorff topological spaces for the induced topology on $$f^{-1}(y)$$. In particular, $$X$$ is Hausdorff iff the continuous map from $$X$$ into the one-point topological space is separated.
• Yes. You proved that any continuous map defined on a Hausdorff space is separated, and you indicated that the existence of a separated map $f\colon X\rightarrow Y$ does not imply that $X$ is Hausdorff. Indeed, take any nonHausdorff $X$. Then the identity map on $X$ is separated. May 20, 2016 at 13:07
• Fibers Hausdorff under subspace topology does not imply separated. Consider $f : \{a,b,c\} \to \{0,1\}, a \mapsto 0, b \mapsto 0, c \mapsto 1$ where open sets of $\{a,b,c\}$ are subsets containing $c$ and $\{0,1\}$ has the indiscrete topology. Then $f^{-1}(0) = \{a,b\}$ is Hausdorff under subspace topology, as is $f^{-1}(1)$. But $(a,b)$ is in the closure of the diagonal in $\{a,b,c\}\times_{f}\{a,b,c\}$ and not in the diagonal. Hausdorff should be replaced with relatively Hausdorff to fix this. Apr 17, 2020 at 22:20

format: plain


text:
# Lecture 24: Linear Programming and Two-Person Games

Flash and JavaScript are required for this feature.

## Description

This lecture focuses on several topics that are specific parts of optimization. These include linear programming (LP), the max-flow min-cut theorem, two-person zero-sum games, and duality.

## Summary

Linear program: Minimize cost subject to $$Ax = b$$ and $$x\geq 0$$
Inequalities make the problem piecewise linear.
Simplex method reduces cost from corner point to corner point.
Dual linear program is a maximization: Max = Min!
Game: $$X$$ chooses rows of payoff matrix, $$Y$$ chooses columns.

Related sections in textbook: VI.2–VI.3

Instructor: Prof. Gilbert Strang

The following content is provided under a Creative Commons license. Your support will help MIT OpenCourseWare continue to offer high-quality educational resources for free. To make a donation or to view additional materials from hundreds of MIT courses, visit MIT OpenCourseWare at ocw.mit.edu.

GILBERT STRANG: OK. Let me just say our next topic, moving really toward machine learning, would be the last section of chapter 6 about stochastic gradient descent. I think Professor Sra from computer science, if he is able, he will take the class Friday and tell us about SGDs, Stochastic Gradient Descent, critical algorithm. I mean that, at a quick look, stochastic gradient descent does smaller batches at a time, so it's computationally faster than pure gradient descent. But also, stochastic gradient descent is able to solve probabilistic problems where you're trying to minimize an expected value instead of a function.

Anyway, it's an important thing. Actually, there is a lecture at 2:00 in neuroscience about the gradient descent algorithms. And then Professor Boyd is speaking here at 4:30 this afternoon. It's overwhelming.

So I'm going to talk today about several topics that are specific parts of optimization. Linear programming is a very famous part of optimization. I don't know if you've met it. I think it's worth knowing what the inputs are and what's the key fact about linear programming. And, of course, also, what are the algorithms.

That's usually what we want to know. What's the problem? What are the results, the mathematical results? And what are the computational tools? Yes, so that's very established. Max-flow min-cut is one specific linear programming that I think maybe would serve as the best example.

And then two-person games, have you met those? So would you know what the rules are in a two-person zero-sum game? In game theory, those are the ones that are clear-- everything's well-established there. And, in fact, they're equivalent to a linear program. So that's why those two are coming in today.

And then the key fact about two-person games and about linear programming is duality. So if there's any word on that board, it's the one in capital letters that has math content. I'm just going to start with linear programming and then move on.

So what's a linear program? It's we're optimizing a linear cost function. So we're minimizing the cost c transpose x. So that vector x is the unknown that we're looking for, and this vector c is the cost vector. So that is c1 x1 plus, plus cn xn.

So you can see why it's called linear programming. The cost is linear. The constraints are also linear. So the constraints on x are a set of linear equations. Of course, I'm not thinking of A as being a square invertible matrix. No way. If it were, that would tell us what x had to be and our problem would be over.

We have n unknowns. This is m by n, of course. x is n by 1. That's our unknown vector. And I'm thinking that m would be smaller than n.

But we do have constraints, and now comes the thing that makes linear programming not actually linear. And that's the constraint x greater or equal to 0. And I've written that as a vector but that means x1 greater or equal to 0, on to xn greater or equal to 0. So it's a vector inequality.

So we have minimizing a very simple function with pretty straightforward constraints but inequality constraints. So the set of-- these two together are the constraints. And in linear algebra-- in linear programming language this is called a feasible set of x's. It's the constraint set, capital K in the notes.

So let me draw a picture to show-- or maybe I'll just ask. How many of you are already familiar with linear programming? Oh, quite a lot. So I won't belabor the point. But let me just draw a picture.

So my picture will be just here. So that's n equals 3. So this is the x1, x2, x3 space. And x greater or equal to 0 means what? It means that I'm in this 1/8 of this space, right? It's the non-negative-- well, I would say quadrant but I really should say octant because it's 1/8 of the full 3D space.

So I'm in here. And then maybe I have m as maybe just one constraint. So let me take the cost to be, say, x1 plus 2 x2 plus 5 x3, say. And the constraint, I'm just going to have one equation-- x1 plus x2. Let me make it easy, make that constraint an easy one to-- so this is what we want to minimize. And that's what we have to satisfy, as well as x greater or equal to 0.

So that's a plane. One equation gives us a plane in R3. The plane would go through-- would hit the axes at 3, 0, 0. And so the min-- the point has to lie on that plane. And it has to lie in the octant, so that plane is chopped off to be a triangle. This is a good visualization of linear programming.

And what's the conclusion? Well, our cost is linear. So the result is that one of these three corners is the winner. It could happen. It could happen that maybe I have equal values on those two corners, and therefore all the way along would be also winners.

But when I have a linear function, it's a maximum at the ends. And these are the ends, those three corners. So 3, 0, 0, 0, 3, 0, or 0, 0, 3 are the three corners, and one of those is the winner and the problem is solved.

And, in fact, for this case, since I'm minimizing, I guess it would be that corner that wins. So let me give it a star, not an x. Yes. 3, 0, 0 because that-- oh. No, that's 3. So the value turned out to be 3 at the point 3, 0, 0. And that's x star. Good. Good, good, good.

What more do I want to do, I said? Yes.

AUDIENCE: Shouldn't it be at point 0, 0, 3?

GILBERT STRANG: Should it be-- oh, no. 0, 0, 3 would have x3 is 3. That's fine. It gives us a chance, I think. That would give me a cost of 15. This would give me a cost of 6, and that would give me a cost of 3. Yes.

It's obvious that if we could enumerate all the corners, we would have a super fast way to get the answer. But the trouble is, of course, that for large values of m and n, there are exponentially many corners, and we don't want to see them all. So that's what makes linear programming take time and need ideas.

So, for algorithms, there are two types of algorithms, two types of codes that solve these. The older, well-established ones are the-- so one way is the simplex method, which finds a corner. We know the optimum one of the corners. So it will find one corner, and it will go to the next corner.

So if it starts at one of these corners, it will travel along an edge that lowers the cost. And it has to stop at the end because it's linear. The cost will keep going down and going down until it bumps into the end point, and then it can't go further. And then we would, from that next corner, we would go to the next corner.

Each time, it's like steepest descent on the edges. From the first corner, we go the steepest way till we can't go further, we've hit another corner. And we recompute the linear algebra, find which direction is steepest from there.

So that's the idea of the simplex method, which was invented by Dantzig. And the algebra is not going to be in today's lecture but it's straightforward. Well, people have to optimize it because that's a highly frequently used method. Yes.

But then, about 20 years later maybe, or 30, I remember going to a lecture in downtown Boston by Karmarkar. So I have to put his name down-- Karmarkar. And he was in The New York Times, all the newspapers, so it was a big deal.

He had an alternative algorithm. And the exact algorithm he proposed hasn't survived until today but the idea has. And the idea was to go to travel inside the feasible set and not around the edges. So his idea-- because in here, would maybe travel down near that edge, start again, travel again. So it's steepest descent in the constraint set, the feasible set. And you can use calculus and this idea.

So this is interior point method. So I'll just use the word interior. That's telling us that we're inside the feasible set. We don't hit, come all the way to the boundary intentionally, because we want room to move, and to find derivatives, and to use Newton's method to minimize.

You choose a search direction, just as all of optimization does. And in that search direction, you track it and you stop before you bump into the edge of the feasible set. And then you compute derivatives again. So you can use calculus.

And it's a method that-- it's an idea that-- the interior idea came before Karmarkar. But he got super publicity, so it really got attention, got new thinking. And new ideas came partly from people at MIT.

And these two are now still locked in competition. One hasn't beaten the other in all problems. So linear programming is here. But then, for nonlinear programming, quadratic programming, where the cost is quadratic, nonlinear programming, semi-definite programming-- that's where you have a matrix unknown and matrix constraints-- those are all-- the more complicated you get, the more it tends to be interior point methods.

That's a summary of linear programming. Now I'd like to give an example. And then I haven't told you the main-- well, let me tell you the main fact about duality. This is really-- and I'll write that maybe here next to it.

So duality is there's a dual program, a dual LP. And that dual is going to do a maximum instead of a minimum And the cost is going to involve the b from the primal problem. So this is now called the primal problem, and this is its dual.

So they're twin problems. They use the same data but quite differently. It's like transposing things. So let's call it the unknown y. So for y1 to ym, I guess, because b, the right-hand side over here, is m by 1. So that's maximize that subject to-- what are the constraints?

Well, the cost function over here, c, the cost vector, goes into the constraints. And I think the greater or equal sign probably becomes a less or equal to sign. The A gets transposed. I think that's probably the constraint in the dual. And it happens it doesn't need y. We don't have y greater or equal to 0 over here.

So that's a dual problem. It has a linear cost. It has linear inequality constraints. It can be solved by the simplex method. You could choose whether you solve that one or this one, because if you solve one, you solve the other. The two are closely connected and that's the key idea of duality.

So maybe I'll put the idea of, first of all, a weak duality. Which says that this quantity that we're trying to maximize-- we're getting it as large as possible-- is always less or equal to any c transpose x. This is for any feasible, allowed-- any x and y that satisfy the constraints. Remember, feasible means satisfies the constraints.

So, in other words, this problem, this maximization problem, you're trying to push this up. The minimization problem, you're trying to pull this down. And it's easier to show that the one, the b transpose-- it's easier to show that inequality. Let's do that.

So b transpose y proof. It should be a one-line proof. So b transpose y-- what do I do? So b transpose y well, I look over here. That's where b shows up.

That's x transpose A transpose y, because b is Ax. I'm feasible, so my b is Ax. And for any x-- this is for this is for any x that b is going to be Ax. So am I good so far?

And now what do I do? Now I look here. I see A transpose y sitting right in front of me. So I say, well, OK, less or equal to. And I guess I'm done.

A transpose y is less or equal to c. So I have x transpose c, c transpose x. So this equals this, less or equal that. I've got it. Weak duality is just put together the requirements on x and y and you have it.

But was this important? If the mathematics is right, everything has to have its place, play its role. And so what's the role of x greater or equal to 0 there? Why do we need x-- If we just even think of n equal 1, just a number, where do we use the fact that x is greater or equal to 0? Do we use it?

This looks so smooth, because A transpose y-- I'll write that as x transpose c for the moment, just so your eye says that's the same x transpose, and the A transpose y is less or equal to c. Where is x greater or equal to 0 coming in?

AUDIENCE: [INAUDIBLE].

GILBERT STRANG: Yes.

AUDIENCE: Like above. It's from the that.

GILBERT STRANG: Yes, that's true. But I want to see-- so here's my point. The fact that A transpose y is less or equal to c, that's fine. Highly important. But if x was negative, it would be the other way. You would go the other way and you wouldn't have what you want.

So we really do use the fact that x is greater or equal to 0 to say that I have this less or equal this. And then I multiply by something positive and then I still have less or equal. OK, good. So the math is right. Everything does its part.

And then, of course, the beautiful result, the important result is that there is strong duality, just called duality, which is that at the maximum-- now this is not for any x and y but this is for-- this is going to be for x y star, the winner, and x star, the winner-- equality holds. So that's duality. The maximum in the dual problem is the same as the minimum in the primal problem. The two have met. There is no duality gap.

In some cooked up nonlinear problems, there could be a gap between the maximum and the minimum, but you hope not. And here the big theorem is not. They're equal. You push this up, push that down.

Another way to say that duality is that this is pushing that up at some max-- I could write that as a maximum of a minimum equaling a minimum of a maximum, if I wanted. So the duality in linear programming was the same as von Neumann's minimax theorem. And his theorem applied to two-person games.

So the key math result is duality for linear programming, and it's going to be-- you'll see the same thing happening for two-person games. And it's a minimax theorem, or a saddle point. Or it's just things come out right. Yes.

So just to mention that mathematical programming, of course, includes much more difficult problems. This is linear programming. That problem, as you see, has a beautiful, simple theory. And the paying attention is paying attention to the algorithm, because you've got two important choices and they both get highly developed.

Now, OK. So for game, now I'm going to turn to-- well, I'll do an example of max flow equal min cut, just see what-- and then go to two-person game. So here's an example of a-- so I start with a graph. Let me just imagine.

So this is the source. This is the sink. And I'm sending flow through the network. So it's a network that I'm sending flow through. So my job is to maximize-- I'll set x at the source to be 0. And then the flow, the total flow will come into the sink. So I want to maximize x at the sink.

So it's a linear programming and there are constraints. So what are the constraints? Every edge has a capacity. So let's see. Suppose that edge has capacity 5. Let me put capacities on all these edges. 2, 1, 3, 4. I'm just stabbing around here. 1,000. And let me say 2 and 4.

I have no idea what's happening here. But if we see the problem, we'll probably be able to solve it. So these constraints are that the flow variable, which would be the y that I'm trying to maximize, cannot-- the amount of flow, just in ordinary words, the amount of flow on the edges can't go higher than the capacity.

I could send 11 along this edge, but then I've got nowhere to send it after that. I could send, well, 900 on that edge. but, obviously, it would get stuck there. So the question is, what's the maximum I can send through that network? It's a classical problem.

And, in fact, it's an integer programming problem. These are all integer capacities. I could insist on integer flow. But it's a very remarkable integer problem because I could allow fractions and the answer would not be a-- would not involve fractions.

In other words, if I keep it as an integer problem, then the mathematics is definitely harder for an integer problem. What's different? So the x's could be integers or they could be real numbers. Over here, they were real numbers. I happened to get an integer for this, but if I had 10 crossing planes in 15 dimensions, the integers would be totally lost.

But the point is, here, that if I allow real numbers, it doesn't get me any more flow, that the winning flow is an integer anyway. So it's an integer problem which can be safely relaxed, and you can safely use simplex method, or Karmarkar's method, or any interior point method with non-integers, because in the interior here you're not starting or ending at integers. You can do it because the integer answer will be, in the end, better.

And what is that answer? I think I've made those capacities too easy to-- oh, I didn't do this one. So what shall I-- shall I make it large, like 9? I don't know.

What's the best we can do through that network? Can you-- I can't see it from here yet? What should I do? Obviously, in this simple problem I can get anything I want pretty much that far. But then what can I do?

Let me even make that 19. So I'm not imposing much of a limit on that edge either. But these edges are quite tight limits, and these are sort of intermediate limits.

What do you think is the most I can send through? And how would you show me that I couldn't send more? That's the key question. I want to get a bound on the-- an upper bound on this maximum. This maximum getting into the sink is less or equal to-- and what number would you propose?

Could I get 1,000 through? I could start, but of course it would pile up there. I couldn't get further. What do you think is the best I can do?

AUDIENCE: 10?

GILBERT STRANG: 10? I can't do more than 10? How could I do 10?

AUDIENCE: So you go 12--

GILBERT STRANG: 12 this way?

AUDIENCE: Yes. 19.

GILBERT STRANG: Oh, OK.

AUDIENCE: And then split the 8 and 2. Can you split?

GILBERT STRANG: I see. 10 that way, 10 this-- yes, absolutely you can split. And then this could go here, and that would be able to go there. So I can get 10 through. Correct.

AUDIENCE: [INAUDIBLE].

GILBERT STRANG: Can I do anything better? Oh, I could be sending some up this way at the same time. So I could get 3 along the top. So this is like an auction.

We can get up to 13. Can we get-- so that was 3 going this way and 10 going this way. Is 13 an-- can I not exceed 13?

AUDIENCE: 14?

AUDIENCE: 14.

GILBERT STRANG: Do I hear 14? Oh, I've got a lot of room for one more. So, OK. So 14 in any case. All right. Do I hear 15?

AUDIENCE: Can you do two more on the bottom, like 12 instead of 10?

GILBERT STRANG: If I did 12, then what would I do?

AUDIENCE: Split the other two up.

GILBERT STRANG: I'd send two up here. What am I going to do with them from here?

AUDIENCE: [INAUDIBLE].

GILBERT STRANG: Send them?

AUDIENCE: Up again.

GILBERT STRANG: Up again, and along. But then the 3 that I had right now would be cut back to 1.

It's a lot of fun, this max flow problem. And I'm looking for a bound to know when to quit, to know when I've optimized. That's the whole idea of duality, is to find some upper thing that I'm trying to push down but I can't go beyond it.

So I don't think I could get more than-- you see, everything has to cross this middle. So 3 and 4. And I don't think I could beat 23. If somebody said more than 23, I would be very doubtful, because I couldn't get it across the middle.

But then, can I get 23? I doubt it. Maybe 14 is the best possible. So how would we show that 14 is the best possible?

I think if I could find-- so this is called a cut, a cut in this network. Oh, yes, I see a cut. A cut like there. You see that?

Every bit of flow has got to cross that cut. And the total capacity crossing is the 3 and the 1 and the 2 and the 8, which is 14. So I can't get more than 14 through. And somehow that cut is loaded to capacity. Probably those edges all have to be fully up to capacity that cross the cut.

So the cut is a separation of edges that go with the source and-- sorry-- nodes that go with the source, nodes that go with the sink. Yes. And then it's the edges across the cut.

Is that OK for an example? So that's the duality. The maximum flow turned out to be 14, and the minimum cut turned out to be 14. And when those match, 14 equal 14, I know I'm through. I know I'm through because I'm able to get 14 through and I could never get more. Yes. 3 and 4 and 6 and 8. Yes.

And, of course, in a big network, the maximum cut is not going to be visible. Well, you couldn't-- it would have thousands of edges. You couldn't see what you were doing, But you could solve this problem fast, actually fast.

And it's an important-- in practice, it's an important example. A lot of other things fit into the max flow min cut example. And therefore solving it in faster than-- oh, I didn't even say about speed.

So the simplex method, almost always it's average case. Dan Spielman, who was on the faculty here, who's just terrific in this area, was maybe among the first to study the average case.

So for an average choice of A and b and c, instead of making the worst choice-- for the worst choice, you can create a feasible set that it has to go corner, corner, corner, corner to get to the end, so the simplex method would take exponentially long. But that's extremely rare. It doesn't happen in practice, I think. And the average one is a polynomial, so it's a fast method on average.

And we can show-- actually, that was a famous result that came from Russia, that linear programming is in the big P versus LP world, linear programming goes with P. Linear programming is a problem that can be solved in polynomial time. The simplex method won't always do it but it can be done. Yes. There came into the world, the ellipsoid methods, and it was an exciting time to decide that linear programming was actually P and not LP.

So this is a case of duality where you can understand duality by the statement that the flow cannot exceed the capacity of the cut. So that's what duality is, that any flow has to be less or equal the capacity of any cut, the capacity being the sum of the ones.

So, of course, there are other cuts. That cut has to be crossed, but that's gone 3, 7, 14, 22 capacity. So the 14 capacity was the minimum, and that gave the maximum. Nice. Isn't it nice? Yes.

So there is another world here of two-person games that also has duality and could be expressed. So let me just talk finally today about two-person games. So the two persons are x and y of course. What other names could they have?

And there is a matrix involved. This is the payoff matrix. So let me take a very simple game first.

So x is going to choose one of these rows, and y is going to choose one of these columns. And let's say payoff from x to y. I like it that way because, then, x, who's paying, is going to be minimizing, as x was up here. And y, who's collecting, is going to be maximizing, as in the dual.

So the payoff-- well, let's see. I think maybe 1, 4, 2, 8 would be probably a fairly easy game to play. So it's a two-person game, a zero-sum game. Zero sum means-- that means all pay-- what x pays goes to y. y gets all that x pays. There's no third party here. No lawyers involved.

And y is going to choose a column, and x is going to choose a row. And x wants to make it small, and y wants to make it big. So what happens in this game?

What does y choose to make it big? The second column. What does x choose to make it small? The first row. So it's going to be focused in on that 2, because if y keeps choosing that column, 2 is the best-- the least that-- x is going to have to pay 2, and he achieves that by choosing the first row.

So it's a simple game. That's a saddle point. It's a minimum for y in its column, and it's a maximum for x in its row. But, of course, a matrix, another matrix might not have such a saddle point.

So let me-- do you see-- OK with this game? That would be a sort of straightforward game where simple strategy-- column 2 every time, row 1 every time is the optimal. But now let me just exchange that.

So, again, x1 and x2. y1 and y2 are the two columns. What happens now? Well, y kind of likes the big number 8 there. So it goes for the second. The second column still has the bigger numbers. So y aims for column 2.

But then what does x do? What row does x choose if y is in the column 2?

AUDIENCE: Second.

GILBERT STRANG: The second. OK. So have I found a saddle point? Where y chooses this column, x chooses this row, is that a saddle point? No. Because what will y do now?

He sees x choosing the second row all the time, and y sees a 4, a very tempting 4, in that row. So y is going to choose y1, the first column, pretty often. Not all the time, because what happens if he just-- if y chooses this column all the time, then x will choose this row and the payoff would only be 1, so that things went downhill for y there.

So this is not a saddle point. And what do we do? Mixed strategy, which is y will choose the two columns with some probabilities that add to 1.

So there will be a third possibility, that p x1 and 1-- I'm sorry-- p y1. p times this column and 1 minus p times the second column. So that will be p plus 1 minus p times 8, and 4p plus 1 minus p times 2.

That's this mixed column. By mixing his strategy, we have a strategy like a third person, y3. And, of course, the x is going to notice after a while what the strategy is. This is an open competition. You're not hiding-- you're not able to hide anything.

You might think, well, maybe y will jump around, but that's foolishness. y is going to end up finding the best choice of p between 0 and 1. And it will actually be between 0 and 1 because the extreme strategies of column 1 and column 2 were not winners.

But now x is going to do the same thing. p x1-- he's going to-- he or she is going to combine those rows. So this would be p1 for the first row, and 1-- sorry-- p-- oh, I better choose another number. What's another letter than p?

AUDIENCE: q.

GILBERT STRANG: q? OK, q. So this row is a combination of those rows, so it's q plus 1 minus q times 4 in the first position, and p times 8 and 1 minus p-- q times 8. q times 8 and 1 minus q times 2. I'm sorry that I've written this too small.

But what's going to happen? What's going to determine p and q and solve the game? Well, if these are equal, then what happens? Then x is OK with either one. x has nothing to choose if those are equal and y is staying with his mixed strategy, which gives him this third combination column. Then x is good.

Now, you might say, well, then x could do what it wanted. But x couldn't do what it wanted. If x doesn't stick with the optimal strategy q for x, then y will take advantage. So, really, the game settles down to once-- so these should be equal.

So when those are equal, what do I get? I have p-- it looks like I have 8 minus 7p there for the first one. And here, I have 4p minus 2p. That's 2p plus 1. Did I get that possibly right?

AUDIENCE: Plus 2.

GILBERT STRANG: 2, 4p minus 2p is the 2p. Oh, it's 2. Yes. OK. So those are equal. And that tells me that 9p is 6, and p is 2/3.

So it turned out that the best strategy for y is 2/3 on the first column which didn't look so promising, and 1/3 on the second column. And by creating that strategy, what do these numbers come out to be? And they're supposed to come out equal.

So 4p plus-- so 4 times 2/3 is 8/3, plus 1 minus p is 1/3 times-- plus 2/3 is 10/3. So I think that this is 10/3. And if that one isn't 10/3, I'm very surprised.

So that's 2/3-- help. Is it? 4p, 2p, 4/3. Yes, it's telling me they're the same. Did I set them equal? Yes. I set them equal to find p. So they have to be the same. Except for instructor mistakes, which never happen, I suppose. OK.

So those should be equal. Then x has no way to do better, choose these columns. But he can't choose those columns freely-- those rows freely because y could take advantage, unless-- so this would give the best strategy for q-- sorry-- the best q for x. Yes.

Do you see that picture now? There could be other-- it could be a much bigger matrix, of course. There could be other columns. Suppose there was a 0, 0 column. What difference-- what would be the effect on the optimal strategy of having that additional column, that additional option for y3? Well, he wouldn't take it.

So let's make it more tempting. 10, 10, 10. Oh, he would take that, right? Yes. That was not-- so I'm not sure what I am trying to say here. Yes.

There certainly could be-- there could be rows that-- or columns, or rows for x, that don't enter the mixed, the optimal mixed strategy. A mixed strategy is some combination of strategies, some combination of pure strategies, like choose this column, choose this row. But some columns may not-- or rows-- may not show up in the best mixture. So I won't complete that partial thought there.

So do you see that we have a duality theorem? First of all, you could write that as a linear program. The unknown is p for x-- for y. The unknown is q for x. So, actually, you just have one unknown in this simple problem, for this small problem.

But you have a minimization, a maximization. They meet at the optimum. And the duality theorem becomes the theorem for two-person games. Linear programming matches two-person games.

The point about two persons is very important. Three-person games are incredibly complicated. No theory at this simple level would solve three-person games. So that's where John Nash's Nobel Prize comes into the picture. So his Nobel Prize was in economics because of the wide applications, but he was able to analyze the problem of-- and for functions more than for matrices-- of a three-person or n-person game.

So you know the story of John Nash? The book A Beautiful Mind and the movie A Beautiful Mind. So it's one of those movies that involves MIT because he was here. But you can't recognize anything about MIT in the movie. It's like Good Will Hunting. You're maybe in some basement of some remote building. But anyway.

It was of course a tragic-- tragic, and then cheer, then wonderful, and then tragic again for John Nash. He had-- so when I met him, he was going to teach linear algebra, one section, but that never developed. That was when he was-- his mental state was going downhill. And he moved to Princeton and just stayed. And then the wonderful thing was that he improved, and then the very sad thing was his death in a car accident on the way home from the Nobel Prize. So quite a story, an amazing story. Yes.

So that's specific optimization problems, linear programming and two-person games. And I hope that Friday it will be Professor Sra. Anyway, the lecture will certainly be about stochastic gradient descent. Good. Thanks.