Formatting Optimization Problems with LaTeX

Constrained optimization problems are almost everywhere in engineering research. A mathematical description of those problems with a single objective is to minimize or maximize an objective function over a set of decision variables under a set of constraints. There are different ways to format optimization problems; personally, I follow the format used in the book “Convex Optimization” by Stephen Boyd and Lieven Vandenberghe. For example, a general optimization problem has the form

This is generated by the following code:

\begin{equation*}
\begin{aligned}
& \underset{x}{\text{minimize}}
& & f_0(x) \\
& \text{subject to}
& & f_i(x) \leq b_i, \; i = 1, \ldots, m.
\end{aligned}
\end{equation*}

As seen in the code, the formatting is done by the aligned environment, which is defined in the amsmath package, so you need to include the following line in the preamble:

\usepackage{amsmath}

Unlike the tabular environment, in which you can specify the alignment of each column, in the aligned environment, each column (separated by &) has a default alignment, which alternates between right and left-aligned. Therefore, all the odd columns are right-aligned and all the even columns are left-aligned.

We conclude with a real example:

The above problem is formulated for completing low-rank positive semidefinite matrices. It is convex, or more precisely, it is a semidefinite program.  The corresponding code is

\begin{equation*}
\begin{aligned}
& \underset{X}{\text{minimize}}
& &\mathrm{trace}(X) \\
& \text{subject to}
& & X_{ij} = M_{ij}, \; (i,j) \in \Omega, \\
&&& X \succeq 0.
\end{aligned}
\end{equation*}

蒙特利尔日记（三）

2009年6月12日（续）

和老板约了一起吃午饭，于是匆匆乘地铁回旅馆。下车后，我开始找出口，看到一扇门上挂了块牌子，上面写的是法语，但其中一个词我认识：sortie，意思是出口。当时我暗自欣喜，心想至少认识一个关键词，但等到我推门而出的时候，顿时警铃大作，响彻整座车站，站内的所有人都朝我看，看来只认识一个关键词是不够的。还好我脸皮厚，心想这也不是我的错，谁叫他们不用英语的，于是乎转过身，大摇大摆从另一个方向走了出去。

中饭在Rue Bishop上的一家印度餐馆吃。Rue Bishop靠近Rue Sainte-Cathenine（蒙特利尔的一条主要的商业街）的那一段真的很cool，两边是各式各样的饭店，而且都有户外用餐的地方，再加上很好的天气，看看就觉得很愉快，更不用说吃吃饭，喝喝酒了。

饭后去爬了Mount Royal，其实是座小山，海拔才700英尺左右，充其量叫hill，当地人叫它mountain实在是夸张了一点（这让我想到蒙古人把北京那些小湖都叫＂海＂）。好在它就在市中心的边上，在顶上可以俯瞰整个市区，风景不错。

下山后，在回旅馆的路上路过Montreal Museum of Fine Arts，主馆区很早就关掉了，只剩一个关于John Lennon和Yoko Ono的展览还开着。这个展览是为了纪念他们两个人于1969年在蒙特利尔进行的反战抗议。静坐抗议在英文中叫＂sit-in＂；John和Yoko对之稍加变革：1969年3月结婚后，他们在阿姆斯特丹度蜜月的主要活动就是邀请媒体拍摄他们在旅馆床上静坐示威，被称为＂bed-in＂。其间他们录制了一首单曲《Give Peace a Chance》，之后成为美国反战运动的主题曲。

晚饭去了家中餐馆，但这家饭店显然为当地人而开：菜单上没有中文，价格比一般中餐馆的两倍还要贵，味道也不怎么样，除了有点情调和服务比一般中餐馆要好外，我觉得无处可以恭维了。看来要吃点让人激动的中餐可能只有回中国了。

蒙特利尔日记（二）

2009年6月12日

上学期修一门统计课的时候认识一个从蒙特利尔来的女孩，她听说我要去她的城市，给我开了一张单子，列了推荐的地方和饭店等。我在地图上圈了一下她推荐的地方，就跑出去了。原先看地图的时候觉得蒙特利尔蛮大的，一走才发现这个城市真的很好，似乎什么地方走走都可以到。蒙特利尔教堂很多，第一个经过的是Christ Church Cathedral，属于Anglican Church。这座教堂很cool，特别是它的Neo-Gothic的尖顶和背后的高楼的反差。基督教的教派（Christian denomination）过于复杂，Anglican Church是英国圣公会在英国以外的一些国家的分枝，在美国叫Episcopal Church，应该是换汤不换药的。原本打算把这重重关系搞搞清楚，现在已经基本放弃。出了Christ Church Cathedral，我就在附近随便逛逛，特别是一条主要的商业街Rue Sainte-Catherine和几座路过的教堂。说实话，我不是很欣赏那些教堂的玻璃（stained glass），觉得太过写实，人物的比例和真实的过于接近，反而少了神秘感，还是文艺复兴风格的好看。

