Second-order negative-curvature methods for box-constrained and general constrained optimization

A Nonlinear Programming algorithm that converges to second-order stationary points is introduced in this paper. The main tool is a second-order negative-curvature method for box-constrained minimization of a certain class of functions that do not possess continuous second derivatives. This method is used to define an Augmented Lagrangian algorithm of PHR (Powell-Hestenes-Rockafellar) type. Convergence proofs under weak constraint qualifications are given. Numerical examples showing that the new method converges to second-order stationary points in situations in which first-order methods fail are exhibited.

Outer Trust-Region Method for Constrained Optimization

Given an algorithm A for solving some mathematical problem based on the iterative solution of simpler subproblems, an outer trust-region (OTR) modification of A is the result of adding a trust-region constraint to each subproblem. The trust-region size is adaptively updated according to the behavior of crucial variables. The new subproblems should not be more complex than the original ones, and the convergence properties of the OTR algorithm should be the same as those of Algorithm A. In the present work, the OTR approach is exploited in connection with the ""greediness phenomenon"" of nonlinear programming. Convergence results for an OTR version of an augmented Lagrangian method for nonconvex constrained optimization are proved, and numerical experiments are presented.

Constrained pole placement for linear systems using low-order output feedback controllers

The paper presents a simple approach to the problem of designing low-order output feedback controllers for linear continuous systems. The controller can place all of the closed-loop poles within a circle, C(- , 1/ β) , with centre at - and radius of 1/ β in the left half s-plane. The design method is based on transformation of the original system and then applying the bounded-real-lemma to the transformed system. It is shown that subjected to the solvability of an algebraic Riccati equation (ARE), output feedback controllers can then be systematically derived. Furthermore, the order of the controller is low and equals only the number of the open-loop poles lying outside the circle. A step-by-step design algorithm is given. Numerical examples are given to illustrate the design method.

Cutting angle method - a tool for constrained global optimization

Cutting angle method (CAM) is a deterministic global optimization technique applicable to Lipschitz functions f: Rn → R. The method builds a sequence of piecewise linear lower approximations to the objective function f. The sequence of solutions to these relaxed problems converges to the global minimum of f. This article adapts CAM to the case of linear constraints on the feasible domain. We show how the relaxed problems are modified, and how the numerical efficiency of solving these problems can be preserved. A number of numerical experiments confirms the improved numerical efficiency.

Polyhedral combinatorics of the cardinality constrained quadratic knapsack problem and the quadratic selective travelling salesman problem

This paper considers the Cardinality Constrained Quadratic Knapsack Problem (QKP) and the Quadratic Selective Travelling Salesman Problem (QSTSP). The QKP is a generalization of the Knapsack Problem and the QSTSP is a generalization of the Travelling Salesman Problem. Thus, both problems are NP hard. The QSTSP and the QKP can be solved using branch-and-cut methods. Good bounds can be obtained if strong constraints are used. Hence it is important to identify strong or even facet-defining constraints. This paper studies the polyhedral combinatorics of the QSTSP and the QKP, i.e. amongst others we identify facet-defining constraints for the QSTSP and the QKP, and provide mathematical proofs that they do indeed define facets.

New cutting-planes for the time-and/or precedence-constrained ATSP and directed VRP

In this paper, we introduce five classes of new valid cutting planes for the precedence-constrained (PC) and/or time-window-constrained (TW) Asymmetric Travelling Salesman Problems (ATSPs) and directed Vehicle Routing Problems (VRPs). We show that all five classes of new inequalities are facet-defining for the directed VRP-TW, under reasonable conditions and the assumption that vehicles are identical. Similar proofs can be developed for the VRP-PC. As ATSP-TW and PC-ATSP can be formulated as directed identical-vehicle VRP-TW and PC-VRP, respectively, this provides a link to study the polyhedral combinatorics for the ATSP-TW and PC-ATSP. The first four classes of these new cutting planes are cycle-breaking inequalities that are lifted from the well-known D^-_k and D⁺_k inequalities (see Grötschel and Padberg in Polyhedral theory. The traveling salesman problem: a guided tour of combinatorial optimization, Wiley, New York, 1985). The last class of new cutting planes, the TW ₂ inequalities, are infeasible-path elimination inequalities. Separation of these constraints will also be discussed. We also present prelimanry numerical results to demonstrate the strengh of these new cutting planes.

Determination of structurally constrained controllors

This paper reports on determination of structurally constrained controllers for linear uncertain time-invariant systems from state controllers. It is shown that practical structures such as output and decentralized controllers may be derived from state feedback controllers. A previously studied load frequency control of a two-area interconnected power system is considered to illustrate the proposed approach.