Search

The long-term operation of hydro-thermal power generation systems is modeled by a large-scale stochastic optimization problem that includes nonlinear constraints due to the head computation in hydroelectric plants. We do a detailed development of the problem model and state it by a non-anticipative scenario analysis, leading to a large-scale nonlinear programming problem. This is solved by a filter algorithm with sequential quadratic programming iterations that minimize quadratic Lagrangian approximations using exact hessians in L∞ trust regions. The method is applied to the long-term planning of the Brazilian system, with over 100 hydroelectric and 50 thermoelectric plants, distributed in 5 interconnected subsystems. This problem with 50 synthetically generated inflow scenarios and a horizon of 60 months, amounting to about one million variables and 15000 nonlinear constraints was solved by the filter algorithm in a standard 2016 notebook computer in 10 h of CPU.

This is a short tutorial on complexity studies for differentiable convex optimization. A complexity study is made for a class of problems, an "oracle" that obtains information about the problem at a given point, and a stopping rule for algorithms. These three items compose a scheme, for which we study the performance of algorithms and problem complexity. Our problem classes will be quadratic minimization and convex minimization in ℝn. The oracle will always be first order. We study the performance of steepest descent and Krylov spacemethods for quadratic function minimization and Nesterov’s approach to the minimization of differentiable convex functions.

We consider the minimization of a convex function on a bounded polyhedron (polytope) represented by linear equality constraints and non-negative variables. We define the Levenberg---Marquardt and central trajectories starting at the analytic center using the same parameter, and show that they satisfy a primal-dual relationship, being close to each other for large values of the parameter. Based on this, we develop an algorithm that starts computing primal-dual feasible points on the Levenberg---Marquardt trajectory and eventually moves to the central path. Our main theorem is particularly relevant in quadratic programming, where points on the primal-dual Levenberg---Marquardt trajectory can be calculated by means of a system of linear equations. We present some computational tests related to box constrained trust region subproblems.

We modify the first order algorithm for convex programming described by Nesterov in his book (in Introductory lectures on convex optimization. A basic course. Kluwer, Boston, 2004). In his algorithms, Nesterov makes explicit use of a Lipschitz constant L for the function gradient, which is either assumed known (Nesterov in Introductory lectures on convex optimization. A basic course. Kluwer, Boston, 2004), or is estimated by an adaptive procedure (Nesterov 2007). We eliminate the use of L at the cost of an extra imprecise line search, and obtain an algorithm which keeps the optimal complexity properties and also inherit the global convergence properties of the steepest descent method for general continuously differentiable optimization. Besides this, we develop an adaptive procedure for estimating a strong convexity constant for the function. Numerical tests for a limited set of toy problems show an improvement in performance when compared with the original Nesterov’s algorithms.

In Gonzaga et al. [A globally convergent filter method for nonlinear programming, SIAM J. Optimiz. 14 (2003), pp. 646–669] we discuss general conditions to ensure global convergence of inexact restoration filter algorithms for non-linear programming. In this article we show how to avoid the Maratos effect by means of a second-order correction. The algorithms are based on feasibility and optimality phases, which can be either independent or not. The optimality phase differs from the original one only when a full Newton step for the tangential minimization of the Lagrangian is efficient but not acceptable by the filter method. In this case a second-order corrector step tries to produce an acceptable point keeping the efficiency of the rejected step. The resulting point is tested by trust region criteria. Under the usual hypotheses, the algorithm inherits the quadratic convergence properties of the feasibility and optimality phases. This article includes a comparison between classical Sequential Quadratic Pr...

We study a family of penalty functions for augmented Lagrangian methods, and concentrate on a penalty based on the modified logarithmic barrier function. The convex conjugate of this penalty induces a Bregman distance, and the dual iterates associated with the augmented Lagrangian algorithm correspond to the iterates produced by a proximal point algorithm based on this distance. The global convergence of the dual iterates is then proved. Moreover, the level curves of the quadratic approximation of the dual kernels associated with these penalty functions are the Dikin ellipsoids. Copyright © 2008 John Wiley & Sons, Ltd.

