Search

In this paper we propose a Variable neighborhood descent based heuristic for the capacitated clustering problem and related handover minimization problem. The performance of the proposed approach is assessed on benchmark instances from the literature. The obtained results confirm that of our approach is highly competitive with the state-of-the-art methods, significantly outperforming all of them on the set of randomly-generated instances tested.

In this paper we address the problem of multi-agent optimization for convex functions expressible as sums of convex functions. Each agent has access to only one function in the sum and can use only local information to update its current estimate of the optimal solution. We consider two consensus-based iterative algorithms, based on a combination between a consensus step and a subgradient decent update. The main difference between the two algorithms is the order in which the consensus-step and the subgradient descent update are performed. We obtain upper bounds on performance metrics of the two algorithms. We show that updating first the current estimate in the direction of a subgradient and then executing the consensus step ensures a tighter upper bound compared with the case where the steps are executed in reversed order. In support of our analytical results, we give some numerical simulations of the algorithms as well.

In this paper the problem of optimal control in the classical statement is considered. With the help of the theory of exact penalty functions the original problem is reduced to the problem of unconstrained minimization of a nonsmooth functional. For this functional the necessary minimum conditions in terms of hypodifferential are found. A class of problems, for which these conditions are also sufficient, is distinguished. On the basis of these conditions the hypodifferential descent method is applied to the considered problem. Under some additional assumptions the hypodifferential descent method converges in a certain sense.

We propose a fuzzy learning method by a descent technique, to calculate the characteristic parameters of elliptic- and circular-shaped microshield lines.From input–output data, generated using conformal mapping technique, the inference rules expressing the input output relation of the data are obtained automatically using the proposed fuzzy inference system. The learning speed of this method is substantially higher than that of the neural model. The numerical results are in very good agreement with the results reported elsewhere. © 2011 Wiley Periodicals, Inc. Microwave Opt Technol Lett 53:2648–2653, 2011; View this article online at wileyonlinelibrary.com. DOI 10.1002/mop.26335

This paper presents a general and comprehensive description of Optimization Methods, and Algorithms from a novel viewpoint. It is shown, in particular, that Direct Methods, Iterative Methods, and Computer Science Algorithms belong to a well-defined general class of both Finite and Infinite Procedures, characterized by suitable descent directions.

The introduction of function extremum promotes the development of calculus, which is the prerequisite and important condition for the development and development of many mathematical ideas. Except for extreme problems in social life or science and technology, the issue of cost in economic issues, the shortest distance in mathematics problem can be solved by the function extreme value thought. However, because the extreme value problem is not well described, learners cannot easily observe and learn. This paper takes the uniform speed and uniform acceleration and descent in the descent model as an example. In the uniform acceleration, the dichotomy is introduced to solve the function extremum problem. Through MATLAB simulation, the position of the steepest descent point is found intuitively and relevant conclusions are obtained. It is hoped that the research process of the problem can be helpful to the study of refractive problems, and it is hoped that the visually intuitive simulation results can enable learners to understand the descent model more objectively.

The desire to return humans to the moon has motivated the evaluation of existing lunar descent guidance algorithms and the development of new ideas. This paper outlines a design for a targeting algorithm that quickly and reliably generates a two-dimensional reference trajectory and a real-time three-dimensional guidance algorithm that can use this or any reference trajectory as its basis. The targeting algorithm is analytical in nature and allows for updates to the reference in real time. Monte Carlo analysis demonstrates the reliable performance of the algorithms in both a general sense and for retargeting once the lunar descent has been initiated.

The equilibrium signal-setting problem is stated and subsequently formulated as a continuous equilibrium network design problem. The bilevel formulation is nonconvex and therefore cannot be solved for global optima by using descent solution algorithms. Therefore, a lower bound using a system optimal flow pattern is proposed that will be quite tight in both uncongested and highly congested network traffic situations. A solution algorithm based on the standard steepest-descent method is proposed for the lower-bound problem. Performance of the solution algorithm on a network problem is reported.

