# US 2023/0274128 A1 · Method and apparatus for accelerated optimization

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2023/0274128 A1
- Document ID: US20230274128A1
- Status: Published application
- Kind: A1
- Application number: 18/105,494
- Filed: 2023-02-03
- Published: 2023-08-31
- Earliest claimed: 2022-02-03
- Applicants: The United States of America, AS Represented By the Secretary of the Navy
- Inventors: Isaac Michael Ross; Mark Karpenko
- Web page: https://patentgrep.com/patent/US20230274128A1

## CPC

- G06N 3/0464: Convolutional networks [CNN, ConvNet]
- G06N 3/08: Learning methods
- G06N 3/084: Backpropagation, e.g. using gradient descent
- G06N 3/09: Supervised learning
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

A method, apparatus and system including the execution of an accelerated optimization method. According to an exemplary embodiment, the accelerated optimization method includes: first-order optimality conditions for a generic nonlinear optimization problem are generated as part of the terminal transversality conditions of an optimal control problem. It is shown that the Lagrangian of the optimization problem is connected to the Hamiltonian of the optimal control problem via a zero-Hamiltonian, infinite-order, singular arc. The necessary conditions for the singular optimal control problem are used to produce an auxiliary controllable dynamical system whose trajectories generate algorithm primitives for the optimization problem. A three-step iterative map for a generic algorithm is designed by a semi-discretization step. Neither the feedback control law nor the differential equation governing the algorithm need be derived explicitly. A search direction is produced by a proximal-aiming-type method that dissipates a control Lyapunov function. New step size procedures based on minimizing control Lyapunov functions along a search vector complete the design of the accelerated optimization algorithms.

## Claims

### Claim 1

A method for processing digital representations of a group of objects and identifying within the group of objects a target object, the method including the execution of an accelerated optimization method to identify the target object within the digital representations of the group of objects, the accelerated optimization method comprising:
a) a user choosing a CLF V convergence condition;
b) initializing the accelerated optimization method according to:
λx0=−∂xL(1, λs0, x0), s0=e (x0) and setting k=0;
c) computing Vk=V(z(k));
d) while stopping conditions are not met do;
d1) generate ζ(k);
d2) compute hk0;
d3) advance to (z(k+1), x(k+1)) using hk0;
d4) compute Vk+1=V (z (k+1));
d5) while Vk+1 has not decreased sufficiently do;
d4a) backtrack (z(k+1), x(k+1)) along ζ(k); recompute Vk+1;
d6) end while; and
d7) update k←k+1; and
e) end while.

### Claim 2 (depends on 1)

The method for processing digital representations of a group of objects according to claim 1, wherein step a) of the accelerated optimization method includes:
a user choosing a CLF V convergence condition and the parameters associated with a Problem (P) or (P*); and
wherein step d1) includes generating ζ(k) by solving Problem (P*)(or (P)).

### Claim 3 (depends on 1)

