cvxpy
cvxpy copied to clipboard
cvxpy
Presence of certain functions of a matrix Parameter as a constant offset to quadratic objective function leads to compilation failure in QpMatrixStuffing
Describe the bug Objective functions involving constant functions of a matrix parameter sometimes lead to a compilation failure. Specifically, the AddExpression object has no attribute '_lazy_canonical_form.' This is very opaque so I don't really understand what is causing it; it seems to be similar to #2460.
I can workaround by doing some extra logic to realize that the parameter is ending up as a constant offset to the objective and just leaving it out, but the behavior is unexpected (constant offsets change nothing, and the problem is identified as DPP).
To Reproduce This script has a constant function of a scalar parameter as an offset to the objective function and compiles and solves just fine:
n=2
x = cp.Variable(n, nonneg=True)
y = cp.Variable(n, nonneg=True)
p=cp.Parameter(())
p.value=1
objective_ok = cp.sum_squares(x + y)-2*p
problem_ok = cp.Problem(cp.Minimize(objective_ok))
problem_ok.solve(verbose=True)
This script is equivalent except the constant offset involves a matrix parameter instead and fails:
n = 2
x = cp.Variable(n, nonneg=True)
y = cp.Variable(n, nonneg=True)
P = cp.Parameter((n,n))
P.value=np.array([[1.0,0.0],[0.0,1.0]])
objective = cp.sum_squares(x + y)-2*cp.log_det(P)
problem = cp.Problem(cp.Minimize(objective))
problem.solve(verbose=True)
using cp.lambda_min,cp.lambda_sum_smallest also fails in the same way. cp.lambda_max runs fine, as does cp.sum_squares, cp.sum, cp.log_sum_exp, cp.min. I hypothesize that the issue is concave functions of unknown sign?
Expected behavior The DPP problem should compile down to OSQP and solve.
Output Run:
n = 2
x = cp.Variable(n, nonneg=True)
y = cp.Variable(n, nonneg=True)
P = cp.Parameter((n,n))
P.value=np.array([[1.0,0.0],[0.0,1.0]])
objective = cp.sum_squares(x + y)-2*cp.log_det(P)
problem = cp.Problem(cp.Minimize(objective))
problem.solve(verbose=True)
Receive:
===============================================================================
CVXPY
v1.7.2
===============================================================================
(CVXPY) Oct 29 06:29:30 PM: Your problem has 4 variables, 0 constraints, and 4 parameters.
(CVXPY) Oct 29 06:29:30 PM: It is compliant with the following grammars: DCP, DQCP
(CVXPY) Oct 29 06:29:30 PM: CVXPY will first compile your problem; then, it will invoke a numerical solver to obtain a solution.
(CVXPY) Oct 29 06:29:30 PM: Your problem is compiled with the CPP canonicalization backend.
-------------------------------------------------------------------------------
Compilation
-------------------------------------------------------------------------------
(CVXPY) Oct 29 06:29:30 PM: Compiling problem (target solver=OSQP).
(CVXPY) Oct 29 06:29:30 PM: Reduction chain: CvxAttr2Constr -> Qp2SymbolicQp -> QpMatrixStuffing -> OSQP
(CVXPY) Oct 29 06:29:30 PM: Applying reduction CvxAttr2Constr
(CVXPY) Oct 29 06:29:30 PM: Applying reduction Qp2SymbolicQp
(CVXPY) Oct 29 06:29:30 PM: Applying reduction QpMatrixStuffing
---------------------------------------------------------------------------
AttributeError Traceback (most recent call last)
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\utilities\performance_utils.py:37, in lazyprop.<locals>._lazyprop(self)
36 try:
---> 37 return getattr(self, attr_name)
38 except AttributeError:
AttributeError: 'AddExpression' object has no attribute '_lazy_canonical_form'
During handling of the above exception, another exception occurred:
AttributeError Traceback (most recent call last)
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\utilities\performance_utils.py:37, in lazyprop.<locals>._lazyprop(self)
36 try:
---> 37 return getattr(self, attr_name)
38 except AttributeError:
AttributeError: 'NegExpression' object has no attribute '_lazy_canonical_form'
During handling of the above exception, another exception occurred:
AttributeError Traceback (most recent call last)
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\utilities\performance_utils.py:37, in lazyprop.<locals>._lazyprop(self)
36 try:
---> 37 return getattr(self, attr_name)
38 except AttributeError:
AttributeError: 'multiply' object has no attribute '_lazy_canonical_form'
During handling of the above exception, another exception occurred:
AttributeError Traceback (most recent call last)
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\utilities\performance_utils.py:37, in lazyprop.<locals>._lazyprop(self)
36 try:
---> 37 return getattr(self, attr_name)
38 except AttributeError:
AttributeError: 'log_det' object has no attribute '_lazy_canonical_form'
During handling of the above exception, another exception occurred:
NotImplementedError Traceback (most recent call last)
Cell In[86], line 8
6 objective = cp.sum_squares(x + y)-2*cp.log_det(P)
7 problem = cp.Problem(cp.Minimize(objective))
----> 8 problem.solve(verbose=True)
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\problems\problem.py:609, in Problem.solve(self, *args, **kwargs)
606 raise ValueError(
607 "Cannot specify both 'solver' and 'solver_path'. Please choose one.")
608 return self._solve_solver_path(solve_func,solver_path, args, kwargs)
--> 609 return solve_func(self, *args, **kwargs)
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\problems\problem.py:1191, in Problem._solve(self, solver, warm_start, verbose, bibtex, gp, qcp, requires_grad, enforce_dpp, ignore_dpp, canon_backend, **kwargs)
1188 self.unpack(chain.retrieve(soln))
1189 return self.value
-> 1191 data, solving_chain, inverse_data = self.get_problem_data(
1192 solver, gp, enforce_dpp, ignore_dpp, verbose, canon_backend, kwargs
1193 )
1195 if verbose:
1196 print(_NUM_SOLVER_STR)
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\problems\problem.py:805, in Problem.get_problem_data(self, solver, gp, enforce_dpp, ignore_dpp, verbose, canon_backend, solver_opts)
802 s.LOGGER.info(
803 'Compiling problem (target solver=%s).', solver_name)
804 s.LOGGER.info('Reduction chain: %s', reduction_chain_str)
--> 805 data, inverse_data = solving_chain.apply(self, verbose)
806 safe_to_cache = (
807 isinstance(data, dict)
808 and s.PARAM_PROB in data
809 and not any(isinstance(reduction, EvalParams)
810 for reduction in solving_chain.reductions)
811 )
812 self._compilation_time = time.time() - start
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\reductions\chain.py:76, in Chain.apply(self, problem, verbose)
74 if verbose:
75 s.LOGGER.info('Applying reduction %s', type(r).__name__)
---> 76 problem, inv = r.apply(problem)
77 inverse_data.append(inv)
78 return problem, inverse_data
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\reductions\qp2quad_form\qp_matrix_stuffing.py:272, in QpMatrixStuffing.apply(self, problem)
270 # Form the constraints
271 extractor = CoeffExtractor(inverse_data, canon_backend)
--> 272 params_to_P, params_to_q, flattened_variable = self.stuffed_objective(
273 problem, extractor)
275 # Reorder constraints to Zero, NonNeg.
276 constr_map = group_constraints(cons)
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\reductions\qp2quad_form\qp_matrix_stuffing.py:244, in QpMatrixStuffing.stuffed_objective(self, problem, extractor)
241 def stuffed_objective(self, problem, extractor):
242 # extract to 0.5 * x.T * P * x + q.T * x + r
243 expr = problem.objective.expr.copy()
--> 244 params_to_P, params_to_q = extractor.quad_form(expr)
245 # Handle 0.5 factor.
246 params_to_P = 2*params_to_P
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\utilities\coeff_extractor.py:222, in CoeffExtractor.quad_form(self, expr)
218 quad_forms = replace_quad_forms(root, {})
220 # Calculate affine parts and combine them with quadratic forms to get
221 # the coefficients.
--> 222 coeffs, constant = self.extract_quadratic_coeffs(root.args[0],
223 quad_forms)
224 # Restore expression.
225 restore_quad_forms(root.args[0], quad_forms)
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\utilities\coeff_extractor.py:95, in CoeffExtractor.extract_quadratic_coeffs(self, affine_expr, quad_forms)
85 # Here we take the problem objective, replace all the SymbolicQuadForm
86 # atoms with variables of the same dimensions.
87 # We then apply the canonInterface to reduce the "affine head"
(...) 91 # [d1 d2 ...]
92 # where ci,di are the vector and constant for the ith parameter.
93 affine_id_map, affine_offsets, x_length, affine_var_shapes = \
94 InverseData.get_var_offsets(affine_expr.variables())
---> 95 op_list = [affine_expr.canonical_form[0]]
96 param_coeffs = canonInterface.get_problem_matrix(op_list,
97 x_length,
98 affine_offsets,
(...) 101 affine_expr.size,
102 self.canon_backend)
104 # Iterates over every entry of the parameters vector,
105 # and obtains the Pi and qi for that entry i.
106 # These are then combined into matrices [P1.flatten(), P2.flatten(), ...]
107 # and [q1, q2, ...]
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\utilities\performance_utils.py:39, in lazyprop.<locals>._lazyprop(self)
37 return getattr(self, attr_name)
38 except AttributeError:
---> 39 setattr(self, attr_name, func(self))
40 return getattr(self, attr_name)
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\utilities\canonical.py:43, in Canonical.canonical_form(self)
36 @pu.lazyprop
37 def canonical_form(self):
38 """The graph implementation of the object stored as a property.
39
40 Returns:
41 A tuple of (affine expression, [constraints]).
42 """
---> 43 return self.canonicalize()
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\atoms\atom.py:322, in Atom.canonicalize(self)
320 constraints = []
321 for arg in self.args:
--> 322 obj, constr = arg.canonical_form
323 arg_objs.append(obj)
324 constraints += constr
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\utilities\performance_utils.py:39, in lazyprop.<locals>._lazyprop(self)
37 return getattr(self, attr_name)
38 except AttributeError:
---> 39 setattr(self, attr_name, func(self))
40 return getattr(self, attr_name)
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\utilities\canonical.py:43, in Canonical.canonical_form(self)
36 @pu.lazyprop
37 def canonical_form(self):
38 """The graph implementation of the object stored as a property.
39
40 Returns:
41 A tuple of (affine expression, [constraints]).
42 """
---> 43 return self.canonicalize()
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\atoms\atom.py:322, in Atom.canonicalize(self)
320 constraints = []
321 for arg in self.args:
--> 322 obj, constr = arg.canonical_form
323 arg_objs.append(obj)
324 constraints += constr
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\utilities\performance_utils.py:39, in lazyprop.<locals>._lazyprop(self)
37 return getattr(self, attr_name)
38 except AttributeError:
---> 39 setattr(self, attr_name, func(self))
40 return getattr(self, attr_name)
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\utilities\canonical.py:43, in Canonical.canonical_form(self)
36 @pu.lazyprop
37 def canonical_form(self):
38 """The graph implementation of the object stored as a property.
39
40 Returns:
41 A tuple of (affine expression, [constraints]).
42 """
---> 43 return self.canonicalize()
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\atoms\atom.py:322, in Atom.canonicalize(self)
320 constraints = []
321 for arg in self.args:
--> 322 obj, constr = arg.canonical_form
323 arg_objs.append(obj)
324 constraints += constr
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\utilities\performance_utils.py:39, in lazyprop.<locals>._lazyprop(self)
37 return getattr(self, attr_name)
38 except AttributeError:
---> 39 setattr(self, attr_name, func(self))
40 return getattr(self, attr_name)
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\utilities\canonical.py:43, in Canonical.canonical_form(self)
36 @pu.lazyprop
37 def canonical_form(self):
38 """The graph implementation of the object stored as a property.
39
40 Returns:
41 A tuple of (affine expression, [constraints]).
42 """
---> 43 return self.canonicalize()
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\atoms\atom.py:327, in Atom.canonicalize(self)
325 # Special info required by the graph implementation.
326 data = self.get_data()
--> 327 graph_obj, graph_constr = self.graph_implementation(arg_objs,
328 self.shape,
329 data)
330 return graph_obj, constraints + graph_constr
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\atoms\atom.py:351, in Atom.graph_implementation(self, arg_objs, shape, data)
332 def graph_implementation(
333 self, arg_objs, shape: Tuple[int, ...], data=None
334 ) -> Tuple[lo.LinOp, List['Constraint']]:
335 """Reduces the atom to an affine expression and list of constraints.
336
337 Parameters
(...) 349 (LinOp for objective, list of constraints)
350 """
--> 351 raise NotImplementedError()
NotImplementedError:
Version
- OS: Windows 11
- CVXPY Version: v1.7.2
@GGooeytoe sorry it took so long to review your issue. Could you try with the SCIPY backend? by specifying canon_backend=cp.SCIPY_CANON_BACKEND?
Graph implementations (in my understanding) are only for the CPP backend and it might be the cause of the issue?
It is really weird that you end up calling this method from the atom superclass though.. I feel like that shouldn't really happen.
Doesn't look like it matters. In fact, in the actual scenario I encountered the bug the scipy backend was getting picked automatically anyway.
Reproducer: Running:
import numpy as np
import cvxpy as cp
n=2
x=cp.Variable(n,nonneg=True)
y=cp.Variable(n,nonneg=True)
P=cp.Parameter((n,n))
P.value=np.array([[1.0,0.0],[0.0,1.0]])
objective = cp.sum_squares(x + y)-2*cp.log_det(P)
problem=cp.Problem(cp.Minimize(objective))
problem.solve(verbose=True,canon_backend=cp.SCIPY_CANON_BACKEND)
Yields:
===============================================================================
CVXPY
v1.7.2
===============================================================================
(CVXPY) Nov 19 10:03:17 AM: Your problem has 4 variables, 0 constraints, and 4 parameters.
(CVXPY) Nov 19 10:03:17 AM: It is compliant with the following grammars: DCP, DQCP
(CVXPY) Nov 19 10:03:17 AM: CVXPY will first compile your problem; then, it will invoke a numerical solver to obtain a solution.
(CVXPY) Nov 19 10:03:17 AM: Your problem is compiled with the SCIPY canonicalization backend.
-------------------------------------------------------------------------------
Compilation
-------------------------------------------------------------------------------
(CVXPY) Nov 19 10:03:17 AM: Compiling problem (target solver=OSQP).
(CVXPY) Nov 19 10:03:17 AM: Reduction chain: CvxAttr2Constr -> Qp2SymbolicQp -> QpMatrixStuffing -> OSQP
(CVXPY) Nov 19 10:03:17 AM: Applying reduction CvxAttr2Constr
(CVXPY) Nov 19 10:03:17 AM: Applying reduction Qp2SymbolicQp
(CVXPY) Nov 19 10:03:17 AM: Applying reduction QpMatrixStuffing
---------------------------------------------------------------------------
AttributeError Traceback (most recent call last)
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\utilities\performance_utils.py:37, in lazyprop.<locals>._lazyprop(self)
36 try:
---> 37 return getattr(self, attr_name)
38 except AttributeError:
AttributeError: 'AddExpression' object has no attribute '_lazy_canonical_form'
During handling of the above exception, another exception occurred:
AttributeError Traceback (most recent call last)
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\utilities\performance_utils.py:37, in lazyprop.<locals>._lazyprop(self)
36 try:
---> 37 return getattr(self, attr_name)
38 except AttributeError:
AttributeError: 'NegExpression' object has no attribute '_lazy_canonical_form'
During handling of the above exception, another exception occurred:
AttributeError Traceback (most recent call last)
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\utilities\performance_utils.py:37, in lazyprop.<locals>._lazyprop(self)
36 try:
---> 37 return getattr(self, attr_name)
38 except AttributeError:
AttributeError: 'multiply' object has no attribute '_lazy_canonical_form'
During handling of the above exception, another exception occurred:
AttributeError Traceback (most recent call last)
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\utilities\performance_utils.py:37, in lazyprop.<locals>._lazyprop(self)
36 try:
---> 37 return getattr(self, attr_name)
38 except AttributeError:
AttributeError: 'log_det' object has no attribute '_lazy_canonical_form'
During handling of the above exception, another exception occurred:
NotImplementedError Traceback (most recent call last)
Cell In[11], line 1
----> 1 problem.solve(verbose=True,canon_backend=cp.SCIPY_CANON_BACKEND)
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\problems\problem.py:609, in Problem.solve(self, *args, **kwargs)
606 raise ValueError(
607 "Cannot specify both 'solver' and 'solver_path'. Please choose one.")
608 return self._solve_solver_path(solve_func,solver_path, args, kwargs)
--> 609 return solve_func(self, *args, **kwargs)
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\problems\problem.py:1191, in Problem._solve(self, solver, warm_start, verbose, bibtex, gp, qcp, requires_grad, enforce_dpp, ignore_dpp, canon_backend, **kwargs)
1188 self.unpack(chain.retrieve(soln))
1189 return self.value
-> 1191 data, solving_chain, inverse_data = self.get_problem_data(
1192 solver, gp, enforce_dpp, ignore_dpp, verbose, canon_backend, kwargs
1193 )
1195 if verbose:
1196 print(_NUM_SOLVER_STR)
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\problems\problem.py:805, in Problem.get_problem_data(self, solver, gp, enforce_dpp, ignore_dpp, verbose, canon_backend, solver_opts)
802 s.LOGGER.info(
803 'Compiling problem (target solver=%s).', solver_name)
804 s.LOGGER.info('Reduction chain: %s', reduction_chain_str)
--> 805 data, inverse_data = solving_chain.apply(self, verbose)
806 safe_to_cache = (
807 isinstance(data, dict)
808 and s.PARAM_PROB in data
809 and not any(isinstance(reduction, EvalParams)
810 for reduction in solving_chain.reductions)
811 )
812 self._compilation_time = time.time() - start
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\reductions\chain.py:76, in Chain.apply(self, problem, verbose)
74 if verbose:
75 s.LOGGER.info('Applying reduction %s', type(r).__name__)
---> 76 problem, inv = r.apply(problem)
77 inverse_data.append(inv)
78 return problem, inverse_data
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\reductions\qp2quad_form\qp_matrix_stuffing.py:272, in QpMatrixStuffing.apply(self, problem)
270 # Form the constraints
271 extractor = CoeffExtractor(inverse_data, canon_backend)
--> 272 params_to_P, params_to_q, flattened_variable = self.stuffed_objective(
273 problem, extractor)
275 # Reorder constraints to Zero, NonNeg.
276 constr_map = group_constraints(cons)
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\reductions\qp2quad_form\qp_matrix_stuffing.py:244, in QpMatrixStuffing.stuffed_objective(self, problem, extractor)
241 def stuffed_objective(self, problem, extractor):
242 # extract to 0.5 * x.T * P * x + q.T * x + r
243 expr = problem.objective.expr.copy()
--> 244 params_to_P, params_to_q = extractor.quad_form(expr)
245 # Handle 0.5 factor.
246 params_to_P = 2*params_to_P
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\utilities\coeff_extractor.py:222, in CoeffExtractor.quad_form(self, expr)
218 quad_forms = replace_quad_forms(root, {})
220 # Calculate affine parts and combine them with quadratic forms to get
221 # the coefficients.
--> 222 coeffs, constant = self.extract_quadratic_coeffs(root.args[0],
223 quad_forms)
224 # Restore expression.
225 restore_quad_forms(root.args[0], quad_forms)
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\utilities\coeff_extractor.py:95, in CoeffExtractor.extract_quadratic_coeffs(self, affine_expr, quad_forms)
85 # Here we take the problem objective, replace all the SymbolicQuadForm
86 # atoms with variables of the same dimensions.
87 # We then apply the canonInterface to reduce the "affine head"
(...) 91 # [d1 d2 ...]
92 # where ci,di are the vector and constant for the ith parameter.
93 affine_id_map, affine_offsets, x_length, affine_var_shapes = \
94 InverseData.get_var_offsets(affine_expr.variables())
---> 95 op_list = [affine_expr.canonical_form[0]]
96 param_coeffs = canonInterface.get_problem_matrix(op_list,
97 x_length,
98 affine_offsets,
(...) 101 affine_expr.size,
102 self.canon_backend)
104 # Iterates over every entry of the parameters vector,
105 # and obtains the Pi and qi for that entry i.
106 # These are then combined into matrices [P1.flatten(), P2.flatten(), ...]
107 # and [q1, q2, ...]
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\utilities\performance_utils.py:39, in lazyprop.<locals>._lazyprop(self)
37 return getattr(self, attr_name)
38 except AttributeError:
---> 39 setattr(self, attr_name, func(self))
40 return getattr(self, attr_name)
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\utilities\canonical.py:43, in Canonical.canonical_form(self)
36 @pu.lazyprop
37 def canonical_form(self):
38 """The graph implementation of the object stored as a property.
39
40 Returns:
41 A tuple of (affine expression, [constraints]).
42 """
---> 43 return self.canonicalize()
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\atoms\atom.py:322, in Atom.canonicalize(self)
320 constraints = []
321 for arg in self.args:
--> 322 obj, constr = arg.canonical_form
323 arg_objs.append(obj)
324 constraints += constr
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\utilities\performance_utils.py:39, in lazyprop.<locals>._lazyprop(self)
37 return getattr(self, attr_name)
38 except AttributeError:
---> 39 setattr(self, attr_name, func(self))
40 return getattr(self, attr_name)
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\utilities\canonical.py:43, in Canonical.canonical_form(self)
36 @pu.lazyprop
37 def canonical_form(self):
38 """The graph implementation of the object stored as a property.
39
40 Returns:
41 A tuple of (affine expression, [constraints]).
42 """
---> 43 return self.canonicalize()
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\atoms\atom.py:322, in Atom.canonicalize(self)
320 constraints = []
321 for arg in self.args:
--> 322 obj, constr = arg.canonical_form
323 arg_objs.append(obj)
324 constraints += constr
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\utilities\performance_utils.py:39, in lazyprop.<locals>._lazyprop(self)
37 return getattr(self, attr_name)
38 except AttributeError:
---> 39 setattr(self, attr_name, func(self))
40 return getattr(self, attr_name)
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\utilities\canonical.py:43, in Canonical.canonical_form(self)
36 @pu.lazyprop
37 def canonical_form(self):
38 """The graph implementation of the object stored as a property.
39
40 Returns:
41 A tuple of (affine expression, [constraints]).
42 """
---> 43 return self.canonicalize()
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\atoms\atom.py:322, in Atom.canonicalize(self)
320 constraints = []
321 for arg in self.args:
--> 322 obj, constr = arg.canonical_form
323 arg_objs.append(obj)
324 constraints += constr
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\utilities\performance_utils.py:39, in lazyprop.<locals>._lazyprop(self)
37 return getattr(self, attr_name)
38 except AttributeError:
---> 39 setattr(self, attr_name, func(self))
40 return getattr(self, attr_name)
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\utilities\canonical.py:43, in Canonical.canonical_form(self)
36 @pu.lazyprop
37 def canonical_form(self):
38 """The graph implementation of the object stored as a property.
39
40 Returns:
41 A tuple of (affine expression, [constraints]).
42 """
---> 43 return self.canonicalize()
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\atoms\atom.py:327, in Atom.canonicalize(self)
325 # Special info required by the graph implementation.
326 data = self.get_data()
--> 327 graph_obj, graph_constr = self.graph_implementation(arg_objs,
328 self.shape,
329 data)
330 return graph_obj, constraints + graph_constr
File ~\.local\share\mamba\envs\unsupervised_covariances\Lib\site-packages\cvxpy\atoms\atom.py:351, in Atom.graph_implementation(self, arg_objs, shape, data)
332 def graph_implementation(
333 self, arg_objs, shape: Tuple[int, ...], data=None
334 ) -> Tuple[lo.LinOp, List['Constraint']]:
335 """Reduces the atom to an affine expression and list of constraints.
336
337 Parameters
(...) 349 (LinOp for objective, list of constraints)
350 """
--> 351 raise NotImplementedError()
NotImplementedError:
@GGooeytoe this might be fixed with the recent cleanup of the QP pathway (#3015). Could you install cvxpy from master and try again to see if your issue is fixed now?
Sorry for the very delayed response; lost the message in my inbox.
TL;DR is that master does compile successfully (progress), but gives the wrong answer (uh-oh).
I ran:
import cvxpy as cp
import numpy as np
n = 2
x = cp.Variable(n, nonneg=True)
y = cp.Variable(n, nonneg=True)
P = cp.Parameter((n,n))
P.value=np.array([[1.0,0.0],[0.0,1.0]])
objective = cp.sum_squares(x + y)-2*cp.log_det(P)
problem = cp.Problem(cp.Minimize(objective))
problem.solve(verbose=True)
and received:
===============================================================================
CVXPY
v1.8.0.dev0+171.7206dcc
===============================================================================
(CVXPY) Dec 08 07:20:08 PM: Your problem has 4 variables, 0 constraints, and 4 parameters.
(CVXPY) Dec 08 07:20:08 PM: It is compliant with the following grammars: DCP, DQCP
(CVXPY) Dec 08 07:20:08 PM: CVXPY will first compile your problem; then, it will invoke a numerical solver to obtain a solution.
(CVXPY) Dec 08 07:20:08 PM: Your problem is compiled with the CPP canonicalization backend.
-------------------------------------------------------------------------------
Compilation
-------------------------------------------------------------------------------
(CVXPY) Dec 08 07:20:08 PM: Compiling problem (target solver=OSQP).
(CVXPY) Dec 08 07:20:08 PM: Reduction chain: Dcp2Cone -> CvxAttr2Constr -> ConeMatrixStuffing -> OSQP
(CVXPY) Dec 08 07:20:08 PM: Applying reduction Dcp2Cone
(CVXPY) Dec 08 07:20:08 PM: Applying reduction CvxAttr2Constr
(CVXPY) Dec 08 07:20:08 PM: Applying reduction ConeMatrixStuffing
(CVXPY) Dec 08 07:20:08 PM: Applying reduction OSQP
(CVXPY) Dec 08 07:20:08 PM: Finished problem compilation (took 4.585e-02 seconds).
(CVXPY) Dec 08 07:20:08 PM: (Subsequent compilations of this problem, using the same arguments, should take less time.)
-------------------------------------------------------------------------------
Numerical solver
-------------------------------------------------------------------------------
(CVXPY) Dec 08 07:20:08 PM: Invoking solver OSQP to obtain a solution.
-----------------------------------------------------------------
OSQP v1.0.0 - Operator Splitting QP Solver
(c) The OSQP Developer Team
-----------------------------------------------------------------
problem: variables n = 11, constraints m = 28
nnz(P) + nnz(A) = 24
settings: algebra = Built-in,
OSQPInt = 4 bytes, OSQPFloat = 8 bytes,
linear system solver = QDLDL v0.1.8,
eps_abs = 1.0e-05, eps_rel = 1.0e-05,
eps_prim_inf = 1.0e-04, eps_dual_inf = 1.0e-04,
rho = 1.00e-01 (adaptive: 50 iterations),
sigma = 1.00e-06, alpha = 1.60, max_iter = 10000
check_termination: on (interval 25, duality gap: on),
time_limit: 1.00e+10 sec,
scaling: on (10 iterations), scaled_termination: off
warm starting: on, polishing: on,
iter objective prim res dual res gap rel kkt rho time
1 -6.3999e+01 1.62e-10 2.00e+00 -6.40e+01 2.00e+00 1.00e-01 1.23e-04s
25 -1.0000e+30 1.13e-10 2.00e+00 -1.60e+03 2.00e+00 1.00e-01 2.43e-04s
status: dual infeasible
number of iterations: 25
run time: 3.21e-04s
optimal rho estimate: 1.00e-06
-------------------------------------------------------------------------------
Summary
-------------------------------------------------------------------------------
(CVXPY) Dec 08 07:20:08 PM: Problem status: unbounded
(CVXPY) Dec 08 07:20:08 PM: Optimal value: -inf
(CVXPY) Dec 08 07:20:08 PM: Compilation took 4.585e-02 seconds
(CVXPY) Dec 08 07:20:08 PM: Solver (including time spent in interface) took 2.707e-03 seconds
Which is great, it compiles and runs, but bad in that the solution is wrong. The cost function, for the given parameters, can NEVER be negative (sum_squares is non negative, x and y are constrained non negative anyway, and log_det(P) is 0). CVXPY even recognizes that the cp.sum_squares(x+y) term is nonnegative. I get the same, incorrect, answer using the SCIPY backend:
import cvxpy as cp
import numpy as np
n = 2
x = cp.Variable(n, nonneg=True)
y = cp.Variable(n, nonneg=True)
P = cp.Parameter((n,n))
P.value=np.array([[1.0,0.0],[0.0,1.0]])
objective = cp.sum_squares(x + y)-2*cp.log_det(P)
problem = cp.Problem(cp.Minimize(objective))
problem.solve(verbose=True,canon_backend=cp.SCIPY_CANON_BACKEND)
yields:
===============================================================================
CVXPY
v1.8.0.dev0+171.7206dcc
===============================================================================
(CVXPY) Dec 08 07:29:20 PM: Your problem has 4 variables, 0 constraints, and 4 parameters.
(CVXPY) Dec 08 07:29:20 PM: It is compliant with the following grammars: DCP, DQCP
(CVXPY) Dec 08 07:29:20 PM: CVXPY will first compile your problem; then, it will invoke a numerical solver to obtain a solution.
(CVXPY) Dec 08 07:29:20 PM: Your problem is compiled with the SCIPY canonicalization backend.
-------------------------------------------------------------------------------
Compilation
-------------------------------------------------------------------------------
(CVXPY) Dec 08 07:29:20 PM: Compiling problem (target solver=OSQP).
(CVXPY) Dec 08 07:29:20 PM: Reduction chain: Dcp2Cone -> CvxAttr2Constr -> ConeMatrixStuffing -> OSQP
(CVXPY) Dec 08 07:29:20 PM: Applying reduction Dcp2Cone
(CVXPY) Dec 08 07:29:20 PM: Applying reduction CvxAttr2Constr
(CVXPY) Dec 08 07:29:20 PM: Applying reduction ConeMatrixStuffing
(CVXPY) Dec 08 07:29:20 PM: Applying reduction OSQP
(CVXPY) Dec 08 07:29:20 PM: Finished problem compilation (took 1.181e-02 seconds).
(CVXPY) Dec 08 07:29:20 PM: (Subsequent compilations of this problem, using the same arguments, should take less time.)
-------------------------------------------------------------------------------
Numerical solver
-------------------------------------------------------------------------------
(CVXPY) Dec 08 07:29:20 PM: Invoking solver OSQP to obtain a solution.
-----------------------------------------------------------------
OSQP v1.0.0 - Operator Splitting QP Solver
(c) The OSQP Developer Team
-----------------------------------------------------------------
problem: variables n = 11, constraints m = 28
nnz(P) + nnz(A) = 24
settings: algebra = Built-in,
OSQPInt = 4 bytes, OSQPFloat = 8 bytes,
linear system solver = QDLDL v0.1.8,
eps_abs = 1.0e-05, eps_rel = 1.0e-05,
eps_prim_inf = 1.0e-04, eps_dual_inf = 1.0e-04,
rho = 1.00e-01 (adaptive: 50 iterations),
sigma = 1.00e-06, alpha = 1.60, max_iter = 10000
check_termination: on (interval 25, duality gap: on),
time_limit: 1.00e+10 sec,
scaling: on (10 iterations), scaled_termination: off
warm starting: on, polishing: on,
iter objective prim res dual res gap rel kkt rho time
1 -6.3999e+01 1.62e-10 2.00e+00 -6.40e+01 2.00e+00 1.00e-01 1.01e-04s
25 -1.0000e+30 1.13e-10 2.00e+00 -1.60e+03 2.00e+00 1.00e-01 1.78e-04s
status: dual infeasible
number of iterations: 25
run time: 2.65e-04s
optimal rho estimate: 1.00e-06
-------------------------------------------------------------------------------
Summary
-------------------------------------------------------------------------------
(CVXPY) Dec 08 07:29:20 PM: Problem status: unbounded
(CVXPY) Dec 08 07:29:20 PM: Optimal value: -inf
(CVXPY) Dec 08 07:29:20 PM: Compilation took 1.181e-02 seconds
(CVXPY) Dec 08 07:29:20 PM: Solver (including time spent in interface) took 2.642e-03 seconds
Removing the parameter results in the correct answer:
import cvxpy as cp
import numpy as np
n = 2
x = cp.Variable(n, nonneg=True)
y = cp.Variable(n, nonneg=True)
P = cp.Parameter((n,n))
P.value=np.array([[1.0,0.0],[0.0,1.0]])
objective = cp.sum_squares(x + y)
problem = cp.Problem(cp.Minimize(objective))
problem.solve(verbose=True)
yields:
===============================================================================
CVXPY
v1.8.0.dev0+171.7206dcc
===============================================================================
(CVXPY) Dec 08 07:26:07 PM: Your problem has 4 variables, 0 constraints, and 0 parameters.
(CVXPY) Dec 08 07:26:07 PM: It is compliant with the following grammars: DCP, DQCP
(CVXPY) Dec 08 07:26:07 PM: (If you need to solve this problem multiple times, but with different data, consider using parameters.)
(CVXPY) Dec 08 07:26:07 PM: CVXPY will first compile your problem; then, it will invoke a numerical solver to obtain a solution.
(CVXPY) Dec 08 07:26:07 PM: Your problem is compiled with the CPP canonicalization backend.
-------------------------------------------------------------------------------
Compilation
-------------------------------------------------------------------------------
(CVXPY) Dec 08 07:26:07 PM: Compiling problem (target solver=OSQP).
(CVXPY) Dec 08 07:26:07 PM: Reduction chain: Dcp2Cone -> CvxAttr2Constr -> ConeMatrixStuffing -> OSQP
(CVXPY) Dec 08 07:26:07 PM: Applying reduction Dcp2Cone
(CVXPY) Dec 08 07:26:07 PM: Applying reduction CvxAttr2Constr
(CVXPY) Dec 08 07:26:07 PM: Applying reduction ConeMatrixStuffing
(CVXPY) Dec 08 07:26:07 PM: Applying reduction OSQP
(CVXPY) Dec 08 07:26:07 PM: Finished problem compilation (took 5.926e-03 seconds).
-------------------------------------------------------------------------------
Numerical solver
-------------------------------------------------------------------------------
(CVXPY) Dec 08 07:26:07 PM: Invoking solver OSQP to obtain a solution.
-----------------------------------------------------------------
OSQP v1.0.0 - Operator Splitting QP Solver
(c) The OSQP Developer Team
-----------------------------------------------------------------
problem: variables n = 6, constraints m = 6
nnz(P) + nnz(A) = 12
settings: algebra = Built-in,
OSQPInt = 4 bytes, OSQPFloat = 8 bytes,
linear system solver = QDLDL v0.1.8,
eps_abs = 1.0e-05, eps_rel = 1.0e-05,
eps_prim_inf = 1.0e-04, eps_dual_inf = 1.0e-04,
rho = 1.00e-01 (adaptive: 50 iterations),
sigma = 1.00e-06, alpha = 1.60, max_iter = 10000
check_termination: on (interval 25, duality gap: on),
time_limit: 1.00e+10 sec,
scaling: on (10 iterations), scaled_termination: off
warm starting: on, polishing: on,
iter objective prim res dual res gap rel kkt rho time
1 0.0000e+00 0.00e+00 0.00e+00 0.00e+00 0.00e+00 1.00e-01 1.05e-04s
25 0.0000e+00 0.00e+00 0.00e+00 0.00e+00 0.00e+00 1.00e-01 1.82e-04s
status: solved
solution polishing: unsuccessful
number of iterations: 25
optimal objective: 0.0000
dual objective: -0.0000
duality gap: 0.0000e+00
primal-dual integral: 0.0000e+00
run time: 2.62e-04s
optimal rho estimate: 1.00e-06
-------------------------------------------------------------------------------
Summary
-------------------------------------------------------------------------------
(CVXPY) Dec 08 07:26:07 PM: Problem status: optimal
(CVXPY) Dec 08 07:26:07 PM: Optimal value: 0.000e+00
(CVXPY) Dec 08 07:26:07 PM: Compilation took 5.926e-03 seconds
(CVXPY) Dec 08 07:26:07 PM: Solver (including time spent in interface) took 2.929e-03 seconds
@GGooeytoe this turned out to be a very complex bug https://github.com/cvxpy/cvxpy/pull/3027 Fixed now though.
Thank you!
Long term it might be nice to introduce some presolve-like operations to try to simplify problems like this; the example problem really can be solved as a QP and handling it via exponential and PSD constraints is kind of overkill. Detecting this very simple case of the parameter just being a constant offset probably isn't too hard, but I'm not sure how you would go about more general cases.
@GGooeytoe if you set ignore_dpp=True in solve it will simplify to a QP and in general evaluate all constant expressions and eliminate the atoms involved. The complexity is around DPP (https://www.cvxpy.org/tutorial/dpp/index.html), where the parameter needs to enter the solver problem data linearly. Your example is definitely a strange case where it would probably be better to flag it as non-DPP, even though it can theoretically be canonicalized into a DPP compliant format. Something for us to think about.
thanks for fixing @SteveDiamond , this was indeed a very weird bug. I think we can close this for now as #3027 raises proper error messages for handling this DPP + non-supported cones in QP solvers case.