逛完后，我去乘地铁，想不到售票大妈不讲英语，于是我们交流的形式变成我问问题，她说Yes或No，直到她收了我的美元。我后来发现大多数地方都是收美元的，只是把美元当成等值加元用，如今他们是赚的，因为美元比加元略贵，但我不知道去年美元比加元便宜的时候，他们是不是也这样做。出了地铁站是著名的Notre-Dame Basilica of Montreal，但他们竟然收门票，这或许是我目前去过的唯一一座收门票的教堂（不过我记得波士顿的Trinity Church好象也收门票，只是我当时没进去）。里面还是很漂亮的，特别是屋顶和走廊都漆成蓝色，还有一点不寻常的是玻璃上画的都不是圣经故事，而是蒙特利尔的宗教历史场景，所以既有早期的欧洲殖民者，也有印第安人。Basilica后面还有一座小的chapel，1978年毁于纵火，之后重建，于1982年重新开放，用了雕塑家Charles Daudelin（魁北克人）的作品作为altarpiece。在教堂里同卖纪念品的女孩聊了会儿天，我是很喜欢她的法语口音，觉得法语口音的那种俏皮的味道在美国女孩中是找不到的。

（未完待续）

蒙特利尔日记（一）

2009年6月11日

晚上离开芝加哥的时候，天在下雨。上了架小飞机，用Harper’s和Newsweek（Stephen Colbert是这一期Newsweek的编辑）打发了两个小时，终于到了蒙特利尔，到时已是半夜。天气还不错，稍稍有点闷。去旅馆的路上，出租车司机见我们是从美国来的，开始用带着口音的英语向我们介绍蒙特利尔的景点和饭店。我已经蛮累了，特别是在芝加哥，去机场的路上竟然堵了两小时，和洛杉矶有得一比，所以除了记得他推荐一家叫Schwartz’s的饭店外，也记不得他说了些什么了。因为在魁北克，官方语言是法语，但蒙特利尔的很多人也讲英语，所以我倒不担心lost in translation。旅馆在downtown，离这次开会的McGill的校园仅仅两个街区，所以还是很方便的。离开会还有两天，这次早来两天，一是懒得从芝加哥飞回西雅图，二是想乘机玩一下。

东岸游记（六）

走完Wall Street后沿着Broadway往南走，可以在Battery Park乘渡船去Liberty Island看自由女神像。途中会经过著名的Wall Street Bull（其实并不在Wall Street上）。我到的时候正好有几个旅游团在（包括来自中国的），很多人围着铜牛照相，似乎都很兴奋，但那天（9/15/2008）美国股市的表现却恰恰相反，受Lehman Brothers申请破产保护的消息的影响，Dow Jones工业平均指数下泻498.86点，差不多是这次金融危机开始的一个正式信号。

纽约和上海人都很多，但最大的不同是你在纽约可以遇见来自世界各地的人。我在排队等渡船的时候，周围挤满了各种各样的人，我仔细一听，竟然听不到英语，而且我前后左右的几组人都讲完全不同的语言，这或许就是纽约的美妙之处了。耗费无数耐心后终于到了岛上，我绕着著名的自由女神像逛了一圈。看过电影The Legend of 1900（中文名好像叫＂海上钢琴师＂）的人或许还记得片子开头的时候有一段场景描写从海上到达新大陆的欧洲移民看到自由女神像时的兴奋和激动。这种兴奋和激动现在是很难复制了，但无论历史怎么演进，这片土地还是一片为自由平等民主的精神所笼罩的土地，而这座雕像还是这种精神的象征，这也就不难理解为什么上Liberty Island的安检过程和上飞机一样严格了。

记得一次和一个美国朋友聊天，他突然说了一句让我肃然起敬的话。大致意思是他为美国而骄傲，但他骄傲的并不是世界第一的军事实力，而是美国是世界上唯一一个生来就实现民主的国家。至于此处的＂唯一＂，我没有考证过，不过在当今有影响力的国家里，他说的应该属实。当然有人可以讥笑美国历史短，但却不得不承认，就在这短短的二百多年里，整个世界的历史似乎是以她为中心的。仔细想想，其实美国是一群欧洲知识分子的政治试验品，但这个试验取得了巨大成功。有次开车的时候听NPR的广播，里面在讲Seattle Art Museum最近的一个展览，叫

Life, Liberty and the Pursuit of Happiness: American Art from the Yale University Art Gallery