Optimization of linked signal system in urban traffic road networks is considered in this paper. This problem can be formulated as a nonlinear program subject to network flows following Wardrop’s first principle in which traffic rerouting effects are taken into account. We propose a descent framework to effectively solve a linked signal system with network flows. Numerical calculations are implemented on well-known example road networks and good results are reported.

Gradient descent in image distances can lead a navigating agent to the goal location, but in environments with an anisotropic distribution of landmarks, gradient home vectors deviate from the true home direction. These deviations can be reduced by applying Newton's method to matched-filter descent in image distances (MFDID). Based on several image databases we demonstrate that the home vectors produced by the Newton-based MFDID method are usually closer to the true home direction than those obtained from the original MFDID method. The greater accuracy of Newton-MFDID home vectors in the vicinity of the goal location would allow a navigating agent to approach the goal on straighter trajectories, improve the results of triangulation procedures, and enhance a robot's ability to detect its arrival at a goal.

Function optimization underlies many real-world problems and hence is an important research subject. Most of the existing optimization methods were developed to solve primarily unconstrained problems. Since real-world problems are often constrained, appropriate handling of constraints is necessary in order to use the optimization methods. In particular, the performances of some methods such as Genetic Algorithms (GA) can be substantially undermined by ineffective constraint handling. Despite much effort devoted to the studies of constraint-handling methods, it has been reported that each of them has certain limitations. Hence, further studies for designing more effective constraint-handling methods are needed. For this reason, we investigated the guidelines for a method to effectively handle constraints. The guidelines are that the method 1) takes the approach of repair operators, 2) monotonically decreases both the number of violated constraints and constraint violations, and 3) searches over the boundaries of violated constraints. Based on these guidelines, we designed a new constraint-handling method Pareto Descent Repair operator (PDR) in which ideas derived from multi-objective local search and gradient projection method are incorporated. Experiments comparing GA that use PDR and some of the existing constraint-handling methods confirmed the effectiveness of PDR.

This paper describes techniques to implement gradient-descent-based machine learning algorithms on crossbar arrays made of memristors or other analog memory devices. We introduce the Unregulated Step Descent (USD) algorithm, which is an approximation of the steepest descent algorithm, and discuss how it addresses various hardware implementation issues. We discuss the effect of device parameters and their variability on performance of the algorithm by using artificially generated and real-world datasets. In addition to providing insights on the effect of device parameters on learning, we illustrate how the USD algorithm partially offsets the effect of device variability. Finally, we discuss how the USD algorithm can be implemented in crossbar arrays using a simple 4-phase training scheme. The method allows parallel update of crossbar memory elements and reduces the hardware cost and complexity of the training architecture significantly.

Supervised Descent Method (SDM) is a highly efficient and accurate approach for facial landmark locating/face alignment. It learns a sequence of descent directions that minimize the difference between the estimated shape and the ground truth in HOG feature space during training, and utilize them in testing to predict shape increment iteratively. In this paper, we propose to modify SDM in three respects: (1) Multi-scale HOG features are applied orderly as a coarse-to-fine feature detector; (2) Global to local constraints of the facial features are considered orderly in regression cascade; (3) Rigid Regularization is applied to obtain more stable prediction results. Extensive experimental results demonstrate that each of the three modifications could improve the accuracy and robustness of the traditional SDM methods. Furthermore, enhanced by the three-fold improvements, the extended SDM compares favorably with other state-of-the-art methods on several challenging face data sets, including LFPW, HELEN and 300 Faces in-the-wild.

Many real-world problems entail multiple conflicting objectives, which makes multiobjective optimization an important subject. Much attention has been paid to Genetic Algorithm (GA) as a potent multiobjective optimization method, and the effectiveness of its hybridization with local search (LS) has recently been reported in the literature. However, there have been a relatively small number of studies on LS methods for multiobjective function optimization. Although each of the existing LS methods has some strong points, they have respective drawbacks such as high computational cost and inefficiency of improving objective functions. Hence, a more effective and efficient LS method is being sought, which can be used to enhance the performance of the hybridization. Pareto descent directions are defined in this paper as descent directions to which no other descent directions are superior in improving all objective functions. Moving solutions in such directions is expected to maximally improve all objective functions simultaneously. This paper proposes a new LS method, Pareto Descent Method (PDM), which finds Pareto descent directions and moves solutions in such directions. In the case part or all of them are infeasible, it finds feasible Pareto descent directions or descent directions as necessary and moves solutions in these directions. PDM finds these directions by solving linear programming problems. Thus, it is computationally inexpensive. Experiments have shown that PDM is superior to existing methods.

