Suboptimal Midcourse Guidance of Interceptors for High-Speed Targets with Alignment Angle Constraint

Using the recently developed computationally efficient model predictive static programming and a closely related model predictive spread control concept, two nonlinear suboptimal midcourse guidance laws are presented in this paper for interceptors engaging against incoming high-speed ballistic missiles. The guidance laws are primarily based on nonlinear optimal control theory, and hence imbed effective trajectory optimization concepts into the guidance laws. Apart from being energy efficient by minimizing the control usage throughout the trajectory (minimum control usage leads to minimum turning, and hence leads to minimum induced drag), both of these laws enforce desired alignment constraints in both elevation and azimuth in a hard-constraint sense. This good alignment during midcourse is expected to enhance the effectiveness of the terminal guidance substantially. Both point mass as well as six-degree-of-freedom simulation results (with a realistic inner-loop autopilot based on dynamic inversion) are presented in this paper, which clearly shows the effectiveness of the proposed guidance laws. It has also been observed that, even with different perturbations of missile parameters, the performance of guidance is satisfactory. A comparison study, with the vector explicit guidance scheme proposed earlier in the literature, also shows that the newly proposed model-predictive-static-programming-based and model-predictive-spread-control-based guidance schemes lead to lesser lateral acceleration demand and lesser velocity loss during engagement.

A Convex Optimization Framework for Almost Budget Balanced Allocation of a Divisible Good

We address the problem of allocating a single divisible good to a number of agents. The agents have concave valuation functions parameterized by a scalar type. The agents report only the type. The goal is to find allocatively efficient, strategy proof, nearly budget balanced mechanisms within the Groves class. Near budget balance is attained by returning as much of the received payments as rebates to agents. Two performance criteria are of interest: the maximum ratio of budget surplus to efficient surplus, and the expected budget surplus, within the class of linear rebate functions. The goal is to minimize them. Assuming that the valuation functions are known, we show that both problems reduce to convex optimization problems, where the convex constraint sets are characterized by a continuum of half-plane constraints parameterized by the vector of reported types. We then propose a randomized relaxation of these problems by sampling constraints. The relaxed problem is a linear programming problem (LP). We then identify the number of samples needed for ``near-feasibility'' of the relaxed constraint set. Under some conditions on the valuation function, we show that value of the approximate LP is close to the optimal value. Simulation results show significant improvements of our proposed method over the Vickrey-Clarke-Groves (VCG) mechanism without rebates. In the special case of indivisible goods, the mechanisms in this paper fall back to those proposed by Moulin, by Guo and Conitzer, and by Gujar and Narahari, without any need for randomization. Extension of the proposed mechanisms to situations when the valuation functions are not known to the central planner are also discussed. Note to Practitioners-Our results will be useful in all resource allocation problems that involve gathering of information privately held by strategic users, where the utilities are any concave function of the allocations, and where the resource planner is not interested in maximizing revenue, but in efficient sharing of the resource. Such situations arise quite often in fair sharing of internet resources, fair sharing of funds across departments within the same parent organization, auctioning of public goods, etc. We study methods to achieve near budget balance by first collecting payments according to the celebrated VCG mechanism, and then returning as much of the collected money as rebates. Our focus on linear rebate functions allows for easy implementation. The resulting convex optimization problem is solved via relaxation to a randomized linear programming problem, for which several efficient solvers exist. This relaxation is enabled by constraint sampling. Keeping practitioners in mind, we identify the number of samples that assures a desired level of ``near-feasibility'' with the desired confidence level. Our methodology will occasionally require subsidy from outside the system. We however demonstrate via simulation that, if the mechanism is repeated several times over independent instances, then past surplus can support the subsidy requirements. We also extend our results to situations where the strategic users' utility functions are not known to the allocating entity, a common situation in the context of internet users and other problems.

Unified Vdd Vth Optimization Based DVFM Controller for a Logic Block

In this paper analytical expressions for optimal Vdd and Vth to minimize energy for a given speed constraint are derived. These expressions are based on the EKV model for transistors and are valid in both strong inversion and sub threshold regions. The effect of gate leakage on the optimal Vdd and Vth is analyzed. A new gradient based algorithm for controlling Vdd and Vth based on delay and power monitoring results is proposed. A Vdd-Vth controller which uses the algorithm to dynamically control the supply and threshold voltage of a representative logic block (sum of absolute difference computation of an MPEG decoder) is designed. Simulation results using 65 nm predictive technology models are given.

Topology Optimization of Micromachined Structures with the Manufacturing Constraints of KOH Etching of (110) Silicon