We present a general filter algorithm that allows a great deal of freedom in the step computation. Each iteration of the algorithm consists basically in computing a point which is not forbidden by the filter, from the current point. We prove its global convergence, assuming that the step must be efficient, in the sense that, near a feasible nonstationary point, the reduction of the objective function is “large.” We show that this condition is reasonable, by presenting two classical ways of performing the step which satisfy it. In the first one, the step is obtained by the inexact restoration method of Martinez and Pilotta. In the second, the step is computed by sequential quadratic programming.

We present a method for constructing linear programming problems with randomly generated data. Besides the number of variables and constraints, the dimensions of the primal and dual faces are given. We show that, for problems in which the constraint matrix is carelessly constructed with random entries, with probability one only one between primal degeneracy and dual degeneracy appears.

In this paper we list several useful properties of central points in linear programming problems. We study the logarithmic barrier function, the analytic center and the central path, relating the proximity measures and scaled Euclidean distances defined for the primal and primal–dual problems. We study the Newton centering steps, and show how large the short steps used in path following algorithms can actually be, and what variation can be ensured for the barrier function in each iteration of such methods. We relate the primal and primal–dual Newton centering steps and propose a primal-only path following algorithm for linear programming.

In this paper we present a filter algorithm for nonlinear programming and prove its global convergence to stationary points. Each iteration is composed of a feasibility phase, which reduces a measure of infeasibility, and an optimality phase, which reduces the objective function in a tangential approximation of the feasible set. These two phases are totally independent, and the only coupling between them is provided by the filter. The method is independent of the internal algorithms used in each iteration, as long as these algorithms satisfy reasonable assumptions on their efficiency. Under standard hypotheses, we show two results: for a filter with minimum size, the algorithm generates a stationary accumulation point; for a slightly larger filter, all accumulation points are stationary.

We consider first the differentiable nonlinear programming problem and study the asymptotic behavior of methods based on a family of penalty functions that approximate asymptotically the usual exact penalty function. We associate two parameters to these functions: one is used to control the slope and the other controls the deviation from the exact penalty. We propose a method that does not change the slope for feasible iterates and show that for problems satisfying the Mangasarian-Fromovitz constraint qualification all iterates will remain feasible after a finite number of iterations. The same results are obtained for non-smooth convex problems under a Slater qualification condition.

Este artigo aborda o problema de locação ótima de torres de transmissão como uma aplicação de métodos de busca em grafos com nós parcialmente ordenados com uma modelagem que aplica a este problema pela primeira vez o conceito de relações de preferência entre nós. São primeiramente apresentados resultados sobre grafos e algoritmos de busca. As restrições eletro-mecânicas e topográficas à obtenção do caminho de custo mínimo são descritas, são definidos os nós, arcos, custos, e caminhos, além de outros componentes do grafo e são descritos os algoritmos de otimização utilizados. O trabalho introduz e demonstra a validade de relações de preferência entre nós, que são utilizadas (juntamente com comparações de custos) no processo de eliminação de caminhos. Este procedimento aumenta a eficiência dos algoritmos de otimização utilizados.This paper focuses on optimal transmission tower spotting as an application of search methods in a graph with partially ordered nodes and for the first time models the problem using preference relations between nodes. First basic results from graph theory and search algorithms are presented. Electro-mechanical and topographical constraints to obtaining the path of minimum cost are described, the nodes, arcs, costs and paths are defined, and the optimization algorithms are shown. The paper introduces and demonstrates the validity of preference relations between nodes. These are used together with cost comparisons to eliminate paths. This procedure increases the efficiency of the optimization algorithms.

We describe a method for solving the maximum likelihood estimate problem of a mixing distribution, based on an interior cutting plane algorithm with cuts through analytic centers. From increasingly refined discretized statistical problem models we construct a sequence of inner non-linear problems and solve them approximately applying a primal-dual algorithm to the dual formulation. Refining the statistical problem is equivalent to adding cuts to the inner problems.

