Skip to content

2.3. Optimization

Consider the optimization problem:

\[ \min_{x \in \mathbb{R}^n} f(x), \]

where \(f:\mathbb{R}^n \to \mathbb{R}\) is convex.

To solve the problem numerically, the subpackage specular.optimization.solver provides the following methods:

  • the specular gradient (SPEG) method
  • the stochastic specular gradient (S-SPEG) method
  • the hybrid specular gradient (H-SPEG) method

Given an initial point \(x_0 \in \mathbb{R}^n\), method takes the form:

\[ x_{k+1} = x_k - h_k s_k, \]

where \(h_k > 0\) is the step size and \(s_k\) is the specular gradient for each \(k \in \mathbb{N}\).

Name Rule (Formula) Type Input Description
constant \(h_k = a\) float a Fixed step size for all \(k\).
not_summable \(h_k = a / \sqrt{k}\) float a \(\lim_{k \to \infty }h_k = 0\), but \(\sum h_k = \infty\).
square_summable_not_summable \(h_k = a / (b + k)\) list [a, b] \(\sum h_k^2 < \infty\) and \(\sum h_k = \infty\).
geometric_series \(h_k = a \cdot r^k\) list [a, r] Exponentially decaying step size.
user_defined Custom Callable f(k) User-provided function of iteration \(k\).

Quick Example

from specular.optimization.step_size import StepSize

# Use a square-summable rule: h_k = 10 / (2 + k)
step = StepSize(name='square_summable_not_summable', parameters=[10.0, 2.0])
h_1 = step(1)
print(h_1)

3.3333333333333335

2.3.2. The specular gradient method

The one dimensional case

import specular 

# Objective function: f(x) = |x|
def f(x):
    return abs(x)

step_size = specular.StepSize('constant', 0.1) 

# Specular gradient method
res = specular.gradient_method(f=f, x_0=1.0, step_size=step_size, form='specular gradient', max_iter=20)

Higher dimensional cases

import specular 

# Objective function: f(x) = sum(x^2)
def f(x):
    return float(np.sum(np.array(x)**2))

# Component functions for Stochastic test
# f(x) = x1^2 + x2^2
# f1(x) = x1^2, f2(x) = x2^2
def f_comp_1(x):
    return x[0]**2

def f_comp_2(x):
    return x[1]**2

f_components = [f_comp_1, f_comp_2]

x_0 = [1.0, 1.0]
step_size = specular.StepSize('square_summable_not_summable', [0.5, 1.0]) 

# Specular gradient method
res1 = specular.gradient_method(f=f, x_0=x_0, step_size=step_size, form='specular gradient', max_iter=50)

# Stochastic specular gradient method
res2 = specular.gradient_method(f=f, x_0=x_0, step_size=step_size, form='stochastic', f_j=f_components, max_iter=100)

# hybrid specular gradient method
res3 = specular.gradient_method(f=f_quad_vector, x_0=x_0, step_size=step_size, form='hybrid', f_j=f_components, switch_iter=5, max_iter=20)

2.3.3. OptimizationResult

The class OptimizationResult collects the optimization results. To get history of optimization, call history().

import specular 

# Objective function: f(x) = sum(x^2)
def f(x):
    return float(np.sum(np.array(x)**2))

x_0 = [1.0, 1.0]
step_size = specular.StepSize('square_summable_not_summable', [0.5, 1.0]) 

# Specular gradient method
res_x, res_f, res_time = specular.gradient_method(f=f, x_0=x_0, step_size=step_size, form='specular gradient', max_iter=50).history()

2.3.4. API Reference

specular.optimization.step_size.StepSize

Step size rules for optimization methods.

Source code in specular\optimization\step_size.py 
  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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