International audience; This paper studies the multitrip cumulative capacitated vehicle routing problem (mt-CCVRP), a variant of the classical capacitated vehicle routing problem (CVRP). In the mt-CCVRP the objective function becomes the minimization of the sum of arrival times at required nodes and each vehicle may perform more than one trip. Applications of this NP-Hard problem can be found in disaster logistics. This article presents a Multistart Evolutionary Local Search (MS-ELS) that alternates between giant tour and mt-CCVRP solutions, and uses an adapted split procedure and a variable neighborhood descent (VND). The results on two sets of instances show that this approach finds very good results in relatively short computing time compared with a multistart iterated local search which works directly on the mt-CCVRP solution space.

We present a cut-peak function method for finding a global minimizer of the bound constrained optimization problems. A simple cut-peak function and choice function are defined at a local minimizer. By minimizing the choice function, a global descent of the original objective function is assured. Since the pattern search method does not require the gradient of the choice function, smoothing technique is not employed. The new algorithm is simple to implement and numerical results indicate its efficiency.

In this paper, a parallel hybrid heuristic is developed for the multicommodity capacitated location problem with balancing requirements. The hybrid involves variable neighborhood descent (VND) and slope scaling (SS). Both methods evolve in parallel within a master-slave architecture where the slave processes communicate through adaptive memories. Numerical results are reported on different types of randomly generated instances, using an increasing number of processors and different distributions of processes between SS and VND.

The pseudospectrum descent method (PsDM) is proposed, a new parallel method for the computation of pseudospectra. The idea behind the method is to use points from an already existing pseudospectrum level curve ∂Λe to generate in parallel the points of a new level curve ∂Λδ such that δ > e. This process can be continued for several steps to approximate several pseudospectrum level curves lying inside the original curve. It is showed via theoretical analysis and experimental evidence that PsDM is embarrassingly parallel, like GRID, and that it adjusts to the geometric characteristics of the pseudospectrum; in particular it captures disconnected components. Results obtained on a parallel system using MPI validate the theoretical analysis and demonstrate interesting load-balancing issues.

Drawing upon data from the phonologies, morphologies, numeral systems, constituent orders, case systems, and lexicons of the world’s languages, Quantifying Language Dynamics introduces new, quantitative methodologies for understanding language contact, evolution, and patterns of phylogenetic descent.

In this chapter the Global Optimisation of Signal Settings (GOSS) problem is studied and a meta-heuristic algorithm is proposed for its solution. The GOSS problem arises when the parameters of all (or some) signalised intersections of a network are jointly optimised so as to minimise the value of an objective function (such as total travel time). This problem has been widely studied elsewhere and several algorithms have been proposed, mainly based on descent methods. These algorithms require high computing times for real-scale problems and usually lead to a local optimum since the objective function is hardly ever convex. The high computing times are due to the need to perform traffic assignment to determine the objective function at any iteration. In this chapter we propose a multi-start method based on a Feasible Descent Direction Algorithm (FDDA) for solving this problem. The algorithm is able to search for a local optimal solution and requires lower computing times at any iteration. The proposed algorithm is tested on a real-scale network, also under different demand levels, by adopting different assignment algorithms proposed in the literature. Initial results show that the proposed algorithms perform well and that computing times are compatible with planning purposes also for real-scale networks.