Each master iteration of a simplified Newton algorithm for solving a system of equations starts by computing the Jacobian matrix and then uses this matrix in the computation ofp Newton steps: the first of these steps is exact, and the other are called "simplified". In this paper we apply this approach to a large step path following algorithm for monotone linear complementarity problems. The resulting method generates sequences of objective values (duality gaps) that converge to zero with Q-orderp+1 in the number of master iterations, and with a complexity of $$O(\sqrt n L)$$ iterations.

The literature on interior point algorithms shows impressive results related to the speed of convergence of the objective values, but very little is known about the convergence of the iterate sequences. This paper studies the horizontal linear complementarity problem, and derives general convergence properties for algorithms based on Newton iterations. This problem provides a simple and general framework for most existing primal-dual interior point methods. The conclusion is that most of the published algorithms of this kind generate convergent sequences. In many cases (whenever the convergence is not too fast in a certain sense), the sequences converge to the analytic center of the optimal face.

In this paper a unified treatment of algorithms is described for linear programming methods based on the central path. This path is a curve along which the cost decreases, and that stays always far...

Since Karmarkar published his algorithm for linear programming, several different interior directions have been proposed and much effort was spent on the problem transformations needed to apply these new techniques. This paper examines several search directions in a common framework that does not need any problem transformation. These directions prove to be combinations of two problem-dependent vectors, and can all be improved by a bidirectional search procedure. We conclude that there are essentially two polynomial algorithms: Karmarkar's method and the algorithm that follows a central trajectory, and they differ only in a choice of parameters (respectively lower bound and penalty multiplier).

We present a procedure for computing lower bounds for the optimal cost in a linear programming problem. Whenever the procedure succeeds, it finds a dual feasible slack and the associated duality gap. Although no projective transformations or problem restatements are used, the method coincides with the procedures by Todd and Burrell and by de Ghellinck and Vial when these procedures are applicable. The procedure applies directly to affine potential reduction algorithms, and improves on existent techniques for finding lower bounds.

Interior methods for linear programming were designed mainly for problems formulated with equality constraints and non-negative variables. The formulation with inequality constraints has shown to be very convenient for practical implementations, and the translation of methods designed for one formulation into the other is not trivial. This paper relates the geometric features of both representations, shows how to transport data and procedures between them and shows how cones and conical projections can be associated with inequality constraints.

This paper presents some examples of ill-behaved central paths in convex optimization. Some contain infinitely many fixed length central segments; others manifest oscillations with infinite variation. These central paths can be encountered even for infinitely differentiable data.

The Linear Programming Problem is manipulated to be stated as a Non-Linear Programming Problem in which Karmarkar's logarithmic potential function is minimized in the positive cone generated by the original feasible set. The resulting problem is then solved by a master algorithm that iteratively rescales the problem and calls an internal unconstrained non-linear programming algorithm. Several different procedures for the internal algorithm are proposed, giving priority either to the reduction of the potential function or of the actual cost. We show that Karmarkar's algorithm is equivalent to this method in the special case in which the internal algorithm is reduced to a single steepest descent iteration. All variants of the new algorithm have the same complexity as Karmarkar's method, but the amount of computation is reduced by the fact that only one projection matrix must be calculated for each call of the internal algorithm.

This paper presents a new class of outer approximations algorithms which incorporate constraint dropping schemes. The algorithms are based on the use of certain types of optimality functions, which are commonly used in minimization algorithms, for defining stationary points. The algorithms are implementable in that all the inner minimizations and maximizations need to be carried out only approximately. It is shown that any accumulation point constructed by these algorithms is both feasible and stationary.

The problem of optimal network capacity planning is reshaped into a problem of minimum-cost paths in a graph.A special graph-search algorithm is then developed to find optimum line addition policies during a finite planning period. The application to a real life problem is also described.