0
# Data Structures
1
2
Core classes for representing quadratic programs, solutions, and active constraint sets. These provide structured data handling with validation, optimality checking, and comprehensive solution information.
3
4
## Capabilities
5
6
### Problem Representation
7
8
The Problem class provides a structured representation of quadratic programs with validation and metrics.
9
10
```python { .api }
11
class Problem:
12
"""
13
Data structure describing a quadratic program.
14
15
The QP is formulated as:
16
minimize 1/2 x^T P x + q^T x
17
subject to G x <= h
18
A x = b
19
lb <= x <= ub
20
"""
21
22
P: Union[np.ndarray, spa.csc_matrix] # Symmetric cost matrix
23
q: np.ndarray # Cost vector
24
G: Optional[Union[np.ndarray, spa.csc_matrix]] = None # Inequality matrix
25
h: Optional[np.ndarray] = None # Inequality vector
26
A: Optional[Union[np.ndarray, spa.csc_matrix]] = None # Equality matrix
27
b: Optional[np.ndarray] = None # Equality vector
28
lb: Optional[np.ndarray] = None # Lower bounds
29
ub: Optional[np.ndarray] = None # Upper bounds
30
31
def __init__(
32
self,
33
P: Union[np.ndarray, spa.csc_matrix],
34
q: np.ndarray,
35
G: Optional[Union[np.ndarray, spa.csc_matrix]] = None,
36
h: Optional[np.ndarray] = None,
37
A: Optional[Union[np.ndarray, spa.csc_matrix]] = None,
38
b: Optional[np.ndarray] = None,
39
lb: Optional[np.ndarray] = None,
40
ub: Optional[np.ndarray] = None,
41
): ...
42
43
def check_constraints(self) -> None:
44
"""
45
Check constraint dimensions and consistency.
46
47
Raises:
48
- ProblemError: If constraints are inconsistent or malformed
49
"""
50
51
def cond(self, active_set: ActiveSet) -> float:
52
"""
53
Compute condition number of the problem matrix.
54
55
Parameters:
56
- active_set: Active constraint set for the condition number computation
57
58
Returns:
59
Condition number of the symmetric matrix representing problem data
60
"""
61
62
def unpack(self) -> Tuple[
63
Union[np.ndarray, spa.csc_matrix], # P
64
np.ndarray, # q
65
Optional[Union[np.ndarray, spa.csc_matrix]], # G
66
Optional[np.ndarray], # h
67
Optional[Union[np.ndarray, spa.csc_matrix]], # A
68
Optional[np.ndarray], # b
69
Optional[np.ndarray], # lb
70
Optional[np.ndarray], # ub
71
]:
72
"""
73
Unpack problem matrices and vectors as a tuple.
74
75
Returns:
76
Tuple of (P, q, G, h, A, b, lb, ub)
77
"""
78
79
@property
80
def has_sparse(self) -> bool:
81
"""
82
Check whether the problem has sparse matrices.
83
84
Returns:
85
True if at least one of P, G, or A matrices is sparse
86
"""
87
88
@property
89
def is_unconstrained(self) -> bool:
90
"""
91
Check whether the problem has any constraint.
92
93
Returns:
94
True if the problem has no constraints (G, A, lb, ub all None)
95
"""
96
97
def save(self, file: str) -> None:
98
"""
99
Save problem to a compressed NumPy file.
100
101
Parameters:
102
- file: Either filename (string) or open file where data will be saved.
103
If file is a string, the .npz extension will be appended if not present.
104
"""
105
106
@staticmethod
107
def load(file: str) -> 'Problem':
108
"""
109
Load problem from a NumPy file.
110
111
Parameters:
112
- file: File-like object, string, or pathlib.Path to read from.
113
File-like objects must support seek() and read() methods.
114
115
Returns:
116
Problem instance loaded from file
117
"""
118
119
def get_cute_classification(self, interest: str) -> str:
120
"""
121
Get the CUTE classification string of the problem.
122
123
Parameters:
124
- interest: Either 'A' (academic), 'M' (modeling), or 'R' (real application)
125
126
Returns:
127
CUTE classification string in format "QLR2-{interest}N-{nb_var}-{nb_cons}"
128
129
Raises:
130
- ParamError: If interest is not 'A', 'M', or 'R'
131
"""
132
```
133
134
Usage example:
135
136
```python
137
import numpy as np
138
import scipy.sparse as spa
139
from qpsolvers import Problem
140
141
# Define QP matrices
142
P = np.array([[2.0, 1.0], [1.0, 2.0]])
143
q = np.array([1.0, -1.0])
144
G = np.array([[-1.0, 0.0], [0.0, -1.0]])
145
h = np.array([0.0, 0.0])
146
147
# Create problem instance
148
problem = Problem(P, q, G, h)
149
150
# Validate the problem
151
problem.check_constraints()
152
153
# Check condition number with active set
154
from qpsolvers import ActiveSet
155
active_set = ActiveSet() # Empty active set
156
cond_num = problem.cond(active_set)
157
print(f"Condition number: {cond_num}")
158
159
# Unpack for solver
160
P_out, q_out, G_out, h_out, A_out, b_out, lb_out, ub_out = problem.unpack()
161
```
162
163
### Solution Representation
164
165
The Solution class contains comprehensive solution information including primal/dual variables and optimality checks.
166
167
```python { .api }
168
class Solution:
169
"""
170
Solution returned by a QP solver for a given problem.
171
172
Contains primal solution, dual multipliers, objective value, and
173
optimality verification methods.
174
"""
175
176
problem: Problem # The problem this solution corresponds to
177
found: Optional[bool] = None # True if solution found, False if infeasible
178
obj: Optional[float] = None # Primal objective value
179
x: Optional[np.ndarray] = None # Primal solution vector
180
y: Optional[np.ndarray] = None # Dual multipliers (equalities)
181
z: Optional[np.ndarray] = None # Dual multipliers (inequalities)
182
z_box: Optional[np.ndarray] = None # Dual multipliers (box constraints)
183
extras: dict # Solver-specific information
184
185
def __init__(
186
self,
187
problem: Problem,
188
extras: dict = None,
189
found: Optional[bool] = None,
190
obj: Optional[float] = None,
191
x: Optional[np.ndarray] = None,
192
y: Optional[np.ndarray] = None,
193
z: Optional[np.ndarray] = None,
194
z_box: Optional[np.ndarray] = None,
195
): ...
196
197
def is_optimal(self, eps_abs: float) -> bool:
198
"""
199
Check whether the solution satisfies optimality conditions.
200
201
Parameters:
202
- eps_abs: Absolute tolerance for residuals and duality gap
203
204
Returns:
205
True if solution is optimal within tolerance
206
"""
207
208
def primal_residual(self) -> float:
209
"""
210
Compute primal feasibility residual.
211
212
Returns:
213
Maximum violation of primal constraints
214
"""
215
216
def dual_residual(self) -> float:
217
"""
218
Compute dual feasibility residual.
219
220
Returns:
221
Norm of dual residual (KKT stationarity condition)
222
"""
223
224
def duality_gap(self) -> float:
225
"""
226
Compute duality gap between primal and dual objectives.
227
228
Returns:
229
Absolute difference between primal and dual objectives
230
"""
231
```
232
233
Usage example:
234
235
```python
236
from qpsolvers import solve_problem, Problem
237
import numpy as np
238
239
# Create and solve problem
240
problem = Problem(P, q, G, h, A, b)
241
solution = solve_problem(problem, solver="osqp")
242
243
# Check solution status
244
if solution.found:
245
print(f"Solution found!")
246
print(f"Objective value: {solution.obj}")
247
print(f"Primal solution: {solution.x}")
248
249
# Check optimality
250
if solution.is_optimal(eps_abs=1e-6):
251
print("Solution is optimal")
252
253
# Examine dual multipliers
254
if solution.z is not None:
255
active_inequalities = np.where(solution.z > 1e-8)[0]
256
print(f"Active inequality constraints: {active_inequalities}")
257
258
# Check residuals
259
print(f"Primal residual: {solution.primal_residual():.2e}")
260
print(f"Dual residual: {solution.dual_residual():.2e}")
261
print(f"Duality gap: {solution.duality_gap():.2e}")
262
263
# Solver-specific information
264
if solution.extras:
265
print(f"Solver extras: {solution.extras}")
266
267
else:
268
print("No solution found (infeasible/unbounded)")
269
```
270
271
### Active Set Representation
272
273
The ActiveSet class tracks which inequality constraints are active at the solution.
274
275
```python { .api }
276
class ActiveSet:
277
"""
278
Indices of inequality constraints that are active (saturated) at the optimum.
279
280
A constraint is active when it holds with equality at the solution.
281
"""
282
283
G_indices: Sequence[int] # Active linear inequality constraints
284
lb_indices: Sequence[int] # Active lower bound constraints
285
ub_indices: Sequence[int] # Active upper bound constraints
286
287
def __init__(
288
self,
289
G_indices: Optional[Sequence[int]] = None,
290
lb_indices: Optional[Sequence[int]] = None,
291
ub_indices: Optional[Sequence[int]] = None,
292
): ...
293
```
294
295
Usage example:
296
297
```python
298
from qpsolvers import ActiveSet, solve_problem, Problem
299
import numpy as np
300
301
# Solve a problem
302
problem = Problem(P, q, G, h, lb=np.zeros(2), ub=np.ones(2))
303
solution = solve_problem(problem, solver="osqp")
304
305
if solution.found:
306
# Identify active constraints from dual multipliers
307
active_G = []
308
active_lb = []
309
active_ub = []
310
311
if solution.z is not None:
312
active_G = np.where(solution.z > 1e-8)[0].tolist()
313
314
if solution.z_box is not None:
315
active_lb = np.where(solution.z_box < -1e-8)[0].tolist()
316
active_ub = np.where(solution.z_box > 1e-8)[0].tolist()
317
318
# Create active set
319
active_set = ActiveSet(
320
G_indices=active_G,
321
lb_indices=active_lb,
322
ub_indices=active_ub
323
)
324
325
print(f"Active linear inequalities: {active_set.G_indices}")
326
print(f"Active lower bounds: {active_set.lb_indices}")
327
print(f"Active upper bounds: {active_set.ub_indices}")
328
```
329
330
## Advanced Usage
331
332
### Problem Validation and Debugging
333
334
```python
335
from qpsolvers import Problem, ProblemError
336
import numpy as np
337
338
def create_validated_problem(P, q, G=None, h=None, A=None, b=None, lb=None, ub=None):
339
"""Create a problem with comprehensive validation."""
340
341
try:
342
problem = Problem(P, q, G, h, A, b, lb, ub)
343
problem.check_constraints()
344
345
# Check positive semi-definiteness
346
eigenvals = np.linalg.eigvals(P)
347
if np.any(eigenvals < -1e-12):
348
print("Warning: P matrix is not positive semi-definite")
349
350
# Check condition number
351
cond_num = problem.condition_number()
352
if cond_num > 1e12:
353
print(f"Warning: Problem is ill-conditioned (cond={cond_num:.2e})")
354
355
return problem
356
357
except ProblemError as e:
358
print(f"Problem validation failed: {e}")
359
return None
360
```
361
362
### Solution Analysis
363
364
```python
365
def analyze_solution(solution: Solution, tolerance: float = 1e-6):
366
"""Comprehensive solution analysis."""
367
368
if not solution.found:
369
print("No solution found")
370
return
371
372
print(f"Objective value: {solution.obj:.6f}")
373
print(f"Solution vector: {solution.x}")
374
375
# Optimality check
376
is_opt = solution.is_optimal(tolerance)
377
print(f"Is optimal (tol={tolerance}): {is_opt}")
378
379
# Residual analysis
380
primal_res = solution.primal_residual()
381
dual_res = solution.dual_residual()
382
gap = solution.duality_gap()
383
384
print(f"Primal residual: {primal_res:.2e}")
385
print(f"Dual residual: {dual_res:.2e}")
386
print(f"Duality gap: {gap:.2e}")
387
388
# Constraint analysis
389
if solution.z is not None:
390
active_ineq = np.where(solution.z > tolerance)[0]
391
print(f"Active inequalities: {active_ineq.tolist()}")
392
393
if solution.z_box is not None:
394
active_lb = np.where(solution.z_box < -tolerance)[0]
395
active_ub = np.where(solution.z_box > tolerance)[0]
396
print(f"Active lower bounds: {active_lb.tolist()}")
397
print(f"Active upper bounds: {active_ub.tolist()}")
398
```
399
400
### Working with Large Problems
401
402
```python
403
import scipy.sparse as spa
404
from qpsolvers import Problem, solve_problem
405
406
def create_sparse_problem(n: int):
407
"""Create a large sparse QP problem."""
408
409
# Sparse cost matrix (tridiagonal)
410
P = spa.diags([1, -2, 1], [-1, 0, 1], shape=(n, n), format="csc")
411
P = P.T @ P # Make positive semi-definite
412
413
# Cost vector
414
q = np.random.randn(n)
415
416
# Sparse inequality constraints
417
G = spa.random(n//2, n, density=0.1, format="csc")
418
h = np.random.rand(n//2)
419
420
return Problem(P, q, G, h)
421
422
# Create and solve large problem
423
large_problem = create_sparse_problem(1000)
424
solution = solve_problem(large_problem, solver="osqp")
425
analyze_solution(solution)
426
```