We introduce an alternative approach for the analysis and numerical approximation of the optimal feedback control mapping. It consists in looking at a typical optimal control problem in such a way that feasible controls are mappings depending both in time and space. In this way, the feedback form of the problem is built-in from the very beginning. Optimality conditions are derived for one such optimal mapping, which by construction is the optimal feedback mapping of the problem. In formulating optimality conditions, costates in feedback form are solutions of linear, first-order transport systems, while optimal descent directions are solutions of appropriate obstacle problems. We treat situations with no constraint-sets for control and state, as well as the more general case where a constraint-set is considered for the control variable. Constraints for the state variable are deferred to a coming contribution.

In this paper, we propose a heuristic based upon the large neighborhood search for the disjunctively constrained knapsack problem (DCKP). The proposed method combines a two-phase procedure and a large neighborhood search. First, the two-phase procedure is applied in order to provide a starting feasible solution for the large neighborhood search. The first phase serves to determine a feasible solution by successively solving two subproblems: the weighted independent set and the classical binary knapsack. The second phase tries to improve the quality of the solutions by using a descent method which applies both degrading and re-optimizing strategies. Second, a large neighborhood search is introduced in order to diversify the search space. Finally, the performance of the proposed method is computationally analyzed on a set of benchmark instances of the literature where its provided results are compared to those reached by Cplex solver and some recent algorithms. The provided results show that the method is very competitive since it is able to reach new solutions within small runtimes.

This paper deals with the Unrelated Parallel Machine Scheduling Problem with Setup Times (UPMSPST). The objective is to minimize the maximum completion time of the schedule, the so-called makespan. This problem is commonly found in industrial processes like textile manufacturing and it belongs to NP-Hard class. It is proposed an algorithm named AIV based on Iterated Local Search (ILS) and Variable Neighborhood Descent (VND). This algorithm starts from an initial solution constructed on a greedy way by the Adaptive Shortest Processing Time (ASPT) rule. Then, this initial solution is refined by ILS, using as local search the Random VND procedure, exploring neighborhood structures based on swaps and multiple insertions. In this procedure, here called RVND, there is no fixed sequence of neighborhoods, because they are sorted on each application of the local search. The perturbations of ILS consist in reinserting jobs from one machine to another. AIV was tested using benchmark instances from literature and statistical analysis of the computational experiments showed that AIV outperformed the algorithms of the literature, setting new improved solutions.

The selection of appropriate beam irradiation directions in radiotherapy – beam angle optimization (BAO) problem – is very impor- tant for the quality of the treatment, both for improving tumor irradia- tion and for better organs sparing. However, the BAO problem is still not solved satisfactorily and, most of the time, beam directions continue to be manually selected in clinical practice which requires many trial and error iterations between selecting beam angles and computing fluence patterns until a suitable treatment is achieved. The objective of this pa- per is to introduce a new approach for the resolution of the BAO problem, using an hybrid electromagnetism-like algorithm with descent search to tackle this highly non-convex optimization problem. Electromagnetism- like algorithms are derivative-free optimization methods with the ability to avoid local entrapment. Moreover, the hybrid electromagnetism-like algorithm with descent search has a high ability of producing descent directions. A set of retrospective treated cases of head-and-neck tumors at the Portuguese Institute of Oncology of Coimbra is used to discuss the benefits of the proposed algorithm for the optimization of the BAO problem., Fundação para a Ciência e a Tecnologia (FCT)

The possibility to synthesize the attitude control for a gyrostabilized platform is investigated under the most general assumptions on its drifts, using the principle of maximum. The analytical form of the control vector, explicitly depending on all components of the state vector of a navigation system of a descent vehicle, is a specific feature of the found solution.

Although the point has already been emphasized by various authors that the assumption of descent with modification is not required to justify cladistics, recent debate suggests that there is still confusion surrounding the necessary and sufficient background knowledge underlying the method. Three general axioms necessary to justify cladistics-the discoverability of characters, hierarchy, and parsimony-are reviewed. Although the assumption of evolution is sufficient to justify cladistics, it is also sufficient to justify competing approaches like maximum likelihood, which suggests that the philosophical support for the cladistic approach is strengthened by purging reference to descent with modification altogether.

