Hide keyboard shortcuts

Hot-keys on this page

r m x p   toggle line displays

j k   next/prev highlighted chunk

0   (zero) top of page

1   (one) first highlighted chunk

1# ------------------------------------------------------------------------------ 

2# Copyright (C) 2018-2019 Maximilian Stahlberg 

3# 

4# This file is part of PICOS. 

5# 

6# PICOS is free software: you can redistribute it and/or modify it under the 

7# terms of the GNU General Public License as published by the Free Software 

8# Foundation, either version 3 of the License, or (at your option) any later 

9# version. 

10# 

11# PICOS is distributed in the hope that it will be useful, but WITHOUT ANY 

12# WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR 

13# A PARTICULAR PURPOSE. See the GNU General Public License for more details. 

14# 

15# You should have received a copy of the GNU General Public License along with 

16# this program. If not, see <http://www.gnu.org/licenses/>. 

17# ------------------------------------------------------------------------------ 

18 

19"""Linear matrix inequalities.""" 

20 

21from collections import namedtuple 

22 

23from .. import glyphs, settings 

24from ..apidoc import api_end, api_start 

25from ..caching import cached_property 

26from .constraint import ConicConstraint, ConstraintConversion 

27 

28_API_START = api_start(globals()) 

29# ------------------------------- 

30 

31 

32class LMIConstraint(ConicConstraint): 

33 """Linear matrix inequality. 

34 

35 An inequality with respect to the positive semidefinite cone, also known as 

36 a Linear Matrix Inequality (LMI) or an SDP constraint. 

37 """ 

38 

39 def __init__(self, lhs, relation, rhs, customString=None): 

40 """Construct a :class:`LMIConstraint`. 

41 

42 :param ~picos.expressions.AffineExpression lhs: 

43 Left hand side expression. 

44 :param str relation: 

45 Constraint relation symbol. 

46 :param ~picos.expressions.AffineExpression rhs: 

47 Right hand side expression. 

48 :param str customString: 

49 Optional string description. 

50 """ 

51 from ..expressions import AffineExpression 

52 

53 required_type = self._required_type() 

54 

55 assert isinstance(lhs, required_type) 

56 assert isinstance(rhs, required_type) 

57 assert relation in self.LE + self.GE 

58 

59 if lhs.shape != rhs.shape: 

60 raise ValueError("Failed to form a constraint: " 

61 "Expressions have incompatible dimensions.") 

62 

63 if lhs.shape[0] != lhs.shape[1]: 

64 raise ValueError("Failed to form a constraint: " 

65 "LMI expressions are not square.") 

66 

67 self.lhs = lhs 

68 self.rhs = rhs 

69 self.relation = relation 

70 

71 psd = self.psd 

72 if not psd.hermitian: 

73 needed = "symmetric" if required_type is AffineExpression \ 

74 else "hermitian" 

75 

76 raise ValueError("Failed to form a constraint: {} is not " 

77 "necessarily {}. Consider a constraint on {} instead.".format( 

78 psd.string, needed, glyphs.Tr("{}.hermitianized")(psd.string))) 

79 

80 super(LMIConstraint, self).__init__( 

81 self._get_type_term(), customString, printSize=True) 

82 

83 def _get_type_term(self): 

84 return "LMI" 

85 

86 def _required_type(self): 

87 from ..expressions import AffineExpression 

88 

89 return AffineExpression 

90 

91 @cached_property 

92 def semidefVar(self): 

93 """The variable posed positive semidefinite, or :obj:`None`.""" 

94 from ..expressions import HermitianVariable, SymmetricVariable 

95 from ..expressions.data import cvxopt_equals 

96 

97 psd = self.psd 

98 

99 if len(psd._linear_coefs) == 1 and not psd._constant_coef: 

100 var, coef = next(iter(psd._linear_coefs.items())) 

101 

102 if isinstance(var, (SymmetricVariable, HermitianVariable)) \ 

103 and cvxopt_equals(coef, var._vec.identity, 

104 relTol=settings.RELATIVE_HERMITIANNESS_TOLERANCE): 

105 return var 

106 

