An augmented penalty function method with penalty parameter updates for nonconvex optimization

Given an augmented Lagrangian scheme for a general optimization problem, we use an epsilon subgradient step for improving the dual function. This can be seen as an update for an augmented penalty method, which is more stable because it does not force the penalty parameter to tend to infinity. We establish for this update primal-dual convergence for our augmented penalty method. As illustration, we apply our method to the test-bed kissing number problem.     

A primal-dual augmented Lagrangian

Nonlinearly constrained optimization problems can be solved by minimizing a sequence of simpler unconstrained or linearly constrained subproblems. In this paper, we consider the formulation of subproblems in which the objective function is a generalization of the Hestenes-Powell augmented Lagrangian function. The main feature of the generalized function is that it is minimized with respect to both the primal and the dual variables simultaneously. The benefits of this approach include: (i) the ability to control the quality of the dual variables during the solution of the subproblem; (ii) the availability of improved dual estimates on early termination of the subproblem; and (iii) the ability to regularize the subproblem by imposing explicit bounds on the dual variables. We propose two primal-dual variants of conventional primal methods: a primal-dual bound constrained Lagrangian (pdBCL) method and a primal-dual ℓ ₁ linearly constrained Lagrangian (pdℓ ₁LCL) method. Finally, a new sequential quadratic programming (pdSQP) method is proposed that uses the primal-dual augmented Lagrangian as a merit function.     

Quadratic convergence of potential-reduction methods for degenerate problems

Global and local convergence properties of a primal-dual interior-point pure potential-reduction algorithm for linear programming problems is analyzed. This algorithm is a primal-dual variant of the Iri-Imai method and uses modified Newton search directions to minimize the Tanabe-Todd-Ye (TTY) potential function. A polynomial time complexity for the method is demonstrated. Furthermore, this method is shown to have a unique accumulation point even for degenerate problems and to have Q-quadratic convergence to this point by an appropriate choice of the step-sizes. This is, to the best of our knowledge, the first superlinear convergence result on degenerate linear programs for primal-dual interior-point algorithms that do not follow the central path. Received: February 12, 1998 / Accepted: March 3, 2000?Published online January 17, 2001     

Long-step strategies in interior-point primal-dual methods

In this paper we analyze from a unique point of view the behavior of path-following and primal-dual potential reduction methods on nonlinear conic problems. We demonstrate that most interior-point methods with efficiency estimate can be considered as different strategies of minimizing aconvex primal-dual potential function in an extended primal-dual space. Their efficiency estimate is a direct consequence of large local norm of the gradient of the potential function along a central path. It is shown that the neighborhood of this path is a region of the fastest decrease of the potential. Therefore the long-step path-following methods are, in a sense, the best potential-reduction strategies. We present three examples of such long-step strategies. We prove also an efficiency estimate for a pure primal-dual potential reduction method, which can be considered as an implementation of apenalty strategy based on a functional proximity measure. Using the convex primal dual potential, we prove efficiency estimates for Karmarkar-type and Dikin-type methods as applied to a homogeneous reformulation of the initial primal-dual problem.     

Interior-point methods for linear optimization based on a kernel function with a trigonometric barrier term

In this paper, we present a new barrier function for primal–dual interior-point methods in linear optimization. The proposed kernel function has a trigonometric barrier term. It is shown that in the interior-point methods based on this function for large-update methods, the iteration bound is improved significantly. For small-update interior-point methods, the iteration bound is the best currently known bound for primal–dual interior-point methods.     

A primal-dual approximation algorithm for generalized steiner network problems

We present the first polynomial-time approximation algorithm for finding a minimum-cost subgraph having at least a specified number of edges in each cut. This class of problems includes, among others, the generalized Steiner network problem, also called the survivable network design problem. Ifk is the maximum cut requirement of the problem, our solution comes within a factor of 2k of optimal. Our algorithm is primal-dual and shows the importance of this technique in designing approximation algorithms.Research supported by an NSF Graduate Fellowship, DARPA contracts N00014-91-J-1698 and N00014-92-J-1799, and AT&T Bell Laboratories.Research supported in part by Air Force contract F49620-92-J-0125 and DARPA contract N00014-92-J-1799.Part of this work was done while the author was visiting AT&T Bell Laboratories and Bellcore.     