This letter proposes a new global descent method based on not only the concept of a conventional descent method in mathematical programming but also the concept of search direction in particle swarm optimization (PSO) in metaheuristics. The proposed method, called particle swarm optimization based global descent method (PSOGDM), consists of two main procedures; (i) determination of search direction and (ii) global optimization for given search direction. Although the search direction that has three parameters is decided based on the concept of PSO, the proposed PSOGDM is a single-point search different from PSO. Global optimization for a given search direction is performed by PSO. The search capability of the proposed PSOGDM is examined based on the results of numerical experiments using five typical benchmark problems. Copyright © 2009 Institute of Electrical Engineers of Japan. Published by John Wiley & Sons, Inc.

In this paper, we present an efficient approach for solving capacitated single allocationhub location problems. We use a modified version of a previous mixed integer linearprogramming formulation developed by us for p‐hub median problems. This formulationrequires fewer variables and constraints than those traditionally used in the literature. Wedevelop good heuristic algorithms for its solution based on simulated annealing (SA) andrandom descent (RDH). We use the upper bound to develop an LP‐based branch and boundsolution method. The problem, as we define it, finds applications in the design of postaldelivery networks, particularly in the location of capacitated mail sorting and distributioncentres. We test our algorithms on data obtained from this application. To the best of ourknowledge, this problem has not been solved in the literature. Computational results arepresented indicating the usefulness of our approach.

Natural gradient descent is an on-line variable-metric optimization algorithm which utilizes an underlying Riemannian parameter space. We analyze the dynamics of natural gradient descent beyond the asymptotic regime by employing an exact statistical mechanics description of learning in two-layer feed-forward neural networks. For a realizable learning scenario we find significant improvements over standard gradient descent for both the transient and asymptotic stages of learning, with a slower power law increase in learning time as task complexity grows.

We describe a parallel method for unconstrained optimization based on the quasi-Newton descent method of Broyden, Fletcher, Goldfarb, and Shanno. Our algorithm is suitable for both single-instruction and multiple-instruction parallel architectures and has only linear memory requirements in the number of parameters used to fit the data. We also present the results of numerical testing on both single and multiple Gaussian data fitting problems.

The inference of the evolutionary history of a set of languages is a complex problem. Although some languages are known to be related through descent from common ancestral languages, for other languages determining whether such a relationship holds is itself a difficult problem. In this paper we report on new methods, developed by linguists Johanna Nichols (University of California, Berkeley), Donald Ringe and Ann Taylor (University of Pennsylvania, Philadelphia), and me, for answering some of the most difficult questions in this domain. These methods and the results of the analyses based on these methods were presented in November 1995 at the Symposium on the Frontiers of Science held by the National Academy of Sciences.

In this article we combine the concept of microevolutionary hill-climbing search with the systematic search concept of arc revision to form a hybrid system that quickly finds solutions to static and dynamic Fuzzy Constraint Truth Optimization Problems (FCTOPs). Furthermore, we present the results of two experiments. In the first experiment, our microevolutionary hybrid system outperforms a modified version of a well known hill-climber, the Iterative Descent Method (IDM), on a test suite of 500 randomly generated static Fuzzy Constraint Networks.In the second experiment, we compare two methods for solving FCTOPs using a test suite of an additional 250 randomly generated FCTOPs. In the first method, all the constraints of a FCTOP are known by the hybrid system at run-time. We refer to this method as the static method for solving FCTOPs. In the second method, only half of the constraints of a FCTOP are known at run-time. Each time our hybrid system discovers a solution that satisfies all of the const...

In this paper a Variable Neighborhood Descent (VND) approach, is developed to solve the Single Machine Total Weighted Tardiness Problem (SMTWTP). New strategy was proposed to select iteratively the accurate neighborhood. Our approach was compared to VND state-of-the-art approaches. Statistical tests were also applied on the empirical results, to show that the DR_VND outperforms the proposed approaches for 72 % of instances for the SMTWTP. The proposed approach was applied on a real case.

