Convergence of a Penalty Method for Mathematical Programming with Complementarity Constraints

We adapt the convergence analysis of the smoothing (Ref. 1) and regularization (Ref. 2) methods to a penalty framework for mathematical programs with complementarity constraints (MPCC); we show that the penalty framework shares convergence properties similar to those of these methods. Moreover, we give sufficient conditions for a sequence generated by the penalty framework to be attracted to a B-stationary point of the MPCC.     

Optimality conditions for nonlinear infinite programming problems

An infinite programming problem consists in minimizing a functional defined on a real Banach space under an infinite number of constraints. The main purpose of this article is to provide sufficient conditions of optimality under generalized convexity assumptions. Such conditions are necessarily satisfied when the problem possesses the property that every stationary point is a global minimizer.     

Decomposition of the convex simplex method

Rutenberg (Ref. 1) provided a decomposition method to solve the problem of minimizing a separable, nonlinear objective function with large-scale linear constraints by using the convex simplex method (Ref. 2). However, there seem to be some errors in his paper (Ref. 3). This paper will rebuild the method by using more convenient and consistent notation.     

Sequential gradient-restoration algorithm for optimal control problems with nondifferential constraints

This paper considers the numerical solution of optimal control problems involving a functionalI subject to differential constraints, nondifferential constraints, and terminal constraints. The problem is to find the statex(t), the controlu(t), and the parameter π so that the functional is minimized, while the constraints are satisfied to a predetermined accuracy. The approach taken is a sequence of two-phase processes or cycles, composed of a gradient phase and a restoration phase. The gradient phase involves a single iteration and is designed to decrease the functional, while the constraints are satisfied to first order. The restoration phase involves one or several iterations and is designed to restore the constraints to a predetermined accuracy, while the norm of the variations of the control and the parameter is minimized. The principal property of the algorithm is that it produces a sequence of feasible suboptimal solutions: the functionsx(t),u(t), π obtained at the end of each cycle satisfy the constraints to a predetermined accuracy. Therefore, the functionals of any two elements of the sequence are comparable. The stepsize of the gradient phase is determined by a one-dimensional search on the augmented functionalJ, and the stepsize of the restoration phase by a one-dimensional search on the constraint errorP. If α _g is the gradient stepsize and α _r is the restoration stepsize, the gradient corrections are ofO(α _g ) and the restoration corrections are ofO(α _r α _g ²). Therefore, for α _g sufficiently small, the restoration phase preserves the descent property of the gradient phase: the functionalÎ at the end of any complete gradient-restoration cycle is smaller than the functionalI at the beginning of the cycle. To facilitate the numerical solution on digital computers, the actual time ? is replaced by the normalized timet, defined in such a way that the extremal arc has a normalized time length Δt=1. In this way, variable-time terminal conditions are transformed into fixed-time terminal conditions. The actual time τ at which the terminal boundary is reached is regarded to be a component of the parameter π being optimized. The present general formulation differs from that of Ref. 4 because of the inclusion of the nondifferential constraints to be satisfied everywhere over the interval 0 ≤t ≤ 1. Its importance lies in that (i) many optimization problems arise directly in the form considered here, (ii) problems involving state equality constraints can be reduced to the present scheme through suitable transformations, and (iii) problems involving inequality constraints can be reduced to the present scheme through suitable transformations. The latter statement applies, for instance, to the following situations: (a) problems with bounded control, (b) problems with bounded state, (c) problems with bounded time rate of change of the state, and (d) problems where some bound is imposed on an arbitrarily prescribed function of the parameter, the control, the state, and the time rate of change of the state. Numerical examples are presented for both the fixed-final-time case and the free-final-time case. These examples demonstrate the feasibility as well as the rapidity of convergence of the technique developed in this paper.     

Minimizing the weighted number of early and tardy jobs in a stochastic single machine scheduling problem

We study a static stochastic single machine scheduling problem in which jobs have random processing times with arbitrary distributions, due dates are known with certainty, and fixed individual penalties (or weights) are imposed on both early and tardy jobs. The objective is to find an optimal sequence that minimizes the expected total weighted number of early and tardy jobs. The general problem is NP-hard to solve; however, in this paper, we develop certain conditions under which the problem is solvable exactly. An efficient heuristic is also introduced to find a candidate for the optimal sequence of the general problem. Our illustrative examples and computational results demonstrate that the heuristic performs well in identifying either optimal sequences or good candidates with low errors. Furthermore, we show that special cases of the problem studied here reduce to some classical stochastic single machine scheduling problems including the problem of minimizing the expected weighted number of early jobs and the problem of minimizing the expected weighted number of tardy jobs which are both solvable by the proposed exact or heuristic methods.     

Penalty methods for mathematical programming inE nwith general constraint sets

This paper extends the principal supporting results and the general convergence theorems for penalty methods, obtained by Fiacco and McCormick (Ref. 1) for the continuous mathematical programming problem, to the problem of minimizing a mildly regulated objective function over any nonempty subset ofE ⁿ.The constraint set need not be defined through a collection of inequalities. A general auxiliary function is defined, and the desired minimizing sequence is shown to exist, without additional assumptions (i.e., assumptions other than those invoked in the principal convergence theorem of Ref. 1). A particularly interesting consequence is the fact that a discrete (e.g., integer) programming problem can be solved by asingle unconstrained minimization of the auxiliary function.     

