Nonlinear Optimization

Numerical Stability of Path Tracing in Polyhedral Homotopy Continuation Methods

  • Sunyoung Kim
  • Masakazu Kojima
    • Categories Nonlinear Systems and Least-Squares Tags , , ,

    The reliability of polyhedral homotopy continuation methods for solving a polynomial system becomes increasingly important as the dimension of the polynomial system increases. High powers of the homotopy continuation parameter $t$ and ill-conditioned Jacobian matrices encountered in tracing of homotopy paths affect the numerical stability. We present modified homotopy functions with a new homotopy continuation … Read more

    Solving Method for a Class of Bilevel Linear Programming based on Genetic Algorithms

  • Zhong-Ping Wan
  • Guang-Min Wang
  • Xian-Jia Wang
    • Categories Linear, Cone and Semidefinite Programming, Multi-Criteria Optimization, Nonlinear Optimization Tags , ,

    The paper studies and designs an genetic algorithm (GA) of the bilevel linear programming problem (BLPP) by constructing the fitness function of the upper-level programming problem based on the definition of the feasible degree. This GA avoids the use of penalty function to deal with the constraints, by changing the randomly generated initial population into … Read more

    A Null Space Method for Solving System of Equations

  • Nie Pu-yan
    • Categories Nonlinear Optimization Tags , , , ,

    We transform the system of nonlinear equations into a nonlinear programming problem, which is solved by null space algorithms. We do not use standard least square approach. We divide the equations into two groups. One group contains the equations that are treated as equality constraints. The square of other equations is regarded as objective function. … Read more

    Sequential Penalty Quadratic Programming Filter Methods for Nonlinear Programming

  • Nie Pu-yan
    • Categories Nonlinear Optimization Tags , , , ,

    Filter approach is recently proposed by Fletcher and Leyffer in 2002 and is attached importance to. In this paper, the filter approach is used in an sequential penalty quadratic programming (S$l$QP) algorithm which is similar to that of Yuan’s. In every trial step, the step length is controlled by a trust region radius. If the … Read more

    Optimization problems with equilibrium constraints and their numerical solution

  • Michal Kočvara
  • Jiri V. Outrata
    • Categories Complementarity and Variational Inequalities, Nonlinear Optimization, Other Topics Tags

    We consider a class of optimization problems with a generalized equation among the constraints. This class covers several problem types like MPEC (Mathematical Programs with Equilibrium Constraints) and MPCC (Mathematical Programs with Complementarity Constraints). We briefly review techniques used for numerical solution of these problems: penalty methods, nonlinear programming (NLP) techniques and Implicit Programming approach … Read more

    A Local Convergence Theory of a Filter Line Search Method for Nonlinear Programming

  • Choong Ming Chin
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , , ,

    In this paper the theory of local convergence for a class of line search filter type methods for nonlinear programming is presented. The algorithm presented here is globally convergent (see Chin [4]) and the rate of convergence is two-step superlinear. The proposed algorithm solves a sequence of quadratic progrmming subproblems to obtain search directions and … Read more

    PHoM – a Polyhedral Homotopy Continuation Method for Polynomial Systems

  • Katsuki Fujisawa
  • Sunyoung Kim
  • Masakazu Kojima
  • Tomohiko Mizutani
  • Takayuki Gunji
  • Akiko Takeda
    • Categories Nonlinear Systems and Least-Squares Tags , , , ,

    PHoM is a software package in C++ for finding all isolated solutions of polynomial systems using a polyhedral homotopy continuation method. Among three modules constituting the package, the first module StartSystem constructs a family of polyhedral-linear homotopy functions, based on the polyhedral homotopy theory, from input data for a given system of polynomial equations $\f(\x) … Read more

    First- and Second-Order Methods for Semidefinite Programming

  • Renato D.C. Monteiro
    • Categories Nonlinear Optimization, Semi-definite Programming Tags , , , , , , ,

    In this paper, we survey the most recent methods that have been developed for the solution of semidefinite programs. We first concentrate on the methods that have been primarily motivated by the interior point (IP) algorithms for linear programming, putting special emphasis in the class of primal-dual path-following algorithms. We also survey methods that have … Read more

    Location and design of a competitive facility for profit maximisation

  • Emilio Carrizosa
  • Frank Plastria
    • Categories Facility Planning and Design, Nonlinear Optimization Tags , , , , ,

    A single facility has to be located in competition with fixed existing facilities of similar type. Demand is supposed to be concentrated at a finite number of points, and consumers patronise the facility to which they are attracted most. Attraction is expressed by some function of the quality of the facility and its distance to … Read more

    A DC piecewise affine model and a bundling technique in nonconvex nonsmooth minimization

  • Antonio Fuduli
  • Manlio Gaudioso
  • Giovanni Giallombardo
    • Categories Nonsmooth Optimization, Unconstrained Optimization Tags , , ,

    We introduce an algorithm to minimize a function of several variables with no convexity nor smoothness assumptions. The main peculiarity of our approach is the use of an the objective function model which is the difference of two piecewise affine convex functions. Bundling and trust region concepts are embedded into the algorithm. Convergence of the … Read more