One of the issue in using of mobile antenna is determining of mobile antenna station in order to proper service. Difference ray of mobile antenna station and their placement and geographical qualification are the factors that caused the problem of mobile antenna antennas be np_hard optimization problem. In this paper in order to finding proper answers for this problem, the combination of genetic algorithm and learning automata are used. Our purpose is that the specified area be covered and the overlapping of mobile antenna station be minimum. In this paper proposed master-slave automata. One of the automata play master automata role and others plays slave automata roles. In last work, actual environment, descent of frequency dosn't considered. In the end of paper, proposed algorithm compared with other famous algorithms. Results shows that proposed algorithm is better than others from product result and cost effective aspect.

Virtual network mapping considers the problem of fitting multiple virtual networks into one physical network in a cost-optimal way. This problem arises in Future Internet research. One of the core ideas is to utilize different virtual networks to cater to different application classes, each with customized protocols that deliver the required Quality-of- Service. In this work we introduce a Greedy Randomized Adaptive Search Procedure (GRASP) and Variable Neighborhood Search (VNS) algorithm for solving the Virtual Network Mapping Problem. Both algorithms make use of a Variable Neighborhood Descent with ruin-and-recreate neighborhoods. We show that the VNS approach significantly outperforms the previously best known algorithms for this problem.

In this paper we present a new algorithm for the approximate solution of the logit-based stochastic user equilibrium problem. The main advantage of this algorithm is that it provides route flows explicitly, of particular interest in the evaluation of route guidance and information systems; in previously proposed methods for the stochastic user equilibrium problem, only link flows are provided. The proposed algorithm alternates between two main phases. In the subproblem phase, profitable routes are generated. In the restricted master problem phase, a descent method is used to solve the restriction to the original problem to the subset of the total set of routes generated so far. We present and evaluate alternative strategies for generating routes algorithmically, and discuss the possibility of utilizing such strategies for reducing the inherent problem of overlapping route flows in logit-based traffic models.

Look down, way down. Past the background information and the section describing methods. Past the tables full of numbers and all the pretty graphs. Have you come to the part with the conclusions? Sorry, your descent is not yet complete. You’ll find it — if it even exists —at the very bottom

In theoretical computational statistics, the detection of heavy tails in computing costs of some random search algorithms generated an increased interest in the modeling of this heavy-tailed behavior. We propose a general model for these algorithms that reproduces this characteristic. The model represents the search for a solution as the descent of a search tree with regular branching factors and equiprobable nodes. In this work, we present a way to generate heavy-tailed search trees using very simple rules, and we show how a particular case relates to the famous Wallis product.

Multi-instance multi-label learning (MIML) is a framework for supervised classification where the objects to be classified are bags of instances associated with multiple labels. For example, an image can be represented as a bag of segments and associated with a list of objects it contains. Prior work on MIML has focused on predicting label sets for previously unseen bags. We instead consider the problem of predicting instance labels while learning from data labeled only at the bag level. We propose Rank-Loss Support Instance Machines, which optimize a regularized rank-loss objective and can be instantiated with different aggregation models connecting instance-level predictions with bag-level predictions. The aggregation models that we consider are equivalent to defining a "support instance" for each bag, which allows efficient optimization of the rank-loss objective using primal sub-gradient descent. Experiments on artificial and real-world datasets show that the proposed methods achieve higher accuracy than other loss functions used in prior work, e.g., Hamming loss, and recent work in ambiguous label classification.

Geometric structures that apply to rational points can sometimes be formulated in terms of sections: functorial properties of the space of sections, abelianization and base change. In favorable circumstances we establish Galois descent for sections, see Proposition 28. We furthermore study the behaviour of sections under fibrations and finite etale covers between varieties. The notion of the anabelian fibre above a section is introduced.The results of J. Stix (Math. J. Okayama Univ. 52:29–43, 2010) on the behaviour of the space of sections under Weil restriction of scalars are summarized in Sect. 3.5.

