Search

A gradient-based search method (GBSM) is developed to solve multi-objective optimization problems. It uses the multi-objective gradient information to construct descent directions, i.e., Pareto descent directions (PDDs), to accelerate the convergence. In addition, a multi-objective evolutionary algorithm based on decomposition is adopted to improve the diversity. The comparisons between GBSM with several selected multi-objective evolutionary algorithms and gradient based algorithms on benchmark functions indicate that the proposed method performs competitively and effectively.

We consider relative or subjective optimization problems where the goal function and feasible set are dependent on the current state of the system under consideration. In general, they are formulated as quasi-equilibrium problems, hence finding their solutions may be rather difficult. We describe a rather general class of relative optimization problems in metric spaces, which in addition depend on the starting state. We also utilize quasi-equilibrium type formulations of these problems and show that they admit rather simple descent solution methods. This approach gives suitable trajectories tending to a relatively optimal state. We describe several examples of applications of these problems. Preliminary results of computational experiments confirmed efficiency of the proposed method.

This research is focused on Unconstrained Optimization problems. Among a number of methods that can be used to solve Unconstrained Optimization problems we have worked on Gradient and Coordinate Descent methods. Step size plays an important role for optimization. Here we have performed numerical experiment with Gradient and Coordinate Descent method for several step size choices. Comparison between different variants of Gradient and Coordinate Descent methods and their efficiency are demonstrated by implementing in loss functions minimization problem.

In this study, we focus mainly on the problem of finding the minimum-length path through a set of circular regions by a fixed-wing unmanned aerial vehicle. Such a problem is referred to as the Dubins traveling salesman problem with neighborhoods (DTSPN). Algorithms developed in the literature for solving DTSPN either are computationally demanding or generate low-quality solutions. To achieve a better trade-off between solution quality and computational cost, an efficient gradient-free descent method is designed. The core idea of the descent method is to decompose DTSPN into a series of subproblems, each of which consists of finding the minimum-length path of a Dubins vehicle from a configuration to another configuration via an intermediate circular region. By analyzing the geometric properties of the subproblems, we use a bisection method to solve the subproblems. As a result, the descent method can efficiently address DTSPN by successively solving a series of subproblems. Finally, several numerical experiments are carried out to demonstrate the descent method in comparison with several existing algorithms.

Objective to implement the neighborhood descent heuristic approach into solving the lotsizing problem. Methods a variable neighborhood descent heuristic approach and a framework of lotsizing problem. Results dynamic lotsizing problem is supposed to be an NPhard problem ndash a problem for which there is no known polynomial algorithm so the time to find a solution grows with a problem size. In the article we explain thenbsp basic lotsizing lotsizing in closedloop describe methods used by other researchers and provide reasoning for using a variable neighborhood descent heuristic method. Implementation of the method is presented in a numerical example. Application of the method significantly reduces estimation time when searching for lotsizing problem solution. Application of the method significantly reduces estimation time when searching for lotsizing problem solution. Scientific novelty the method may significantly reduce time expenses during the solution of the lotsizing problem. Practical significance the method may be implemented for solving the lotsizing problem in various industries such as pulp and paper consumer goods industry and heavy industry.

