Dynamical System Approach for Optimal Control Problems with Equilibrium Constraints Using Gap-Constraint-Based Reformulation
Kangyu Lin, Toshiyuki Ohtsuka · 2024
Read Dynamical System Approach for Optimal Control Problems with Equilibrium Constraints Using Gap-Constraint-Based Reformulation by Kangyu Lin, Toshiyuki Ohtsuka (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-01326.txt.
Introduction
Kangyu Lin and Toshiyuki Ohtsuka attacked control problems with built-in balance constraints in a 2024 paper. Such problems pair a moving system with equilibrium rules, as in contact mechanics or market clearing. Direct methods discretize first, then optimize, but the balance rules are nonsmooth and stubborn.
Their smoothing step rewrites the rules through a gap function, giving a compact, almost-smooth constraint set that computes kindly. A dynamical solver then walks a chain of smoothed problems, driven by a semismooth Newton flow with fast local settling. A numerical example confirmed the pipeline works. The authors say the pair of tricks makes a hard problem class tractable for direct solvers used in engineering practice.
Catalog record
| CREATOR | Kangyu Lin, Toshiyuki Ohtsuka |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 94 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-01326
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Dynamical System Approach for Optimal Control Problems with Equilibrium Constraints Using Gap-Constraint-Based Reformulation Kangyu Lin, Toshiyuki Ohtsuka Abstract Optimal control problems for nonsmooth dynamical systems governed by differential variational inequalities (DVI) are called optimal control problems with equilibrium constraints (OCPEC). It provides a general formalism for nonsmooth optimal control. However, solving OCPEC using the direct method (i.e., first-discretize-then-optimize) is challenging owing to the lack of correct sensitivity and constraint regularity. This study uses the direct method to solve OCPEC and overcomes the numerical difficulties from two aspects: In the discretization step, we propose a class of novel approaches using gap functions to smooth the DVI, where gap functions are initially proposed for solving variational inequalities. The generated smoothing approximations of discretized OCPEC are called gap-constraint-based reformulations, which have a concise and semismoothly differentiable constraint system; In the optimization step, we propose an efficient dynamical system approach to solve the discretized OCPEC, where a sequence of gap-constraint-based reformulations is solved approximately. This dynamical system approach involves a semismooth Newton flow and achieves local exponential convergence under standard assumptions. The benchmark test shows that the proposed method is computationally tractable and achieves fast local convergence. I Introduction I-A Background Optimal control is a powerful optimization-based control method that has been applied in many complex control tasks of smooth dynamical systems. Technological advancements have recently focused on the optimal control of nonsmooth dynamical systems, which arises in several cutting-edge engineering problems, such as the trajectory optimization of a mechanical system with contact-rich behavior [ 1 , 2 ] , bilevel optimal control [ 3 ] , and game-theoretic planning for autonomous driving [ 4 ] . Hence, an urgent demand exists to study efficient and reliable numerical methods for nonsmooth optimal control. Historically, several mathematical formalisms have been proposed in various scenarios for modeling nonsmooth dynamical systems [ 5 , 6 , 7 , 8 ] , such as differential inclusions (DIs), differential variational inequalities (DVIs), and dynamical complementarity systems (DCSs). DVI [ 5 ] has garnered significant attention owing to its generality and ability to exploit the system structures using the mature theory of variational inequalities (VIs), where VI is a unified mathematical formalism for equilibrium problems [ 9 ] . Thus, this study considers optimal control problems (OCPs) for a class of nonsmooth systems governed by DVI, known as optimal control problems with equilibrium constraints (OCPECs). We briefly review VI and DVI in subsections II-D and II-E , respectively. The direct method, also called first-discretize-then-optimize method, is practical for numerically solving OCPs of smooth dynamical systems [ 10 ] . However, its extension to OCPEC, that is, first discretize the DVI using time-stepping methods [ 6 ] and then solve the discretized OCPEC using nonlinear programming (NLP) solvers, encounters great challenges: In the discretization step, time-stepping methods achieve only first-order accuracy. Moreover, the numerical sensitivities are incorrect, that is, the gradient information of the discretized OCPEC does not match that of the continuous-time OCPEC, which implies that many artificial local minima exist in the discretized OCPEC [ 11 ] ; In the optimization step, the discretized OCPEC is a difficult NLP problem called mathematical programming with equilibrium constraints (MPECs), which violates almost all constraint qualifications (CQs) required by the NLP theory. One approach to alleviating difficulties caused by the lack of correct sensitivity and constraint regularity is to smooth the DVI and then use the continuation method in the smoothing parameter. However, the smoothed DVI behaves similarly to the nonsmooth system when the smoothing parameter is small. Thus, we need to solve a sequence of large-scale problems that become increasingly difficult. Difficulties in solving OCPEC are discussed in detail in subsection III-B and III-C . Recently, advanced discretization methods with switch detection [ 12 ] have been proposed for a class of nonsmooth systems that can be transformed into an index-zero DCS: In the discretization step, higher-order accuracy and correct numerical sensitivity are achieved by locating the nonsmooth points at the discretization time points; However, in the optimization step, the resulting discretized OCP is an NLP problem called mathematical programming with complementarity constraints (MPCCs), which is a special case of MPEC and violates CQs as well. Their extension to DVI also needs to be explored. I-B Motivation and related works Despite the aforementioned challenges, the direct method remains the preferred approach to developing numerical methods for nonsmooth optimal control because it allows the use of many well-established optimization theories and algorithms. This study considers solving OCPEC using the direct method; thus, the following two critical problems need to be addressed: • How can the DVI be smoothed to make the smoothing approximation of discretized OCPEC easier to solve? • How can a sequence of smoothing approximations of the discretized OCPEC be solved efficiently? Classical approaches to smoothing the DVI replace the VI with its Karush–Kuhn–Tucker (KKT) conditions, where the complementarity conditions are further smoothed or relaxed [ 13 , 14 , 15 , 16 , 17 , 18 ] . These approaches introduce Lagrange multipliers, thus generating a smoothing approximation of the discretized OCPEC with many additional variables and constraints. We review some of these approaches in subsection III-C . Inspired by the merit-function-based algorithm for solving the VI, our previous work [ 19 ] provides a new approach to smoothing the DVI. This approach uses a tailored merit function called regularized gap function [ 20 ] to reformulate the VI as a small number of inequalities, where one of the inequalities is further relaxed. This is a multiplier-free approach and thus generates a smaller smoothing approximation of the discretized OCPEC. A recent study in bilevel optimization [ 21 ] also used a doubly regularized gap function to reformulate the lower-level problem and reported some promising results. However, gap functions were shown to be only once continuously differentiable when initially proposed; thus, solution methods presented in [ 19 ] and [ 21 ] only use the first-order gradient information of gap functions and achieve a slow local convergence rate. The smoothing of DVI enables us to obtain the solution to the discretized OCPEC by solving a sequence of smoothing approximations of the discretized OCPEC. This is known as the continuation method [ 22 ] , which is a general methodology to develop algorithms for solving difficult problems. Its core idea is to obtain the solution to a difficult problem by solving a sequence of easier problems, where the solution method of each problem is warm-started by the solution of the previous problem. Its standard implementation is to solve each problem exactly using off-the-shelf solvers, where one example is the NLP-based method [ 18 ] for solving MPCC. However, the later problems become increasingly difficult; thus, solving them exactly often requires more time. An alternative implementation is to solve each problem approximately while ensuring that the approximation error is bounded, or better yet, finally converges to zero. This implementation can be regarded as a case of the dynamical system approach , also known as the systems theory of algorithm [ 23 ] , where the iterative algorithm is viewed as a dynamical system and studied from a system perspective. Benefiting from the mature and fruitful theory of dynamical systems, we can make