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