Enlarging the region of convergence of Newton's method for constrained optimization

In this paper, we consider Newton's method for solving the system of necessary optimality conditions of optimization problems with equality and inequality constraints. The principal drawbacks of the method are the need for a good starting point, the inability to distinguish between local maxima and local minima, and, when inequality constraints are present, the necessity to solve a quadratic programming problem at each iteration. We show that all these drawbacks can be overcome to a great extent without sacrificing the superlinear convergence rate by making use of exact differentiable penalty functions introduced by Di Pillo and Grippo (Ref. 1). We also show that there is a close relationship between the class of penalty functions of Di Pillo and Grippo and the class of Fletcher (Ref. 2), and that the region of convergence of a variation of Newton's method can be enlarged by making use of one of Fletcher's penalty functions.This work was supported by the National Science Foundation, Grant No. ENG-79-06332.     

Derivative-free methods for bound constrained mixed-integer optimization

We consider the problem of minimizing a continuously differentiable function of several variables subject to simple bound constraints where some of the variables are restricted to take integer values. We assume that the first order derivatives of the objective function can be neither calculated nor approximated explicitly. This class of mixed integer nonlinear optimization problems arises frequently in many industrial and scientific applications and this motivates the increasing interest in the study of derivative-free methods for their solution. The continuous variables are handled by a linesearch strategy whereas to tackle the discrete ones we employ a local search-type approach. We propose different algorithms which are characterized by the way the current iterate is updated and by the stationarity conditions satisfied by the limit points of the sequences they produce.     

On the uniqueness of search directions in variable-metric algorithms

Generalized variable-metric algorithms presented in Ref. 1 produce a unique search direction independently of parameters in the algorithms under several conditions. They generate a unique sequence of minimizing points for the given initial conditions if the objective function is quadratic.     

Global Convergence Analysis of Line Search Interior-Point Methods for Nonlinear Programming without Regularity Assumptions

As noted by Wächter and Biegler (Ref. 1), a number of interior-point methods for nonlinear programming based on line-search strategy may generate a sequence converging to an infeasible point. We show that, by adopting a suitable merit function, a modified primal-dual equation, and a proper line-search procedure, a class of interior-point methods of line-search type will generate a sequence such that either all the limit points of the sequence are KKT points, or one of the limit points is a Fritz John point, or one of the limit points is an infeasible point that is a stationary point minimizing a function measuring the extent of violation to the constraint system. The analysis does not depend on the regularity assumptions on the problem. Instead, it uses a set of satisfiable conditions on the algorithm implementation to derive the desired convergence property.Communicated by Z. Q. LuoThis research was partially supported by Grant R-314-000-026/042/057-112 of National University of Singapore and Singapore-MIT Alliance. We thank Professor Khoo Boo Cheong, Cochair of the High Performance Computation Program of Singapore-MIT Alliance, for his support     

On the generation of updates for quasi-Newton methods

We present a unified technique for updating approximations to Jacobian or Hessian matrices when any linear structure can be imposed. The updates are derived by variational means, where an operator-weighted Frobenius norm is used, and are finally expressed as solutions of linear equations and/or unconstrained extrema. A certain behavior of the solutions is discussed for certain perturbations of the operator and the constraints. Multiple secant relations are then considered. For the nonsparse case, an explicit family of updates is obtained including Broyden, DFP, and BFGS. For the case where some of the matrix elements are prescribed, explicit solutions are obtained if certain conditions are satisfied. When symmetry is assumed, we show, in addition, the connection with the DFP and BFGS updates.This work was partially supported by a grant from Control Data     

Convergence to a second-order point of a trust-region algorithm with a nonmonotonic penalty parameter for constrained optimization

In a recent paper (Ref. 1), the author proposed a trust-region algorithm for solving the problem of minimizing a nonlinear function subject to a set of equality constraints. The main feature of the algorithm is that the penalty parameter in the merit function can be decreased whenever it is warranted. He studied the behavior of the penalty parameter and proved several global and local convergence results. One of these results is that there exists a subsequence of the iterates generated by the algorithm that converges to a point that satisfies the first-order necessary conditions.In the current paper, we show that, for this algorithm, there exists a subsequence of iterates that converges to a point that satisfies both the first-order and the second-order necessary conditions.This research was supported by the Rice University Center for Research on Parallel Computation, Grant R31853, and the REDI Foundation.     

On the solution of affine generalized Nash equilibrium problems with shared constraints by Lemke’s method

