From jfp@andrew.cmu.edu Thu Jun 2 07:48:21 2005 Date: Wed, 01 Jun 2005 20:55:14 -0400 From: Javier Pena To: Henry Wolkowicz Cc: jfp@andrew.cmu.edu Subject: Re: submission to MPB (fwd) Dear Henry, Attached please find my report on Freund-Ordonez-Toh paper. The paper is essentially a report on some computational experiments to test how much correlation there is between the number of iterations of an SDP solver and certain ``condition'' measures (Renegar's Freund's and two others). The paper makes the contribution of adding some computational conclusions to the (now sizable) theoretical literature on conditioning for optimization. That certainly has some merit. I did have several comments/suggestions that the authors should address/reply to. Please do not hesitate to contact me if you have any questions. Best regards, Javier --On Tuesday, March 1, 2005 11:31 AM -0500 Henry Wolkowicz wrote: > hi > Yes -- May is fine - thanks!! > Henry > > > Prof. Henry Wolkowicz |USE Email: hwolkowicz AT uwaterloo.ca > Univ. of Waterloo |URL http://orion.math.uwaterloo.ca/~hwolkowi > Dept of Comb and Opt |Tel (519) 888-4567, x5589, office MC6065 > Waterloo, Ont. CANADA N2L 3G1 |Fax (519) 725-5441 > Parkinson's Law: "Work expands to fill the time available for > completion, right up to deadline and not a moment before." > > On Tue, 1 Mar 2005, Javier Pena wrote: > >> Dear Henry, >> >> Yes, I would be happy to referee the paper. Would it be >> okay if I send you my report my the end of May? >> (This semester is a bit hectic.) >> >> Best regards, >> >> Javier >> >> --On Monday, February 28, 2005 6:32 PM -0500 Henry Wolkowicz >> wrote: >> >> > Dear Javier, >> > The attached paper >> > "Behavioral Measures and their Correlation with IPM Iteration >> > Counts on Semi-Definite Programming Problems" >> > Fernando Ordonez and Robert M. Freund and Kim Chuan Toh >> > >> > has been submitted to >> > Series B, Mathematical Programming, special issue on >> > "Large-Scale Nonlinear and Semidefinite Programming"; in memory of Jos >> > Sturm >> > http://orion.math.uwaterloo.ca/~hwolkowi/w04workshop.d/mpbspecialissue >> > .d/ callforpapers.html >> > >> > Would you be willing to referee this paper? A 2-3 month time period is >> > suitable. >> > >> > Thanks in advance for your help. >> > best regards Henry >> > >> > >> > Prof. Henry Wolkowicz |USE Email: hwolkowicz AT uwaterloo.ca >> > Univ. of Waterloo |URL http://orion.math.uwaterloo.ca/~hwolkowi >> > Dept of Comb and Opt |Tel (519) 888-4567, x5589, office MC6065 >> > Waterloo, Ont. CANADA N2L 3G1 |Fax (519) 725-5441 >> > Parkinson's Law: "Work expands to fill the time available for >> > completion, right up to deadline and not a moment before." >> > >> >> > [ Part 2, Application/PDF 55KB. ] [ Unable to print this part. ] From fordon@usc.edu Wed Dec 7 07:33:10 2005 Date: Wed, 07 Dec 2005 01:12:40 -0800 (PST) From: Fernando Ordonez To: Henry Wolkowicz Cc: Robert Freund , mattohkc@math.nus.edu.sg Subject: submission to math programming B. Dear Henry, in light of the bug spotted by Hua on our code and its effect on the paper, we have revised the paper we submitted to Math Prog. B. Please find the updated version of the paper attached to this email: Behavioral Measures and their Correlation with IPM Iterations Counts on Semi-Definite Programming Problems. by Freund, Ordonez and Toh. As I pointed out in the previous email, the changes due to this correction were minor: 12 problems had a change in Dp, 4 problems had a change in g^m, some correlation values were modified slightly. All conclusions of the paper remain valid. Please let me know if you would like additional explanation of these changes for the referees or something... Finally I would like to commend your student for an excelent work spotting our mistake. best wishes, Fernando -- Fernando Ordonez Assistant Professor Industrial and Systems Engineering, USC 3715 McClintock Ave., GER-247 Los Angeles, CA 90089-0193 213-821-2413 ---------- Forwarded message ---------- Date: Wed, 7 Dec 2005 00:55:42 -0800 (PST) From: Fernando Ordonez To: Hua Wei Cc: Henry Wolkowicz , Robert Freund , mattohkc@math.nus.edu.sg Subject: Re: Fwd: the code for computing Geometrical measure and Renegar's condition number Dear Hua, first I would like to thank you for your detailed look at our work and for spotting a real error in our computation and paper. We were indeed computing the minimum norm primal epsilon optimal solution, instead of the maximum norm for the measure Dp. I am attaching the revised Dp.m file (you probably have your own correct version of it already) and a revised paper with the correct Dp measures. As you noticed, the change in the results turns out to be minimal. In fact this only affects Dp for 12 problems and the g^m measure for 4. The conclusions of the paper remain valid. This is in part due to the fact that we are only reporting two significant digits, but mostly because the primal level sets are indeed not too large for these problems in the SDPLIB (the dual problems are well posed), hence the maximum and minimum norm solutions of the epsilon optimal level sets are not that different. Finally, I'll point out that deciding whether a problem has a t_p =0 (g_p = \infty) is indeed a difficult question. Same applies to \rho_P = 0 and D_d = \infty. Part of the difficulty is because computing optimal values close to zero make interior point solver face serious precision problems. Hence we decided on the status of the value of these measures based on the following: first based on the theoretical relationships between g_p, D_d and \rho_P we used the computed values to all three measures to get evidence that problems had \infty measures; second we used the more accurate SDPT3-aug solver to compute more precisely the value of measures close to zero; finally we used some rule of thumbs such as: if g_p = 1/t_p > 10^8 then g_p = \infty and if \rho_P < 10^(-6) then \rho_P =0. Thanks again for your detailed look at our work and letting us know that we had a bug. Best wishes... Fernando On Mon, 14 Nov 2005, Hua Wei wrote: > From: Hua Wei > Date: Nov 14, 2005 1:37 PM > Subject: the code for computing Geometrical measure and Renegar's > condition number > To: Hua Wei > Cc: Henry Wolkowicz , rfreund@mit.edu > > > Dear Professor Ordonez, > > Several months ago, you sent me the code for testing the Geometrical > measure and the Renegar's condition measures in the paper"Behavioral > measures and their correlation with IPM iteration counts on SDP > problems". I am working with it right now with my supervisor Henry > Wolkowicz. Thanks very much for your code. > > However, I encountered some weird results, so I have a detailed look > on the code. It might be a bug: > > In the Dp.m file, you are using a primal formulation to compute the > D_p value. However, the formulation in the paper (Page 6 Proposition > 1) is to maximize while the default behavior for primal problem in > SDPT3 is to minimize. So we may need to change the C2 to -C2 in the > code, and use -mean(obj) as the D_p value. I tested some of the > SDPLIB problems with the new formulation. Amazingly, they return > almost the same D_p value. I guess a possible explanation is that we > have a very small(or unique) optimal solution set such that minimize > and maximize will return almost the same D_p value. > > The code for Dd.m and tpcomp.m and tdcomp.m seems correctly handled > this situation. > > BTW, your paper indicates that some of the td or tp values are 0, thus > the corresponding gd or gp value is inf. However, the return result > from SDPT3 is always some small number. Did you use some tolerance so > that whenever td or tp is less than that tolerance, you set td or tp > to be 0. What is the tolerance? What about > primal_distance_to_infeasibility value? sometime they are 0 too. > > Thanks, > > Hua Wei > > > > Dear Hua, > > > > > > I remember well our conversation at the confernce, and it was very nice to > > > meet you in Stockholm... > > > > > > I'm attaching a zip file which contains all the matlab files needed to > > > compute the condition number and aggregate geometry measure for a SDP > > > problem. Check out the example.m file to get an idea on how to run > > > it. Should be self explanatory, we refer to measures as we do in the > > > paper. These files use SDPT3, so if you would like to use another SDP > > > solver you will have to change the function calls (sqlp). > > > > > > Please do let me know how correlated your measure of strict > > > complementarity is to the condition number and geometry measures. This is > > > really interesting stuff for me. > > > > > > best wishes, > > > fernando > > > > > > On Sun, 5 Jun 2005, Hua Wei wrote: > > > > > > > Date: Sun, 05 Jun 2005 10:47:18 -0400 > > > > From: Hua Wei > > > > To: fordon@usc.edu > > > > Subject: About the talks in SIAMopt conference > > > > > > > > Dear Professor Ordonez, > > > > > > > > My name is Hua Wei and I am a PhD student of Professor Henry Wolkowiczs in U. of Waterloo. I sat in your talk about iteration counts on SDP in the Siam optimization conference in Stockholm. Your talk was very clear and nicely organized and presented. I talked to you about the relation between the strictly complementary measure and the iteration counts. You said you could email me the code for measuring the aggregate geometry measure so I could test if the strictly complementary slackness condition has some correlation with the geometry measure. So, I am writing this email to see if you have some time and could send me a copy of your code. > > > > > > > > BTW, I found your paper in the optimization-online. > > > > > > > > > > > > Thanks a lot. > > > > > > > > Hua Wei > > > > Dept of Combinatorics & Optimization, > > > > University of Waterloo, Waterloo, Ontario > > > > (MC5161, Phone: 519-742-8312 ext 6410(work), ) > > > > > > -- > > > Fernando Ordonez > > > Assistant Professor > > > Industrial and Systems Engineering, USC > > > 3715 McClintock Ave., GER-247 > > > Los Angeles, CA 90089-0193 > > > 213-821-2413 > > > > > > -- Fernando Ordonez Assistant Professor Industrial and Systems Engineering, USC 3715 McClintock Ave., GER-247 Los Angeles, CA 90089-0193 213-821-2413 [ Part 2, "" Application/PDF 369KB. ] [ Unable to print this part. ]