The focus of this paper is on designing useful compliant micro-mechanisms of high-aspect-ratio which can be microfabricated by the cost-effective wet etching of (110) orientation silicon (Si) wafers. Wet etching of (110) Si imposes constraints on the geometry of the realized mechanisms because it allows only etch-through in the form of slots parallel to the wafer's flat with a certain minimum length. In this paper, we incorporate this constraint in the topology optimization and obtain compliant designs that meet the specifications on the desired motion for given input forces. Using this design technique and wet etching, we show that we can realize high-aspect-ratio compliant micro-mechanisms. For a (110) Si wafer of 250 µm thickness, the minimum length of the etch opening to get a slot is found to be 866 µm. The minimum achievable width of the slot is limited by the resolution of the lithography process and this can be a very small value. This is studied by conducting trials with different mask layouts on a (110) Si wafer. These constraints are taken care of by using a suitable design parameterization rather than by imposing the constraints explicitly. Topology optimization, as is well known, gives designs using only the essential design specifications. In this work, we show that our technique also gives manufacturable mechanism designs along with lithography mask layouts. Some designs obtained are transferred to lithography masks and mechanisms are fabricated on (110) Si wafers.

Prioritizing constraint evaluation for efficient points-to analysis

Pervasive use of pointers in large-scale real-world applications continues to make points-to analysis an important optimization-enabler. Rapid growth of software systems demands a scalable pointer analysis algorithm. A typical inclusion-based points-to analysis iteratively evaluates constraints and computes a points-to solution until a fixpoint. In each iteration, (i) points-to information is propagated across directed edges in a constraint graph G and (ii) more edges are added by processing the points-to constraints. We observe that prioritizing the order in which the information is processed within each of the above two steps can lead to efficient execution of the points-to analysis. While earlier work in the literature focuses only on the propagation order, we argue that the other dimension, that is, prioritizing the constraint processing, can lead to even higher improvements on how fast the fixpoint of the points-to algorithm is reached. This becomes especially important as we prove that finding an optimal sequence for processing the points-to constraints is NP-Complete. The prioritization scheme proposed in this paper is general enough to be applied to any of the existing points-to analyses. Using the prioritization framework developed in this paper, we implement prioritized versions of Andersen's analysis, Deep Propagation, Hardekopf and Lin's Lazy Cycle Detection and Bloom Filter based points-to analysis. In each case, we report significant improvements in the analysis times (33%, 47%, 44%, 20% respectively) as well as the memory requirements for a large suite of programs, including SPEC 2000 benchmarks and five large open source programs.

Solving Dynamic Constraint Single Objective Functions using a Nature Inspired Technique

We present in this paper a new algorithm based on Particle Swarm Optimization (PSO) for solving Dynamic Single Objective Constrained Optimization (DCOP) problems. We have modified several different parameters of the original particle swarm optimization algorithm by introducing new types of particles for local search and to detect changes in the search space. The algorithm is tested with a known benchmark set and compare with the results with other contemporary works. We demonstrate the convergence properties by using convergence graphs and also the illustrate the changes in the current benchmark problems for more realistic correspondence to practical real world problems.

The Feedback Capacity of the Binary Erasure Channel With a No-Consecutive-Ones Input Constraint

The input-constrained erasure channel with feedback is considered, where the binary input sequence contains no consecutive ones, i.e., it satisfies the (1, infinity)-RLL constraint. We derive the capacity for this setting, which can be expressed as C-is an element of = max(0 <= p <= 0.5) (1-is an element of) H-b (p)/1+(1-is an element of) p, where is an element of is the erasure probability and Hb(.) is the binary entropy function. Moreover, we prove that a priori knowledge of the erasure at the encoder does not increase the feedback capacity. The feedback capacity was calculated using an equivalent dynamic programming (DP) formulation with an optimal average-reward that is equal to the capacity. Furthermore, we obtained an optimal encoding procedure from the solution of the DP, leading to a capacity-achieving, zero-error coding scheme for our setting. DP is, thus, shown to be a tool not only for solving optimization problems, such as capacity calculation, but also for constructing optimal coding schemes. The derived capacity expression also serves as the only non-trivial upper bound known on the capacity of the input-constrained erasure channel without feedback, a problem that is still open.

Topology optimization of silicon anode structures for lithium-ion battery applications

This thesis presents a topology optimization methodology for the systematic design of optimal multifunctional silicon anode structures in lithium-ion batteries. In order to develop next generation high performance lithium-ion batteries, key design challenges relating to the silicon anode structure must be addressed, namely the lithiation-induced mechanical degradation and the low intrinsic electrical conductivity of silicon. As such, this work considers two design objectives of minimum compliance under design dependent volume expansion, and maximum electrical conduction through the structure, both of which are subject to a constraint on material volume. Density-based topology optimization methods are employed in conjunction with regularization techniques, a continuation scheme, and mathematical programming methods. The objectives are first considered individually, during which the iteration history, mesh independence, and influence of prescribed volume fraction and minimum length scale are investigated. The methodology is subsequently extended to a bi-objective formulation to simultaneously address both the compliance and conduction design criteria. A weighting method is used to derive the Pareto fronts, which demonstrate a clear trade-off between the competing design objectives. Furthermore, a systematic parameter study is undertaken to determine the influence of the prescribed volume fraction and minimum length scale on the optimal combined topologies. The developments presented in this work provide a foundation for the informed design and development of silicon anode structures for high performance lithium-ion batteries.

Novel critical phenomena in optimization driven processes on networks