The method for processing digital representations of a group of objects according to claim 1, wherein step d2) includes:
computing hk0 using,
M
1
(
k
)
[
χ
h
k
BL
]
+
h
k
BL
⁢
M
2
(
k
)
⁢
χ
=
b
k
,
where, M1(k), M2(k) and bk are matrices (of appropriate dimensions) that depend on the known values of iterates of at point k, and x is a variable that comprises za(k+1), ψλx, Ψλy, ψλs, ψv, ψs and ψx, the known values of iterates given by:
A
1
(
k
+
1
)
:
{
λ
y
(
k
+
1
)
=
λ
y
(
k
)
+
h
k
⁢
ω
⁡
(
k
)
λ
s
⁢
(
k
+
1
)
=
λ
s
⁢
(
k
)
+
h
k
⁢
μ
⁡
(
k
)
v
⁡
(
k
+
1
)
=
v
⁡
(
k
)
+
h
k
⁢
u
⁡
(
k
)
A
2
(
k
+
1
)
:
{
x
⁡
(
k
+
1
)
=
x
⁡
(
k
)
+
h
k
⁢
v
⁡
(
k
+
1
)
A
3
(
k
+
1
)
:
{
λ
x
⁢
(
k
+
1
)
=
-
∂
x
L
⁡
(
λ
y
(
k
+
1
)
,
λ
s
(
k
+
1
)
,
x
⁡
(
k
+
1
)
)
s
⁡
(
k
+
1
)
=
e
⁡
(
x
⁡
(
k
+
1
)
)
.

### Claim 4 (depends on 1)

The method for processing digital representations of a group of objects according to claim 1, wherein step d2) includes:
computing hk0 using,
h
k
FE
=
-
z
k
T
⁢
Qf
k
f
k
T
⁢
Qf
k
=
-
f
⁢
V
⁡
(
z
k
)
2
⁢
V
(
f
k
)
,
where fk=f(zk, ζk) and f is given by,
z
.
=
f
⁡
(
λ
y
,
λ
s
,
v
,
x
,
ζ
)
:=
[
-
[
∂
x
2
L
⁡
(
λ
y
,
⁢
λ
s
,
x
)
]
⁢
v
0
0
0
(
∂
x
e
⁢
(
x
)
]
⁢
v
]
︸
f
0
+
[
-
[
∂
x
L
⁡
(
ω
,
⁢
μ
,
x
)
ω
μ
u
0
]
︸
f
1
,
where,
z:=(λx, λy, λs, v, s)
ζ:=(u, μw)
f0≡f0(λy, λs, v, x)
f1≡f1 (x, ζ)

### Claim 5 (depends on 1)

The method for processing digital representations of a group of objects according to claim 1, wherein step d2) includes:
computing hk0 using,
h
k
tan
=
V
⁡
(
z
k
)
-
f
⁢
V
⁡
(
z
k
)
.

### Claim 6 (depends on 1)

The method for processing digital representations of a group of objects according to claim 1, wherein step d3) includes:
advancing to (z(k+1), x(k+1)) using hk0 and
A
1
(
k
+
1
)
:
{
λ
y
(
k
+
1
)
=
λ
y
(
k
)
+
h
k
⁢
ω
⁡
(
k
)
λ
y
(
k
+
1
)
=
λ
y
(
k
)
+
h
k
⁢
μ
⁡
(
k
)
υ
⁡
(
k
+
1
)
=
υ
⁡
(
k
)
+
h
k
⁢
u
⁡
(
k
)
A
2
(
k
+
1
)
:
{
x
⁡
(
k
+
1
)
=
x
⁡
(
k
)
+
h
k
⁢
υ
⁡
(
k
+
1
)
A
3
(
k
+
1
)
:
{
λ
x
(
k
+
1
)
=
-
∂
x
L
⁡
(
λ
y
(
k
+
1
)
,
λ
s
(
k
+
1
)
,
x
⁡
(
k
+
1
)
)
s
⁡
(
k
+
1
)
=
e
⁡
(
x
⁡
(
k
+
1
)
)
.

### Claim 7 (depends on 1)

The method for processing digital representations of a group of objects according to claim 1, wherein the digital representations of a group of objects includes a plurality of object pixel images and the target object is a pixel image of the target image.

### Claim 8 (depends on 1)

The method for processing digital representations of a group of objects according to claim 1, wherein the digital representations of a group of objects includes a plurality of objects associated with characteristics of a device or process and the target object is a target object associated with a target characteristic of the device or process.

### Claim 9

A method for modeling a device or process to generate a model based on a group of digital representations of the device or process characteristics, the method including the execution of an accelerated optimization method to classify the digital representations of the device or process associated with each digital representation, the accelerated optimization method comprising:
a) a user choosing a CLF V convergence condition;
b) initializing the accelerated optimization method according to:
λx0=<∂xL(1, λs0, x0), s0=e(x0) and setting k=0;
c) computing Vk=V(z(k));
d) while stopping conditions are not met do;
d1) generate ζ(k);
d2) compute hk0;
d3) advance to (z(k+1), x(k+1)) using hk0;
d4) compute Vk+1=V(z(k+1));
d5) while Vk+1 has not decreased sufficiently do;
d4a) backtrack (z(k+1), x(k+1)) along ζ(k); recompute Vk+1;
d6) end while; and
d7) update k←k+1; and
e) end while.

### Claim 10 (depends on 9)

The method for modeling a device or process according to claim 9, wherein step a) of the accelerated optimization method includes:
a user choosing a CLF V convergence condition and the parameters associated with a Problem (P) or (P*); and
wherein step d1) includes generating ζ(k) by solving Problem (P*)(or (P)).

### Claim 11 (depends on 9)

