Extension d'algorithmes d'ordre zéro pour l'optimisation stochastique

The electrical discharge machining process (EDM) was discovered in the 1950s, and was then used essentially to destroy unrecoverable damaged screws. Since then, huge progress has been achieved in making this process reliable and able to perform the most complex machining operations on the most sophisticated materials. Two main processes use electrical discharge machining. First, Die Sinking EDM (DSEDM) in which an electrode, moved along a usually vertical axis, makes an imprint into a mechanical element ; second, Wire EDM (WEDM), uses a wire as an electrode and makes it possible to perform cut operations. Two specific aspects of the EDM process make it particularly challenging for optimization. First, the process evolves with the machining position. In the DSEDM process, where the electrode sinks deeply into the material, the fragments spawn by erosion (contamination) are trapped, thus modifying the sparking conditions. In the WEDM process, the main factors that drive the evolution of the process are the machining operations. Second, the measurements are very noisy, which is due to underlying, mainly random, physical phenomenon ; this is particularly true to spark triggering. The process evolution influences the single criterion to be minimized : total machining time. However, the latter is only known once the operations are completed. As a result, the whole history of manipulated variables influences the final criterion to minimize in this case of dynamic optimization. A major contribution of this work is a proof that a first-order model of the DSEDM process, with the machining position as a state variable, makes it possible to transform a dynamic optimization problem into a static optimization problem. The tools used in this demonstration are Pontryagin's Minimum Principle as well as Parametric Programming. The conclusion is that in order to achieve minimum machining time, maximum speed must be sought all along the trajectory. The online search for maximum speed is another important contribution of this thesis. Noisy efficiency functions are, indeed, known to be a significant challenge to the reliability of optimization algorithms. To address this issue the Golden Ratio Search and the Nelder-Mead Simplex algorithms were chosen as the starting point, as they do not rely explicitly on the gradient of the efficiency function. The addition of a further dilation condition makes these algorithms more effective in stochastic mode. This condition is based on the detection of contradictory measurement samples as compared to the shape of the efficiency function, which is assumed to be unimodal. As a result of this modification, the density of the final optimization points is well centred relative to the theoretical optimum, and dispersion is small. Moreover, the size of the search region for both algorithms never approaches zero. Consequently, as the machining conditions evolve, the optimizer can target a new optimum. This adaptability proves to be a significant improvement over existing algorithms. In the case of the DSEDM process, a simple model of the efficiency surface as a function of the control variables, which has been calibrated on sample measures, has allowed for a validation of the static optimization. For the WEDM process, conclusive results for the modified algorithms have been obtained both by simulation and during machine-based tests.

Trust-region methods based on radial basis functions with application to biomedical imaging

Rodrigue Oeuvray

We have developed a new derivative-free algorithm based on Radial Basis Functions (RBFs). Derivative-free optimization is an active field of research and several algorithms have been proposed recently. Problems of this nature in the industrial setting are quite frequent. The reason is that in a number of applications the optimization process contains simulation packages which are treated as black boxes. The development of our own algorithm was originally motivated by an application in biomedical imaging: the medical image registration problem. The particular characteristics of this problem have incited us to develop a new optimization algorithm based on trust-region methods. However it has been designed to be generic and to be applied to a wide range of problems. The main originality of our approach is the use of RBFs to build the models. In particular we have adapted the existing theory based on quadratic models to our own models and developed new procedures especially designed for models based on RBFs. We have tested our algorithm called BOOSTERS against state-of-the-art methods (UOBYQA, NEWUOA, DFO). On the medical image registration problem, BOOSTERS appears to be the method of choice. The tests on problems from the CUTEr collection show that BOOSTERS is comparable to, but not better than other methods on small problems (size 2-20). It is performing very well for medium size problems (20-80). Moreover, it is able to solve problems of dimension 200, which is considered very large in derivative-free optimization. We have also developed a new class of algorithms combining the robustness of derivative-free algorithms with the faster rate of convergence characterizing Newtonlike-methods. In fact, they define a new class of algorithms lying between derivative-free optimization and quasi-Newton methods. These algorithms are built on the skeleton of our derivative-free algorithm but they can incorporate the gradient when it is available. They can be interpreted as a way of doping derivative-free algorithms with derivatives. If the derivatives are available at each iteration, then our method can be seen as an alternative to quasi-Newton methods. At the opposite, if the derivatives are never evaluated, then the algorithm is totally similar to BOOSTERS. It is a very interesting alternative to existing methods for problems whose objective function is expensive to evaluate and when the derivatives are not available. In this situation, the gradient can be approximated by finite differences and its costs corresponds to n additional function evaluations assuming that Rn is the domain of definition of the objective function. We have compared our method with CFSQP and BTRA, two gradient-based algorithms, and the results show that our doped method performs best. We have also a theoretical analysis of the medical image registration problem based on maximization of mutual information. Most of the current research in this field is concentrated on registration based on nonlinear image transformation. However, little attention has been paid to the theoretical properties of the optimization problem. In our analysis, we focus on the continuity and the differentiability of the objective function. We show in particular that performing a registration without extension of the reference image may lead to discontinuities in the objective function. But we demonstrate that, under some mild assumptions, the function is differentiable almost everywhere. Our analysis is important from an optimization point of view and conditions the choice of a solver. The usual practice is to use generic optimization packages without worrying about the differentiability of the objective function. But the use of gradient-based methods when the objective function is not differentiable may result in poor performance or even in absence of convergence. One of our objectives with this analysis is also that practitioners become aware of these problems and to propose them new algorithms having a potential interest for their applications.

