COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

### How can I solve semidefinite programming problems? Can any one with

• Email
• Follow

```Hello.

I am a student learning signal processing. I need my data to be calculated which needs optimization. And I am using Mathematica for programming. But till now I do not find any functions in mathematica for semidefinte programming. The problem is

min C'XC

s.t. B>=0, W>=0 ,t>=0, X'=X

where C' ,X' are the transpose of C and X, respectively. C,B,W are  matrices where B is a block matrix containing X. t is a number to be calculated. X is the unknown symmetic matrix to be found. I asked Nathan Brixius,the author of SDPMATH package which is used in Mathematica for semidefinite programming in 90's. But the link to SDPMATH package is missing (http://www.cs.uiowa.edu/~brixius/sdp.html ). And after I wrote a letter to the author ,  he said the package is lost.

How can I solve semidefinite programming problems in mathematica? Are there any innard or build-in methods in mathematica? Can any one with kindness help me?

Thanks a lot.

```
 0
Reply fmingu 12/19/2010 10:11:20 AM

See related articles to this posting

```On Dec 19, 4:11 am, fmingu <fmi...@163.com> wrote:
> Hello.
>
>  I am a student learning signal processing. I need my data to be calculated which needs optimization. And I am using Mathematica for programming. But till now I do not find any functions in mathematica for semidefinte programming. The problem is
>
>  min C'XC
>
> s.t. B>=0, W>=0 ,t>=0, X'=X
>
> where C' ,X' are the transpose of C and X, respectively. C,B,W are  matrices where B is a block matrix containing X. t is a number to be calculated. X is the unknown symmetic matrix to be found. I asked Nathan Brixius, the author of SDPMATH package which is used in Mathematica for semidefinite programming in 90's. But the link to SDPMATH package is missing (http://www.cs.uiowa.edu/~brixius/sdp.html). And after I wrote a letter to the author, he said the package is lost.
>
> How can I solve semidefinite programming problems in mathematica? Are there any innard or build-in methods in mathematica? Can any one with kindness help me?
>
> Thanks a lot.

You might be able to finesse the positive definiteness constraints, at
least for smallish problems. This can be done by defining a function
that operates only on explicitly numeric matrices and returns the
minimal eigenvalue.

In the code and simple  example below I do not check that the matrix
inputs are square and symmetric, but I enforce that in the way it is
called. This might need adjusting for various usages. I also do not
know whether Eigenvalues will always come up with real values when
given a symmetric input, as it is a numeric algorithm and subject to
numeric error. So I take the real part of the eigenvalues it computes.

In[1]:= n = 5;
cc = RandomInteger[{0, 10}, n];

In[3]:= xvars = Array[x, {n, n}];
Do[x[i, j] = x[j, i], {i, 2, n}, {j, i - 1}]
fvars = Union[Flatten[xvars]];

In[6]:= mineig[mat : {{_?NumericQ ..} ..}] :=
With[{eigvals = Eigenvalues[mat]}, Min[Re[eigvals]]]

In[7]:= {min, vals} =
FindMinimum[{cc.xvars.cc, {mineig[xvars] >= 0}}, fvars]

During evaluation of In[7]:= FindMinimum::eit: The algorithm does not
converge to the tolerance of 4.806217383937354`*^-6 in 500 iterations.
The best estimated solution, with feasibility residual, KKT residual,
or complementary residual of
{4.991839325346274*10^-7,0.0001756205712055703,1.006553812005796*10^-10},
is returned. >>

Out[7]= {-0.000102810847622932, {x[1, 1] -> 0.4745617099801545,
x[1, 2] -> -0.2366811680109855, x[1, 3] -> -0.2132627776342026,
x[1, 4] -> -0.2702226619552426, x[1, 5] -> -0.2453269610921312,
x[2, 2] -> 0.4759415776673994, x[2, 3] -> -0.03653531695016651,
x[2, 4] -> 0.103983724598686, x[2, 5] -> -0.01760774267839494,
x[3, 3] -> 0.4587401126362137, x[3, 4] -> -0.0003398923289131131,
x[3, 5] -> -0.07268674827647269, x[4, 4] -> 0.7191478545392413,
x[4, 5] -> 0.004481278729767096, x[5, 5] -> 0.4939968048471287}}