一个学者提到Thomas Jefferson在最初起草《独立宣言》的时候，用的是“Life, Liberty and the pursuit of Prosperity”，但他最后受他一个法国朋友的影响，把“Prosperity”改成“Happiness”，因为前者更侧重经济上的繁荣，而后者是个人自由追求的一个综合概括，从此The Pursuit of Happiness成为American Dream的一个精炼的总结。我好像没办法从Wikipedia上验证他说的，但无论如何，这一表述意味着对个人自由的尊重是美国的核心价值观，而眼前的自由女神像就是这一核心价值观的艺术象征。

东岸游记（五）

决心快把去东岸的流水帐报完，否则就要忘记了。上次写到美国宪法第五修正案。

第六修正案规定刑事诉讼中被告的权利，包括迅速和公开的审判、陪审团制度、与原告的证人对质、获取对其有利的证人、取得律师协助其辩护等。

第七修正案规定民事诉讼中，只要争执额超过二十美元就有请陪审团审判的权利。

第八修正案禁止过多的保释金和罚金，并禁止酷刑。

第九修正案说宪法对于公民权利的列举不应该被理解为否定或蔑视人民保留的其他权利，也即保护了其他没有被宪法明确列举的权利。虽然现在看来，《权利法案》是人类争取公民权利道路上的里程碑式的文件，但当初也不是所有人都赞成通过该法案的。Alexander Hamilton就曾反对过。他是美国首任财长，也是美国最早的宪法律师之一，你可以在十美元的钞票上发现他的头像。他反对的理由之一就是在宪法中详细列举具体的权利可能会限制那些未被列举的权利，特别是那些无法由法律限定的天然权利。所以引入第九修正案从很大意义上说是为了抵消这种惧怕。

第十修正案规定未授予合众国且未禁止各州行使的权利由各州或人民保留。这一条是对联邦权利的限制。

顺便放一张Federal Hall的照片，门口竖有George Washington的铜像。

The Audacity of Doubting (III)

Before we talk about the assumption of independent and identically distributed data, we might find it helpful to look at a simple example – spam filtering. You have every reason to wonder at the accuracy of Gmail’s spam filter. Google is not hiring cheap labor from India or China to handpick the emails containing keywords such as “adult,” “viagra,” etc. and put them in your spam folder. Although they reveal little technical details on their relevant help page, I’m sure that they must have used very sophisticated machine learning technologies and trained classifiers on a massive amount of data. Another undoubted truth is that many dirty engineering tricks must have been used in their spam filtering system.

I call those engineering tricks “dirty” not because I favor theoreticians over engineers, but because sometimes the real-life situation can become very nasty and only dirty tricks can handle it. This is exactly what Jack Bauer testified in a Senate hearing:

“When I am activated, when I am brought into a situation, there is a reason. And that reason is to complete the objectives of my mission at all costs.”

“For a combat soldier the difference between success and failure is your ability to adapt to your enemy. The people that I deal with – they don’t care about your rules. All they care about is the result. My job is to keep them from accomplishing their objectives.”

“In answer to your question, am I above the law? No, sir. I am more than willing to be judged by the people you claim to represent. I will let them decide what price I should pay. But please, do not sit there with that smug look on your face and expect me to regret the decisions that I have made. Because, sir, the truth is, I don’t.”

Bravo! Basically, engineers face the dilemma of waterboarding all the time. Is waterboarding torture? Of course it is (I’m glad that Attorney General Eric Holder agrees with me). Shall we use it systematically for interrogating terrorists? Of course not. Why? Because it is immoral. But shall we never consider it as an option for interrogation? Well, sometimes the ends justify the means. That’s why Jack Bauer does not and does not need to regret his decisions.

A gentler word to describe these engineering tricks is “ad hoc.” Given a problem, I long for a simple, general and elegant solution; those who advocate ad hoc tricks from the beginning – I can’t help but question their aesthetics. However, we still need ad hoc solutions, perhaps a lot of them, simply because of the gap between reality and our romantic fantasy about the world we live in.

I’m a hypocrite :(

Recently I’ve been revising my newly accepted journal paper. To address one reviewer’s comments, I need to reread a few papers authored by a rising star in the machine learning community. Her papers at first glance look like the back of a hot slim blonde, but when you dig into the details, it’s like the blonde turns around and takes your breath away by her super ugly face;) I’m not saying that her papers were badly written. Quite the opposite, her papers provide a nontraditional yet important perspective of a very hot topic in machine learning, and her investigation is indeed very systematic. However, the heavy dose of math that she injected into her papers doesn’t let me feel a flow of elegance; instead, the salesman’s tone, the poor presentation, and the awkward notations put together a huge turnoff, not to mention a bug that I discovered in one of her proofs. I literally felt angry when I was reading her papers. I wish it was my impatience that amplified my feelings. We actually met when she came to the UW for a job talk, and because we’re interested in very similar research topics, we chatted after her presentation. To vent my anger toward her papers, I almost wanted to say, “Hey, your writing sucks!” Of course I didn’t do that. I smiled, and told her how interesting I thought her theory was and how much I appreciated her thorough therectical analysis. And I just couldn’t stop there – I went on giving my compliments till her face glowed with delight and gratitude. Oh my God, what a big hypocrite I am!

