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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
|
"""
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 | None = None,
constraints: Iterable[Constraint] = (),
solver: Solver = Solver.CVXOPT,
psatz: type[Canonicalization] = PutinarPSatz
) -> SOSProblem:
"""
Create a sum-of-squares optimization problem.
"""
if cost is None and not constraints:
raise ValueError("Problem is empty, is has neither a cost nor any constraints!")
elif cost is None:
cost = poly.from_number(0)
return psatz(SOSProblem(cost, constraints, solver))
def minimize(cost, *args, **kwargs) -> SOSProblem:
""" Alias for make_problem. """
return make_problem(cost, *args, **kwargs)
def maximize(cost, *args, **kwargs) -> SOSProblem:
""" Alias for make_problem(-cost, constraints, ...). """
return make_problem(-cost, *args, **kwargs)
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)
|