Dynamic bundle methods

Lagrangian relaxation is a popular technique to solve difficult optimization problems. However, the applicability of this technique depends on having a relatively low number of hard constraints to dualize. When there are many hard constraints, it may be preferable to relax them dynamically, according to some rule depending on which multipliers are active. From the dual point of view, this approach yields multipliers with varying dimensions and a dual objective function that changes along iterations. We discuss how to apply a bundle methodology to solve this kind of dual problems. Our framework covers many separation procedures to generate inequalities that can be found in the literature, including (but not limited to) the most violated inequality. We analyze the resulting dynamic bundle method giving a positive answer for its primal-dual convergence properties, and, under suitable conditions, show finite termination for polyhedral problems. Claudia Sagastizábal is on leave from INRIA Rocquencourt, France. Research supported by CNPq Grant No.303540-03/6.     

Stability of the primal-dual partition in linear semi-infinite programming

We analyse the primal-dual states in linear semi-infinite programming (LSIP), where we consider the primal problem and the so called Haar's dual problem. Any linear programming problem and its dual can be classified as bounded, unbounded or inconsistent, giving rise to nine possible primal-dual states, which are reduced to six by the weak duality property. Recently, Goberna and Todorov have studied this partition and its stability in continuous LSIP in a series of papers [M.A. Goberna and M.I. Todorov, Primal, dual and primal-dual partitions in continuous linear semi-infinite programming, Optimization 56 (2007), pp. 617–628; M.A. Goberna and M.I. Todorov, Generic primal-dual solvability in continuous linear semi-infinite programming, Optimization 57 (2008), pp. 239–248]. In this article we consider the general case, with no continuity assumptions, discussing the maintenance of the primal-dual state of the problem by allowing small perturbations of the data. We characterize the stability of all of the six possible primal-dual states through necessary and sufficient conditions which depend on the data, and can be easily checked, showing some differences with the continuous case. These conditions involve the strong Slater constraint qualification, and some distinguished convex sets associated to the data.     

A parallel projection method for solving generalized linear least-squares problems

Summary A parallel projection algorithm is proposed to solve the generalized linear least-squares problem: find a vector to minimize the 2-norm distance from its image under an affine mapping to a closed convex cone. In each iteration of the algorithm the problem is decomposed into several independent small problems of finding projections onto subspaces, which are simple and can be tackled parallelly. The algorithm can be viewed as a dual version of the algorithm proposed by Han and Lou [8]. For the special problem under consideration, stronger convergence results are established. The algorithm is also related to the block iterative methods of Elfving [6], Dennis and Steihaug [5], and the primal-dual method of Springarn [14].This material is based on work supported in part by the National Science foundation under Grant DMS-8602416 and by the Center for Supercomputing Research and Development, University of Illinois at Urbana-Champaign     

A path to the Arrow–Debreu competitive market equilibrium

We present polynomial-time interior-point algorithms for solving the Fisher and Arrow–Debreu competitive market equilibrium problems with linear utilities and n players. Both of them have the arithmetic operation complexity bound of )) for computing an -equilibrium solution. If the problem data are rational numbers and their bit-length is L, then the bound to generate an exact solution is O(n ⁴ L) which is in line with the best complexity bound for linear programming of the same dimension and size. This is a significant improvement over the previously best bound )) for approximating the two problems using other methods. The key ingredient to derive these results is to show that these problems admit convex optimization formulations, efficient barrier functions and fast rounding techniques. We also present a continuous path leading to the set of the Arrow–Debreu equilibrium, similar to the central path developed for linear programming interior-point methods. This path is derived from the weighted logarithmic utility and barrier functions and the Brouwer fixed-point theorem. The defining equations are bilinear and possess some primal-dual structure for the application of the Newton-based path-following method. Dedicated to Clovis Gonzaga on the occassion of his 60th birthday. This author was supported in part by NSF Grants DMS-0306611 and DMS-0604513. The author would like to thank Curtis Eaves, Osman Güler, Kamal Jain and Mike Todd for insightful discussions on this subject, especially on their mathematical references and economic interpretations of the fixed-point model presented in this paper.     

Two properties of condition numbers for convex programs via implicitly defined barrier functions