class StepSize:
    """
    Step size rules for optimization methods.
    """
    __options__ = [
        'constant',
        'not_summable',
        'square_summable_not_summable',
        'geometric_series',
        'user_defined'
    ]

    def __init__(
        self,
        name: str,
        parameters: float | np.floating | int | Tuple | list | np.ndarray | Callable
    ):
        """
        The step size rules for optimization methods $x_{k+1} = x_k - h_k s_k$, where $s_k$ is the search direction and $h_k > 0$ is the step size at iteration $k >= 1$.

        Parameters:
            name (str):
                Options: 'constant', 'not_summable', 'square_summable_not_summable', 'geometric_series', 'user_defined'
            parameters (float | int | tuple | list | np.ndarray | Callable):
                The parameters required for the selected step size rule:

                * 'constant': float or int

                    A number `a > 0` for the rule :math:`h_k = a` for each `k`.

                * 'not_summable': float or int

                    A number `a > 0` for the rule :math:`h_k = a / sqrt{k}` for each `k`.

                * 'square_summable_not_summable': list or tuple

                    A pair of numbers `[a, b]`, where `a > 0` and `b >= 0`, for the rule :math:`h_k = a / (b + k)` for each `k`.

                * 'geometric_series': list or tuple

                    A pair of numbers `[a, r]`, where `a > 0` and `0 < r < 1`, for the rule :math:`h_k = a * r^k` for each `k`.

                * 'user_defined': Callable

                    A function that takes the current iteration `k` as input and returns the step size (float).

        Examples:
            >>> from specular.optimization.step_size import StepSize
            >>> 
            >>> # 'constant': h_k = a
            >>> step = StepSize(name='constant', parameters=0.5)
            >>> 
            >>> # 'not_summable' rule: h_k = a / sqrt(k)
            >>> # a = 2.0
            >>> step = StepSize(name='not_summable', parameters=2.0)
            >>> 
            >>> # 'square_summable_not_summable' rule: h_k = a / (b + k
            >>> # a = 10, b = 2
            >>> step = StepSize(name='square_summable_not_summable', parameters=[10.0, 2.0])
            >>> 
            >>> # 'geometric_series' rule: h_k = a * r^k
            >>> # a = 1.0, r = 0.5
            >>> step = StepSize(name='geometric_series', parameters=[1.0, 0.5])
            >>> 
            >>> # 'user_defined' callable.
            >>> # Custom rule: h_k = 1 / k^2
            >>> custom_rule = lambda k: 1.0 / (k**2)
            >>> step = StepSize(name='user_defined', parameters=custom_rule)
        """
        self.step_size = name
        self.parameters = parameters

        init_methods = {
            'constant': self._init_constant,
            'not_summable': self._init_not_summable,
            'square_summable_not_summable': self._init_square_summable,
            'geometric_series': self._init_geometric,
            'user_defined': self._init_user_defined
        }

        if name not in init_methods:
             raise ValueError(f"Invalid step size '{name}'. Options: {self.__options__}")

        init_methods[name]()

    def __call__(self, k: int) -> float:
        """
        Returns the step size at iteration k.
        """
        return self._rule(k)

    # ==== Initialization Methods ====
    def _init_constant(self):
        if not isinstance(self.parameters, (float, int, np.floating)):
            raise TypeError(f"Invalid type: number required. Got {type(self.parameters)}")

        if self.parameters <= 0:
            raise ValueError(f"Invalid value: positive number required. Got {self.parameters}")

        self.a = float(self.parameters)
        self._rule = self._calc_constant

    def _init_not_summable(self):
        if not isinstance(self.parameters, (float, int, np.floating)):
            raise TypeError(f"Invalid type: number required. Got {type(self.parameters)}")

        if self.parameters <= 0:
            raise ValueError(f"Invalid value: positive number required. Got {self.parameters}")

        self.a = float(self.parameters)
        self._rule = self._calc_not_summable

    def _init_square_summable(self):
        if not isinstance(self.parameters, (tuple, list, np.ndarray)):
            raise TypeError(f"Invalid type: list/tuple required. Got {type(self.parameters)}")

        if len(self.parameters) != 2:
            raise ValueError(f"Invalid length: 2 parameters [a, b] required. Got {len(self.parameters)}")

        self.a, self.b = self.parameters[0], self.parameters[1]

        if self.a <= 0 or self.b < 0:
            raise ValueError(f"Invalid parameters: a > 0 and b >= 0 required. Got a={self.a}, b={self.b}")

        self._rule = self._calc_square_summable_not_summable

    def _init_geometric(self):
        if not isinstance(self.parameters, (tuple, list, np.ndarray)):
            raise TypeError(f"Invalid type: list/tuple required. Got {type(self.parameters)}")

        if len(self.parameters) != 2:
            raise ValueError(f"Invalid length: 2 parameters [a, r] required. Got {len(self.parameters)}")

        self.a, self.r = self.parameters[0], self.parameters[1]

        if self.a <= 0 or not (0.0 < self.r < 1.0):
            raise ValueError(f"Invalid parameters: a > 0 and 0 < r < 1 required. Got a={self.a}, r={self.r}")

        self._rule = self._calc_geometric_series

    def _init_user_defined(self):
        if not callable(self.parameters):
            raise TypeError("Invalid type: callable function required.")

        self._rule = self.parameters

    # ==== Calculation Methods ====
    def _calc_constant(self, k: int) -> float:
        """
        h_k = a 
        """
        return self.a

    def _calc_not_summable(self, k: int) -> float:
        """
        h_k = a / sqrt{k}
        """
        return self.a / math.sqrt(k)

    def _calc_square_summable_not_summable(self, k: int) -> float:
        """
        h_k = a / (b + k)
        """
        return self.a / (self.b + k)

    def _calc_geometric_series(self, k: int) -> float:
        """
        h_k = a * r**k
        """
        return self.a * (self.r ** k)

