Search

The main goal of this dissertation is to study the formulation and analysis of primal-dual path-following methods for nonlinear programming (NLP), which involves the minimization or maximization of a nonlinear objective function subject to constraints on the variables. Two important types of nonlinear program are problems with nonlinear equality constraints and problems with nonlinear inequality constraints. In this dissertation, two new methods are proposed for nonlinear programming. The first is a new primal-dual path-following augmented Lagrangian method (PDAL) for solving a nonlinear program with equality constraints only. The second is a new primal-dual path-following shifted penalty-barrier method (PDPB) for solving a nonlinear program with a mixture of equality and inequality constraints. The method of PDPB may be regarded as an extension of PDAL to handle nonlinear inequality constraints.Algorithms PDAL and PDPB are iterative methods that share the same "two-level" structure involving outer and inner iterations. In the outer iteration of PDAL, the optimality conditions are perturbed to define a "path-following trajectory'' parameterized by a set of Lagrange multiplier estimates and a penalty parameter. The iterates are constructed to closely follow the trajectory towards a constrained local minimizer of the nonlinear program. If an outer iterate deviates significantly from the trajectory, then an inner iteration is invoked in which a primal-dual augmented Lagrangian merit function is minimized to force the iterates back to a neighborhood of the trajectory.A similar approach is used to handle the inequality constraints in PDPB. In this case, the trajectory is followed towards a local solution of the mixed-constraint nonlinear program. This trajectory is parameterized by a set of Lagrange multiplier estimates and penalty and barrier parameters associated with the equality and inequality constraints. If an iterate moves away from the trajectory, a primal-dual shifted penalty-barrier merit function is minimized using a trust-region method. By introducing slack variables, global convergence can be achieved from any starting point without the need for an initial strictly feasible point. Furthermore, numerical experiments indicate that when minimizing the shifted barrier function, the trust-region method requires fewer matrix factorizations and iterations than a comparable line-search method.

We propose a new duality scheme based on a sequence of smooth minorants of the weighted-l1 penalty func- tion, interpreted as a parametrized sequence of augmented Lagrangians, to solve non-convex constrained optimization problems. For the induced sequence of dual problems, we establish strong asymptotic duality properties. Namely, we show that (i) the sequence of dual problems is convex and (ii) the dual values monotonically increase to the optimal primal value. We use these properties to devise a subgradient based primal–dual method, and show that the generated primal sequence accumulates at a solution of the original problem. We illustrate the performance of the new method with three different types of test problems: A polynomial non-convex problem, large-scale instances of the celebrated kissing num- ber problem, and the Markov–Dubins problem. Our numerical experiments demonstrate that, when compared with the tra- ditional implementation of a well-known smooth solver, our new method (using the same well-known solver in its sub- problem) can find better quality solutions, i.e. ‘deeper’ local minima, or solutions closer to the global minimum. Moreover, our method seems to be more time efficient, especially when the problem has a large number of constraints. Refereed/Peer-reviewed

International audience; We present a primal–dual algorithm for solving a constrained optimization problem. This method is based on a Newtonian method applied to a sequence of perturbed KKT systems. These systems follow from a reformulation of the initial problem under the form of a sequence of penalized problems, by introducing an augmented Lagrangian for handling the equality constraints and a log-barrier penalty for the inequalities. We detail the updating rules for monitoring the different parameters (Lagrange multiplier estimate, quadratic penalty and log-barrier parameter), in order to get strong global convergence properties. We show that one advantage of this approach is that it introduces a natural regularization of the linear system to solve at each iteration, for the solution of a problem with a rank deficient Jacobian of constraints. The numerical experiments show the good practical performances of the proposed method especially for degenerate problems.

Distributed algorithms for solving coupled semidefinite programs (SDPs) commonly require many iterations to converge. They also put high computational demand on the computational agents. In this paper we show that in case the coupled problem has an inherent tree structure, it is possible to devise an efficient distributed algorithm for solving such problems. This algorithm can potentially enjoy the same efficiency as centralized solvers that exploit sparsity. The proposed algorithm relies on predictor-corrector primal-dual interior-point methods, where we use a message-passing algorithm to compute the search directions distributedly. Message-passing here is closely related to dynamic programming over trees. This allows us to compute the exact search directions in a finite number of steps. Furthermore this number can be computed a priori and only depends on the coupling structure of the problem. We use the proposed algorithm for analyzing robustness of large-scale uncertain systems distributedly. We test the performance of this algorithm using numerical examples., 14 pages and 6 figurs. Submitted to IEEE Transactions on Automatic Control

Sequential quadratic programming (SQP) methods are a popular class of methods for nonlinearly constrained optimization. They are particularly effective for solving a sequence of related problems, such as those arising in mixed-integer nonlinear programming and the optimization of functions subject to differential equation constraints. Recently, there has been considerable interest in the formulation of stabilized SQP methods, which are specifically designed to handle degenerate optimization problems. Existing stabilized SQP methods are essentially local in the sense that both the formulation and analysis focus on the properties of the methods in a neighborhood of a solution. A new SQP method is proposed that has favorable global convergence properties yet, under suitable assumptions, is equivalent to a variant of the conventional stabilized SQP method in the neighborhood of a solution. The method combines a primal-dual generalized augmented Lagrangian function with a flexible line search to obtain a sequence of improving estimates of the solution. The method incorporates a convexification algorithm that allows the use of exact second derivatives to define a convex quadratic programming (QP) subproblem without requiring that the Hessian of the Lagrangian be positive definite in the neighborhood of a solution. This gives the potential for fast convergence in the neighborhood of a solution. Additional benefits of the method are that each QP subproblem is regularized and the QP subproblem always has a known feasible point. Numerical experiments are presented for a subset of the problems from the CUTEr test collection. © 2013 Society for Industrial and Applied Mathematics.