The work presented in this Ph.D thesis was developed in the context of complex network theory, from a statistical physics standpoint. We examine two distinct problems in this research field, taking a special interest in their respective critical properties. In both cases, the emergence of criticality is driven by a local optimization dynamics. Firstly, a recently introduced class of percolation problems that attracted a significant amount of attention from the scientific community, and was quickly followed up by an abundance of other works. Percolation transitions were believed to be continuous, until, recently, an 'explosive' percolation problem was reported to undergo a discontinuous transition, in [93]. The system's evolution is driven by a metropolis-like algorithm, apparently producing a discontinuous jump on the giant component's size at the percolation threshold. This finding was subsequently supported by number of other experimental studies [96, 97, 98, 99, 100, 101]. However, in [1] we have proved that the explosive percolation transition is actually continuous. The discontinuity which was observed in the evolution of the giant component's relative size is explained by the unusual smallness of the corresponding critical exponent, combined with the finiteness of the systems considered in experiments. Therefore, the size of the jump vanishes as the system's size goes to infinity. Additionally, we provide the complete theoretical description of the critical properties for a generalized version of the explosive percolation model [2], as well as a method [3] for a precise calculation of percolation's critical properties from numerical data (useful when exact results are not available). Secondly, we study a network flow optimization model, where the dynamics consists of consecutive mergings and splittings of currents flowing in the network. The current conservation constraint does not impose any particular criterion for the split of current among channels outgoing nodes, allowing us to introduce an asymmetrical rule, observed in several real systems. We solved analytically the dynamic equations describing this model in the high and low current regimes. The solutions found are compared with numerical results, for the two regimes, showing an excellent agreement. Surprisingly, in the low current regime, this model exhibits some features usually associated with continuous phase transitions.

Application-specific modified particle swarm optimization for energy resource scheduling considering vehicle-to-grid

This paper presents a modified Particle Swarm Optimization (PSO) methodology to solve the problem of energy resources management with high penetration of distributed generation and Electric Vehicles (EVs) with gridable capability (V2G). The objective of the day-ahead scheduling problem in this work is to minimize operation costs, namely energy costs, regarding he management of these resources in the smart grid context. The modifications applied to the PSO aimed to improve its adequacy to solve the mentioned problem. The proposed Application Specific Modified Particle Swarm Optimization (ASMPSO) includes an intelligent mechanism to adjust velocity limits during the search process, as well as self-parameterization of PSO parameters making it more user-independent. It presents better robustness and convergence characteristics compared with the tested PSO variants as well as better constraint handling. This enables its use for addressing real world large-scale problems in much shorter times than the deterministic methods, providing system operators with adequate decision support and achieving efficient resource scheduling, even when a significant number of alternative scenarios should be considered. The paper includes two realistic case studies with different penetration of gridable vehicles (1000 and 2000). The proposed methodology is about 2600 times faster than Mixed-Integer Non-Linear Programming (MINLP) reference technique, reducing the time required from 25 h to 36 s for the scenario with 2000 vehicles, with about one percent of difference in the objective function cost value.

Filters method in direct search optimization, new measures to admissibility

Constrained nonlinear optimization problems are usually solved using penalty or barrier methods combined with unconstrained optimization methods. Another alternative used to solve constrained nonlinear optimization problems is the lters method. Filters method, introduced by Fletcher and Ley er in 2002, have been widely used in several areas of constrained nonlinear optimization. These methods treat optimization problem as bi-objective attempts to minimize the objective function and a continuous function that aggregates the constraint violation functions. Audet and Dennis have presented the rst lters method for derivative-free nonlinear programming, based on pattern search methods. Motivated by this work we have de- veloped a new direct search method, based on simplex methods, for general constrained optimization, that combines the features of the simplex method and lters method. This work presents a new variant of these methods which combines the lters method with other direct search methods and are proposed some alternatives to aggregate the constraint violation functions.

Application-Specific Modified Particle Swarm Optimization for energy resource scheduling considering vehicle-to-grid

This paper presents a modified Particle Swarm Optimization (PSO) methodology to solve the problem of energy resources management with high penetration of distributed generation and Electric Vehicles (EVs) with gridable capability (V2G). The objective of the day-ahead scheduling problem in this work is to minimize operation costs, namely energy costs, regarding the management of these resources in the smart grid context. The modifications applied to the PSO aimed to improve its adequacy to solve the mentioned problem. The proposed Application Specific Modified Particle Swarm Optimization (ASMPSO) includes an intelligent mechanism to adjust velocity limits during the search process, as well as self-parameterization of PSO parameters making it more user-independent. It presents better robustness and convergence characteristics compared with the tested PSO variants as well as better constraint handling. This enables its use for addressing real world large-scale problems in much shorter times than the deterministic methods, providing system operators with adequate decision support and achieving efficient resource scheduling, even when a significant number of alternative scenarios should be considered. The paper includes two realistic case studies with different penetration of gridable vehicles (1000 and 2000). The proposed methodology is about 2600 times faster than Mixed-Integer Non-Linear Programming (MINLP) reference technique, reducing the time required from 25 h to 36 s for the scenario with 2000 vehicles, with about one percent of difference in the objective function cost value.