1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
|
"""
Sum of Squares Package
======================
This is a package to solve sum-of-squares optimization problems.
Module Overview
---------------
Class diagram: Arrows denote inheritance, diamonds indicate composition.
::
┏━━sumofsquares package━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ ┃
┃ ┌─.abc──────────────┐ ┌─.problems────────────────────────────────────────────────────┐ ┃
┃ │ ┌──────────────┐ │ │ │ ┃
┃ │ │ Problem │◀─┼───┼────────────┬───────────────────┬──────────────────┐ │ ┃
┃ │ └──────────────┘ │ │ │ │ │ │ ┃
┃ │ │ │ │ ┌───────────────────┐ ┌────────────┐ ┌──────────────────┐ │ ┃
┃ │ ◇ │ │ │ ConicProblem │ │ SOSProblem │ │InternalSOSProblem│ │ ┃
┃ │ ┌──────────────┐ │ │ └───────────────────┘ └────────────┘ └──────────────────┘ │ ┃
┃ │ │ Solver(Enum) │ │ │ │ ┃
┃ │ └──────────────┘ │ │ │ ┃
┃ │ │ │ │ ┃
┃ │ ┌──────────────┐ │ │ ┌─────────────┐ │ ┃
┃ │ │ Result │◀─┼───┼─│ ConicResult │ │ ┃
┃ │ └──────────────┘ │ │ └─────────────┘ │ ┃
┃ │ │ │ └──────────────────────────────────────────────────────────────┘ ┃
┃ │ │ │ ┃
┃ │ ◇ │ ┌─.solvers.cvxopt──┐ ┌─.solvers.scs─────┐ ┌─.solvers.mosek───┐ ┃
┃ │ ┌──────────────┐ │ │ │ │ │ │ │ ┃
┃ │ │ SolverInfo │◀─┼───┼───────┬──────────┼──┼──────┬───────────┼──┼──────┐ │ ┃
┃ │ └──────────────┘ │ │ │ │ │ │ │ │ │ │ ┃
┃ │ │ │ ┌──────────┐ │ │ ┌─────────┐ │ │ ┌─────────┐ │ ┃
┃ │ │ │ │CVXOptInfo│ │ │ │ SCSInfo │ │ │ │MosekInfo│ │ ┃
┃ │ │ │ └──────────┘ │ │ └─────────┘ │ │ └─────────┘ │ ┃
┃ │ │ └──────────────────┘ └──────────────────┘ └──────────────────┘ ┃
┃ │ │ ┃
┃ │ │ ┌─.constraints──────────────────────────────────────────────────────┐ ┃
┃ │ ┌──────────────┐ │ │ │ ┃
┃ │ │ Constraint │◀─┼───┼───────────────────────────┬────────┬──────────┬─────────┐ │ ┃
┃ │ └──────────────┘ │ │ │ │ │ │ │ ┃
┃ │ ┌──────────────┐ │ │ ┌───────────────────────┐ │ ┌───────────┐ │ ┌───────────────┐ │ ┃
┃ │ │ Set │◀─┼───┼─│ BasicSemialgebraicSet │ │ │EqualToZero│ │ │ExponentialCone│ │ ┃
┃ │ └──────────────┘ │ │ └───────────────────────┘ │ └───────────┘ │ └───────────────┘ │ ┃
┃ │ │ │ ◇ │ │ │ ┃
┃ │ │ │ │ ┌───────────┐ ┌────────────────────┐ │ ┃
┃ │ │ │ └───────│NonNegative│ │PositiveSemiDefinite│ │ ┃
┃ │ │ │ └───────────┘ └────────────────────┘ │ ┃
┃ │ │ │ │ ┃
┃ │ │ │ │ ┃
┃ └───────────────────┘ └───────────────────────────────────────────────────────────────────┘ ┃
┃ ┃
┃ ┌─.canon───────────────────────────────────────────────────┐ ┌─.variable─────────────────┐ ┃ ┏━━━polymatrix package━━━━━━━━━┓
┃ │ │ │ │ ┃ ┃ ┃
┃ │ ┌────────────────────┐ │ │ ┌───────────┐ │ ┃ ┃ ┌──────────┐ ┌──────────┐ ┃
┃ │ │ Canonicalization │ │ │ │OptVariable│──────────┼──╋───╋─▶│ Variable │ │Expression│ ┃
┃ │ └────────────────────┘ │ │ └───────────┘ │ ┃ ┃ └──────────┘ └──────────┘ ┃
┃ │ ▲ │ │ ▲ │ ┃ ┃ │ ┃
┃ │ ├────────────────────┐ │ │ │ │ ┃ ┃ ┌─────────┘ ┃
┃ │ │ │ │ │ │ │ ┃ ┃ ◇ ┃
┃ │ ┌───────────────┐ ┌───────────┐ │ │ ┌────────────────┐ │ ┃ ┃ ┌─────────────────────┐ ┃
┃ │ │ PutinarPSatz │ │ LogDet │ │ │ │OptVariableMixin│────────┼──╋───╋─▶│ ExpressionBaseMixin │ ┃
┃ │ └───────────────┘ └───────────┘ │ │ └────────────────┘ │ ┃ ┃ └─────────────────────┘ ┃
┃ └──────────────────────────────────────────────────────────┘ └───────────────────────────┘ ┃ ┃ ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛ ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
"""
from typing import Iterable
import polymatrix as poly
from polymatrix.expression.expression import Expression
from polymatrix.expressionstate import ExpressionState
from .abc import Problem, Result, Set, Constraint, Solver
from .canon import Canonicalization, PutinarPSatz
from .constraints import BasicSemialgebraicSet, NonNegative
from .problems import SOSProblem
from .utils import partition
from .variable import (
OptVariable,
from_name as internal_from_name,
from_names as internal_from_names)
# export optimization variable constructors
from_name = internal_from_name
from_names = internal_from_names
def make_sos_constraint(expr: Expression, domain: Set | None = None) -> NonNegative:
return NonNegative(expr, domain)
def make_set(*polynomials: Iterable[Expression]):
return BasicSemialgebraicSet(polynomials)
def make_problem(
cost: Expression,
constraints: Iterable[Constraint] = (),
solver: Solver = Solver.CVXOPT,
psatz: Canonicalization = PutinarPSatz
) -> SOSProblem:
"""
Create a sum-of-squares optimization problem.
"""
return psatz(SOSProblem(cost, constraints, solver))
def solve_problem(
cost: Expression,
constraints: Iterable[Constraint] = (),
solver: Solver = Solver.CVXOPT,
verbose: bool = False,
state: ExpressionState | None = None
) -> tuple[Problem, Result]:
"""
Solve a sum-of-squares optimization problem.
"""
if state is None:
state = poly.make_state()
prob = make_problem(cost, constraints, solver)
return prob, prob.solve(verbose)
|
