Novel approach to accelerating Newton's method for sup-norm optimization arising inH ∞-control

We present algorithms for solving general sup-norm minimization problems over spaces of analytic functions, such as those arising inH control. We also give an analysis and some theory of these algorithms. Part of this is specific to analytic optimization, while part holds for general sup-norm optimization. In particular, we are proposing a type of Newton-type algorithm which actually uses very high-order terms. The novel feature is that higher-order terms can be chosen in many ways while still maintaining a second-order convergence rate. Then, a clever choice of higher-order terms greatly reduces computation time. Conceivably this technique can be modified to accelerate Newton algorithms in some other circumstances. Estimates of order of convergence as well as results of numerical tests are also presented.This work was partially supported by the Air Force Office of Scientific Research and the National Science Foundation.     

Generalized γ-Valid Cut Procedure for Concave Minimization

The concept of a -valid cutting plane has been used in many types of algorithms for solving concave minimization problems. Unfortunately, the procedures proposed to date for constructing these cuts are valid only under certain assumptions that often may not hold in practice. Chief among these is the requirement that the feasible region of the concave minimization problem in question have full dimension, and that the objective function of this problem be concave rather than quasiconcave. In this article, we propose, validate, and show how to implement a more general -valid cutting plane procedure which eliminates these restrictions.     

Solving a class of multiplicative programming problems via c-programming

In this note we show that many classes of global optimization problems can be treated most satisfactorily by classical optimization theory and conventional algorithms. We focus on the class of problems involving the minimization of the product of several convex functions on a convex set which was studied recently by Kunoet al. [3]. It is shown that these problems are typical composite concave programming problems and thus can be handled elegantly by c-programming [4]–[8] and its techniques.     

ℓ1-Minimization with Magnitude Constraints in the Frequency Domain

In this paper, we study the -optimal control problem with additional constraints on the magnitude of the closed-loop frequency response. In particular, we study the case of magnitude constraints at fixed frequency points (a finite number of such constraints can be used to approximate an -norm constraint). In previous work, we have shown that the primal-dual formulation for this problem has no duality gap and both primal and dual problems are equivalent to convex, possibly infinite-dimensional, optimization problems with LMI constraints. Here, we study the effect of approximating the convex magnitude constraints with a finite number of linear constraints and provide a bound on the accuracy of the approximation. The resulting problems are linear programs. In the one-block case, both primal and dual programs are semi-infinite dimensional. The optimal cost can be approximated, arbitrarily well from above and within any predefined accuracy from below, by the solutions of finite-dimensional linear programs. In the multiblock case, the approximate LP problem (as well as the exact LMI problem) is infinite-dimensional in both the variables and the constraints. We show that the standard finite-dimensional approximation method, based on approximating the dual linear programming problem by sequences of finite-support problems, may fail to converge to the optimal cost of the infinite-dimensional problem.     

The complementary convex structure in global optimization

We show the importance of exploiting the complementary convex structure for efficiently solving a wide class of specially structured nonconvex global optimization problems. Roughly speaking, a specific feature of these problems is that their nonconvex nucleus can be transformed into a complementary convex structure which can then be shifted to a subspace of much lower dimension than the original underlying space. This approach leads to quite efficient algorithms for many problems of practical interest, including linear and convex multiplicative programming problems, concave minimization problems with few nonlinear variables, bilevel linear optimization problems, etc...     

Properties and Solution Methods for Large Location—Allocation Problems

Location-allocation with l _p distances is studied. It is shown that this structure can be expressed as a concave minimization programming problem. Since concave minimization algorithms are not yet well developed, five solution methods are developed which utilize the special properties of the location-allocation problem. Using the rectilinear distance measure, two of these algorithms achieved optimal solutions in all 102 test problems for which solutions were known. The algorithms can be applied to much larger problems than any existing exact methods.     

Parallel computing in nonconvex programming

In this paper, we are concerned with the development of parallel algorithms for solving some classes of nonconvex optimization problems. We present an introductory survey of parallel algorithms that have been used to solve structured problems (partially separable, and large-scale block structured problems), and algorithms based on parallel local searches for solving general nonconvex problems. Indefinite quadratic programming posynomial optimization, and the general global concave minimization problem can be solved using these approaches. In addition, for the minimum concave cost network flow problem, we are going to present new parallel search algorithms for large-scale problems. Computational results of an efficient implementation on a multi-transputer system will be presented.     

H∞-Controllers for Time-Delay Systems Using Linear Matrix Inequalities

In this paper, H -control design is developed for nominally linear systems with input as well as state delays. Both stability and H -norm bound conditions are established for asymptotically stable controlled systems. Necessary and sufficient conditions for feedback control synthesis are established first by using two forms; the first has one term representing pure state feedback, and the second has two terms comprising pure state feedback plus delayed state feedback. Then, the corresponding synthesis conditions for the cases of static-output feedback and observer-based feedback controllers are developed. The results are cast conveniently into a linear matrix inequality (LMI) framework, which can be solved numerically by efficient interior-point methods. With the aid of the LMI control toolbox software, the theoretical work is illustrated by computer simulation of numerous examples.     

A branch-and-reduce approach to global optimization

This paper presents valid inequalities and range contraction techniques that can be used to reduce the size of the search space of global optimization problems. To demonstrate the algorithmic usefulness of these techniques, we incorporate them within the branch-and-bound framework. This results in a branch-and-reduce global optimization algorithm. A detailed discussion of the algorithm components and theoretical properties are provided. Specialized algorithms for polynomial and multiplicative programs are developed. Extensive computational results are presented for engineering design problems, standard global optimization test problems, univariate polynomial programs, linear multiplicative programs, mixed-integer nonlinear programs and concave quadratic programs. For the problems solved, the computer implementation of the proposed algorithm provides very accurate solutions in modest computational time.     

How to Extend the Concept of Convexity Cuts to Derive Deeper Cutting Planes

A new type of cutting plane, termed a decomposition cut, is introduced that can be constructed under the same assumptions as the well-known convexity cut. Therefore it can be applied in algorithms (e.g. cutting plane, branch-and-cut) for various problems of global optimization, such as concave minimization, bilinear programming, reverse-convex programming, and integer programming. In computational tests with cutting plane algorithms for concave minimization, decomposition cuts were shown to be superior to convexity cuts.