Affine generalized Nash equilibrium problems (AGNEPs) represent a class of non-cooperative games in which players solve convex quadratic programs with a set of (linear) constraints that couple the players’ variables. The generalized Nash equilibria (GNE) associated with such games are given by solutions to a linear complementarity problem (LCP). This paper treats a large subclass of AGNEPs wherein the coupled constraints are shared by, i.e., common to, the players. Specifically, we present several avenues for computing structurally different GNE based on varying consistency requirements on the Lagrange multipliers associated with the shared constraints. Traditionally, variational equilibria (VE) have been amongst the more well-studied GNE and are characterized by a requirement that the shared constraint multipliers be identical across players. We present and analyze a modification to Lemke’s method that allows us to compute GNE that are not necessarily VE. If successful, the modified method computes a partial variational equilibrium characterized by the property that some shared constraints are imposed to have common multipliers across the players while other are not so imposed. Trajectories arising from regularizing the LCP formulations of AGNEPs are shown to converge to a particular type of GNE more general than Rosen’s normalized equilibrium that in turn includes a variational equilibrium as a special case. A third avenue for constructing alternate GNE arises from employing a novel constraint reformulation and parameterization technique. The associated parametric solution method is capable of identifying continuous manifolds of equilibria. Numerical results suggest that the modified Lemke’s method is more robust than the standard version of the method and entails only a modest increase in computational effort on the problems tested. Finally, we show that the conditions for applying the modified Lemke’s scheme are readily satisfied in a breadth of application problems drawn from communication networks, environmental pollution games, and power markets.     

Second-order necessary conditions of the Kuhn-Tucker type under new constraint qualifications

We are concerned with a nonlinear programming problem with equality and inequality constraints. We shall give second-order necessary conditions of the Kuhn-Tucker type and prove that the conditions hold under new constraint qualifications. The constraint qualifications are weaker than those given by Ben-Tal (Ref. 1).The author would like to thank Professor N. Furukawa and the referees for their many valuable comments and helpful suggestions.     

Maximum principle in the problem of time optimal response with nonsmooth constraints : PMM vol. 40, n 6, 1976, pp. 1014–1023

The problem of optimal response [1, 2] with nonsmooth (generally speaking, nonfunctional) constraints imposed on the state variables is considered. This problem is used to illustrate the method of proving the necessary conditions of optimality in the problems of optimal control with phase constraints, based on constructive approximation of the initial problem with constraints by a sequence of problems of optimal control with constraint-free state variables. The variational analysis of the approximating problems is carried out by means of a purely algebraic method involving the formulas for the incremental growth of a functional [3, 4] and the theorems of separability of convex sets is not used.Using a passage to the limit, the convergence of the approximating problems to the initial problem with constraints is proved, and for general assumptions the necessary conditions of optimality resembling the Pontriagin maximum principle [1] are derived for the generalized solutions of the initial problem. The conditions of transversality are expressed, in the case of nonsmooth (nonfunctional) constraints by a novel concept of a cone conjugate to an arbitrary closed set of a finite-dimensional space. The concept generalizes the usual notions of the normal and the normal cone for the cases of smooth and convex manifolds.     

Tikhonov Regularization Methods for Variational Inequality Problems

Motivated by the work of Facchinei and Kanzow (Ref. 1) on regularization methods for the nonlinear complementarity problem and the work of Ravindran and Gowda (Ref. 2) for the box variational inequality problem, we study regularization methods for the general variational inequality problem. A sufficient condition is given which guarantees that the union of the solution sets of the regularized problems is nonempty and bounded. It is shown that solutions of the regularized problems form a minimizing sequence of the D-gap function under a mild condition.     

Sequential conjugate-gradient-restoration algorithm for optimal control problems. Part 2. Examples

In Ref. 1, Heideman and Levy developed the sequential conjugate-gradient-restoration algorithm for minimizing a functional subject to differential constraints and terminal constraints. In this report, several numerical examples are presented, some pertaining to a quadratic functional subject to linear constraints and some pertaining to a nonquadratic functional subject to nonlinear constraints. These examples demonstrate the feasibility as well as the rapid convergence characteristic of the sequential conjugate-gradient-restoration algorithm.     

非线性互补约束优化问题的可行性条件

本文研究了非线性互补约束优化问题的可行性条件，其中约束条件除互补问题外还包括第一水平(设计)变量和第二水平(状态)变量同时出现的其它非线性约束，它是线性互补约束优化问题的可行性条件的推广。     

Coordinate Transformations and Derivation of Open-Loop Nash Equilibria

Leitmann (Ref. 1) introduced coordinate transformations to derive global optima of a class of dynamic optimization problems. We present applications of this method to derive open-loop Nash equilibria for finite-time horizon differential games. The method of coordinate transformations is especially useful in cases where the original game does not satisfy the global curvature conditions normally imposed in sufficient optimality conditions.     

Inexact proximal Newton methods for self-concordant functions

We analyze the proximal Newton method for minimizing a sum of a self-concordant function and a convex function with an inexpensive proximal operator. We present new results on the global and local convergence of the method when inexact search directions are used. The method is illustrated with an application to L1-regularized covariance selection, in which prior constraints on the sparsity pattern of the inverse covariance matrix are imposed. In the numerical experiments the proximal Newton steps are computed by an accelerated proximal gradient method, and multifrontal algorithms for positive definite matrices with chordal sparsity patterns are used to evaluate gradients and matrix-vector products with the Hessian of the smooth component of the objective.