EPFL2005

Modeling and Simulation of Energy Efficient Milling Process Plans for Prismatic Parts

Nenad Nesic

The milling process has been continuously optimized from many aspects: forces, velocities, stability, quality. Numerous papers have been published that report results in the domain of toolpath optimization with criteria such as raising the quality of the machined part, obtaining a stable machining process and maximizing the material removal rate. However, only recently researchers have started investigating the ecological impact of machining processes. With the constantly increasing prices of electrical energy and all environmental problems caused by the production and waste of the energy, it has become indispensable to look for ways to optimize machining processes from the energy consumption aspect, too. It is in this domain, then, that the work described in this dissertation contributes – to add a new criterion for the sustainable operation of machine tools: reducing the energy consumption during the use phase of the machine tool. The total energy spent in a machining process is the sum of power spent by all machine tool subsystems multiplied by the time that they are working. Therefore, the operating strategies for increasing energy efficiency for the high-speed machining processes must be oriented towards the reduction of the total machining time (productive and unproductive) and reduction of instantaneous consumed power in the machining process or, preferably, both. There are many causes for milling process time and energy inefficiency. The major sources of potential time reductions include: (i) the issues related to the geometry and topology of the toolpath („air-time”, overlapping segments, gouge and uncut regions, orientation of the toolpath), (ii) the issues related to the kinematics of the feed drives (the feed velocity/acceleration profile). The possible domains for power consumption reduction are related to the forces that exist in the machining process (cutting, inertial, gravitational and friction forces). The power invested to overcome the cutting force is necessary for the machining process but its consumption should be optimized through constant cutting engagement and feedrate scheduling strategies. The other forces are responsible for the pure mechanical power loss and they should be minimized. The optimization variables for inertial and gravitational forces include the feed motion profile and moving mass configuration, while friction losses are load and/or velocity dependent. In addition, there are some power losses in the electric components of machine tool drives (electrical power losses), whose dependency on velocity and mechanical load can also be modeled. Despite many research efforts to analyze and model the phenomena causing inefficiency of the machining process, they are usually not taken into account during milling process planning. In fact, rare are the attempts to use this knowledge to optimize the milling process with more than one of the above mentioned criteria. The reason for that lies in the fact that increasing the instantaneous values of tool engagement and feedrate in order to minimize total machining time also increases the consumed power and, indirectly, deteriorates the tool and/or destabilizes the cutting process. The existence of conflicting criteria in the objective functions imposes the use of evolutionary algorithms for multiobjective optimization. The process of experimental validation of such an optimization model requires costly and complex external hardware setup and it is also time consuming. Hence, there is an emerging need for the development of an accurate model, which would be used for the simulation of the milling process and testing the competing optimization strategies. The ultimate goal of contemporary manufacturing science and engineering is the development of a holistic virtual machine tool system. The motivation of this PhD research is to contribute to this objective by developing the “virtual milling process for prismatic parts (produced by 2.5D milling)”. This category of objects is selected, because the majority of CNC milling tasks can be performed using 2.5D milling. A very large number of mechanical parts are prismatic (their geometry consists exclusively of features that represent 2D contours extruded in a perpendicular direction). Parts that are even more complex are usually produced from a blank by a 2.5D roughing and 3D–5D finishing. Therefore, development of an accurate model of a 2.5D milling process represents a significant contribution to manufacturing engineering. Starting with above given problem description, we have defined the following research objectives: 1. Model power and energy consumption of a 2.5D milling machine as a function of the toolpath geometry (curvature and continuity), cutting engagement, real feedrate profiles and spindle rotational speed, taking into account moving mass configuration, all power losses (mechanical and electrical) in feed-axis and spindle drives and electromechanical constraints of servo drives; 2. Design an integrated software environment for simulation of the developed models; 3. Validate the model experimentally; 4. Demonstrate the potential of its use for multi-objective process optimization. Cutting engagement calculation is performed by using two competing methodologies, in order to make a comparison of their performances. The first one, the pixel based method, is based on discrete image processing, while the other, the exact method, is based on Boolean operations and vector geometry. The tests performed in more than 20 feature/toolpath combinations demonstrate that the exact method is more precise whereas the pixel-based method is computationally much faster. The machine tool operator commands a constant feedrate value. During the process, based on his/her subjective judgment, he/she can manually tune it to keep the process in the desired boundaries. One of the objectives of this research is to predict the real feedrate values so that they can be integrated in the part program before the process start. The feasible profiles of feed velocities for each toolpath segment are analyzed by answering the following questions: can the commanded feedrate be achieved and with what sequence of acceleration and deceleration phases, how much the tool has to slow down in corners and how does the feedrate profile degenerate in segments where the commanded feedrate cannot be reached? In order to determine all forces and torques, a machine tool model is developed. The following subsystems are modeled as rigid bodies (without vibrations): feed motor shaft, transmission, lead screw/nut pair, lead screw bearings, guides (sliding and rolling design), table with the workpiece and electrospindle (rotor, stator and bearings). All kinetic variables (linear and angular speeds; cutting, inertial and friction forces and torques) are then calculated in the joints of this multi-body system. The modeling of all speeds, forces and torques that occur in the machine tool system during the machining process, allows for calculation of various indicators of process time and energy efficiency: material removal rate, total machining time, useful power (invested in cutting), power loss due to the friction in the joints, power losses in electrical motors, electrical energy consumption of feed and spindle drives. In order to assess the accuracy and the reliability of the developed model two sets of experiments have been performed. The model validation is performed on several subsystem levels and the simulation results show a very good compliance with the experimental results. The first experimental setup consists of the force dynamometer, to measure cutting force components in linear axis directions, two laser optical position sensors, to measure the real feedrate and the power sensor, to measure the total power consumption of the machine tool electrical motors. The machining process was performed on the 6-axis machining center C.B. Ferrari A152 and the data acquisition platform was developed in LabVIEW 2010. The second experimental setup consists of the torque dynamometer, to measure the cutting torque directly on the spindle, the built-in current sensor that measures the motor current proportional to the electrical power consumed by the spindle and, again, the power sensor, to measure the total power consumption of the machine tool electrical motors. This time, MIKRON HPM 600U, a 5-axis milling machine equipped with the controller iTNC530, was used for the experimentation. The developed model is ready for practical implementation. Several examples have been prepared to demonstrate its capabilities in the domains of milling process simulation, sensitivity analysis and prospective optimization strategies. These examples include the prediction of various kinetostatic variables for given toolpaths, choice of the optimum machining strategy (minimization of machining time, moving mass and energy consumption) and process optimization by feedrate scheduling (reduction of cutting force fluctuation). As a conclusion, the major contribution of this PhD research is the development of a comprehensive rigid-body dynamics model of a machine tool system, aimed for the generation, simulation and optimization of 21⁄2D milling process plans. The model features several novelties compared to existing approaches: (i) it takes into account the machine tool rigid body dynamics and real tool kinematics in toolpath planning, (ii) it predicts all mechanical and electrical power losses in the machine tool system (iii) it allows the modeling of machine tool system electromechanical constraints. The model was experimentally validated on two real machine tools in different workshops and its capabilities for the simulation of different toolpath patterns and optimization of process parameters were successfully demonstrated using several examples.

EPFL2012

An Accelerated First-Order Method for Non-convex Optimization on Manifolds

Nicolas Boumal, Christopher Arnold Criscitiello

We describe the first gradient methods on Riemannian manifolds to achieve accelerated rates in the non-convex case. Under Lipschitz assumptions on the Riemannian gradient and Hessian of the cost function, these methods find approximate first-order critical points faster than regular gradient descent. A randomized version also finds approximate second-order critical points. Both the algorithms and their analyses build extensively on existing work in the Euclidean case. The basic operation consists in running the Euclidean accelerated gradient descent method (appropriately safe-guarded against non-convexity) in the current tangent space, then moving back to the manifold and repeating. This requires lifting the cost function from the manifold to the tangent space, which can be done for example through the Riemannian exponential map. For this approach to succeed, the lifted cost function (called the pullback) must retain certain Lipschitz properties. As a contribution of independent interest, we prove precise claims to that effect, with explicit constants. Those claims are affected by the Riemannian curvature of the manifold, which in turn affects the worst-case complexity bounds for our optimization algorithms.