__call__(k)

Returns the step size at iteration k.

Source code in specular\optimization\step_size.py 
90
91
92
93
94
def __call__(self, k: int) -> float:
    """
    Returns the step size at iteration k.
    """
    return self._rule(k)

__init__(name, parameters)

The step size rules for optimization methods \(x_{k+1} = x_k - h_k s_k\), where \(s_k\) is the search direction and \(h_k > 0\) is the step size at iteration \(k >= 1\).

Parameters:

Name Type Description Default
name str

Options: 'constant', 'not_summable', 'square_summable_not_summable', 'geometric_series', 'user_defined'

 required
parameters float | int | tuple | list | ndarray | Callable

The parameters required for the selected step size rule:

  • 'constant': float or int

    A number a > 0 for the rule :math:h_k = a for each k.

  • 'not_summable': float or int

    A number a > 0 for the rule :math:h_k = a / sqrt{k} for each k.

  • 'square_summable_not_summable': list or tuple

    A pair of numbers [a, b], where a > 0 and b >= 0, for the rule :math:h_k = a / (b + k) for each k.

  • 'geometric_series': list or tuple

    A pair of numbers [a, r], where a > 0 and 0 < r < 1, for the rule :math:h_k = a * r^k for each k.

  • 'user_defined': Callable

    A function that takes the current iteration k as input and returns the step size (float).

 required

Examples:

>>> from specular.optimization.step_size import StepSize
>>> 
>>> # 'constant': h_k = a
>>> step = StepSize(name='constant', parameters=0.5)
>>> 
>>> # 'not_summable' rule: h_k = a / sqrt(k)
>>> # a = 2.0
>>> step = StepSize(name='not_summable', parameters=2.0)
>>> 
>>> # 'square_summable_not_summable' rule: h_k = a / (b + k
>>> # a = 10, b = 2
>>> step = StepSize(name='square_summable_not_summable', parameters=[10.0, 2.0])
>>> 
>>> # 'geometric_series' rule: h_k = a * r^k
>>> # a = 1.0, r = 0.5
>>> step = StepSize(name='geometric_series', parameters=[1.0, 0.5])
>>> 
>>> # 'user_defined' callable.
>>> # Custom rule: h_k = 1 / k^2
>>> custom_rule = lambda k: 1.0 / (k**2)
>>> step = StepSize(name='user_defined', parameters=custom_rule)
Source code in specular\optimization\step_size.py 
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
def __init__(
    self,
    name: str,
    parameters: float | np.floating | int | Tuple | list | np.ndarray | Callable
):
    """
    The step size rules for optimization methods $x_{k+1} = x_k - h_k s_k$, where $s_k$ is the search direction and $h_k > 0$ is the step size at iteration $k >= 1$.

    Parameters:
        name (str):
            Options: 'constant', 'not_summable', 'square_summable_not_summable', 'geometric_series', 'user_defined'
        parameters (float | int | tuple | list | np.ndarray | Callable):
            The parameters required for the selected step size rule:

            * 'constant': float or int

                A number `a > 0` for the rule :math:`h_k = a` for each `k`.

            * 'not_summable': float or int

                A number `a > 0` for the rule :math:`h_k = a / sqrt{k}` for each `k`.

            * 'square_summable_not_summable': list or tuple

                A pair of numbers `[a, b]`, where `a > 0` and `b >= 0`, for the rule :math:`h_k = a / (b + k)` for each `k`.

            * 'geometric_series': list or tuple

                A pair of numbers `[a, r]`, where `a > 0` and `0 < r < 1`, for the rule :math:`h_k = a * r^k` for each `k`.

            * 'user_defined': Callable

                A function that takes the current iteration `k` as input and returns the step size (float).

    Examples:
        >>> from specular.optimization.step_size import StepSize
        >>> 
        >>> # 'constant': h_k = a
        >>> step = StepSize(name='constant', parameters=0.5)
        >>> 
        >>> # 'not_summable' rule: h_k = a / sqrt(k)
        >>> # a = 2.0
        >>> step = StepSize(name='not_summable', parameters=2.0)
        >>> 
        >>> # 'square_summable_not_summable' rule: h_k = a / (b + k
        >>> # a = 10, b = 2
        >>> step = StepSize(name='square_summable_not_summable', parameters=[10.0, 2.0])
        >>> 
        >>> # 'geometric_series' rule: h_k = a * r^k
        >>> # a = 1.0, r = 0.5
        >>> step = StepSize(name='geometric_series', parameters=[1.0, 0.5])
        >>> 
        >>> # 'user_defined' callable.
        >>> # Custom rule: h_k = 1 / k^2
        >>> custom_rule = lambda k: 1.0 / (k**2)
        >>> step = StepSize(name='user_defined', parameters=custom_rule)
    """
    self.step_size = name
    self.parameters = parameters

    init_methods = {
        'constant': self._init_constant,
        'not_summable': self._init_not_summable,
        'square_summable_not_summable': self._init_square_summable,
        'geometric_series': self._init_geometric,
        'user_defined': self._init_user_defined
    }

    if name not in init_methods:
         raise ValueError(f"Invalid step size '{name}'. Options: {self.__options__}")

    init_methods[name]()

