An adaptive primal-dual framework for nonsmooth convex minimization

We propose a new self-adaptive and double-loop smoothing algorithm to solve composite, nonsmooth, and constrained convex optimization problems. Our algorithm is based on Nesterov’s smoothing technique via general Bregman distance functions. It self-adaptively selects the number of iterations in the inner loop to achieve a desired complexity bound without requiring to set the accuracy a priori as in variants of augmented Lagrangian methods (ALM). We prove (1𝑘)-convergence rate on the last iterate of the outer sequence for both unconstrained and constrained settings in contrast to ergodic rates which are common in ALM as well as alternating direction method-of-multipliers literature. Compared to existing inexact ALM or quadratic penalty methods, our analysis does not rely on the worst-case bounds of the subproblem solved by the inner loop. Therefore, our algorithm can be viewed as a restarting technique applied to the ASGARD method in Tran-Dinh et al. (SIAM J Optim 28(1):96–134, 2018) but with rigorous theoretical guarantees or as an inexact ALM with explicit inner loop termination rules and adaptive parameters. Our algorithm only requires to initialize the parameters once, and automatically updates them during the iteration process without tuning. We illustrate the superiority of our methods via several examples as compared to the state-of-the-art.

Uncooperative Rendezvous in Space: Design of an Electronic Architecture for High Performance Avionic with Multi Sensor Input and Intensive Data Rate.

Michaël Yannick Juillard

Active Debris Removal missions consist of sending a satellite in space and removing one or more debris from their current orbit. A key challenge is to obtain information about the uncooperative target. By gathering the velocity, position, and rotation of the desired object, the satellite is able to plan its trajectory and define the sequence of approach. It requires the use of a variety of sensors with often a high data rate. For this task, a dedicated payload computer is envisioned with the responsibility of processing the information from the various rendezvous sensors. This component has the goal to provide meaningful information to the main satellite computer about the targeted debris. The focus of this work is on the data processing, the number of elements, and the electrical energy with constraints due to internal communication.First, an avionic testbench was built at the EPFL Space Center to assess early hardware and software architectures. The goal is to enable Hardware-In-the-Loop testing while developing the payload computer. A communication data bus has been implemented between the Platform and the Payload On-Board Computer. Emphasis was placed on the reliability of the high-level protocol and multiple concepts for improvement were analyzed.In a second phase, the testbench has been extended to support other data buses. The aim was to develop a reliable and efficient backup or fall-back data bus in case of failure in the main link. Four data buses have been tested with extensive analyses on their resilience to error and the efficiency of their data exchange.In parallel, extensive work has been performed to develop a simulation and optimization tool. Its goal is to support the design of payload avionic architectures for ADR missions by providing trade-offs and analyses. In the first iteration, a simulator has been created with instances of various high-level elements modeled.The second iteration introduced the additional dimension of optimization. It is trying to determine the best set of instruments and algorithms to use. With this capability, numerous analyses have been conducted on the influence of various parameters linked to the general optimizer behavior. It allows us to better understand the strength and limitations of the tool.The third step regarding the tool was to start its verification. The task has been to develop an Hardware-In-the-Loop architecture to compare its behavior with the results of the optimizer. The implementation of various mock-up algorithms enables the verification of their models in the tool. These analyses guarantee the feasibility of the outputted solution.The last part was dedicated to the creation and analysis of a realistic payload avionic architecture. The goal was to test the capability of the tool with hardware elements inspired by actual components. This work has shown the procedure to efficiently use the tool in the design phase of a mission.In conclusion, the work on the communication between the Payload and the Platform On-Board Computer has brought valuable lessons and experiences to the projects. They can now be used for the establishment of the high-level protocol into ClearSpace-1 flight software. In addition, the optimizer created allows tackling the design of complex payload avionic architecture where mass saving and processing resources are crucial. It is an essential point to develop a highly efficient payload computer for an Active Debris Removal satellite.

EPFL2022

Adaptation in Stochastic Algorithms: From Nonsmooth Optimization to Min-Max Problems and Beyond

Ahmet Alacaoglu

Stochastic gradient descent (SGD) and randomized coordinate descent (RCD) are two of the workhorses for training modern automated decision systems. Intriguingly, convergence properties of these methods are not well-established as we move away from the specific case of smooth minimization. In this dissertation, we focus on related problems of nonsmooth optimization and min-max optimization to improve the theoretical understanding of stochastic algorithms.First, we study SGD-based adaptive algorithms and propose a regret analysis framework overcoming the limitations of the existing ones in the convex case. In the nonconvex case, we prove convergence of an adaptive gradient algoritm for solving constrained weakly convex optimization, generalizing the previously known results on unconstrained smooth optimization. We also propose an algorithm combining Nesterov's smoothing with SGD to solve convex problems with infinitely many linear constraints, with optimal rates.Then, we move on to convex-concave min-max problems with bilinear coupling and analyze primal-dual coordinate descent (PDCD) algorithms. We obtain the first PDCD methods with the optimal

\mathcal{O}(1/k)

rate on the the standard optimality measure expected primal-dual gap, which was an open question since 2014. Our analysis also aims to explain the practical behavior of these algorithms by showing that the last iterate enjoys adaptive linear convergence without altering the parameters, depending on a certain error bound condition. Furthermore, we propose an algorithm combining the favorable properties of two branches of PDCD methods: the new method uses large step sizes with dense data and its per-iteration cost depends on the number of nonzeros of the data matrix. Thanks to these unique properties, this method enjoys compelling practical performance complementing its rigorous theoretical guarantees.Next, we consider monotone variational inequalities that generalize convex-concave min-max problems with nonbilinear coupling. We introduce variance reduced algorithms that converge under the same set of assumptions as their deterministic counterparts and improve the best-known complexities for solving convex-concave min-max problems with finite-sum structure. Optimality of our algorithms for this problem class is established in a recent work via matching lower bounds. Finally, we show our preliminary results on policy optimization methods for solving two player zero-sum Markov games for competitive reinforcement learning (RL). Even though this is a nonconvex-nonconcave min-max problem in general, thanks to the special structure, it is tractable to find an approximate Nash equilibrium. We introduce an algorithm that improves the best-known sample complexity of policy gradient methods. This development combines tools from RL and stochastic primal-dual optimization, showing the importance of techniques from convex-concave optimization.

EPFL2021