Who’s the Madoff?

A recent article on the Wall Street Journal titled “Chinese Premier Blames Recession on U.S. Actions” reports the speech given by Premier Wen at the World Ecnomic Forum in Davos [full text of Premier Wen’s speech]. Apparently, most American readers are not happy with the blaming game. Let’s zoom in to the paragrah of Premier Wen’s speech that this Wall Street Journal article is about:

“This crisis is attributable to a variety of factors and the major ones are: inappropriate macroeconomic policies of some economies and their unsustainable model of development characterized by prolonged low savings and high consumption; excessive expansion of financial institutions in blind pursuit of profit; lack of self-discipline among financial institutions and rating agencies and the ensuing distortion of risk information and asset pricing; and the failure of financial supervision and regulation to keep up with financial innovations, which allowed the risks of financial derivatives to build and spread. As the saying goes, ‘A fall in the pit, a gain in your wit,’ we must draw lessons from this crisis and address its root causes. In other words, we must strike a balance between savings and consumption, between financial innovation and regulation, and between the financial sector and real economy.”

Harsh criticism it is, but before we let our emotions cloud our judgement and our pride blind our eyes, we may simply ask ourselves the question, “Are all these words purely communist rhetorics attacking the leading democracy in the world?” Chinese must be deeply frustrated by the loss of their investment in the US, and Chinese leaders must have felt burned by the huge impact on China’s economy – the soaring unemployment will directly threaten the legitimacy of their ruling.

In the long run, China is facing much tougher problems than the US. Their model of development is even more unsustainable in the sense that the growth of their economy results in the destruction of their environment. Their industry is driven even more by the blind pursuit of profit; otherwise, how to explain the tainted milk formula that killed at least six and sickened thousands of babies? Their market is better described by “no self-discipline” than “lack of self-discipline” given the rampant piracy and knockoff products. However, I just can’t see any direct link between these problems in China and the current financial crisis that started in the US and has already spread around the world.

You can look at the case of Bernie Madoff and blame his victims for their own greed, but you can’t argue that those victims instead of Madoff should be put on trial. If we could use our wildest imagination and view the current global economy as a Ponzi scheme, then who would be the Bernie Madoff here?

I think Premier Wen was speaking the truth rather than seeking a retaliation on US Treasury Secretary Timothy Geithner’s comment on China as a currency manipulator. Americans do not need to apologize for their way of life, especially to China, because without the demand from the US, Chinese would not rejoice over their economic boom. But this doesn’t mean that the American way is always the right way and

“When I became a man, I put childish ways behind me.” (1 Corinthians 13:11, NIV)

The Audacity of Doubting (II)

The phlogiston theory offers seemingly reasonable explanations for many other phenomena of combustion. If we restrict ourselves to these phenomena only, both the phlogiston theory and the oxygen theory are logically sound. This poses a problem called “model selection” in the terminology of statistical learning. Basically, when we have multiple (possibly infinitely many) models that can explain the given data equally well, which one shall we choose? It’ll be a tough decision, but fortunately, there’re many criteria out there helping you. The most famous one is probably Occam’s razor. It essentially means “the simpler, the better.” If translated into a political slogan, it would be “Vote for simplicity” or “Simiplicity we can believe in.”

What scares me in the story of phlogiston is not that they chose the wrong criterion but the fact that none of these criteria, no matter how sophisticated they are, can prevent us from selecting the wrong model. For example, Francis Crick commented on Occam’s razor, “While Occam’s razor is a useful tool in the physical sciences, it can be a very dangerous implement in biology. It is thus very rash to use simplicity and elegance as a guide in biological research.” [1]

Among all the fields of science, mathematics is the only discipline that deserves the word “perfect.” The reason is simple – we human beings are the creators of the subjects studied in math, while we are not for other fields such as physics, chemistry, biology, not to mention the social sciences. Moreover, when mathematicians lay down lemmas, propositions and theorems, they prescribe the conditions or assumptions first, which implies the disclaimer that they’re responsible for the conclusions only when the prespecified conditions or assumptions hold. What if some assumptions are seemingly self-evident but cannot be proved? They simply label them as “axioms,” whose validity they take no responsibility for.

As to the other fields of science, our study or investigation relies heavily on the observations from controlled or uncontrolled experiments. In statistical learning, these observations are called “training data.” A common assumption in statistical learning is that the data samples are independent and identically distributed. In layman’s terms, it basically means that the observations are very representative of the subject under study. This assumption comes very handy for theoretical analysis, but how good is it in reality?

[1] Francis Crick, What Mad Pursuit: A Personal View of Scientific Discovery, New York: Basic Books, 1988.