DRUM :: Browsing by Author "Tits, Andre L."

Browsing by Author "Tits, Andre L."

Now showing 1 - 8 of 8

Avoiding the Maratos Effect by Means of a Nomnonotone Line Search IL Inequality Constrained Problems - Feasible Iterates.
(1989) Bannans, J. Frederic; Panier, Eliane R.; Tits, Andre L.; ISR
When solving inequality constrained optimization problems via Sequential Quadratic Programming (SQP), it is potentially advantageous to generate iterates that all satisfy the constraints: all quadratic programs encountered are then feasible and there is no need for a surrogate merit function. It has recently been shown that this is indeed possible, by means of a suitable perturbation of the original SQP iteration, without losing superlinear convergence. In this context, the well known Maratos effect is compounded by the possible infeasibility of the full step of one even close to a solution. These difficulties have been accommodated by making use of a suitable modification of a bending" technique proposed by Mayne and Polak, requiring evaluation of the constraints function at an auxiliary point at each iteration. In part I of this two-part paper, it was shown that, when feasibility of the successive iterates is not required, the Maratos effect can be avoided by combining Mayne and Polak's technique with a nonmonotone line search proposed by Grippo, Lampariello and Lucidi in the context of unconstrained optimization, in such a way that, asymptotically, function evaluations are no longer performed at auxiliary points. In this second part, we show that feasibility can be restored without resorting to additional constraint evaluations, by adaptively estimating a bound on the second derivatives of the active constraints. Extension to constrained minimax problems is briefly discussed.
CONSOLE User's Manual.
(1987) Fan, Michael K-H.; Koninckx, Jan; Wang, Li-Sheng; Tits, Andre L.; ISR
The CONSOLE tandem is a tool for optimization-based design of a large class of systems. The essential requirements are that a simulator be available for evaluating the performance of instances of the system under consideration and that the parameters to be optimally adjusted vary over a continuous (as opposed to discrete) set of values. Todate, CONSOLE has been used on problems as diverse as design of a controller for a flexible arm, an aircraft, or a copolymerization reactor. The manual is organized as follows. In Chapter 1, the ideas and principles upon which CONSOLE is constructed are outlined and the design methodology underlying CONSOLE is sketched. Chapter 2 introduces the novice user to CONSOLE by way of a simple tutorial example. This chapter is strongly recommended to new users as it leads them step by step through a CONSOLE session. Chapter 3 is entirely devoted to CONVERT. It includes a thorough description of the different data types, assignments and commands that form the CONVERT syntax. Chapter 4 discusses SOLVE. The essential features of the optimization algorithm are outlined and the operation of SOLVE SOLVE is discussed. Special attention is given to the interactive capabilities of SOLVE, in particuar the Pcomb display. In Chapter 5, the question of using an interface between SOLVE and simulators of the user's choice is discussed. A general structure is given. Finally, Chapter 6 presents two design examples. Appendices A and B consist in reference manuals, for CONVERT and SOLVE respectively.
Convex Duality and Entropy-Based Moment Closures: Characterizing Degenerate Densities
(2007-05-30) Hauck, Cory D.; Levermore, C. David; Tits, Andre L.
A common method for constructing a function from a finite set of moments is to solve a constrained minimization problem. The idea is to find, among all functions with the given moments, that function which minimizes a physically motivated, strictly convex functional. In the kinetic theory of gases, this functional is the kinetic entropy; the given moments are macroscopic densities; and the solution to the constrained minimization problem is used to formally derive a closed system of partial differential equations which describe how the macroscopic densities evolve in time. Moment equations are useful because they simplify the kinetic, phase-space description of a gas, and with entropy-based closures, they retain many of the fundamental properties of kinetic transport. Unfortunately, in many situations, macroscopic densities can take on values for which the constrained minimization problem does not have a solution. Essentially, this is because the moments are not continuous functionals with respect to the L1 topology. In this paper, we give a geometric description of these so-called degenerate densities in the most general possible setting. Our key tool is the complementary slackness condition that is derived from a dual formulation of a minimization problem with relaxed constraints. We show that the set of degenerate densities is a union of convex cones and, under reasonable assumptions, that this set is small in both a topological and measure theoretic sense. This result is important for further assessment and implementation of entropy-based moment closures.
An Interior Point Method for Linear Programming, with n Active Set Flavor
(1999) Tits, Andre L.; ISR
It is now well established that, especially on large linearprogramming problems, the simplex method typically takes upa number of iterations considerably larger than recentinterior-points methods in order to reach a solution.On the other hand, at each iteration, the size of thelinear system of equations solved by the formercan be significantly less than that of the linearsystem solved by the latter.The algorithm proposed in this paper can be thought ofas a compromise between the two extremes: conceptuallyan interior-point method, it ignores, at each iteration,all constraints except those in a small "active set"(in the dual framework). For sake of simplicity, inthis first attempt, an affine scaling algorithm is usedand strong assumptions are made on the problem. Globaland local quadratic convergence is proved.
Joint Scheduling and Routing for Ad-hoc Networks Under Channel State Uncertainty
(2007) Pantelidou, Anna; Ephremides, Anthony; Tits, Andre L.; ISR
We determine a joint link activation and routing policy that maximizes the stable throughput region of time-varying wireless ad-hoc networks with multiple commodities. In practice, the state of the channel process from the time it is observed till the time a transmission actually takes place can be significantly different. With this in mind, we introduce a stationary policy that takes scheduling and routing decisions based on a possibly inaccurate estimate of the true channel state. We show optimality of this policy within a broad class of link activation processes. In particular, processes in this class may be induced by any policy, possibly non-stationary, even anticipative and aware of the entire sample paths, including the future, of the arrival, estimated and true channel state processes, as long as it has no knowledge on the current true channel state, besides that available through the estimated channel state.
A polynomial-time interior-point method for conic optimization, with inexact barrier evaluations
(2008-04) Schurr, Simon P.; O'Leary, Dianne P.; Tits, Andre L.
We consider a primal-dual short-step interior-point method for conic convex optimization problems for which exact evaluation of the gradient and Hessian of the primal and dual barrier functions is either impossible or prohibitively expensive. As our main contribution, we show that if approximate gradients and Hessians of the primal barrier function can be computed, and the relative errors in such quantities are not too large, then the method has polynomial worst-case iteration complexity. (In particular, polynomial iteration complexity ensues when the gradient and Hessian are evaluated exactly.) In addition, the algorithm requires no evaluation---or even approximate evaluation---of quantities related to the barrier function for the dual cone, even for problems in which the underlying cone is not self-dual.
A Primal-Dual Interior-Point Method for Nonlinear Programming with Strong Global and Local Convergence Properties
(2002) Tits, Andre L.; Wachter, Andreas; Bakhtiari, Sasan; Urban, Thomas J.; Lawrence, Craig T.; ISR
An exact-penalty-function-based scheme|inspired from an old ideadue to Mayne and Polak (Math. Prog., vol. 11, 1976, pp. 67{80)|isproposed for extending to general smooth constrained optimizationproblems any given feasible interior-point method for inequality constrained problems.
It is shown that the primal-dual interior-point framework allows for a simpler penalty parameter update rule than that discussed and analyzed by the originators of the scheme in the context of first order methods of feasible direction. Strong global and local convergence results are proved under mild assumptions.
In particular,(i) the proposed algorithm does not suffer a common pitfall recently pointed out by Wachter and Biegler; and (ii) the positive definiteness assumption on the Hessian estimate, made in the original version of the algorithm, is relaxed, allowing for the use of exact Hessian information, resulting in local quadratic convergence. Promisingnumerical results are reported.
Note: This report is a major revision to TR 2001-3, "A Primal-Dual Interior-Point Method for Nonlinear Programming with Strong Global and Local Convergence Properties," by A.L. Tits, T.J. Urban, S. Bakhtiari, C.T. Lawrence.
Universal Duality in Conic Convex Optimization
(2004) Schurr, Simon P.; Tits, Andre L.; O'Leary, Dianne P.; ISR
Given a primal-dual pair of linear programs, it is known that if their optimal values are viewed as lying on the extended real line, then the duality gap is zero, unless both problems are infeasible, in which case the optimal values are +infinity and -infinity. In contrast, for optimization problems over nonpolyhedral convex cones, a nonzero duality gap can exist even in the case where the primal and dual problems are both feasible.
For a pair of dual conic convex programs, we provide simple conditions on the onstraint matricesand cone under which the duality gap is zero for every choice of linear objective function and ight-hand-side We refer to this property as niversal duality Our conditions possess the following properties: (i) they are necessary and sufficient, in the sense that if (and only if) they do not hold, the duality gap is nonzero for some linear objective function and ight-hand-side (ii) they are metrically and topologically generic; and (iii) they can be verified by solving a single conic convex program. As a side result, we also show that the feasible sets of a primal conic convex program and its dual cannot both be bounded, unless they are both empty, and we relate this to universal duality.

Browsing by Author "Tits, Andre L."

Results Per Page

Sort Options