Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitc0fd4b2

Browse files
committed
Upload sdpap source fromhttp://sdpa.sourceforge.net
1 parentbb0e142 commitc0fd4b2

32 files changed

+7335
-0
lines changed

‎CITATIONS.bib

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
@article{doi:10.1080/1055678031000118482,
2+
author ="Yamashita, Makoto
3+
and Fujisawa, Katsuki
4+
and Kojima, Masakazu",
5+
title ="Implementation and evaluation of SDPA 6.0 (Semidefinite Programming Algorithm 6.0)",
6+
journal ="Optimization Methods and Software",
7+
volume ="18",
8+
number ="4",
9+
pages ="491-505",
10+
year ="2003",
11+
publisher ="Taylor & Francis",
12+
doi ="10.1080/1055678031000118482",
13+
URL ="https://doi.org/10.1080/1055678031000118482",
14+
eprint ="https://doi.org/10.1080/1055678031000118482"
15+
}
16+
17+
@Inbook{Yamashita2012,
18+
author ="Yamashita, Makoto
19+
and Fujisawa, Katsuki
20+
and Fukuda, Mituhiro
21+
and Kobayashi, Kazuhiro
22+
and Nakata, Kazuhide
23+
and Nakata, Maho",
24+
editor ="Anjos, Miguel F.
25+
and Lasserre, Jean B.",
26+
title ="Latest Developments in the SDPA Family for Solving Large-Scale SDPs",
27+
bookTitle ="Handbook on Semidefinite, Conic and Polynomial Optimization",
28+
year ="2012",
29+
publisher ="Springer US",
30+
address ="Boston, MA",
31+
pages ="687--713",
32+
isbn ="978-1-4614-0769-0",
33+
doi ="10.1007/978-1-4614-0769-0_24",
34+
url ="https://doi.org/10.1007/978-1-4614-0769-0_24"
35+
}