The method for modeling a device or process according to claim 9, wherein step d2) includes:
computing hk0 using,
M
1
(
k
)
[
χ
h
k
BL
]
+
h
k
BL
⁢
M
2
(
k
)
⁢
χ
=
b
k
,
where, M1(k), M2(k) and bk are matrices (of appropriate dimensions) that depend on the known values of iterates of at point k, and x is a variable that comprises za(k+1), ψλx, ψλy, ψλs, ψv, ψs and ψx, the known values of iterates given by:
A
1
(
k
+
1
)
:
{
λ
y
(
k
+
1
)
=
λ
y
(
k
)
+
h
k
⁢
ω
⁡
(
k
)
λ
y
(
k
+
1
)
=
λ
y
(
k
)
+
h
k
⁢
μ
⁡
(
k
)
υ
⁡
(
k
+
1
)
=
v
⁡
(
k
)
+
h
k
⁢
u
⁡
(
k
)
A
2
(
k
+
1
)
:
{
x
⁡
(
k
+
1
)
=
x
⁡
(
k
)
+
h
k
⁢
v
⁡
(
k
+
1
)
A
3
(
k
+
1
)
:
{
λ
x
(
k
+
1
)
=
-
∂
x
L
⁡
(
λ
y
(
k
+
1
)
,
λ
s
(
k
+
1
)
,
x
⁡
(
k
+
1
)
)
s
⁡
(
k
+
1
)
=
e
⁡
(
x
⁡
(
k
+
1
)
)
.

### Claim 12 (depends on 9)

The method for modeling a device or process according to claim 9, wherein step d2) includes:
computing hk0 using,
h
k
FE
=
-
z
k
T
⁢
Qf
k
f
k
T
⁢
Q
⁢
f
k
=
-
f
⁢
V
⁡
(
z
k
)
2
⁢
V
⁡
(
f
k
)
,
where fk=f(zk, ζk) and f is given by,
z
.
=
f
⁡
(
λ
y
,
λ
s
,
v
,
x
,
ζ
)
:=
[
-
[
∂
x
2
L
⁡
(
λ
y
,
⁢
λ
s
,
x
)
]
⁢
v
0
0
0
(
∂
x
e
⁢
(
x
)
]
⁢
v
]
︸
f
0
+
[
-
[
∂
x
L
⁡
(
ω
,
⁢
μ
,
x
)
ω
μ
u
0
]
︸
f
1
,
where,
z:=(λx, λy, λs, v, s)
ζ:=(u, μ, ω)
f0≡f0 (λy, λs, v, x)
f1≡f1 (x, ζ)

### Claim 13 (depends on 9)

The method for modeling a device or process according to claim 9, wherein step d2) includes:
computing hk0 using,
h
k
tan
=
V
⁡
(
z
k
)
-
f
⁢
V
⁡
(
z
k
)
.

### Claim 14 (depends on 9)

The method for modeling a device or process according to claim 9,
A
1
(
k
+
1
)
:
{
λ
y
(
k
+
1
)
=
λ
y
(
k
)
+
h
k
⁢
ω
⁡
(
k
)
λ
y
(
k
+
1
)
=
λ
y
(
k
)
+
h
k
⁢
μ
⁡
(
k
)
v
⁡
(
k
+
1
)
=
v
⁡
(
k
)
+
h
k
⁢
u
⁡
(
k
)
A
2
(
k
+
1
)
:
{
x
⁡
(
k
+
1
)
=
x
⁡
(
k
)
+
h
k
⁢
v
⁡
(
k
+
1
)
A
3
(
k
+
1
)
:
{
λ
x
(
k
+
1
)
=
-
∂
x
L
⁡
(
λ
y
(
k
+
1
)
,
λ
s
(
k
+
1
)
,
x
⁡
(
k
+
1
)
)
s
⁡
(
k
+
1
)
=
e
⁡
(
x
⁡
(
k
+
1
)
)
.

### Claim 15

An apparatus for processing digital representations of a group of objects and identifying within the group of objects a target object, the apparatus including the execution of an accelerated optimization method to identify the target object within the digital representations of the group of objects , the accelerated optimization method comprising:
a) a user choosing a CLF V convergence condition;
b) initializing the accelerated optimization method according to:
λx0=−∂xL(1, λs0, x0), s0=e(x0) and setting k=0;
c) computing Vk=V(z(k));
d) while stopping conditions are not met do;
d1) generate ζ(k);
d2) compute hk0;
d3) advance to (z(k+1), x(k+1)) using hk0;
d4) compute Vk+1=V(z(k+1));
d5) while Vk+1 has not decreased sufficiently do;
d4a) backtrack (z(k+1), x(k+1)) along λ(k); recompute Vk+1;
d6) end while; and
d7) update k←k+1; and
e) end while.