A variation of the One-to-one Pickup and Delivery Problem (OPDP) in connected graphs, the Split Demand One-to-one Pickup and Delivery Problem with the Shortest-path Transport along Real-life Paths (SDOPDPSTRP) is abstracted from passenger train operation plans based on networks. Unlike the classical OPDP, in the SDOPDPSTRP: the demands can be split and must be transported along the shortest path according to passengers requirements and vehicles should travel along a real-life path. A new kind of integer programming model is formulated for the SDOPDPSTRP based on the connection relationship between pickup-delivery demands (pd-pairs). Two different categories of splitting strategies are proposed to solve the SDOPDPSTRP: split the demands before the calculation and split the demands during the calculation. Two Multi-Start Variable Neighborhood Descent (a MS_VND originating from the other literature and a new MS_VND' IN developed in this article) and seven neighborhood operators are proposed for these two splitting strategies to solve the SDOPDPSTRP. The results show that Approach III outperforms Approach I and Approach II in terms of average solutions with the same algorithm termination conditions and in terms of time efficiency, which has great practical significance for real-life transport organizations.

This paper proposes a discrete-time, distributed algorithm for multi-agent networks to achieve the minimum l1-norm solution to a group of linear equations known to possess a family of solutions. We assume each agent in the network knows only one equation and can communicate with only its neighbors. The algorithm is developed based on a combination of the projection-consensus idea and the sub-gradient descent method. Given the underlying network graph to be directed and strongly connected, we prove that the algorithm enables all agents to achieve a common minimum l1-norm solution. The major difficulty to be dealt with is the non-smooth nature of the norm and the lack of strict convexity of the associated relevant performance index.

Con el objetivo de aportar una nueva visión en la resolución de algunos problemas de optimización, este artículo versará acerca de la deducción de un nuevo método numérico en optimización. Para ello, se planteará una modelización genérica de los problemas que se plantean resolver.De este modo, se introducirán los preliminares necesarios para poder proceder con la deducción queposteriormente se hará. En este sentido, el método planteado se enmarcará dentro de los métodosde direcciones factibles, por lo que se introducirán conceptos topológicos sencillos (relacionados conel conjunto admisible) y definiciones relacionadas con las direcciones factibles y de descenso que sepodrán considerar. Posteriormente se procederá con la deducción del algoritmo que presenta esteartículo, procurando que el lector pueda observar el procedimiento de construcción del mismo. Ade-más, se introducirán los aspectos computacionales del método y se propondrán una serie de códigosque permitirán implementar el algoritmo en un lenguaje de programación, en el caso de este artículose utilizará MatLab. Finalmente se mostrarán los resultados obtenidos al ejecutar el método junto conotros métodos ya conocidos para poder comparar los resultados obtenidos. De esta forma, se finali-zará aportando las conclusiones más relevantes y las futuras líneas de investigación para mejorar elmétodo presentado.

Refined product distribution is an application of the Multi-compartment Vehicle Routing Problem (MCVRP), which simultaneously considers the vehicle routing, the assignment of heterogonous vehicles and loading policies of multi-compartment. First, we develop an optimization model with the objective of delivering on-time and minimizing transportation cost. Then we propose a Multi-objective Variable Neighborhood Descent Algorithm (MOVND), where the [Formula: see text]-constraint method transforms the original problem into a series of sub-problems of single objective with constraints. Finally, the efficiency of the proposed algorithm is verified by conducting a large number of small and large instances. Mainly including (i) compared with the classical NSGA-2 algorithm for multi-objective VRP, MOVND provides better performance in terms of convergence, spread and distribution; (ii) the multi-compartment vehicles are able to carry a variety of products simultaneously, which can improve the effective utilization of vehicle space and meet the needs of different customers in a single transportation. In addition, heterogonous vehicles that take full advantage of the characteristics of different vehicles are superior to homogeneous ones in terms of operating cost in the practice of the refined product distribution.

In this paper, the distributed optimization problem over multi-cluster networks is considered. Different from the existing works, this paper studies the optimization algorithm under uncoordinated step sizes. More specifically, by combining a random sleep strategy and the round-robin communication among clusters, a new hierarchical algorithm is developed to solve the considered problem. In the proposed algorithm, the random sleep strategy enables each agent to independently choose either performing the projected subgradient descent, or keeping the previous estimate by a Bernoulli decision, based on which the step size of each agent is selected as an uncoordinated form that only relates to the independent Bernoulli decision variable. Technically, by introducing a key definition on the algorithm history, it is proven that the estimates of the proposed algorithm can converge to the optimal solution even with the uncoordinated step sizes. In addition, we also study the convergence performance of the proposed algorithm with simpler constant step sizes. In this case, it is proven that the random sleep strategy can efficiently improve the convergence accuracy of the algorithm. Finally, the theoretical findings are verified via simulation examples.

Descent & landing (D&L) on small planetary bodies are scientifically rewarding exploration missions but they are technically challenging due to the complex and poorly-known environment around those bodies. The standard guidance synthesis approach considers nominal conditions and applies optimal control theory to obtain guidance law gains, followed by intensive verification and validation. In this article, it is shown that the standard approach may yield gains that are not optimal once dispersions (and/or other optimality metrics) are taken into account and a tuning approach is then proposed based on a priori methodological system assessment. The proposed approach employs systematic high-fidelity simulations to generate trade-off maps. These maps can be generated by on ground operators based on the best estimated conditions and uploaded to the spacecraft as it approaches the target. The proposed systematic guidance tuning and resulting maps also provide a valuable understanding of the system dynamics towards the application of other industry-oriented tools such as structured Η∞ optimisation. It is shown that the proposed tuning enables propellant consumption reductions of around 40% compared to state-of-practice gain selections.

In the paper we propose an accelerated directional search method with non-euclidian prox-structure. We consider convex unconstraint optimization problem in $\mathbb{R}^n$. For simplicity we start from the zero point. We expect in advance that 1-norm of the solution is close enough to its 2-norm. In this case the standard accelerated Nesterov's directional search method can be improved. In the paper we show how to make Nesterov's method $n$-times faster (up to a $\log n$-factor) in this case. The basic idea is to use linear coupling, proposed by Allen-Zhu & Orecchia in 2014, and to make Grad-step in 2-norm, but Mirr-step in 1-norm. We show that for constrained optimization problems this approach stable upon an obstacle., in Russian, 13 pages, 3 figures

With the grown of global concern with environmental issues and incentives on the part of governments, the use of electric vehicles (EVs) by companies has increased. By joining the interest of governments on minimizing the costs of building the recharging infrastructure and of companies on minimizing their transport costs with the adoption of electric vehicles in their fleet, a bilevel optimization problem arises. An approach that combines the Variable Neighborhood Search (VND) with an Ant Colony Optimization (ACO) to solve this bilevel model is proposed here. The results of the computational experiments using different benchmark instances indicate the superior performance of the proposed approach, mainly in the allocation of the charging infrastructure (objective of the leader). Also, the proposal found better solutions than those from the literature while maintains the percentage of electric vehicles that compose the fleet above the required limit.

This paper deals with the Green Electric Vehicle Routing Problem with Time Window and Mixed Fleet and presents a Mixed Integer Linear Programming formulation for it. Initially, we applied the CPLEX solver in this formulation. Then, to reduce the computational time, we used Local Branching and Variable Neighborhood Descent Branching (VNDB) methods. We did computational experiments with a simple adaptation of the 100-customers Solomon’s benchmark instances. The results showed that the three solution strategies reached the optimal solution. However, the running time of the VNDB is considerably smaller than those required by the other two solution methods. Therefore, this fact proves that the VNDB is the more efficient technique in the tested scenario.

A direct multiple shooting (MS) method is implemented to solve optimal control problems (OCP) in the Mayer form. The use of an MS method gives rise to the so-called ‘continuity conditions’ that must be satisfied together with general algebraic equality and inequality constraints. The resulting finite nonlinear optimization problem is solved by a first-order descent method based on the filter methodology. In the equivalent tri-objective problem, the descent method aims to minimize the objective function, the violation of the ‘continuity conditions’ and the violation of the algebraic constraints simultaneously. The numerical experiments carried out with different types of benchmark OCP are encouraging., We acknowledge the financial support of CIDEM, R&D unit funded by the FCT - Portuguese Foundation for the Development of Science and Technology, Ministry of Science, Technology and Higher Education, under the Project UID/EMS/0615/2019, and FCT within the Projects Scope: UID/CEC/00319/2019 and UID/MAT/00013/2013.

International audience; In this paper, we consider the integrated Berth Allocation and Crane Assignment problem, with availability constraints and high tides restrictions, in bulk port context. We were inspired by a real case study of a port owned by our industrial partner. The objective is to minimize the total penalty of tardiness. First, we implemented a greedy heuristic to compute an initial solution. Then, we proposed a sequential Variable Neighborhood Descent (seq-VND) for the problem. In addition, we compared the efficiency of different scenarios for the seq-VND against results given by a mathematical model for the problem.

For the case of public transport, we consider the problem of demand estimation. Given an origin-destination matrix representing the public transport demand, the distribution of flow among different lines can be obtained assuming that it corresponds to a certain equilibrium characterized by an optimization problem. In particular we will focus on the assignment model proposed by Cepeda et al. (2006). However the knowledge of origin-destination matrix is expensive and sometimes unaffordable in practice. Traditionally, it is estimated using statistical or econometrical considerations. In this work, we explore the estimation through the numerical solution of a bilevel optimization problem. One disadvantage of this formulation is the difficulty of obtaining descent directions, hence, for the resolution of the optimization problem we use a derivative-free method. This method was applied for small networks getting good results.

This paper deals with estimating model parameters in graphical models. We reformulate it as an information geometric optimization problem and introduce a natural gradient descent strategy that incorporates additional meta parameters. We show that our approach is a strong alternative to the celebrated EM approach for learning in graphical models. Actually, our natural gradient based strategy leads to learning optimal parameters for the final objective function without artificially trying to fit a distribution that may not correspond to the real one. We support our theoretical findings with the question of trend detection in financial markets and show that the learned model performs better than traditional practitioner methods and is less prone to overfitting., 18 pages, 9 figures

It is well-known that for general convex optimization problems, block-coordinate descent can get stuck in poor local optima. Despite that, versions of this method known as convergent message passing are very successful to approximately solve the dual LP relaxation of the MAP inference problem in graphical models. In attempt to identify the reason why these methods often achieve good local minima, we argue that if in block-coordinate descent the set of minimizers over a variable block has multiple elements, one should choose an element from the relative interior of this set. We show that this rule is not worse than any other rule for choosing block-minimizers. Based on this observation, we develop a theoretical framework for block-coordinate descent applied to general convex problems. We illustrate this theory on convergent message-passing methods.

The robust result of analytical fuzzy reliability analysis (FRA) represents the main effort at evaluating the fuzzy reliability index. In this study, a bioloop-based hybrid method is propos...

In this article, a deterministic annealing neural network algorithm is proposed to solve the minimum concave cost transportation problem. Specifically, the algorithm is derived from two neural network models and Lagrange–barrier functions. The Lagrange function is used to handle linear equality constraints, and the barrier function is used to force the solution to move to the global or near-global optimal solution. In both neural network models, two descent directions are constructed, and an iterative procedure for the optimization of the neural network is proposed. As a result, two corresponding Lyapunov functions are naturally obtained from these two descent directions. Furthermore, the proposed neural network models are proved to be completely stable and converge to the stable equilibrium state, therefore, the proposed algorithm converges. At last, the computer simulations on several test problems are made, and the results indicate that the proposed algorithm always generates global or near-global optimal solutions.

The idea that the brain functions so as to minimize certain costs pervades theoretical neuroscience. Because a cost function by itself does not predict how the brain finds its minima, additional assumptions about the optimization method need to be made to predict the dynamics of physiological quantities. In this context, steepest descent (also called gradient descent) is often suggested as an algorithmic principle of optimization potentially implemented by the brain. In practice, researchers often consider the vector of partial derivatives as the gradient. However, the definition of the gradient and the notion of a steepest direction depend on the choice of a metric. Because the choice of the metric involves a large number of degrees of freedom, the predictive power of models that are based on gradient descent must be called into question, unless there are strong constraints on the choice of the metric. Here, we provide a didactic review of the mathematics of gradient descent, illustrate common pitfalls of using gradient descent as a principle of brain function with examples from the literature, and propose ways forward to constrain the metric., PLoS Computational Biology, 16 (4), ISSN:1553-734X, ISSN:1553-7358

We propose a two-layer, semi-decentralized algorithm to compute a local solution to the Stackelberg equilibrium problem in aggregative games with coupling constraints. Specifically, we focus on a single-leader, multiple follower problem, and after equivalently recasting the Stackelberg game as a mathematical program with complementarity constraints (MPCC), we iteratively convexify a regularized version of the MPCC as inner problem, whose solution generates a sequence of feasible descent directions for the original MPCC. Thus, by pursuing a descent direction at every outer iteration, we establish convergence to a local Stackelberg equilibrium. Finally, the proposed algorithm is tested on a numerical case study, a hierarchical instance of the charging coordination problem of Plug-in Electric Vehicles (PEVs).

We suggest a modified descent splitting method for optimization problems having a special decomposable structure. The proposed modification maintains the basic convergence properties but enables one to reduce computational efforts per iteration and to provide computations in a distributed manner. On the one hand, it consists in component-wise choice of descent directions together with a special threshold control. On the other hand, it involves a simple adaptive step-size choice, which takes into account the problem behavior along the iteration sequence. Preliminary computational tests confirm the efficiency of the proposed modification.

Block-coordinate descent (BCD) is a popular method in large-scale optimization. Unfortunately, its fixed points are not global optima even for convex problems. A succinct characterization of convex problems optimally solvable by BCD is unknown. Focusing on linear programs, we show that BCD fixed points are identical to fixed points of another method, which uses constraint propagation to detect infeasibility of a system of linear inequalities in a primal-dual loop (a special case of this method is the Virtual Arc Consistency algorithm by Cooper et al.). This implies that BCD fixed points are global optima iff a certain propagation rule decides feasibility of a certain class of systems of linear inequalities.

This paper develops a distributed discrete-time algorithm to seek Nash equilibrium for games under Markovian switching topologies. In the game problem considered in this paper, all players are assumed to use gradient-like descent method to update their own actions based on the estimation of all the other players’ actions with the intention to minimize their cost functions. All players exchange their estimation information with their neighbors at each discrete time instant through some undirected graphs that are Markovian switching. Suppose that the transition probability matrix is specified and the union of all switching topologies is connected, it is shown that the players’ actions can converge to the unique Nash equilibrium in the mean square sense for any initial condition. The convergence result is established by utilizing Lyapunov stability theory for discrete-time stochastic systems.

This paper present algorithms for solving a single machine scheduling problem to minimize the sum of total completion times, total tardiness,maxim-um tardiness,and maximum earliness.The single machine total tardiness problem is already NP-hard, so the consider problem is strongly NP-hard, and several algorithms are used to solve it. Branch and bound algorithmwith dominance ruleand local search algorit- hms are proposed for the problem. For the Branch and bound algorithm results- show that using dominance rule improve the performance of the algorithm in both computation times and optimal values,but it need longer times.Thus we tackle the problemof large sizes with local search algorit- hms descent method, simulated annealing and tabusearch. The perfomance of these algorithms is evaluated on a large set of test problems and the results are compared.The computational results show that simulated annealing algorithm and Tabu search algorithm are better than Descent method with preference to simulated annealing algorithm,and show that the three algorithms find optimal or near optimal solutions inreasonable times.

An innovative computational guidance framework is proposed for planetary powered descent using collaborative optimization approach. First, the dynamical model and constraints for planetary powered descent are presented. Then, using collaborative optimization strategy, the computational guidance framework for powered descent is formulated as a multi-discipline optimization problem including trajectory optimization, optimal guidance, and system-level optimization. Finally, the computational guidance approach employs three algorithms for respectively solving the three optimization modules to implement numerical simulations. The optimality and robustness of the computational guidance approach are verified with all constraints satisfied even in the presence of initial state uncertainty.

Some methods for finding the maximum feasible subsystems of systems of linear inequalities are considered. The problem of finding the most accurate algorithm in a parametric family of linear classification algorithms is one of the most important problems in machine learning. In order to solve this discrete optimization problem, an exact (combinatorial) algorithm, its approximations (relaxation and greedy combinatorial descent algorithms), and the approximation algorithm are given. The latter consists in replacing the original discrete optimization problem with a nonlinear programming problem by changing from linear inequalities to their sigmoid functions. The initial results of their comparison are presented.

We revisit the static coverage control problem for placement of vehicles with simple motion on the real line, under the assumption that the cost is a polynomial function of the locations of the vehicles. The main contribution of this paper is to demonstrate the use of tools from numerical algebraic geometry, in particular, a numerical polynomial homotopy continuation method that guarantees to find all solutions of polynomial equations, in order to characterize the \emph{global minima} for the coverage control problem. The results are then compared against a classic distributed approach involving the use of Lloyd descent, which is known to converge only to a local minimum under certain technical conditions., 6 pages, 2 figures

In this paper, we propose a distributed algorithm, called Directed-Distributed Subgradient Descent (D-DSD), to solve multi-agent optimization problems over directed graphs. Existing algorithms mostly deal with similar problems under the assumption of undirected networks, i.e., requiring the weight matrices to be doubly-stochastic. The row-stochasticity of the weight matrix guarantees that all agents reach consensus, while the column-stochasticity ensures that each agent’s local (sub)gradient contributes equally to the global objective. In a directed graph, however, it may not be possible to construct a doubly-stochastic weight matrix in a distributed manner. We overcome this difficulty by augmenting an additional variable for each agent to record the change in the state evolution. In each iteration, the algorithm simultaneously constructs a row-stochastic matrix and a column-stochastic matrix instead of only a doubly-stochastic matrix. The convergence of the new weight matrix, depending on the row-stochastic and column-stochastic matrices, ensures agents to reach both consensus and optimality. The analysis shows that the proposed algorithm converges at a rate of O ( ln k k ) , where k is the number of iterations.

In this paper, we present a new nonmonotone memory gradient algorithm for unconstrained optimization problems. An attractive property of the proposed method is that the search direction always provides sufficient descent step at each iteration. This property is independent of the line search used. Under mild assumptions, the global and local convergence results of the proposed algorithm are established respectively. Numerical results are also reported to show that the proposed method is suitable to solve large-scale optimization problems and is more stable than other similar methods in practical computation.

In this paper, we consider the large-scale case of the robust beamforming problem with interference temperature constraints. Previous semidefinite relaxation (SDR) method becomes impracticable because of its expensive computational cost. Even successive convex approximation (SCA) method, the state-of-the-art method, cannot tackle this problem efficiently. Thus, we are motivated to design two efficient first-order methods, multi-block alternating direction method of multipliers (ADMM) and linear programming-assisted subgradient descent (LPA-SD), to solve it. Numerical results demonstrate the potential of our proposed methods in terms of both computational efficiency and solution quality.

This paper investigates different vector step-size adaptation approaches for non-stationary online, continual prediction problems. Vanilla stochastic gradient descent can be considerably improved by scaling the update with a vector of appropriately chosen step-sizes. Many methods, including AdaGrad, RMSProp, and AMSGrad, keep statistics about the learning process to approximate a second order update---a vector approximation of the inverse Hessian. Another family of approaches use meta-gradient descent to adapt the step-size parameters to minimize prediction error. These meta-descent strategies are promising for non-stationary problems, but have not been as extensively explored as quasi-second order methods. We first derive a general, incremental meta-descent algorithm, called AdaGain, designed to be applicable to a much broader range of algorithms, including those with semi-gradient updates or even those with accelerations, such as RMSProp. We provide an empirical comparison of methods from both families. We conclude that methods from both families can perform well, but in non-stationary prediction problems the meta-descent methods exhibit advantages. Our method is particularly robust across several prediction problems, and is competitive with the state-of-the-art method on a large-scale, time-series prediction problem on real data from a mobile robot., Comment: AAAI Conference on Artificial Intelligence 2019. v2: Correction to Baird's counterexample. A bug in the code lead to results being reported for AMSGrad in this experiment, when they were actually results for Adam

Many problems in smart solution development make use of discrete optimization techniques. It is expected that smart cities will have a constant need for parcel delivery and vehicle routing which is heavily reliant on discrete optimization. In this paper we present an improvement to the Variable neighborhood descent (VND) algorithm for discrete optimization. Our method makes the search procedure more exhaustive at the expense of time performance. Instead of keeping track of a single solution which is being improved, we allow branching of the solution into at most M promising solutions and keep track of them. Our experiments show that the proposed method produces results superior to VND. We analyze the impact on time complexity and give general usage guidelines for our method.

In this study, we tend to propose a replacement hybrid algorithmic rule which mixes the search directions like Steepest Descent (SD) and Quasi-Newton (QN). First, we tend to develop a replacement search direction for combined conjugate gradient (CG) and QN strategies. Second, we tend to depict a replacement positive CG methodology that possesses the adequate descent property with sturdy Wolfe line search. We tend to conjointly prove a replacement theorem to make sure global convergence property is underneath some given conditions. Our numerical results show that the new algorithmic rule is powerful as compared to different standard high scale CG strategies.

In this paper, a stochastic trust region method is proposed to solve unconstrained minimization problems with stochastic objectives. Particularly, this method can be used to deal with nonconvex problems. At each iteration, we construct a quadratic model of the objective function. In the model, stochastic gradient is used to take the place of deterministic gradient for both the determination of descent directions and the approximation of the Hessians of the objective function. The behavior and the convergence properties of the proposed method are discussed under some reasonable conditions. Some preliminary numerical results show that our method is potentially efficient.

Variable neighborhood searches and evolutionary techniques have shown their effectiveness when dealing with many combinatorial optimisation problems. This study proposes to combine these two techniques for addressing the routing problem using electric and modular vehicles. This is a recent problem that aims to overcome recharging battery constraints while maintaining a certain performance regarding to the fleet cost and the traveled distance. An experimental study on benchmark instances is provided to show the relevance of the proposed algorithm.

This paper introduces a continuous formulation for compound state-triggered constraints, which are generalizations of the recently introduced state-triggered constraints. State-triggered constraints are different from ordinary constraints found in optimal control in that they use a state-dependent trigger condition to enable or disable a constraint condition, and can be expressed as continuous functions that are readily handled by successive convexification. Compound state-triggered constraints go a step further, giving designers the ability to compose trigger and constraint conditions using Boolean and and or operations. Simulations of the 6-degree-of-freedom (DoF) powered descent guidance problem obtained using successive convexification are presented to illustrate the utility of state-triggered and compound state-triggered constraints. The examples employ a velocity-triggered angle of attack constraint to alleviate aerodynamic loads, and a collision avoidance constraint to avoid large geological formations. In particular, the velocity-triggered angle of attack constraint demonstrates the ability of state-triggered constraints to introduce new constraint phases to the solution without resorting to combinatorial techniques., Comment: This paper is a modified version of the one presented at the 2019 AIAA Guidance, Navigation, and Control Conference (SciTech) in San Diego, California (17 pages, 10 figures)

In this paper, we present exploitability descent, a new algorithm to compute approximate equilibria in two-player zero-sum extensive-form games with imperfect information, by direct policy optimization against worst-case opponents. We prove that when following this optimization, the exploitability of a player's strategy converges asymptotically to zero, and hence when both players employ this optimization, the joint policies converge to a Nash equilibrium. Unlike fictitious play (XFP) and counterfactual regret minimization (CFR), our convergence result pertains to the policies being optimized rather than the average policies. Our experiments demonstrate convergence rates comparable to XFP and CFR in four benchmark games in the tabular case. Using function approximation, we find that our algorithm outperforms the tabular version in two of the games, which, to the best of our knowledge, is the first such result in imperfect information games among this class of algorithms., Comment: IJCAI 2019, 11 pages, 1 figure

The problem of convex optimization is studied. Usually in convex optimization the minimization is over a d-dimensional domain. Very often the convergence rate of an optimization algorithm depends on the dimension d. The algorithms studied in this paper utilize dictionaries instead of a canonical basis used in the coordinate descent algorithms. We show how this approach allows us to reduce dimensionality of the problem. Also, we investigate which properties of a dictionary are beneficial for the convergence rate of typical greedy-type algorithms.

In this paper we study a hub location problem in which the hubs to be located must form a set of interconnecting lines. The objective is to minimize the total weighted travel time between all pairs of nodes while taking into account a budget constraint on the total set-up cost of the hub network. A mathematical programming formulation, a Benders-branch-and-cut algorithm and several heuristic algorithms, based on variable neighborhood descent, greedy randomized adaptive search, and adaptive large neighborhood search, are presented and compared to solve the problem. Numerical results on two sets of benchmark instances with up to 70 nodes and three lines confirm the efficiency of the proposed solution algorithms.

In this article we propose a descent method for equality and inequality constrained multiobjective optimization problems (MOPs) which generalizes the steepest descent method for unconstrained MOPs by Fliege and Svaiter to constrained problems by using two active set strategies. Under some regularity assumptions on the problem, we show that accumulation points of our descent method satisfy a necessary condition for local Pareto optimality. Finally, we show the typical behavior of our method in a numerical example.

In the present paper, we propose a modification of the method of bi-coordinate variations for network equilibrium problems with mixed demand. This method is based on the equilibrium conditions of the problem under consideration. It uses a special tolerance control and thresholds for constructing descent directions and a variant of the Armijo-type line-search procedure as a rule of step choice. Some results of preliminary numerical calculations which confirm efficiency of the method are also presented.

Stochastic neural networks serve as general models useful for machine learning problems. Several models on discrete state spaces have been studied, and their proposed gradient estimation procedures are based on having closed form solutions for the resulting probability distributions. The methods exploit constraints on network connectivity, such as symmetry, or the absence of cycles. Our interest is in the general case of long-term average cost in networks with arbitrary connectivity, where only knowledge of the transition probabilities is available. We propose an algorithm that computes descent directions based on simultaneous perturbation analysis and measure valued differentiation.

We address a home care service problem, and propose a three-phase metaheuristic based on Variable Neighborhood Decent algorithm and Longest Processing Time algorithm. In the first phase, we resolve the assignment problem using a scheduling algorithm which is the Longest Processing Time algorithm. In the second one, for each nurse, we resolve the routing problem in order to improve the travelled distances using the Variable Neighborhood Decent algorithm. The third phase, is devoted to refine the second phase in terms of maximizing patient's satisfaction regarding services rendered using an efficient heuristic that performs replacements of patients not satisfied between nurses if possible while taking into consideration the distances found in the second phase. The numerical results show the efficiency of the proposed three-phase approach.

The Frank-Wolfe (FW) algorithm has been widely used in solving nuclear norm constrained problems, since it does not require projections. However, FW often yields high rank intermediate iterates, which can be very expensive in time and space costs for large problems. To address this issue, we propose a rank-drop method for nuclear norm constrained problems. The goal is to generate descent steps that lead to rank decreases, maintaining low-rank solutions throughout the algorithm. Moreover, the optimization problems are constrained to ensure that the rank-drop step is also feasible and can be readily incorporated into a projection-free minimization method, e.g., Frank-Wolfe. We demonstrate that by incorporating rank-drop steps into the Frank-Wolfe algorithm, the rank of the solution is greatly reduced compared to the original Frank-Wolfe or its common variants.