This paper is devoted to the optimization problem of continuous multi-partitioning, or multi-labeling, which is based on a convex relaxation of the continuous Potts model. In contrast to previous efforts, which are tackling the optimal labeling problem in a direct manner, we first propose a novel dual model and then build up a corresponding dualitybased approach. By analyzing the dual formulation, sufficient conditions are derived which show that the relaxation is often exact, i.e. there exists optimal solutions that are also globally optimal to the original nonconvex Potts model. In order to deal with the nonsmooth dual problem, we develop a smoothing method based on the log-sum exponential function and indicate that such a smoothing approach leads to a novel smoothed primal-dual model and suggests labelings with maximum entropy. Such a smoothing method for the dual model also yields a new thresholding scheme to obtain approximate solutions. An expectation maximization like algorithm is proposed based on the smoothed formulation which is shown to be superior in efficiency compared to earlier approaches from continuous optimization. Numerical experiments also show that our method outperforms several competitive approaches in various aspects, such as lower energies and better visual quality. publishedVersion

The original publication is available at www.springerlink.com The efficient combination of directions is a significant problem in line search methods that either use negative curvature, or wish to include additional information such as the gradient or different approximations to the Newton direction. In this paper we describe a new procedure to combine several of these directions within an interior-point primal-dual algorithm. Basically, we combine in an efficient manner a modified Newton direction with the gradient of a merit function and a direction of negative curvature, if it exists.We also show that the procedure is well-defined, and it has reasonable theoretical properties regarding the rate of convergence of the method. We also present numerical results from an implementation of the proposed algorithm on a set of small test problems from the CUTE collection. Research supported by Spanish MEC grants BEC2000-0167 and PB98-0728 Publicado

The original publication is available at www.springerlink.com We describe an efficient implementation of an interior-point algorithm for non-convex problems that uses directions of negative curvature. These directions should ensure convergence to second-order KKT points and improve the computational efficiency of the procedure. Some relevant aspects of the implementation are the strategy to combine a direction of negative curvature and a modified Newton direction, and the conditions to ensure feasibility of the iterates with respect to the simple bounds. The use of multivariate barrier and penalty parameters is also discussed, as well as the update rules for these parameters.We analyze the convergence of the procedure; both the linesearch and the update rule for the barrier parameter behave appropriately. As the main goal of the paper is the practical usage of negative curvature, a set of numerical results on small test problems is presented. Based on these results, the relevance of using directions of negative curvature is discussed. Research supported by Spanish MEC grant TIC2000-1750-C06-04; Research supported by Spanish MEC grant BEC2000-0167 Publicado

This papers deals with the restoration of images corrupted by a non-invertible or ill-conditioned linear transform and Poisson noise. Poisson data typically occur in imaging processes where the images are obtained by counting particles, e.g., photons, that hit the image support. By using the Anscombe transform, the Poisson noise can be approximated by an additive Gaussian noise with zero mean and unit variance. Then, the least squares difference between the Anscombe transformed corrupted image and the original image can be estimated by the number of observations. We use this information by considering an Anscombe transformed constrained model to restore the image. The advantage with respect to corresponding penalized approaches lies in the existence of a simple model for parameter estimation. We solve the constrained minimization problem by applying a primal-dual algorithm together with a projection onto the epigraph of a convex function related to the Anscombe transform. We show that this epigraphical projection can be efficiently computed by Newton's methods with an appropriate initialization. Numerical examples demonstrate the good performance of our approach, in particular, its close behaviour with respect to the $I$-divergence constrained model.

International audience; We study the local behavior of a primal-dual inexact interior point meth- ods for solving nonlinear systems arising from the solution of nonlinear optimization problems or more generally from nonlinear complementarity problems. The algo- rithm is based on the Newton method applied to a sequence of perturbed systems that follows by perturbation of the complementarity equations of the original system. In case of an exact solution of the Newton system, it has been shown that the sequence of iterates is asymptotically tangent to the central path (Armand and Benoist in Math. Program. 115:199-222, 2008). The purpose of the present paper is to extend this re- sult to an inexact solution of the Newton system. We give quite general conditions on the different parameters of the algorithm, so that this asymptotic property is satisfied. Some numerical tests are reported to illustrate our theoretical results.

A certain regularization technique for contact problems leads to a family of problems that can be solved efficiently using infinite-dimensional semismooth Newton methods, or in this case equivalently, primal-dual active set strategies. We present two procedures that use a sequence of regularized problems to obtain the solution of the original contact problem: first-order augmented Lagrangian, and path-following methods. The first strategy is based on a multiplier-update, while path-following with respect to the regularization parameter uses theoretical results about the path-value function to increase the regularization parameter appropriately. Comprehensive numerical tests investigate the performance of the proposed strategies for both a 2D as well as a 3D contact problem. http://www.sciencedirect.com/science/article/B6TYH-4K4PSP1-1/1/fde63c41201909b9bdb219e0a48dbc91

Copyright @ 2007 INFORMS The variable neighborhood search metaheuristic is applied to the primal simple plant-location problem and to a reduced dual obtained by exploiting the complementary slackness conditions. This leads to (i) heuristic resolution of (metric) instances with uniform fixed costs, up to n = 15,000 users, and m = n potential locations for facilities with an error not exceeding 0.04%; (ii) exact solution of such instances with up to m = n = 7,000; and (iii) exact solutions of instances with variable fixed costs and up to m = n = 15, 000. This work is supported by NSERC Grant 105574-02; NSERC Grant OGP205041; and partly by the Serbian Ministry of Science, Project 1583.