We study two issues on condition numbers for convex programs: one has to do with the growth of the condition numbers of the linear equations arising in interior-point algorithms; the other deals with solving conic systems and estimating their distance to infeasibility.?These two issues share a common ground: the key tool for their development is a simple, novel perspective based on implicitly-defined barrier functions. This tool has potential use in optimization beyond the context of condition numbers. Received: October 2000 / Accepted: October 2001?Published online March 27, 2002     

How to make a digraph strongly connected

Given a directed graphG, acovering is a subsetB of edges which meets all directed cuts ofG. Equivalently, the contraction of the elements ofB makesG strongly connected. AnO(n ⁵) primal-dual algorithm is presented for finding a minimum weight covering of an edge-weighted digraph. The algorithm also provides a constructive proof for a min-max theorem due to Lucchesi and Younger and for its weighted version.     

On the behavior of the homogeneous self-dual model for conic convex optimization

There is a natural norm associated with a starting point of the homogeneous self-dual (HSD) embedding model for conic convex optimization. In this norm two measures of the HSD model's behavior are precisely controlled independent of the problem instance: (i) the sizes of ɛ-optimal solutions, and (ii) the maximum distance of ɛ-optimal solutions to the boundary of the cone of the HSD variables. This norm is also useful in developing a stopping-rule theory for HSD-based interior-point solvers such as SeDuMi. Under mild assumptions, we show that a standard stopping rule implicitly involves the sum of the sizes of the ɛ-optimal primal and dual solutions, as well as the size of the initial primal and dual infeasibility residuals. This theory suggests possible criteria for developing starting points for the homogeneous self-dual model that might improve the resulting solution time in practice. This research has been partially supported through the MIT-Singapore Alliance.     

Asymptotic analysis of the exponential penalty trajectory in linear programming

We consider the linear program min{cx: Axb} and the associated exponential penalty functionf _r(x) = cx + rexp[(A _ix – b_i)/r]. Forr close to 0, the unconstrained minimizerx(r) off _r admits an asymptotic expansion of the formx(r) = x ^* + rd^* + (r) wherex ^* is a particular optimal solution of the linear program and the error term(r) has an exponentially fast decay. Using duality theory we exhibit an associated dual trajectory(r) which converges exponentially fast to a particular dual optimal solution. These results are completed by an asymptotic analysis whenr tends to : the primal trajectory has an asymptotic ray and the dual trajectory converges to an interior dual feasible solution.Corresponding author. Both authors partially supported by FONDECYT.     

Infeasible-start primal-dual methods and infeasibility detectors for nonlinear programming problems

ln) iterations, where ν is the parameter of a self-concordant barrier for the cone, ε is a relative accuracy and ρ_f is a feasibility measure. We also discuss the behavior of path-following methods as applied to infeasible problems. We prove that strict infeasibility (primal or dual) can be detected in O(ln) iterations, where ρ_· is a primal or dual infeasibility measure. Received April 25, 1996 / Revised version received March 4, 1998 Published online October 9, 1998     

Linear bilevel programs with multiple objectives at the upper level

Bilevel programming has been proposed for dealing with decision processes involving two decision makers with a hierarchical structure. They are characterized by the existence of two optimization problems in which the constraint region of the upper level problem is implicitly determined by the lower level optimization problem. Focus of the paper is on general bilevel optimization problems with multiple objectives at the upper level of decision making. When all objective functions are linear and constraints at both levels define polyhedra, it is proved that the set of efficient solutions is non-empty. Taking into account the properties of the feasible region of the bilevel problem, some methods of computing efficient solutions are given based on both weighted sum scalarization and scalarization techniques. All the methods result in solving linear bilevel problems with a single objective function at each level.     

Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra

We present a unifying framework to establish a lower bound on the number of semidefinite-programming-based lift-and-project iterations (rank) for computing the convex hull of the feasible solutions of various combinatorial optimization problems. This framework is based on the maps which are commutative with the lift-and-project operators. Some special commutative maps were originally observed by Lovász and Schrijver and have been used usually implicitly in the previous lower-bound analyses. In this paper, we formalize the lift-and-project commutative maps and propose a general framework for lower-bound analysis, in which we can recapture many of the previous lower-bound results on the lift-and-project ranks.