specular.optimization.solver

gradient_method(f, x_0, step_size, h=1e-06, form='specular gradient', tol=1e-06, zero_tol=1e-08, max_iter=1000, f_j=None, m=1, switch_iter=2, record_history=True, print_bar=True)

Minimize a nonsmooth convex function using the current backend.

Source code in specular\optimization\solver.py 
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
def gradient_method(
    f: Callable[
        [int | float | np.number | list | np.ndarray],
        int | float | np.number,
    ],
    x_0: Any,
    step_size: StepSize,
    h: float = 1e-6,
    form: str = "specular gradient",
    tol: float = 1e-6,
    zero_tol: float = 1e-8,
    max_iter: int = 1000,
    f_j: Sequence[ComponentFunc] | Callable | None = None,
    m: int = 1,
    switch_iter: int | None = 2,
    record_history: bool = True,
    print_bar: bool = True,
) -> OptimizationResult:
    """
    Minimize a nonsmooth convex function using the current backend.
    """
    impl = cast(Any, _get_solver_module().gradient_method)

    return impl(
        f=f,
        x_0=x_0,
        step_size=step_size,
        h=h,
        form=form,
        tol=tol,
        zero_tol=zero_tol,
        max_iter=max_iter,
        f_j=f_j,
        m=m,
        switch_iter=switch_iter,
        record_history=record_history,
        print_bar=print_bar,
    )

specular.optimization.result

OptimizationResult

Source code in specular\optimization\result.py 
 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
class OptimizationResult:
    def __init__(
            self, 
            method: str,
            solution: np.ndarray, 
            func_val: int | float | np.number, 
            iteration: int, 
            runtime: float,
            all_history: dict
    ):
        self.method = method
        self.solution = solution
        self.func_val = func_val
        self.iteration = iteration
        self.runtime = runtime
        self.all_history = all_history

    def __repr__(self):
        return (
            f"[{self.method}]\n"
            f"    solution: {self.solution}\n"
            f"  func value: {self.func_val}\n"
            f"   iteration: {self.iteration}"
        )

    def last_record(
        self
    ) -> Tuple[float, float, float]:
        """
        Returns the final solution x, the value of f at x, and the runtime as a tuple.

        Returns:
            (x, f(x), runtime)
        """
        return self.solution, self.func_val, self.runtime # type: ignore

    def history(
        self
    ) -> Tuple[np.ndarray, np.ndarray, float]:
        """
        Returns the time grid and the numerical solution as a tuple.

        Returns:
            (x_history, f_history, runtime)
        """
        return self.all_history["variables"], self.all_history["values"], self.runtime

history()

Returns the time grid and the numerical solution as a tuple.

Returns:

Type Description
Tuple[ndarray, ndarray, float]

(x_history, f_history, runtime)
Source code in specular\optimization\result.py 
42
43
44
45
46
47
48
49
50
51
def history(
    self
) -> Tuple[np.ndarray, np.ndarray, float]:
    """
    Returns the time grid and the numerical solution as a tuple.

    Returns:
        (x_history, f_history, runtime)
    """
    return self.all_history["variables"], self.all_history["values"], self.runtime

last_record()

Returns the final solution x, the value of f at x, and the runtime as a tuple.

Returns:

Type Description
Tuple[float, float, float]

(x, f(x), runtime)
Source code in specular\optimization\result.py 
31
32
33
34
35
36
37
38
39
40
def last_record(
    self
) -> Tuple[float, float, float]:
    """
    Returns the final solution x, the value of f at x, and the runtime as a tuple.

    Returns:
        (x, f(x), runtime)
    """
    return self.solution, self.func_val, self.runtime # type: ignore