In 1966, Paul Postal claimed that it is impossible to find grammatical sentences in which there is partial overlap between subject and object, i.e., in sentences like I like us. This observation lead, in direct scholarly descent, to the infamous Binding Principle B (Chomsky 1981). In this article we argue against Postal’s original observation, as we claim that sentences with partial argument overlap are perfectly possible in English and sundry languages, a lthough such expressions are conversationally constrained. The real-world situations that are described in such utterances are unusual, and thus the c onstructions are used infrequently, leading to uncertainty on the part of the speaker whether such expressions are well-formed or not. In the process of grammaticalization of pronouns into person-marking inflection this disprefer ence appears to turn into real impossibility.

This work presents a new algorithm for dictionary learning. Existing algorithms such as MOD and K-SVD often fail to find the best dictionary because they get trapped in a local minimum. Olshausen and Field's Sparsenet algorithm relies on a fixed step projected gradient descent. With the right step, it can avoid local minima and converge towards the global minimum. The problem then becomes to find the right step size. In this work we provide the expression of the optimal step for the gradient descent but the step we use is twice as large as the optimal step. That large step allows the descent to bypass local minima and yields significantly better results than existing algorithms. The algorithms are compared on synthetic data. Our method outperforms existing algorithms both in approximation quality and in perfect recovery rate if an oracle support for the sparse representation is provided.

We introduce our framework, including all of the elements generated at each iteration, as well as the major components of reduction and retreat. The property of nonincreasing function values inherent in the framework is strengthened via the definition of a descent method, and lower-diminishing target-gaps are explored as the result of a successful run of a method within the framework. Finally, we develop our extended notion of approaching stationarity and link this property both to stationary points and to lower-diminishing target-gaps.

Four particular examples of methods within our framework are explored in detail, including generalized line-search and trust-region methods, as well as a general pattern-search method and the classic Nelder–Mead method. In each case, we consider descent, and develop conditions ensuring lower-diminishing target-gaps and an approach to stationarity.

The recently proposed Sparse Shape Composition (SSC) opens a new avenue for shape prior modeling. Instead of assuming any parametric model of shape statistics, SSC incorporates shape priors on-the-fly by approximating a shape instance (usually derived from appearance cues) by a sparse combination of shapes in a training repository. Theoretically, one can increase the modeling capability of SSC by including as many training shapes in the repository. However, this strategy confronts two limitations in practice. First, since SSC involves an iterative sparse optimization at run-time, the more shape instances contained in the repository, the less run-time efficiency SSC has. Therefore, a compact and informative shape dictionary is preferred to a large shape repository. Second, in medical imaging applications, training shapes seldom come in one batch. It is very time consuming and sometimes infeasible to re-construct the shape dictionary every time new training shapes appear. In this paper, we propose an online learning method to address these two limitations. Our method starts from constructing an initial shape dictionary using the K-SVD algorithm. When new training shapes come, instead of re-constructing the dictionary from the ground up, we update the existing one using a block-coordinates descent approach. Using the dynamically updated dictionary, sparse shape composition can be gracefully scaled up to model shape priors from a large number of training shapes without sacrificing run-time efficiency. Our method is validated on lung localization in X-Ray and cardiac segmentation in MRI time series. Compared to the original SSC, it shows comparable performance while being significantly more efficient.

This chapter provides the basic symbols to image present and past ephemeral and committed relationships. Open and closed adoptions are distinguished and presented as a special case of descent. A method for mapping households independently from affinal relationships is described for possible use in social work. The key symbols are circles and lines. Circles represent past and present relationships and lines between circles represent descent or change of partners. Algebraic notations are used to track children as their parents change partners and households.

In this chapter, we take a closer look at combinatorial issues raised by applying outer convexification to constraints that directly depend on a discrete control. We describe several undesirable phenomena that arise when treating such problems with a Sequential Quadratic Programming (SQP) method, and give explanations based on the violation of Linear Independence Constraint Qualification (LICQ). We show that the Nonlinear Programs (NLPs) can instead be treated favorably as Mathematical Programs with Vanishing Constraints (MPVCs), a class of challenging problems with complementary constraints and nonconvex feasible set. We give a summary of a Lagrangian framework for MPVCs due to [3] and others, which allows for the design of derivative based descent methods for the efficient solution of MPVCs in the next chapter.