1""" 2Copyright 2016 Jaehyun Park, 2017 Robin Verschueren 3 4Licensed under the Apache License, Version 2.0 (the "License"); 5you may not use this file except in compliance with the License. 6You may obtain a copy of the License at 7 8 http://www.apache.org/licenses/LICENSE-2.0 9 10Unless required by applicable law or agreed to in writing, software 11distributed under the License is distributed on an "AS IS" BASIS, 12WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13See the License for the specific language governing permissions and 14limitations under the License. 15""" 16 17import numpy as np 18 19import cvxpy.settings as s 20from cvxpy.constraints import (PSD, SOC, Equality, ExpCone, Inequality, NonPos, 21 Zero,) 22from cvxpy.cvxcore.python import canonInterface 23from cvxpy.expressions.variable import Variable 24from cvxpy.problems.objective import Minimize 25from cvxpy.problems.param_prob import ParamProb 26from cvxpy.reductions import InverseData, Solution 27from cvxpy.reductions.cvx_attr2constr import convex_attributes 28from cvxpy.reductions.matrix_stuffing import MatrixStuffing, extract_mip_idx 29from cvxpy.reductions.utilities import (are_args_affine, group_constraints, 30 lower_equality, lower_ineq_to_nonpos,) 31from cvxpy.utilities.coeff_extractor import CoeffExtractor 32 33 34class ConeDims: 35 """Summary of cone dimensions present in constraints. 36 37 Constraints must be formatted as dictionary that maps from 38 constraint type to a list of constraints of that type. 39 40 Attributes 41 ---------- 42 zero : int 43 The dimension of the zero cone. 44 nonpos : int 45 The dimension of the non-positive cone. 46 exp : int 47 The number of 3-dimensional exponential cones 48 soc : list of int 49 A list of the second-order cone dimensions. 50 psd : list of int 51 A list of the positive semidefinite cone dimensions, where the 52 dimension of the PSD cone of k by k matrices is k. 53 """ 54 def __init__(self, constr_map) -> None: 55 self.zero = int(sum(c.size for c in constr_map[Zero])) 56 self.nonpos = int(sum(c.size for c in constr_map[NonPos])) 57 self.exp = int(sum(c.num_cones() for c in constr_map[ExpCone])) 58 self.soc = [int(dim) for c in constr_map[SOC] for dim in c.cone_sizes()] 59 self.psd = [int(c.shape[0]) for c in constr_map[PSD]] 60 61 def __repr__(self) -> str: 62 return "(zero: {0}, nonpos: {1}, exp: {2}, soc: {3}, psd: {4})".format( 63 self.zero, self.nonpos, self.exp, self.soc, self.psd) 64 65 def __str__(self) -> str: 66 """String representation. 67 """ 68 return ("%i equalities, %i inequalities, %i exponential cones, \n" 69 "SOC constraints: %s, PSD constraints: %s.") % (self.zero, 70 self.nonpos, 71 self.exp, 72 self.soc, 73 self.psd) 74 75 def __getitem__(self, key): 76 if key == s.EQ_DIM: 77 return self.zero 78 elif key == s.LEQ_DIM: 79 return self.nonpos 80 elif key == s.EXP_DIM: 81 return self.exp 82 elif key == s.SOC_DIM: 83 return self.soc 84 elif key == s.PSD_DIM: 85 return self.psd 86 else: 87 raise KeyError(key) 88 89 90class ParamQuadProg(ParamProb): 91 """Represents a parameterized quadratic program. 92 93 minimize x'Px + q^Tx + d 94 subject to (in)equality_constr1(A_1*x + b_1, ...) 95 ... 96 (in)equality_constrK(A_i*x + b_i, ...) 97 98 99 The constant offsets d and b are the last column of c and A. 100 """ 101 def __init__(self, P, q, x, A, 102 variables, 103 var_id_to_col, 104 constraints, 105 parameters, 106 param_id_to_col, 107 formatted: bool = False) -> None: 108 self.P = P 109 self.q = q 110 self.x = x 111 self.A = A 112 113 # Form a reduced representation of A, for faster application of 114 # parameters. 115 if np.prod(A.shape) != 0: 116 reduced_A, indices, indptr, shape = ( 117 canonInterface.reduce_problem_data_tensor(A, self.x.size) 118 ) 119 self.reduced_A = reduced_A 120 self.problem_data_index_A = (indices, indptr, shape) 121 else: 122 self.reduced_A = A 123 self.problem_data_index_A = None 124 self._A_mapping_nonzero = None 125 126 # Form a reduced representation of P, for faster application of 127 # parameters. 128 if np.prod(P.shape) != 0: 129 reduced_P, indices, indptr, shape = ( 130 canonInterface.reduce_problem_data_tensor(P, self.x.size, quad_form=True) 131 ) 132 self.reduced_P = reduced_P 133 self.problem_data_index_P = (indices, indptr, shape) 134 else: 135 self.reduced_P = P 136 self.problem_data_index_P = None 137 self._P_mapping_nonzero = None 138 139 self.constraints = constraints 140 self.constr_size = sum([c.size for c in constraints]) 141 self.parameters = parameters 142 self.param_id_to_col = param_id_to_col 143 self.id_to_param = {p.id: p for p in self.parameters} 144 self.param_id_to_size = {p.id: p.size for p in self.parameters} 145 self.total_param_size = sum([p.size for p in self.parameters]) 146 # TODO technically part of inverse data. 147 self.variables = variables 148 self.var_id_to_col = var_id_to_col 149 self.id_to_var = {v.id: v for v in self.variables} 150 # whether this param cone prog has been formatted for a solver 151 self.formatted = formatted 152 153 def is_mixed_integer(self) -> bool: 154 """Is the problem mixed-integer?""" 155 return self.x.attributes['boolean'] or \ 156 self.x.attributes['integer'] 157 158 def apply_parameters(self, id_to_param_value=None, zero_offset: bool = False, 159 keep_zeros: bool = False): 160 """Returns A, b after applying parameters (and reshaping). 161 162 Args: 163 id_to_param_value: (optional) dict mapping parameter ids to values 164 zero_offset: (optional) if True, zero out the constant offset in the 165 parameter vector 166 keep_zeros: (optional) if True, store explicit zeros in A where 167 parameters are affected 168 """ 169 def param_value(idx): 170 return (np.array(self.id_to_param[idx].value) if id_to_param_value 171 is None else id_to_param_value[idx]) 172 param_vec = canonInterface.get_parameter_vector( 173 self.total_param_size, 174 self.param_id_to_col, 175 self.param_id_to_size, 176 param_value, 177 zero_offset=zero_offset) 178 179 if keep_zeros and self._P_mapping_nonzero is None: 180 self._P_mapping_nonzero = canonInterface.A_mapping_nonzero_rows( 181 self.P, self.x.size) 182 P, _ = canonInterface.get_matrix_from_tensor( 183 self.reduced_P, param_vec, self.x.size, 184 nonzero_rows=self._P_mapping_nonzero, 185 with_offset=False, 186 problem_data_index=self.problem_data_index_P) 187 188 q, d = canonInterface.get_matrix_from_tensor( 189 self.q, param_vec, self.x.size, with_offset=True) 190 q = q.toarray().flatten() 191 if keep_zeros and self._A_mapping_nonzero is None: 192 self._A_mapping_nonzero = canonInterface.A_mapping_nonzero_rows( 193 self.A, self.x.size) 194 A, b = canonInterface.get_matrix_from_tensor( 195 self.reduced_A, param_vec, self.x.size, 196 nonzero_rows=self._A_mapping_nonzero, 197 with_offset=True, 198 problem_data_index=self.problem_data_index_A) 199 return P, q, d, A, np.atleast_1d(b) 200 201 def apply_param_jac(self, delP, delq, delA, delb, active_params=None): 202 """Multiplies by Jacobian of parameter mapping. 203 204 Assumes delA is sparse. 205 206 Returns: 207 A dictionary param.id -> dparam 208 """ 209 raise NotImplementedError 210 211 def split_solution(self, sltn, active_vars=None): 212 """Splits the solution into individual variables. 213 """ 214 raise NotImplementedError 215 216 def split_adjoint(self, del_vars=None): 217 """Adjoint of split_solution. 218 """ 219 raise NotImplementedError 220 221 222class QpMatrixStuffing(MatrixStuffing): 223 """Fills in numeric values for this problem instance. 224 225 Outputs a DCP-compliant minimization problem with an objective 226 of the form 227 QuadForm(x, p) + q.T * x 228 and Zero/NonPos constraints, both of which exclusively carry 229 affine arguments. 230 """ 231 232 @staticmethod 233 def accepts(problem): 234 return (type(problem.objective) == Minimize 235 and problem.objective.is_quadratic() 236 and problem.is_dcp() 237 and not convex_attributes(problem.variables()) 238 and all(type(c) in [Zero, NonPos, Equality, Inequality] 239 for c in problem.constraints) 240 and are_args_affine(problem.constraints) 241 and problem.is_dpp()) 242 243 def stuffed_objective(self, problem, extractor): 244 # extract to 0.5 * x.T * P * x + q.T * x + r 245 expr = problem.objective.expr.copy() 246 params_to_P, params_to_q = extractor.quad_form(expr) 247 # Handle 0.5 factor. 248 params_to_P = 2*params_to_P 249 250 # concatenate all variables in one vector 251 boolean, integer = extract_mip_idx(problem.variables()) 252 x = Variable(extractor.x_length, boolean=boolean, integer=integer) 253 254 return params_to_P, params_to_q, x 255 256 def apply(self, problem): 257 """See docstring for MatrixStuffing.apply""" 258 inverse_data = InverseData(problem) 259 # Form the constraints 260 extractor = CoeffExtractor(inverse_data) 261 params_to_P, params_to_q, flattened_variable = self.stuffed_objective( 262 problem, extractor) 263 # Lower equality and inequality to Zero and NonPos. 264 cons = [] 265 for con in problem.constraints: 266 if isinstance(con, Equality): 267 con = lower_equality(con) 268 elif isinstance(con, Inequality): 269 con = lower_ineq_to_nonpos(con) 270 cons.append(con) 271 272 # Reorder constraints to Zero, NonPos. 273 constr_map = group_constraints(cons) 274 ordered_cons = constr_map[Zero] + constr_map[NonPos] 275 inverse_data.cons_id_map = {con.id: con.id for con in ordered_cons} 276 277 inverse_data.constraints = ordered_cons 278 # Batch expressions together, then split apart. 279 expr_list = [arg for c in ordered_cons for arg in c.args] 280 params_to_Ab = extractor.affine(expr_list) 281 282 inverse_data.minimize = type(problem.objective) == Minimize 283 new_prob = ParamQuadProg(params_to_P, 284 params_to_q, 285 flattened_variable, 286 params_to_Ab, 287 problem.variables(), 288 inverse_data.var_offsets, 289 ordered_cons, 290 problem.parameters(), 291 inverse_data.param_id_map) 292 return new_prob, inverse_data 293 294 def invert(self, solution, inverse_data): 295 """Retrieves the solution to the original problem.""" 296 var_map = inverse_data.var_offsets 297 # Flip sign of opt val if maximize. 298 opt_val = solution.opt_val 299 if solution.status not in s.ERROR and not inverse_data.minimize: 300 opt_val = -solution.opt_val 301 302 primal_vars, dual_vars = {}, {} 303 if solution.status not in s.SOLUTION_PRESENT: 304 return Solution(solution.status, opt_val, primal_vars, dual_vars, 305 solution.attr) 306 307 # Split vectorized variable into components. 308 x_opt = list(solution.primal_vars.values())[0] 309 for var_id, offset in var_map.items(): 310 shape = inverse_data.var_shapes[var_id] 311 size = np.prod(shape, dtype=int) 312 primal_vars[var_id] = np.reshape(x_opt[offset:offset+size], shape, 313 order='F') 314 315 # Remap dual variables if dual exists (problem is convex). 316 if solution.dual_vars is not None: 317 # Giant dual variable. 318 dual_var = list(solution.dual_vars.values())[0] 319 offset = 0 320 for constr in inverse_data.constraints: 321 # QP constraints can only have one argument. 322 dual_vars[constr.id] = np.reshape( 323 dual_var[offset:offset+constr.args[0].size], 324 constr.args[0].shape, 325 order='F' 326 ) 327 offset += constr.size 328 329 return Solution(solution.status, opt_val, primal_vars, dual_vars, 330 solution.attr) 331