### Claim 16 (depends on 15)

The apparatus for processing digital representations of a group of objects according to claim 15, wherein step a) of the accelerated optimization method includes:
a user choosing a CLF V convergence condition and the parameters associated with a Problem (P) or (P*); and
wherein step d1) includes generating ζ(k) by solving Problem (P*)(or (P)).

### Claim 17 (depends on 15)

The apparatus for processing digital representations of a group of objects according to claim 15, wherein step d2) includes:
computing hk0 using,
M
1
(
k
)
[
χ
h
k
BL
]
+
h
k
BL
⁢
M
2
(
k
)
⁢
χ
=
b
k
,
where, M1(k), M2(k) and bk are matrices (of appropriate dimensions) that depend on the known values of iterates of at point k, and x is a variable that comprises za(k+1), ψλx, ψλy, ψλs, ψv, ψs and ψx, the known values of iterates given by:
A
1
(
k
+
1
)
:
{
λ
y
(
k
+
1
)
=
λ
y
(
k
)
+
h
k
⁢
ω
⁡
(
k
)
λ
y
(
k
+
1
)
=
λ
y
(
k
)
+
h
k
⁢
μ
⁡
(
k
)
v
⁡
(
k
+
1
)
=
v
⁡
(
k
)
+
h
k
⁢
u
⁡
(
k
)
A
2
(
k
+
1
)
:
{
x
⁡
(
k
+
1
)
=
x
⁡
(
k
)
+
h
k
⁢
v
⁡
(
k
+
1
)
A
3
(
k
+
1
)
:
{
λ
x
(
k
+
1
)
=
-
∂
x
L
⁡
(
λ
y
(
k
+
1
)
,
λ
s
(
k
+
1
)
,
x
⁡
(
k
+
1
)
)
s
⁡
(
k
+
1
)
=
e
⁡
(
x
⁡
(
k
+
1
)
)
.

### Claim 18 (depends on 15)

The apparatus for processing digital representations of a group of objects according to claim 15, wherein step d2) includes:
computing hk0 using,
h
k
FE
=
-
z
k
T
⁢
Qf
k
f
k
T
⁢
Q
⁢
f
k
=
-
f
⁢
V
⁡
(
z
k
)
2
⁢
V
⁡
(
f
k
)
,
where fk=f(zk, ζk) and f is given by,
z
.
=
f
⁡
(
λ
y
,
λ
s
,
v
,
x
,
ζ
)
:=
[
-
[
∂
x
2
L
⁡
(
λ
y
,
⁢
λ
s
,
x
)
]
⁢
v
0
0
0
(
∂
x
e
⁢
(
x
)
]
⁢
v
]
︸
f
0
+
[
-
[
∂
x
L
⁡
(
ω
,
⁢
μ
,
x
)
ω
μ
u
0
]
︸
f
1
,
where,
z:=(λx, λy, λs, v, s) ζ:=(u, μ, w)
f0≡f0 (λy, λs, v, x) f1≡f1 (x, ζ)

### Claim 19 (depends on 15)

The apparatus for processing digital representations of a group of objects according to claim 15, wherein step d2) includes:
computing hk0 using,
h
k
tan
=
V
⁡
(
z
k
)
-
f
⁢
V
⁡
(
z
k
)
.

### Claim 20

A method for accelerating optimization, the method comprising: selecting a control Lyapunov function (CLF) and associated parameters for an optimization problem;
generate an algorithm to solve the optimization problem according to λx0=∂xL(1, λs0, x0), s0=e(x0), where k is set to 0;
until stopping conditions are reached:
generating ζ(k) by solving the optimization problem;
computing hk0 using at least one of a group consisting of
M
1
(
k
)
[
χ
h
k
BL
]
+
h
k
BL
⁢
M
2
(
k
)
⁢
χ
=
b
k
,
h
k
FE
=
-
z
k
T
⁢
Qf
k
f
k
T
⁢
Q
⁢
f
k
=
-
f
⁢
V
⁡
(
z
k
)
2
⁢
V
⁡
(
f
k
)
,
and
h
k
tan
=
V
⁡
(
z
k
)
-
f
⁢
V
⁡
(
z
k
)
.
advancing to (z(k+1), x(k+1) using a three-step iterative map and hk0;
computing Vk+1=V(z(k+1)).
until Vk+1 has decreased to a target threshold, backtracking (z(k+1), x(k+1)) along ζ(k) and recomputing Vk+1; and
incrementing k to the next step.