107 return None 

108 

109 @property 

110 def smaller(self): 

111 """The smaller-or-equal side expression.""" 

112 return self.rhs if self.relation == self.GE else self.lhs 

113 

114 @property 

115 def greater(self): 

116 """The greater-or-equal side expression.""" 

117 return self.lhs if self.relation == self.GE else self.rhs 

118 

119 @cached_property 

120 def psd(self): 

121 """The matrix expression posed to be positive semidefinite.""" 

122 if self.relation == self.GE: 

123 return self.lhs - self.rhs 

124 else: 

125 return self.rhs - self.lhs 

126 

127 @cached_property 

128 def nsd(self): 

129 """The matrix expression posed to be negative semidefinite.""" 

130 if self.relation == self.GE: 

131 return self.rhs - self.lhs 

132 else: 

133 return self.lhs - self.rhs 

134 

135 nnd = psd 

136 npd = nsd 

137 

138 @cached_property 

139 def conic_membership_form(self): 

140 """Implement for :class:`~.constraint.ConicConstraint`.""" 

141 from ..expressions import PositiveSemidefiniteCone 

142 

143 element = self.psd.svec 

144 return element, PositiveSemidefiniteCone(dim=len(element)) 

145 

146 Subtype = namedtuple("Subtype", ("diag",)) 

147 

148 def _subtype(self): 

149 return self.Subtype(self.lhs.shape[0]) 

150 

151 @classmethod 

152 def _cost(cls, subtype): 

153 n = subtype.diag 

154 return n*(n + 1)//2 

155 

156 def _expression_names(self): 

157 yield "lhs" 

158 yield "rhs" 

159 

160 def _str(self): 

161 if self.relation == self.LE: 

162 return glyphs.psdle(self.lhs.string, self.rhs.string) 

163 else: 

164 return glyphs.psdge(self.lhs.string, self.rhs.string) 

165 

166 def _get_size(self): 

167 return self.lhs.shape 

168 

169 def _get_slack(self): 

170 return self.psd.safe_value 

171 

172 

173class ComplexLMIConstraint(LMIConstraint): 

174 """Complex linear matrix inequality.""" 

175 

176 class RealConversion(ConstraintConversion): 

177 """Complex LMI to real LMI conversion.""" 

178 

179 @classmethod 

180 def predict(cls, subtype, options): 

181 """Implement :meth:`~.constraint.ConstraintConversion.predict`.""" 

182 n = subtype.diag 

183 

184 yield ("con", LMIConstraint.make_type(diag=2*n), 1) 

185 

186 @classmethod 

187 def convert(cls, con, options): 

188 """Implement :meth:`~.constraint.ConstraintConversion.convert`.""" 

189 from ..expressions.algebra import block 

190 from ..modeling import Problem 

191 

192 P = Problem() 

193 Z = con.psd 

194 P.add_constraint(block([[Z.real, -Z.imag], [Z.imag, Z.real]]) >> 0) 

195 

196 return P 

197 

198 @classmethod 

199 def dual(cls, auxVarPrimals, auxConDuals, options): 

200 """Implement :meth:`~.constraint.ConstraintConversion.dual`.""" 

201 assert len(auxConDuals) == 1 

202 

203 auxConDual = auxConDuals[0] 

204 if auxConDual is None: 

205 return None 

206 else: 

207 assert auxConDual.size[0] == auxConDual.size[1] 

208 n = auxConDual.size[0] // 2 

209 assert 2*n == auxConDual.size[0] 

210 A = auxConDual[:n, :n] 

211 B = auxConDual[:n, n:] 

212 D = auxConDual[n:, n:] 

213 return (A + 1j*B) + (D + 1j*B).H 

214 

215 def _get_type_term(self): 

216 return "Complex LMI" 

217 

218 def _required_type(self): 

219 from ..expressions import ComplexAffineExpression 

220 

221 return ComplexAffineExpression 

222 

223 @classmethod 

224 def _cost(cls, subtype): 

225 return subtype.diag**2 

226 

227 

228# -------------------------------------- 

229__all__ = api_end(_API_START, globals())