Advances in Optimization and Applications
11th International Conference, OPTIMA 2020, Moscow, Russia, September 28 – October 2, 2020, Revised Selected Papers
- 2020
- Buch
- Herausgegeben von
- Nicholas Olenev
- Yuri Evtushenko
- Prof. Michael Khachay
- Vlasta Malkova
- Verlag
- Springer International Publishing
Über dieses Buch
Dieses Buch stellt den Referenten der 11. Internationalen Konferenz zur Optimierung und Anwendung OPTIMA 2020 dar, die von September bis Oktober 2020 stattfand. Aufgrund der COVID-19 Pandemie wurde die Konferenz online abgehalten. Die 18 überarbeiteten vollständigen Beiträge wurden sorgfältig geprüft und aus 60 Einreichungen ausgewählt. Die Beiträge sind in thematische Abschnitte über globale Optimierung, kombinatorische und diskrete Optimierung, optimale Steuerung, Optimierung in den Wirtschafts-, Finanz- und Sozialwissenschaften sowie Anwendungen gegliedert.
Mit KI übersetzt
Über dieses Buch
This book constitutes the refereed proceedings of the 11th International Conference on Optimization and Applications, OPTIMA 2020, held in September – October 2020. Due to the COVID-19 pandemic the conference was held online.
The 18 revised full papers presented were carefully reviewed and selected from 60 submissions. The papers are organized intopical sections on global optimization; combinatorial and discrete optimization; optimal control; optimization in economy, finance and social sciences; applications.
Anzeige
Inhaltsverzeichnis
-
Frontmatter
-
Global Optimization
-
Frontmatter
-
Global Optimization Method with Numerically Calculated Function Derivatives
Victor Gergel, Alexander SysoyevDas Kapitel stellt eine globale Optimierungsmethode vor, die numerisch berechnete Funktionsderivate nutzt, um die Berechnungskosten bei multidimensionalen Problemen zu senken. Es beginnt mit dem globalen Optimierungsproblem und dem Lipschitz-Zustand, der für die Einschätzung des Funktionsverhaltens unverzichtbar ist. Die Methode nutzt ein verschachteltes Dimensionalitätsreduktionsschema, um mehrdimensionale Probleme in eindimensionale zu verwandeln, was den effektiven Einsatz eindimensionaler Optimierungsalgorithmen ermöglicht. Das Kapitel behandelt auch den Umgang mit diskontinuierlichen Funktionen und präsentiert numerische Experimente zur Validierung der Effizienz des Ansatzes. Die Ergebnisse zeigen die überlegene Leistung der vorgeschlagenen Methode und machen sie zu einer vielversprechenden Lösung für rechenintensive Optimierungsprobleme.KI-Generiert
Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.
AbstractThe paper proposes a method for solving computationally time-consuming multidimensional global optimization problems. The developed method combines the use of a nested dimensional reduction scheme and numerical estimates of the objective function derivatives. Derivatives significantly reduce the cost of solving global optimization problems, however, the use of a nested scheme can lead to the fact that the derivatives of the reduced function become discontinuous. Typical global optimization methods are highly dependent on the continuity of the objective function. Thus, to use derivatives in combination with a nested scheme, an optimization method is required that can work with discontinuous functions. The paper discusses the corresponding method, as well as the results of numerical experiments in which such an optimization scheme is compared with other known methods. -
Improving of the Identification Algorithm for a Quasilinear Recurrence Equation
Anatoly V. Panyukov, Yasir Ali MezaalDas Kapitel geht der Komplexität der Bestimmung der Koeffizienten eines quasilinearen autoregressiven Modells anhand aktueller Informationen über Zustands- und Kontrollvariablen nach. Sie kritisiert die traditionelle Least Squares Method (LSM) wegen ihrer strengen Voraussetzungen und Ineffektivität bei korrelierten Fehlern. Der Autor stellt die Least Deviations Method (LDM) und ihre Verallgemeinerungen, Weighted Least Deviation Method (WLDM) und General Least Deviations Method (GLDM), als robuste Alternativen vor. Das Kapitel schlägt einen verbesserten WLDM-Schätzalgorithmus mit reduzierter Rechenkomplexität vor, der sich für praktische Anwendungen eignet. Die mit dem irakischen Aktienindex durchgeführten Berechnungsexperimente zeigen die Wirksamkeit des vorgeschlagenen Algorithmus und heben sein Potenzial hervor, zukünftige Werte endogener Variablen mit hoher Genauigkeit vorherzusagen.KI-Generiert
Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.
AbstractIdentification of quasilinear recurrence equations (QRE) may be reduced to the problem of regression analysis with mutually dependent observable variables. It is possible to use the generalized least deviations method (GLDM) for such problems. GLDM-estimation consists of solving the sequence of the WLDM-estimation problems. We propose the algorithm to solve the WLDM-estimation problem. Computational complexity of this algorithm does not exceed the quantity \(O(N^2T+T^2)\), where N is the number of coefficients in the considered equation, T is the number of observed readings. The computational complexity of solving practical GLDM estimation problems does not exceed \(O(N^3T+NT^2)\). Results of computational experiments to solve the problem of identifying the recurrence equation of the stock market index in Iraq by original data from the site “ISX-IQ.net” are presented. This results show the possibility to apply a second order quasilinear recurrence equation with quadratic nonlinearity for these purposes. Perhaps increasing the order of the recurrence equation and the accuracy of the calculations give better results. -
Optimization Algorithm for Approximating the Solutions Set of Nonlinear Inequalities Systems in the Problem of Determining the Robot Workspace
Larisa Rybak, Dmitry Malyshev, Elena GaponenkoDas Kapitel behandelt den Optimierungsalgorithmus zur Annäherung der Lösungsmenge nichtlinearer Ungleichungssysteme im Zusammenhang mit der Bestimmung von Roboterarbeitsplätzen. Es beginnt mit der Einführung der Herausforderungen der Rechenkomplexität in globale Optimierungsprobleme und der von Yu.G. vorgeschlagenen Methode ungleicher Beschichtungen. Jewtuschenko. Die Anwendung dieser Methode zur Definition von Roboterarbeitsplätzen wird untersucht, wobei der Schwerpunkt auf der Verwendung von Ungleichheits- und Gleichungssystemen zur Beschreibung von Designbeschränkungen liegt. Die iterative Bisektionsmethode wird als Werkzeug für die Implementierung der Methode hervorgehoben, und die Umwandlung von Decksätzen in teilweise geordnete ganzzahlige Mengen wird als Schlüsselinnovation eingeführt. Diese Transformation verringert die Anzahl der Rahmen und Übergänge von realen zu ganzzahligen Räumen, wodurch die Effizienz der Bestimmung des Arbeitsbereichs deutlich gesteigert wird. Die Effektivität des Ansatzes wird durch seine Anwendung auf den 3-RPS-Roboter demonstriert, der sowohl die Anzahl der Boxen als auch die benötigten Rechenressourcen deutlich reduziert. Das Kapitel schließt mit der Betonung des Potenzials weiterer Forschung zur Beschleunigung von Transformationszeiten, was es zu einer wertvollen Ressource für Fachleute macht, die den Bereich der Robotik durch Optimierung vorantreiben wollen.KI-Generiert
Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.
AbstractThis paper is devoted to the problem of determining the workspace of robots. We consider an approach to the development of a numerical method for approximating the set of solutions of a system of nonlinear inequalities based on the concept of non-uniform coverings. An approach is proposed based on the transformation of non-uniform covering sets into a set of partially ordered sets of integers to reduce computational complexity. An algorithm for transforming boxes of a covering set is presented. The approach has been tested for a 3-RPS robot. The results of the mathematical simulation and analysis of the effectiveness of the proposed approach based on an estimate of the reduction in the amount of numbers describing the covering set are presented. -
Parallel Global Optimization Algorithm with Uniform Convergence for Solving a Set of Constrained Global Optimization Problems
Vladislav Sovrasov, Konstantin BarkalovDas Kapitel stellt einen ausgeklügelten parallelen globalen Optimierungsalgorithmus vor, der darauf ausgelegt ist, das schwierige Problem zu lösen, das globale Minimum an nichtkonvexen Funktionen mit Einschränkungen zu finden. Es nutzt ein Dimensionalitätsreduzierungsprogramm und einen Indexalgorithmus, um teilweise definierte objektive Funktionen und Beschränkungen zu handhaben. Die Konvergenz des Algorithmus ist theoretisch erwiesen, und seine Effizienz wird durch rigorose numerische Experimente sowohl zu künstlich erzeugten als auch zu realen Optimierungsproblemen in Bezug auf Multikriterien unter Beweis gestellt. Die Ergebnisse unterstreichen die Fähigkeit des Algorithmus, Rechenressourcen effizient auf mehrere Probleme zu verteilen, eine einheitliche Konvergenz sicherzustellen und sequenzielle Methoden zu übertreffen. Das Kapitel endet mit einer Diskussion über zukünftige Verbesserungen und das Potenzial für die Implementierung von verteiltem Speicher.KI-Generiert
Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.
AbstractThis paper proposes an extension of global optimization algorithm for solving a set of problems with non-convex constraints. The uniform convergence inherent to the algorithm allows for the optimal distribution of the computational resources, since the number of errors in numerical solutions decreases at approximately equal rate for all problems processed by the algorithm. The algorithm assigns a priority level to each problem and, with every iteration, performs the computations of the objective functions for several problems in parallel. After the algorithm is terminated at any given time, it obtains solutions of similar quality for all the problems of the set. Such sets appear when the global optimization problem has a discrete parameter or, for example, when a multicriteria optimization problem is solved by scalarization techniques. The algorithm employs Peano-type space-filling curves for the reduction of the multidimensional optimization problems to the one-dimensional ones. The efficiency of the implemented algorithm was tested using the sets of artificially generated global optimization problems, as well as a series of problems obtained as a rescult of scalarization of a multicriteria optimization problem. Additional numerical experiments also confirmed the uniform convergence of the proposed method.
-
-
Combinatorial and Discrete Optimization
-
Frontmatter
-
Multi-core Processor Scheduling with Respect to Data Bus Bandwidth
Anton V. Eremeev, Anton A. Malakhov, Maxim A. Sakhno, Maria Y. SosnovskayaDas Kapitel vertieft sich in die Komplexität der Planung von Softwaremodulen auf Mehrkernprozessoren, wobei ein besonderer Schwerpunkt auf den Beschränkungen liegt, die die Datenbusbandbreite auferlegt. Es werden zwei Problemformulierungen eingeführt, die die NP-Härte des Planungsproblems aufzeigen und ein gemischtes ganzzahliges lineares Programmiermodell für eine Formulierung vorschlagen. Zusätzlich wird für die zweite Formulierung ein gieriger Algorithmus präsentiert, der einen praktischen Ansatz für annähernde Lösungen bietet. Das Kapitel umfasst auch computergestützte Experimente und Methoden zur Datengenerierung im realen Leben, wobei die Effektivität und Genauigkeit der vorgeschlagenen Algorithmen hervorgehoben wird. Die Ergebnisse zeigen, dass der gierige Algorithmus qualitativ hochwertige Lösungen mit geringen Rechenkosten bietet und damit ein wertvolles Werkzeug für Praktiker vor Ort ist.KI-Generiert
Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.
AbstractThe paper considers the problem of scheduling software modules on a multi-core processor, taking into account the limited bandwidth of the data bus and the precedence constraints. Two problem formulations with different levels of problem-specific detail are suggested and both shown to be NP-hard. A mixed integer linear programming (MILP) model is proposed for the first problem formulation, and a greedy algorithm is developed for the second one. An experimental comparison of the results of the greedy algorithm and the MILP solutions found by CPLEX solver is carried out. -
A Novel Algorithm for Construction of the Shortest Path Between a Finite Set of Nonintersecting Contours on the Plane
Alexander Petunin, Efim Polishchuk, Stanislav UkolovDieses Kapitel befasst sich mit dem Optimierungsproblem der Minimierung der Werkzeugluftbewegung beim CNC-Blechschneiden, wobei der Schwerpunkt auf dem Continuous Cutting Problem (CCP) liegt. Es wird ein neuartiger Algorithmus, CCP-Relax, eingeführt, der die CCP effizient löst, ohne Diskretisierung, was die Problemgröße und Berechnungszeit verringert. Der Algorithmus besteht aus mehreren Stufen, einschließlich der Entfernung externer Konturen, kontinuierlicher Optimierung, diskreter Optimierung mittels Variabler Nachbarschaftssuche und der Wiederherstellung entfernter Konturen. Die theoretische Rechtfertigung der Eigenschaften des Algorithmus wird diskutiert, wobei seine Fähigkeit hervorgehoben wird, unter bestimmten Bedingungen lokale und globale Minima zu liefern. Darüber hinaus wird in diesem Kapitel die Anwendung des CCP-Relax-Algorithmus auf allgemeinere Schnittprobleme wie das Segment Continuous Cutting Problem (SCCP) und das Generalized Segment Continuous Cutting Problem (GSCCP) untersucht, die eine Grundlage für die Lösung des Intermittent Cutting Problems (ICP) bilden. Numerische Experimente zeigen die Effektivität und Effizienz des Algorithmus bei der Erzeugung qualitativ hochwertiger Werkzeugbahnrouten für echte Schneidpläne.KI-Generiert
Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.
AbstractAn optimization problem that arises during tool path routing for CNC sheet cutting machine is considered for the case when parts are bounded by line segments and circular arcs and pierce points lay on the bounds. Technique of continuous cutting is used, i.e. each contour is cut as a whole from any starting point. The task of tool path length minimization is reduced to the task of air move length minimization which is shown to be equivalent to finding the shortest broken line with vertices on non-nesting disjoint contours on the plane. The algorithm of building such a broken line for a fixed order of contour processing is devised and proved to deliver local minimum. Some sufficient conditions for this minimum to be global are discussed. A heuristic algorithm for finding the optimal contour cutting order is proposed based on Variable Neighborhood Search approach. Results of a computational experiment and a comparison with the exact solution of GTSP problem are presented. -
The Polyhedral-Surface Cutting Plane Method of Optimization over a Vertex-Located Set
Oksana Pichugina, Liudmyla Koliechkina, Nadezhda MuravyovaDie Polyhedral-Surface Cutting Plane Method (PSCM) ist ein neuartiger Ansatz zur Optimierung linearer kombinatorischer Programme auf Sets, die in eine konvexe Oberfläche eingeschrieben sind. Diese Methode erweitert herkömmliche Methoden der Schneideebene, indem sie geometrische Merkmale der machbaren Domäne und der damit verbundenen Polytopie einbezieht. Die PSCM stellt drei Varianten vor: die Modifizierte Kombinatorische Schneideplanmethode (MCCM), die Kombinatorische Polytope-Schneideplanmethode (CPCM) und die Oberflächenschneideplanmethode (SCM). Jede Variante nutzt unterschiedliche Aspekte der konvexen Oberfläche und des Polytopes, um Schnittflächen zu konstruieren, wobei SCM besonders starke Schnitte bietet. Der Aufsatz befasst sich auch mit der Herausforderung der Degeneration bei der kombinatorischen Optimierung und bietet neue Techniken zu ihrer Lösung. Der PSCM ist auf eine breite Palette praktischer Probleme anwendbar, unter anderem in den Bereichen Telekommunikation, VLSI-Design und soziale Netzwerke, was ihn zu einem wertvollen Beitrag im Bereich der kombinatorischen Optimierung macht.KI-Generiert
Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.
AbstractThe Boolean set, permutation vector’s sets and many others belong to a class of vertex-located sets (VLS) as they coincide with a vertex set of their convex hull. A polyhedral-surface cutting plane method (PSCM) for linear constrained optimization over VLS is offered. It utilizes representability of a VLS as an intersection of a strictly convex surface S with a polytope P. PSCM applies iteratively two steps dealing with a polyhedral or a surface relaxation of the original problem. First, a polyhedral relaxation is solved on P, and its solution x is verified on belongingness to S. If it holds, the original problem has been solved. Otherwise, a surface relaxation is considered, and a cut of x is formed utilizing a polyhedral cone with apex at x given by active P-constraints and an intersection of its extreme rays with the circumsurface S. Three versions of PSCM and two ways to form the cuts are presented and illustrated. Applicability of PSCM to solve permutation-based and Boolean linear optimization problems is justified. Area of practical applications of the results is indicated.
-
-
Optimal Control
-
Frontmatter
-
Operator Forms of the Maximum Principle and Iterative Algorithms in Optimal Control Problems
Alexander BuldaevDas Kapitel stellt eine neue Methode zur Lösung optimaler Steuerungsprobleme vor, indem notwendige Bedingungen in Operatorgleichungen umgewandelt werden, die als Fixpunktprobleme interpretiert werden können. Dieser Ansatz ermöglicht die Anwendung bekannter Algorithmen aus der Computermathematik. Die Autoren stellen neue iterative Algorithmen auf der Grundlage von Maximal- und Projektionsoperatoren vor, die ihre Äquivalenz zum Maximalprinzip demonstrieren. Diese Algorithmen bieten sukzessive nichtlokale Steuerungsannäherungen und Rechenstabilität, was sie vielversprechend macht, um die Effizienz der Lösung optimaler Steuerungsprobleme in verschiedenen Branchen zu verbessern.KI-Generiert
Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.
AbstractThe operator equations of the maximum principle are constructed in nonlinear optimal control problems in the form of fixed point problems in the control space. The equivalence of operator equations to the condition of the maximum principle is shown. The constructed operator forms of the maximum principle make it possible to apply and modify the well-known apparatus of the theory and methods of fixed points to search for extreme controls. The control operators under consideration define new iterative algorithms for finding extreme controls. The proposed iterative algorithms of fixed points of the maximum principle have the property of nonlocality of successive control approximations and the absence of a parametric procedure for improving the approximation at each iteration, which is characteristic of the well-known standard gradient type methods. -
Solution of the Problem of the Control System General Synthesis by Approximation of a Set of Extremals
Askhat Diveev, Sergey KonstantinovDieses Kapitel vertieft sich in das komplizierte Problem der allgemeinen Synthese von Kontrollsystemen und konzentriert sich auf die Herausforderung, eine Kontrollfunktion zu finden, die ein bestimmtes Kriterium für jede Ausgangsbedingung optimiert. Herkömmliche Methoden bleiben aufgrund der Komplexität und Unregelmäßigkeit praktischer Kontrollsysteme häufig hinter den Erwartungen zurück. Die Autoren schlagen einen zweistufigen Ansatz vor: Erstens die Lösung des optimalen Kontrollproblems für eine Reihe von Ausgangsbedingungen und zweitens die Annäherung dieser Lösungen mittels symbolischer Regressionsmethoden. Das Kapitel untersucht den Einsatz genetischer Algorithmen, insbesondere des Grey Wolf Optimizer, um optimale Kontrollfunktionen zu finden. Ein Computerexperiment mit einem mobilen Roboter demonstriert die Effektivität dieses Ansatzes und unterstreicht die Fähigkeit, optimale Flugbahnen zu annähern und nahezu optimale Kontrolle für unsichtbare Ausgangsbedingungen zu erreichen. Das Kapitel schließt mit der Betonung der praktischen Anwendbarkeit der vorgeschlagenen Methode, was sie zu einer wertvollen Ressource für Spezialisten in den Bereichen Steuerungssysteme und Optimierung macht.KI-Generiert
Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.
AbstractThe problem of the control system general synthesis is considered. This problem in general case requires finding the solution in the form of multidimensional function of a vector argument. Placing this control function into the right-hand part of differential equations of the control object model allows receiving the system of differential equations which partial solution from any initial condition of the given set is always optimal trajectory for the given quality criterion. In this paper, the problem of control general synthesis is solved based on the approximation of the set of optimal control problem solutions for different initial conditions. These solutions are called extremals. Previously, to solve the general synthesis problem, symbolic regression methods were used without approximation of extremals. Therefore it was often impossible to estimate the proximity of the found solution to the optimal one. To avoid this issue in this work initially we solve the optimal control problems for different initial conditions, and then these solutions are approximated by the symbolic regression method. In a presented computational experiment the proposed approach is used to solve the problem of the control system general synthesis for the mobile robot moving in the area with obstacles. -
Multi-point Stabilization Approach to the Optimal Control Problem with Uncertainties
Askhat Diveev, Elizaveta ShmalkoDieses Kapitel befasst sich mit dem Mehrpunkt-Stabilisierungsansatz für das Problem der optimalen Steuerung mit Unsicherheiten und geht auf die Herausforderung der Implementierung optimaler Steuerungslösungen in realen Szenarien ein. Er führt das Konzept der Machbarkeit in Kontrollsysteme ein und stellt sicher, dass kleine Modelländerungen die Leistung nicht beeinträchtigen. Der Aufsatz stellt eine Synthesemethode für Stabilisierungssysteme vor, die Kontrollfunktionen einbindet, um Machbarkeit zu erreichen. Insbesondere wendet sie ein Computerexperiment mit zwei mobilen Robotern an, bei dem der vorgeschlagene Ansatz mit traditionellen optimalen Kontrollmethoden verglichen wird. Die Ergebnisse zeigen die überlegene Robustheit des Mehrpunktstabilisierungsansatzes gegen Störungen und unterstreichen seine praktische Durchführbarkeit und sein Potenzial für Anwendungen in der realen Welt.KI-Generiert
Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.
AbstractThe article is studying the solution of the optimal control problem on the implementation. The problem here is that to implement the received optimal control a stabilization system is needed. But construction of such system makes changes to the mathematical model of the control object, so that the received control is not more optimal for that object. The paper introduces the concept of feasibility of control systems. An approach based on multi-point stabilization to receive feasible solutions of the optimal control problem is proposed. According to the approach, stabilization system synthesis is solved firstly. The synthesis problem can be solved by any known analytical or technical method. In the paper a symbolic regression method is used for the numerical solution of the synthesis problem. As far as the solution of synthesis problem is received, the differential equations of the model as one-parameter mappings acquire the contraction property, which reduces small model uncertainties. Then positions of stable points in the state space are found such that when switching from one point to another in some time interval the control object will move from initial conditions to terminal one with an optimal value of a quality criterion. In the computational experiment the efficiency of the proposed approach comparative to the direct approach is shown in the presence of uncertainties.
-
-
Optimization in Economy, Finance and Social Sciences
-
Frontmatter
-
Sociality is a Mechanism for Collective Action Dilemma Resolution
Tatiana Babkina, Anna Sedush, Olga Menshikova, Mikhail MyagkovDas Kapitel untersucht die Mechanismen hinter den Dilemmata kollektiven Handelns und konzentriert sich dabei insbesondere auf den Einfluss sozialer Interaktion auf die Zusammenarbeit. Anhand eines modifizierten Spiels um öffentliche Güter untersucht die Studie, wie Sozialisierung Entscheidungsfindung und Verhaltensmuster in Gruppen beeinflusst. Die Forschungsergebnisse unterstreichen die signifikante Verringerung des Trittbrettverhaltens und die verstärkte Zusammenarbeit zwischen sozial interagierenden Gruppen. Darüber hinaus werden geschlechtsspezifische Unterschiede im strategischen Verhalten und die Auswirkungen der Sozialisierung auf kollektive Ergebnisse untersucht. Die Ergebnisse bieten wertvolle Einsichten in die Verbesserung der Zusammenarbeit und die Verbesserung der Nutzung öffentlicher Güter.KI-Generiert
Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.
AbstractNumerous studies (mostly in economics) address the issue of collective action dilemmas for public goods, but few focus on psychological factors that affect individual decisions, and can be instrumental in designing effective mechanisms of public good provision. This paper reports on a series of laboratory experiments where “human sociality” is used as key variable in public goods type games. We show that once social ties have been formed (even after short-term socialization) among group members, it facilitates strategies that lead to much higher rates of public goods provision, and, thus make collective action a success. Moreover, the amount of participants who choose individual strategies decreases in two times. That is, it solves the common problem of free-riders because participants begin to exhibit more socially responsible character. We also demonstrate that results hold in situations that involve risk, and females tend to be better contributors to public goods than their male counterparts. -
Finite Games with Perturbed Payoffs
Vladimir A. Emelichev, Yury V. NikulinDas Kapitel befasst sich mit dem Einsatz der Spieltheorie zur Bewältigung multiobjektiver Entscheidungsfindung in komplexen Systemen mit undefinierten Faktoren. Es führt ein parametrisiertes Optimalitätsprinzip für endliche Spiele ein, das von Pareto-Optimalität bis hin zu Nash-Gleichgewicht reicht. Das Hauptergebnis ist die Ableitung einer Formel für den Quasistabilitätsradius, die das Ausmaß der Auszahlungsstörungen bestimmt, die die Optimalität des Spiels erhalten. Diese Analyse ist bedeutsam, da sie Einblicke in die Stabilität von Spielergebnissen unter Unsicherheit bietet, ein entscheidender Aspekt in verschiedenen Bereichen wie Wirtschaft, Verteidigung und Operationsforschung.KI-Generiert
Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.
AbstractThe parametric concept of equilibrium in a finite cooperative game of several players in a normal form is introduced. This concept is defined by the partitioning of the players into coalitions. In this situation, two extreme cases of this partitioning correspond to the Pareto optimal outcome and the Nash equilibrium outcome, respectively. The parameter space of admissible perturbations in such problem is formed by a set of additive matrices, with two arbitrary Hölder norms specified independently in the outcome and criterion spaces. The analysis of quasistability for a generalized optimal outcome under the perturbations of the linear payoff function coefficients is performed. The limiting level of such perturbations is found. -
Optimization in Big Data Analysis Based on Kolmogorov-Shannon Coding Methods
Georgy K. Kamenev, Ivan G. Kamenev, Daria A. AndrianovaDas Kapitel behandelt die Optimierung der Big-Data-Analyse, wobei der Schwerpunkt auf den Kodierungsmethoden von Kolmogorov und Shannon liegt. Es stellt eine finanzielle und wirtschaftliche Fallstudie vor, um die Anwendung dieser Methoden bei der Lösung komplexer Optimierungsprobleme auf multidimensionale Datensätze zu demonstrieren. Der Text unterstreicht die Bedeutung des Verständnisses der Struktur und Topologie von Datensätzen, um funktionale Werte effektiv zu optimieren. Außerdem wird die Methode der metrischen Datenanalyse (Method of Metric Data Analysis, MMDA) als leistungsstarkes Werkzeug zur Analyse und Visualisierung von modellgenerierten Daten präsentiert, insbesondere in Szenarien, in denen traditionelle Methoden zu kurz greifen. Das Kapitel schließt mit einer praktischen Anwendung der MMDA auf ein großes russisches Zahlungssystem, in der ihr Potenzial zur Identifizierung optimaler und suboptimaler Lösungen in der Big-Data-Forschung aufgezeigt wird.KI-Generiert
Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.
AbstractThe article describes the optimization problem solving for multidimensional and bulks Big Data (data with more than 10 characteristics and \(10^8\) observations or higher), as well as machine-generated data of unlimited volume. It is difficult to analyze and visualize data of such volume and complexity using traditional methods. In contrast (and in addition) to machine learning methods widely used in Big Data analysis, it is proposed to use stochastic methods of data sets’ coding and approximation using Kolmogorov-Shannon metric nets, which are optimal for the entropy of the code. While adapting these methods, new methods are proposed for metrics construction for characteristics with nominal and ordinal scales. -
Construction of a Technologically Feasible Cutting with Pierce Points Placement Constraints
Tatiana Makarovskikh, Anatoly PanyukovDas Kapitel befasst sich mit der Optimierung von Schneidprozessen, insbesondere dem Laserschneiden, das für die Formgebung technischer Werkstoffe mit komplexen Konstruktionen von entscheidender Bedeutung ist. Sie adressiert die Herausforderungen bei der Bestimmung optimaler Faktorkombinationen für Schnittqualität und Prozessgeschwindigkeit. Der Aufsatz stellt einen neuen Ansatz zur Minimierung sowohl des Schneidweges als auch der Wärmespeicherung vor, wobei ein memetischer Algorithmus verwendet wird, der genetische Algorithmen mit adaptiver großer Nachbarschaftssuche kombiniert. Der Schwerpunkt liegt auf der Lösung des Cutting Path Determination Problems (CPDP) und seiner Varianten wie dem General Traveling Salesman Problem (GTSP) und Continuous Cutting Problem (CCP). Im Kapitel wird ein polynomialer Algorithmus zur Konstruktion von Schnittwegen vorgestellt, der Lochpunktbeschränkungen erfüllt, minimale Ketten und effizientes Schneiden gewährleistet. Die Forschung ist insbesondere für Branchen relevant, die präzise und effiziente Schneidprozesse erfordern, wie Luft- und Raumfahrt, Automobil und Fertigung.KI-Generiert
Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.
AbstractThe routing problem arising in cutting is considered. This task is to find the path of the cutting tool that satisfies the technological restrictions and the pierce points placement constraints. Since the time for piercing significantly affects the duration of the cutting process, it is necessary to reduce both the number of pierce points and the distance between successive fragments of the path. This research is devoted to routing problems in plane graphs, which are homeomorphic images of cutting plans. The route covering all the borders of the cut parts determines the path of the cutting tool. The technological constraints are: (1) the absence of intersection of the route internal faces of any initial part with the edges of its remaining part (OE-condition); (2) self-intersections of the cutting path prohibition (NOE-condition); (3) the initial vertices of the covering chains must allow piercing (PPOE-condition). The report presents the polynomial algorithm for constructing a cutting route that satisfies the introduced restrictions and consists of a minimum number of chains. The first two classes are considered and well studied earlier. In this paper we considered the class of PPOE-routes in plane graphs, i.e. routes with restrictions on choice of starting vertices (corresponding the pierce points on a sheet) of covering chains. We proved the necessary and sufficient conditions of these routes existence. Also we developed the polynomial time algorithm PPOE-routing for obtaining of such routes and proved its correctness. -
Effectiveness of Nash Equilibrium Search Algorithms in Four-Person Games in General and Multi-matrix Settings
Ustav Malkov, Vlasta MalkovaDas Kapitel geht der Effektivität von Nash-Gleichgewichtssuchalgorithmen in Vier-Personen-Spielen im Allgemeinen und in Multimatrix-Settings nach. Es beginnt damit, dass das Problem als nichtlineares Programmierproblem dargestellt wird, ähnlich wie bei Bimatrix- und Drei-Personen-Spielen. Der zunächst für Bimatrix- und Drei-Personen-Spiele erfolgreiche Lokale Suchalgorithmus (LS) ist in Vierer-Spielen mit erhöhter Komplexität konfrontiert, insbesondere was Rechenzeit und -ressourcen angeht. Das Kapitel stellt eine kompakte Beschreibung des LS-Algorithmus für Vier-Personen-Spiele vor, die eine effizientere Implementierung in Programmierumgebungen wie Matlab und Python ermöglicht. Die Formulierung der Multi-Matrix ist für Vier-Personen-Spiele verallgemeinert und verwandelt das Problem in ein quadratisches Programmierproblem mit linearen Bedingungen. Dies ermöglicht die Anwendung eines modifizierten Lemke-Howson-Algorithmus, der eine bemerkenswerte Effizienz bei der Lösung von Spielen mit Abmessungen bis zu mehreren hundert Strategien zeigt. Numerische Experimente bestätigen die Wirksamkeit dieser Ansätze, wobei der modifizierte Lemke-Howson-Algorithmus den lokalen Suchalgorithmus in Multimatrix-Settings um mehrere Größenordnungen übertrifft. Das Kapitel schließt mit der Hervorhebung der überlegenen Leistung des modifizierten Lemke-Howson-Algorithmus bei der Lösung von Vier-Personen-Spielen, was ihn zu einer herausragenden Methode im Bereich der Spieltheorie und -optimierung macht.KI-Generiert
Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.
AbstractThe effectiveness of using the local search algorithm (mountain climbing) and the Lemke–Howson method for searching for Nash equilibrium in 4-person games in general and multi-matrix settings using the Matlab, Python, and FORTRAN software environments are studied. The local search procedure implemented in the Python environment, involving the use of multiplication of a multi-dimensional matrix by a vector, turned out to be an effective tool. The modification of the Lemke–Howson method for multi-matrix formulation showed very good results.
-
-
Applications
-
Frontmatter
-
Polynomially Solvable Subcases for the Approximate Solution of Multi-machine Scheduling Problems
Alexander Lazarev, Darya Lemtyuzhnikova, Nikolay Pravdivets, Frank WernerDas Kapitel befasst sich mit der Komplexität von Problemen bei der Planung mehrerer Maschinen, die als NP-hart bekannt sind. Er untersucht sowohl exakte als auch annähernde Methoden zur Lösung dieser Probleme und hebt die Zielkonflikte zwischen Recheneffizienz und Lösungsgenauigkeit hervor. Der zentrale Beitrag ist die Einführung eines metrischen Ansatzes, der Instanzen auf polynmisch lösbare Teilräume projiziert und so die Annäherung von Lösungen mit begrenzten absoluten Fehlern ermöglicht. Dieser Ansatz wird durch umfassende rechnerische Experimente validiert, die seine Effektivität im Umgang mit groß angelegten Planungsproblemen unter Beweis stellen. Das Kapitel diskutiert auch die Implikationen dieser Methode für praktische Anwendungen und schlägt Wege für weitere Forschung vor.KI-Generiert
Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.
AbstractNew metrics for different classes of scheduling problems are introduced. We show how approximate solutions of NP-hard problems can be obtained using these metrics. To do this, we solve the optimization problem in which the introduced metric is used as the objective function, and a system of linear inequalities of (pseudo-)polynomial solvable instances of the initial problem represents the constraints. As a result, we find a projection of the considered sub-instance onto the set of solvable cases of the problem in the introduced metric. -
On Numerical Solving an Equilibrium Problem for a 3D Elastic Body with a Crack Under Coulomb Friction Law
Robert Namm, Georgiy TsoyDas Kapitel behandelt die numerische Lösung eines Gleichgewichtsproblems für einen 3D-elastischen Körper mit Riss nach dem Coulomb-Reibungsgesetz. Es führt eine Methode sukzessiver Annäherungen und ein modifiziertes Dualitätsschema ein, das auf modifizierten Lagrange-Funktionalitäten beruht, die die Recheneffizienz erhöhen. Die Finite-Elemente-Methode wird für die numerische Umsetzung verwendet, und die Wirksamkeit des Algorithmus wird durch rechnerische Experimente nachgewiesen. In diesem Kapitel werden auch die Herausforderungen und zukünftigen Forschungsrichtungen im Umgang mit der unebenen Natur des Problems diskutiert.KI-Generiert
Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.
AbstractAn equilibrium problem for a 3D elastic body with a crack is considered. We assume that nonpenetration boundary conditions and Coulomb friction law are imposed on the crack faces. This leads to the formulation of a problem as a quasi-variational inequality. For solving auxiliary problems with given friction occurring on each outer step of the method of successive approximations we use duality scheme based on the modified Lagrange functional. Computational results illustrating the efficiency of the proposed algorithm are presented. -
On Optimal Selection of Coefficients of a Controller in the Point Stabilization Problem for a Robot-Wheel
Alexander Pesterev, Yury Morozov, Ivan MatrosovDas Kapitel untersucht das Problem der Punktstabilisierung für ein Roboterrad und konzentriert sich auf die optimale Auswahl der Koeffizienten in einem Kontrollgesetz, um globale Stabilität und Zufriedenheit mit Einschränkungen zu gewährleisten. Es stellt ein vereinfachtes Modell eines Radroboters vor, der durch ein Steuerdrehmoment angetrieben wird, und diskutiert die Synthese eines Rückkopplungsgesetzes mit verschachtelten Sättigungsfaktoren. Die Analyse zeigt, wie man Rückkopplungskoeffizienten auswählt, um die Leistung des Controllers zu optimieren und sicherzustellen, dass das Phasenporträt des Closed-Loop-Systems dem eines linearen Systems mit einem stabilen Knoten ähnelt. Die Lösung des Optimierungsproblems wird als eine Familie von Feedback-Koeffizienten mit nur einem Parameter dargestellt, wobei weitere Forschungsarbeiten geplant sind, um die praktischen Auswirkungen dieser Entscheidungen zu untersuchen.KI-Generiert
Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.
AbstractThe point stabilization problem for a robot-wheel is considered. The problem consists in synthesizing control torque in the form of feedback that brings the wheel from an arbitrary initial position on a straight line to a given one, with the control torque and the maximum velocity of wheel motion being constrained. To meet the phase and control constraints, an advanced feedback law in the form of nested saturation functions is suggested. Two of the four coefficients employed in the saturation functions are uniquely determined by the limit value of the control torque and the maximum allowed wheel velocity, while the selection of the other two coefficients can be used to optimize the performance of the controller. In this study, the optimality is meant in the sense that the phase portrait of the closed-loop system is similar to that of a stable node, with the asymptotic rate of decrease of the distance to the target point being as high as possible. The discussion is illustrated by numerical examples.
-
-
Backmatter
- Titel
- Advances in Optimization and Applications
- Herausgegeben von
-
Nicholas Olenev
Yuri Evtushenko
Prof. Michael Khachay
Vlasta Malkova
- Copyright-Jahr
- 2020
- Electronic ISBN
- 978-3-030-65739-0
- Print ISBN
- 978-3-030-65738-3
- DOI
- https://doi.org/10.1007/978-3-030-65739-0
Informationen zur Barrierefreiheit für dieses Buch folgen in Kürze. Wir arbeiten daran, sie so schnell wie möglich verfügbar zu machen. Vielen Dank für Ihre Geduld.