We check by how much the constraint is violated. The minimal
eigenvalue is, one rather suspects, a fuzzy zero.

In[10]:= mineig[xvars /. vals]

Out[10]= -4.990836973695068*10^-7

This is very much a "Your mileage may vary" approach. I would not
expect it to be terribly fast. I would not be surprised if it has
difficulty in enforcing the constraint, for some (perhaps most?)
problems. You might try alterations such as adding an explicit penalty
term in the objective function, perhaps altering it based on
StepMonitor option setting, etc. Below is a very simple form of this
idea, probably not so useful in practice.

FindMinimum[{cc.xvars.cc -
10^5*mineig[xvars], {mineig[xvars] >= 0}}, fvars]

Daniel Lichtblau
Wolfram Research

```
 0
Reply Daniel 12/20/2010 5:41:52 AM

1 Replies
412 Views

Similar Articles

12/13/2013 11:06:16 AM
page loaded in 74773 ms. (0)

Similar Artilces:

Can any one from this group help to solve this problem pl.
All, Consider a set S of n > 1 distinct numbers given in unsorted order. Each of the following problem parts asks you to give an algorithm to determine two distinct numbers x and y in the set S that satisfy a stated condition. Your algorithm must be specified using pseudocode. You must justify that your alogorithm has the requested run time. a) In O(n) time, determine x, y = S such that |x - y| >= |w - z| for all w, z in S. b) In O(n lg n) time, determine x, y = S such that x!=y and |x - y| =< |w - z| for all w, z in S such that w !=z Thanks, Bob. In message <1110739306.920006...

Can you solve this SQL problem?
I have tried and failed <grin>, any help would be appreciated. Here is my data: ID, dtDate, Hours, PayType ============== Joe, 3/23/06, 7, Regular Joe, 3/23/06, 1, Regular Joe, 3/23/06, 2, Overtime Joe, 3/24/06, 4, Regular What SQL to get this recordset? ID, dtDate, Regular, Overtime ====================== Joe, 3/23/06, 8, 2 Joe, 3/24/06, 4, 0 See if this will help. TRANSFORM Sum(TableName.Hours) AS SumOfHours SELECT TableName.ID, TableName.dtDate FROM TableName GROUP BY TableName.ID, TableName.dtDate ORDER BY TableName.PayType DESC PIVOT TableName.PayType; -- Wayne Morgan MS Ac...

Can you solve a problem like this?
Jesus Christ! I am trying to solve a problem for a day (I will tell my progress by the end)... It must be: AEIM BFJN CGKO DHLP It must not be: ABCD EFGH IJKL MNOP How can links be added in alphabetic order down instead of up in a table that has 4 cols for every row, 11 rows and 47 links? #!C:\Programas\xampplite\perl\bin\perl.exe print "Content-type: text/html\n\n"; open(OLDLIST, "<link list.tmp1"); open(NEWLIST, ">link list.tmp2"); \$count=1; \$col=0; \$row=0; \$place=1; @newlist=(); foreach \$line(<OLDLIST>) { \$col=\$count ...

problem i can't seem to solve
i have written a function that returns me a ratio from the world size to pixels. the reason i need this is to draw certain objects of a constant pixel size. the way i do this is to take two corners of my window and use gluUnProject to get world coordinates to compute the "size" of the world and then divide by the size of the diagonal of the window in pixels to obtain the ratio worldPixelRatio. so that if i want to draw a line of 20 pixels i can simply write : glBegin(GL_LINES); glVertex3f(ox,oy,oz); glVertex3f(ox+20*worldPixelRatio,oy,oz); glEnd(); all of this works fine in g...

Can any one write a c++ program which is in matrix , in MPI
hellow everybody Can any one write a c++ program which is a matrix , in MPI. if so do reply me back , i can send you the program . regards James ...

Who can help me solve 2 problems with Yahoopops/Outlook 2003?
First of all: I am not a computer expert, just a dedicated user, so please dont explain in a 'nerd'-ic way! I use YAHOOPOPS to automatically download my mail from TWO Yahoo accounts into my Outlook 2003. In my main computer (in Indonesia) I have no problems with downloading. But strangely enough one of them cannot be accessed from the laptop that I recently bought and that I have with me in Holland now. I use the same settings for both and the YAHOO address for both accounts is just yahoo-id@yahoo.com. What can be the problem? And the solution, of course! :) Another problem that I ha...

Simple I/O problem can't get solved
Greetings to everybody, I have recently started to solve my first Python problems but I came across to this: Write a version of a palindrome recogniser that accepts a file name from the user, reads each line, and prints the line to the screen if it is a palindrome.(by http://www.ling.gu.se/~lager/python_exercises.html) I think I coded it correctly but still I get no output. I do not have any errors I just do not get any output. This is the code: *** import is_palindrome filename = raw_input('Enter a file: ') # A text file f = open(filename) while True: line = f.rea...

can I solve this problem by using Neural Net (very urgent and help plz)
Dear members: I face a problem that someone succeeded in using genetic algorithm and I am wondering whether or not I can use Neural network to solve it. The problem is described as follows: we have a non-linear function: Y=F(h(x)) where h(x) we don't know. Now we desire to have a specific shape of Y, and want to find the optimum h(x) with which we will obtain the desired Y (with the desired shape). There are somebodies using the genetic algorithm to find the h(x). They choose a population of h(x), binarize members of the population and feed them into the program, and test the errors ...

Problem: MSIE6 + \$_POST data. Only on one client and I can't reproduce it!
I am tearing my hair out trying to reproduce a problem. The one client user who has this problem is running IE6 on WinXP Pro. I tried reproducing the problem in Opera, Mozilla, IE5 on Win2k, IE6 on Win2k, but no luck. Here is the problem: Occasionally, either SESSION data or HTTP POST data is lost. Poof! It just disappears, with the exception of the PHPSESSID, which leads me to think it is NOT a session problem. Unfortunately, I cannot reproduce the problem, so am at a loss on what details to give that would help. My only hope is that someone else, somewhere, has experienced a similar sy...

I just can't solve the 'Out of Memory' problem, please Help.
I implemented an image "whitening/low pass" filter. It meant to take a set of time-varying images eg. sequence of movie images and apply 4th order exponential low pass filter onto them. Because I am testing a 100 frames of avi movie which has the size of 570x570 meaning a 570*570*100 matrix, "out of memory" error is given every time i run the filter. I have tried to optimize memory usage as best i can, eg. clear useless vairables, preallocate matrix instead of growing.... but it is still giving me such error. pls help. function wvol = whiten_3D_ver2(vol) % This function...

39% of Karmic Krapware victims have install or upgrade problems they can't solve
"What is your Karmic Koala install/upgrade experience ?" http://ubuntuforums.org/showthread.php?t=1305924&highlight=Karmic+freeze OK, now it's officially been released. "DFS" <nospam@dfs_.com> wrote in message news:hcep59\$4ov\$1@aioe.org... > "What is your Karmic Koala install/upgrade experience ?" > > http://ubuntuforums.org/showthread.php?t=1305924&highlight=Karmic+freeze > > > OK, now it's officially been released. The Ubuntu forums are absolutely saturated with people who can't upgrade, or things crash, or n...

codewarrior p&emicro error:"Can only debug one program at a time."
Hi i ask your help can't acces to a Kinetis uC i have this error: "Failed to resume target process., Can only debug one program at a time." Rebooting PC or programmer(Cyclone max) has no effect How can i get out of this? Thank you ...

2 dimensional Turing machine can solve Halting problem of a 1 dimensional turing machine
COLLABORATORS WANTED. Hi, Check Wikipedia to see that the CARDINALITY of a set of real numbers is greater than the CARDINALITY of a set of integers. Don Gedding in comp.ai.philosophy suggested wikipedia. Now the CARDINALITY of a plane or the power set of integers is greater than the cardinality of the set of integers. So we construct a 2-dimensional TURING MACHINE on which all 1- dimensional TURING MACHINES are enumerated ------ and still there will be more cells on the 2-dimensional TURING machine because the CARDINALITY of a plane is greater than the cardinality of a straight line. Now, ...

Can some one help me to setup a program/macro to get the live CPU busy status(Like Viewsys)
Can some one help me to setup a program/macro to get the live CPU busy status(Like Viewsys) as we dont have viewsys or a third party tool like MOMI to watch the CPU busy percentage.. In article <1690da45-ad17-4831-aaf7-1896f866c0a8@g4g2000pri.googlegroups.com>, Manu <withmanu@gmail.com> wrote: >Can some one help me to setup a program/macro to get the live CPU busy >status(Like Viewsys) as we dont have viewsys or a third party tool >like MOMI to watch the CPU busy percentage.. Check ITUGLIB for a program called CPUBUSY. It just displays an ASCII-art bar chart, s...

Can't get labview to write continiously to spreadsheet, writes one column each time program is run, then appends data the next time it is run.
I am attempting to write load cell, linear transducer and time stamp to EXCEL. Due to the limited room in EXCEL I have a sample rate of 10/second. This is accomplished by setting the DAQ assistant to one sample (HW timed) in the acquisition mode of the task timer. A wait timer set at a loop rate of&nbsp;1000 millaseconds is included in the "while" loop to slow the sampling rate down. This works well. Now the data is taken outside of the loop and entered into a "build array" block and then into a "write to spreadsheet" block. This generates only one row of&...

Perceptrons *can* solve XOR, just can't *learn* it : Reference?
"Having multiple perceptrons can actually solve the XOR problem satisfactorily: this is because each perceptron can partition off a linear part of the space itself, and they can then combine their results. [It is ture that] perceptrons can do this but are unable to learn to do it - they have to be explicitly hand-coded." The above quote is taken from: http://www.cs.bham.ac.uk/~rxb/HTML_text/nnets/3/Q8A3.html I am looking for a good discussion/elaboration of the point. So far, I have found only proofs that *if* the problem is linearly separable, then the perceptron learning rule wil...

Re: A sas program can't e-mail its own log, can it?
On Fri, 18 Nov 2005, Pardee, Roy wrote: > When I run the below code, my attempt at having sas e-mail me the log > file gives me this: > > ERROR: Error opening attachment file \\home\pardre1\deleteme.log. > ERROR: File is in use, \\home\pardre1\deleteme.log. > > There's no trick for avoiding this, is there? > > Thanks! > > -Roy > > Here's the code--the program is \\home\pardre1\deleteme.sas > > data gnu ; > do i = 1 to 1000 ; > r = uniform(1234) ; > output ; > end ; > run ; > > proc univariate dat...

One thing PC users can do that Mac users can't:
http://www.thebestpageintheuniverse.net/c.cgi?u=macs_cant So true! Steve Jobs wrote: > http://www.thebestpageintheuniverse.net/c.cgi?u=macs_cant > > So true! You're a day late and a dollar short. Paul On Sat, 24 Mar 2007 19:03:06 +0000, Paul Russell <prussell@sonic.net> wrote: >Steve Jobs wrote: >> http://www.thebestpageintheuniverse.net/c.cgi?u=macs_cant >> >> So true! > >You're a day late and a dollar short. > It's a long way to Tipperary. -- JAF anarchatntlworldfullstopcom http://www.avaaz.org/en/climate_action_g8 On Sa...

Can any body know TCP/IP and UDP programs can be run in VxSim
Hi All! This is suresh I got problem with network programs in vxworks. I am unable to run Tcp/IP and UDP programs in vxworks simulator. Can any body help on this topic. How can i do these programs in TCP/IP and UDP. Not sure which version of VxWorks you're using as you don't say. For Tornado 2.2.1/VxWorks 5.5 follow the steps described in the Tornando Users Guide section 6.5 to build a custom version of the VxSim BSP with network support and install the driver. ...

In tabbed Safari pages, one page can demand attention. Can I turn that off?
I'm using Safari (latest version, latest osx), and have multiple different pages up at the same time in different tabs on the same window. In particular, two of my pages are Yahoo and the Drudge Report. Many times, while I'm reading the Yahoo page (or any other page), the Drudge Report suddenly updates its page (which is fine) but then switches me automatically to its tabbed page...while I'm reading another page. Rude! It seems pretty sneaky of Drudge Report to do that? (smart, maybe, but seems sneaky) Is there a way to turn OFF this behavior? Also, I wonder how it's done. Anyo...