Re: How can I solve semidefinite programming problems? Can any one with
- To: mathgroup at smc.vnet.net
- Subject: [mg114859] Re: How can I solve semidefinite programming problems? Can any one with
- From: Daniel Lichtblau <danl at wolfram.com>
- Date: Mon, 20 Dec 2010 00:41:45 -0500 (EST)
- References: <ieklo8$4uf$1@smc.vnet.net>
On Dec 19, 4:11 am, fmingu <fmi... at 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