‎README.md

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
#SDPA for Python
2+
3+
`sdpa-python` is a Python 3 wrapper for SDPA (SemiDefinite Programming Algorithm). SDPA is a software package for solving general SDPs based on primal-dual interior-point methods with the HRVW/KSH/M search direction[1].
4+
5+
This package is a Python 3 port of SDPA-P, the Python 2 based wrapper originally written by**Kenta KATO** provided at the[official SDPA website](http://sdpa.sourceforge.net/download.html). This repository aims to provide Python 3 support for SDPA. It will be accompanied with documentation to allow users to link SDPA against modern BLAS libraries (i.e. Intel MKL, Apple Accelerate and NVIDIA cuBLAS).
6+
7+
For installation instructions, please see the documentation website.
8+
9+
##History
10+
11+
SDPA was officially developed between 1995 and 2012 by**Makoto Yamashita, Katsuki Fujisawa, Masakazu Kojima, Mituhiro Fukuda, Kazuhiro Kobayashi, Kazuhide Nakata and Maho Nakata**[1][2][3]. The[official SDPA website](http://sdpa.sourceforge.net/download.html) contains an unmaintained version of SDPA.
12+
13+
Owing to it's implementation that uses LAPACK for numerical linear algebra for dense matrix computation[1], it can be linked against modern LAPACK implementations, providing performance gains on a variety of architectures.
14+
15+
##References
16+
17+
If you are using SDPA for Python in your research, please cite SDPA by citing the following papers and book chapters. The BibTex has been provided in`CITATIONS.bib`.
18+
19+
[1] Makoto Yamashita, Katsuki Fujisawa and Masakazu Kojima, "Implementation and evaluation of SDPA 6.0 (Semidefinite Programming Algorithm 6.0),"*Optimization Methods and Software, vol. 18, no. 4, pp. 491–505*, 2003, doi:[10.1080/1055678031000118482](https://doi.org/10.1080/1055678031000118482).
20+
21+
[2] Makoto Yamashita, Katsuki Fujisawa, Kazuhide Nakata, Maho Nakata, Mituhiro Fukuda, Kazuhiro Kobayashi, and Kazushige Goto, "A high-performance software package for semidefinite programs: SDPA 7,"*[Research Report B-460](http://www.optimization-online.org/DB_HTML/2010/01/2531.html) Dept. of Mathematical and Computing Science, Tokyo Institute of Technology, Tokyo, Japan, September*, 2010.
22+
23+
[3] Makoto Yamashita, Katsuki Fujisawa, Mituhiro Fukuda, Kazuhiro Kobayashi, Kazuhide Nakata and Maho Nakata, “Latest Developments in the SDPA Family for Solving Large-Scale SDPs,” in*Handbook on Semidefinite, Conic and Polynomial Optimization, M. F. Anjos and J. B. Lasserre, Eds. Boston, MA: Springer US*, 2012, pp. 687–713. doi:[10.1007/978-1-4614-0769-0_24](https://doi.org/10.1007/978-1-4614-0769-0_24).

‎sdpap/__init__.py

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
"""__init__.py
2+
Initialization file of sdpap
3+
4+
December 2010, Kenta KATO
5+
"""
6+
7+
fromsdpapimport*
8+
fromfileioimport*
9+
fromparamimport*
10+
fromsymconeimport*
11+
fromsdpaputilsimport*
12+
13+
__all__=filter(lambdas:nots.startswith('_'),dir())

‎sdpap/convert.py

Lines changed: 324 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,324 @@
1+
#!/usr/bin/env python
2+
"""sdpap.convert.py
3+
4+
Convert CLP format to SeDuMi format
5+
This is the module of sdpap.
6+
7+
September 2010, Kenta KATO
8+
"""
9+
10+
fromsymconeimportSymCone
11+
fromscipy.sparseimportcsc_matrix,bmat,eye
12+
fromscipyimportsparse
13+
14+
15+
defclp_toLMI(A,b,c,K,J):
16+
"""Convert from CLP format to LMI standard form (SeDuMi dual format).
17+
18+
Args:
19+
A, b, c, K, J: CLP format
20+
21+
Returns:
22+
A tuple (A2, b2, c2, K2, J2, map_sdpIndex). Each members are:
23+
LMI standard form in SeDuMi dual format, (A2, b2, c2, K2, J2)
24+
J2 has only an attribute 'f'
25+
Index mapping from converted matrix to original matrix map_sdpIndex
26+
"""
27+
# Type check
28+
ifnotsparse.isspmatrix_csc(A):
29+
A=A.tocsc()
30+
ifnotsparse.isspmatrix_csc(b):
31+
b=b.tocsc()
32+
ifnotsparse.isspmatrix_csc(c):
33+
c=c.tocsc()
34+
ifnotK.check_validity()ornotJ.check_validity():
35+
print('clp_toLMI(): K or J is invalid.')
36+
return
37+
38+
# Get size
39+
size_m,size_n=A.shape
40+
41+
K_f=K.f
42+
K_l=K.l
43+
K_q=sum(K.q)
44+
K_s=sum([i**2foriinK.s])
45+
46+
J_f=J.f
47+
J_l=J.l
48+
J_q=sum(J.q)
49+
J_s=sum([i**2foriinJ.s])
50+
51+
# ----------------------------------------
52+
# Make converted K.s part
53+
# ----------------------------------------
54+
iflen(K.s)>0:
55+
# Make index mapping from converted index to original index
56+
map_sdpIndex= [0]*sum([k* (k+1)/2forkinK.s])
57+
offset=0
58+
forkinK.s:
59+
foriinrange(k):
60+
forjinrange(i):
61+
idx1=i*k+j
62+
idx2=j*k+i
63+
map_sdpIndex[i* (i+1)/2+j+offset]= (idx1,idx2)
64+
# i == j case
65+
idx=i*k+i
66+
map_sdpIndex[i* (i+1)/2+i+offset]= (idx,idx)
67+
offset+=k* (k+1)/2
68+
69+
# Split matrix
70+
c_flq=c[0:(K_f+K_l+K_q), :]
71+
c_s=c[(K_f+K_l+K_q):, :]
72+
A_flq=A[:,0:(K_f+K_l+K_q)]
73+
A_s=A[:, (K_f+K_l+K_q):]
74+
75+
# To make converted matrix
76+
convcs_row= []
77+
convcs_val= []
78+
convAs_row= []
79+
convAs_col= []
80+
convAs_val= []
81+
addAs_row= []
82+
addAs_col= []
83+
col_ptr=0
84+
offset_row=0
85+
offset_col=0
86+
else:
87+
map_sdpIndex=None
88+
89+
forsDiminK.s:
90+
A_block=A_s[:,col_ptr:(col_ptr+sDim**2)]
91+
c_block=c_s[col_ptr:(col_ptr+sDim**2)]
92+
93+
# Make conv_cs
94+
for (row,val)inzip(c_block.nonzero()[0],c_block.data):
95+
i=row//sDim
96+
j=row%sDim
97+
ifi>=j:
98+
convcs_row.append(i* (i+1)/2+j+offset_col)
99+
convcs_val.append(val*2ifi>jelseval)
100+
101+
# Make conv_As
102+
for (row,col,val)inzip(A_block.nonzero()[0],A_block.nonzero()[1],
103+
A_block.data):
104+
i=col//sDim
105+
j=col%sDim
106+
ifi>=j:
107+
convAs_row.append(row)
108+
convAs_col.append(i* (i+1)/2+j+offset_col)
109+
convAs_val.append(val*2ifi>jelseval)
110+
111+
# Make add_As
112+
foriinrange(sDim):
113+
forjinrange(i):
114+
addAs_row.extend([i*sDim+j+offset_row,
115+
j*sDim+i+offset_row])
116+
idx=i* (i+1)/2+j+offset_col
117+
addAs_col.extend([idx,idx])
118+
# i == j case
119+
addAs_row.append(i*sDim+i+offset_row)
120+
addAs_col.append(i* (i+1)/2+i+offset_col)
121+
122+
col_ptr+=sDim**2
123+
offset_row+=sDim**2
124+
offset_col+=sDim* (sDim+1)/2
125+
126+
# ----------------------------------------
127+
# Make converted matrix
128+
# ----------------------------------------
129+
# A2
130+
ifK_s>0:
131+
newJ_s=offset_row
132+
newK_s=offset_col
133+
sub_A=csc_matrix((convAs_val, (convAs_row,convAs_col)),
134+
shape=(size_m,newK_s))
135+
sub_As=csc_matrix(([1.0]*len(addAs_row), (addAs_row,addAs_col)),
136+
shape=(newJ_s,newK_s))
137+
new_A=bmat([[A_flq,sub_A]])
138+
else:
139+
newJ_s=0
140+
newK_s=0
141+
new_A=A
142+
143+
ifnotsparse.isspmatrix_csc(new_A):
144+
new_A=new_A.tocsc()
145+
146+
list_A2= []
147+
list_c2= []
148+
ifJ_f>0:
149+
A_f=new_A[0:(J_f), :]
150+
list_A2.append(-A_f.T)
151+
b_f=b[0:(J_f), :]
152+
list_c2.append([-b_f])
153+
154+
ifJ_l>0:
155+
A_l=new_A[(J_f):(J_f+J_l), :]
156+
list_A2.append(-A_l.T)
157+
b_l=b[(J_f):(J_f+J_l), :]
158+
list_c2.append([-b_l])
159+
160+
ifK_l>0:
161+
list_subAl= []
162+
ifK_f>0:
163+
list_subAl.append([csc_matrix((K_f,K_l))])
164+
list_subAl.append([eye(K_l,K_l,format='csc')])
165+
ifK_q+newK_s>0:
166+
list_subAl.append([csc_matrix((K_q+newK_s,K_l))])
167+
sub_Al=bmat(list_subAl)
168+
list_A2.append(-sub_Al)
169+
list_c2.append([csc_matrix((K_l,1))])
170+
171+
ifJ_q>0:
172+
A_q=new_A[(J_f+J_l):(J_f+J_l+J_q), :]
173+
list_A2.append(-A_q.T)
174+
b_q=b[(J_f+J_l):(J_f+J_l+J_q), :]
175+
list_c2.append([-b_q])
176+
177+
ifK_q>0:
178+
list_subAq= []
179+
ifK_f+K_l>0:
180+
list_subAq.append([csc_matrix((K_f+K_l,K_q))])
181+
list_subAq.append([eye(K_q,K_q,format='csc')])
182+
ifK_s>0:
183+
list_subAq.append([csc_matrix((newK_s,K_q))])
184+
sub_Aq=bmat(list_subAq)
185+
list_A2.append(-sub_Aq)
186+
list_c2.append([csc_matrix((K_q,1))])
187+
188+
ifJ_s>0:
189+
A_s=new_A[(J_f+J_l+J_q):, :]
190+
list_A2.append(-A_s.T)
191+
b_s=b[(J_f+J_l+J_q):, :]
192+
list_c2.append([-b_s])
193+
194+
ifK_s>0:
195+
list_subAs= []
196+
ifK_f+K_l+K_q>0:
197+
list_subAs.append([csc_matrix((K_f+K_l+K_q,K_s))])
198+
list_subAs.append([sub_As.T])
199+
sub_As=bmat(list_subAs)
200+
list_A2.append(-sub_As)
201+
list_c2.append([csc_matrix((K_s,1))])
202+
203+
A2=bmat([list_A2])
204+
c2=bmat(list_c2)
205+
206+
ifnewK_s>0:
207+
conv_cs=csc_matrix((convcs_val, (convcs_row, [0]*len(convcs_row))),
208+
shape=(newK_s,1))
209+
b2=-bmat([[c_flq],
210+
[conv_cs]])
211+
else:
212+
b2=-c
213+
214+
K2=SymCone()
215+
K2.f=J.f
216+
K2.l=J.l+K.l
217+
K2.q=J.q+K.q
218+
K2.s=J.s+K.s
219+
220+
J2=SymCone()
221+
J2.f=A2.shape[0]
222+
223+
returnA2,b2,c2,K2,J2,map_sdpIndex
224+
225+
226+
defclp_toEQ(A,b,c,K,J):
227+
"""Convert from CLP format to Equality standard form (Sedumi primal format)
228+
229+
THIS FUNCTION HAS NOT IMPLEMENTED YET.
230+
231+
Args:
232+
A, b, c, K, J: CLP format
233+
234+
Returns:
235+
Equality standard form in SeDuMi primal format, (A2, b2, c2, K2, J2)
236+
"""
237+
##################################################
238+
# Under construction
239+
##################################################
240+
print('THIS FUNCTION HAS NOT IMPLEMENTED YET.')
241+
returnA2,b2,c2,K2,J2
242+
243+
244+
defresult_fromLMI(x2,y2,K,J,map_sdpIndex):
245+
"""Get result of CLP from result of converted problem by clp_toLMI().
246+
247+
Args:
248+
x2, y2: Result of converted problem by clp_toLMI()
249+
K, J : SymCone of CLP
250+
map_sdpIndex: Index mapping from converted matrix to original matrix
251+
252+
Returns:
253+
Result of CLP, (x, y)
254+
"""
255+
# Type check
256+
ifnotsparse.isspmatrix_csc(x2):
257+
x2=x2.tocsc()
258+
ifnotsparse.isspmatrix_csc(y2):
259+
y2=y2.tocsc()
260+
261+
iflen(K.s)>0:
262+
K_f=K.f
263+
K_l=K.l
264+
K_q=sum(K.q)
265+
K_s=sum([i**2foriinK.s])
266+
267+
x_flq=y2[:(K.f+K.l+K_q)]
268+
x_s=y2[(K.f+K.l+K_q):]
269+
x_row= []
270+
x_val= []
271+
for (row,val)inzip(x_s.nonzero()[0],x_s.data):
272+
(idx1,idx2)=map_sdpIndex[row]
273+
ifidx1!=idx2:
274+
x_row.extend([idx1,idx2])
275+
x_val.extend([val,val])
276+
else:
277+
x_row.append(idx1)
278+
x_val.append(val)
279+
280+
x=bmat([[x_flq],
281+
[csc_matrix((x_val, (x_row, [0]*len(x_row))),
282+
shape=(K_s,1))]])
283+
else:
284+
x=y2
285+
286+
size_Jq=sum(J.q)
287+
size_Js=sum([z**2forzinJ.s])
288+
size_Kq=sum(K.q)
289+
290+
y_list= []
291+
ifJ.f+J.l>0:
292+
yfl=x2[:(J.f+J.l)]
293+
y_list.append([yfl])
294+
295+
ifsize_Jq>0:
296+
yq=x2[(J.f+J.l+K.l):(J.f+J.l+K.l+size_Jq)]
297+
y_list.append([yq])
298+
299+
ifsize_Js>0:
300+
ys=x2[(J.f+J.l+K.l+size_Jq+size_Kq):
301+
(J.f+J.l+K.l+size_Jq+size_Kq+size_Js)]
302+
y_list.append([ys])
303+
304+
y=bmat(y_list)
305+
returnx,y
306+
307+
defresult_fromEQ(x2,y2,K,J):
308+
"""Get result of CLP from result of converted problem by clp_toEQ().
309+
310+
THIS FUNCTION HAS NOT IMPLEMENTED YET.
311+
312+
Args:
313+
x2, y2: Result of converted problem by clp_toEQ()
314+
K, J : SymCone of CLP
315+
316+
Returns:
317+
x, y : Result of CLP, (x, y)
318+
"""
319+
##################################################
320+
# Under construction
321+
##################################################
322+
print('THIS FUNCTION HAS NOT IMPLEMENTED YET.')
323+
returnx,y
324+

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp