3
$\begingroup$

My engineering colleagues have devised an interesting approach to equality-constrained optimization. I.e. they wish to solve the problem $\min_x f(x)$ subject to the constraint $g(x) = 0$ where $f, g : \mathbb{R}^n \rightarrow \mathbb{R}$ are smooth functions. Let us say that this optimization problem is well-posed, has a solution, and so on.

I have suggested one of many standard approaches, the augmented Lagrangian algorithm. But upon explaining the augmented Lagrangian algorithm to my colleagues, they saw a parallel with a technique they are familiar with: namely PID control. As a consequence, they have proposed the following approach to equality-constrained optimization. It is an iteration where \begin{align*} x_{n+1} &= x_{n} - \alpha \big( \nabla f(x_n) + \mu_n \nabla g (x_n) \big) \\ % \mu_{n+1} &= \mathrm{PID}\big[ g, \{ x_k\}_{k=1\ldots n} \big] \, . \end{align*} The parameter $\alpha$ is a positive step-size parameter which for now we just take to be small enough. The key is how $\mu_n$ is updated: here $\mu_n$ is treated as a sequence of "control parameters" that are designed to cause the "error" $g(x_n)$ to converge to zero. In other words:

$$\mathrm{PID}\big[ g, \{ x_k\}_{k=1\ldots n} \big] := \gamma_1 g(x_n) + \gamma_2 \sum_{k=1}^{n-1} g(x_k) + \gamma_3 \left\langle \nabla g(x_n), x_{n+1} - x_n \right\rangle \, . $$

The parameters $\gamma_1, \gamma_2, \gamma_3$ are tuned to achieve convergence using the "usual" techniques found in feedback control textbooks.

My question is: can this possibly work? Note that if this method converges, then it seems to be converging to a KKT point.

Thank you.

$\endgroup$
5
  • $\begingroup$ Interesting idea! I know a lot of works that uses control theory to model an optimization algorithm as a feedback controller, but never saw an algorithm that uses directly a PID control to achieve convergence... Did you make any progress on this work? $\endgroup$
    – Tadashi
    May 28, 2018 at 5:04
  • $\begingroup$ No I did not. It's been on the shelf for a while... Could you point me to your 'favourite' reference work in this field? I'd like to take a look. Thanks. $\endgroup$ Jun 28, 2018 at 15:15
  • $\begingroup$ Sure! This recent work analyzes optimization algorithms by using IQC, a tool from robust control theory. $\endgroup$
    – Tadashi
    Jul 2, 2018 at 22:54
  • $\begingroup$ A recent paper from I. Ross may also interest you: arxiv.org/abs/1902.09004 $\endgroup$
    – Tadashi
    Feb 27, 2019 at 20:09
  • $\begingroup$ To contrast the problem statements:Engineering the PID seeks good static parameters for closed loop stability. Search for an optimum tends to vary parameters as the search area is refined and is not robust - it relies on the answer being fixed. High dimension problems make Lyapunov stability challenging. $\endgroup$ Sep 29, 2020 at 6:43

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.