Optimization of a convex program with a polynomial perturbation

We consider the problem of minimizing a convex function plus a polynomial p over a convex body K. We give an algorithm that outputs a solution x whose value is within range_K(p) of the optimum value, where range_K(p)=sup_xKp(x)−inf_xKp(x). When p depends only on a constant number of variables, the algorithm runs in time polynomial in 1/, the degree of p, the time to round K and the time to solve the convex program that results by setting p=0.     

A direct method of linearization for continuous minimax problems

We consider the problem of minimizing a nondifferentiable function that is the pointwise maximum over a compact family of continuously differentiable functions. We suppose that a certain convex approximation to the objective function can be evaluated. An iterative method is given which uses as successive search directions approximate solutions of semi-infinite quadratic programming problems calculated via a new generalized proximity algorithm. Inexact line searches ensure global convergence of the method to stationary points.This work was supported by Project No. CPBP-02.15/2.1.1.     

On the convergence of asynchronous parallel algorithm for large-scale linearly constrained minimization problem

As a synchronization parallel framework, the parallel variable transformation (PVT) algorithm is effective to solve unconstrained optimization problems. In this paper, based on the idea that a constrained optimization problem is equivalent to a differentiable unconstrained optimization problem by introducing the Fischer Function, we propose an asynchronous PVT algorithm for solving large-scale linearly constrained convex minimization problems. This new algorithm can terminate when some processor satisfies terminal condition without waiting for other processors. Meanwhile, it can enhances practical efficiency for large-scale optimization problem. Global convergence of the new algorithm is established under suitable assumptions. And in particular, the linear rate of convergence does not depend on the number of processors.     

Mathematical Properties of Optimization Problems Defined by Positively Homogeneous Functions

We consider the nonlinear programming problem

Dynamic updates of the barrier parameter in primal-dual methods for nonlinear programming

We introduce a framework in which updating rules for the barrier parameter in primal-dual interior-point methods become dynamic. The original primal-dual system is augmented to incorporate explicitly an updating function. A Newton step for the augmented system gives a primal-dual Newton step and also a step in the barrier parameter. Based on local information and a line search, the decrease of the barrier parameter is automatically adjusted. We analyze local convergence properties, report numerical experiments on a standard collection of nonlinear problems and compare our results to a state-of-the-art interior-point implementation. In many instances, the adaptive algorithm reduces the number of iterations and of function evaluations. Its design guarantees a better fit between the magnitudes of the primal-dual residual and of the barrier parameter along the iterations.     

An Algorithm of Global Optimization for Rational Functions with Rational Constraints

To solve a system of nonlinear equations, Wu wen-tsun introduced a new formative elimination method. Based on Wu's method and the theory of nonlinear programming, we here propose a global optimization algorithm for nonlinear programming with rational objective function and rational constraints. The algorithm is already programmed and the test results are satisfactory with respect to precision and reliability.     

A local convergence property of primal-dual methods for nonlinear programming

We prove a new local convergence property of some primal-dual methods for solving nonlinear optimization problems. We consider a standard interior point approach, for which the complementarity conditions of the original primal-dual system are perturbed by a parameter driven to zero during the iterations. The sequence of iterates is generated by a linearization of the perturbed system and by applying the fraction to the boundary rule to maintain strict feasibility of the iterates with respect to the nonnegativity constraints. The analysis of the rate of convergence is carried out by considering an arbitrary sequence of perturbation parameters converging to zero. We first show that, once an iterate belongs to a neighbourhood of convergence of the Newton method applied to the original system, then the whole sequence of iterates converges to the solution. In addition, if the perturbation parameters converge to zero with a rate of convergence at most superlinear, then the sequence of iterates becomes asymptotically tangent to the central trajectory in a natural way. We give an example showing that this property can be false when the perturbation parameter goes to zero quadratically.      

使用非单调线搜索正割方法解约束优化的整体收敛性

基于Powell和Yuan所建议的近似Fetcher罚函数作为函数使用单调线搜索的技术,本文提供了一类正割方法解约束优化。在合理的条件下,证明了所提供的算法的整体收敛性和收敛速率。     

A maximization method for a class of quasiconcave programs

An implementable linearized method of centers is presented for solving a class of quasiconcave programs of the form (P): maximizef ⁰(x), subject tox B andf ⁱ (x)0, for everyi{1, ...,m}, whereB is a convex polyhedral subset ofR ⁿ (Euclideann-space). Each problem function is a continuous quasiconcave function fromR ⁿ intoR ¹. Also, it is assumed that the feasible region is bounded and there existsx B such thatf _i (x) for everyi {1, ...,m}. For a broad class of continuous quasiconcave problem functions, which may be nonsmooth, it is shown that the method produces a sequence of feasible points whose limit points are optimal for Problem (P). For many programs, no line searches are required. Additionally, the method is equipped with a constraint dropping devise.The author wishes to thank a referee for suggesting the use of generalized gradients and a second referee whose detailed informative comments have enhanced the paper.This work was done while the author was in the Department of Mathematical Sciences at the University of Delaware.     

Using the KKT matrix in an augmented Lagrangian SQP method for sparse constrained optimization

The augmented Lagrangian SQP subroutine OPALQP was originally designed for small-to-medium sized constrained optimization problems in which the main calculation on each iteration, the solution of a quadratic program, involves dense, rather than sparse, matrices. In this paper, we consider some reformulations of OPALQP which are better able to take advantage of sparsity in the objective function and constraints.The modified versions of OPALQP differ from the original in using sparse data structures for the Jacobian matrix of constraints and in replacing the dense quasi-Newton estimate of the inverse Hessian of the Lagrangian by a sparse approximation to the Hessian. We consider a very simple sparse update for estimating ² L and also investigate the benefits of using exact second derivatives, noting in the latter case that safeguards are needed to ensure that a suitable search direction is obtained when ² L is not positive definite on the null space of the active constraints.The authors are grateful to John Reid and Nick Gould of the Rutherford Appleton Laboratory for a number of helpful and interesting discussions. Thanks are also due to Laurence Dixon for comments which led to the clarification of some parts of the paper.This work has been partly supported by a CAPES Research Studentship funded by the Brazilian Government.     

Simplex-inspired algorithms for solving a class of convex programming problems

We consider a class of convex programming problems whose objective function is given as a linear function plus a convex function whose arguments are linear functions of the decision variables and whose feasible region is a polytope. We show that there exists an optimal solution to this class of problems on a face of the constraint polytope of dimension not more than the number of arguments of the convex function. Based on this result, we develop a method to solve this problem that is inspired by the simplex method for linear programming. It is shown that this method terminates in a finite number of iterations in the special case that the convex function has only a single argument. We then use this insight to develop a second algorithm that solves the problem in a finite number of iterations for an arbitrary number of arguments in the convex function. A computational study illustrates the efficiency of the algorithm and suggests that the average-case performance of these algorithms is a polynomial of low order in the number of decision variables. The work of T. C. Sharkey was supported by a National Science Foundation Graduate Research Fellowship. The work of H. E. Romeijn was supported by the National Science Foundation under Grant No. DMI-0355533.     

Minimizing the area of a Pareto confidence region

A constrained optimization problem is formulated and solved in order to determine the smallest confidence region for the parameters of the Pareto distribution in a proposed family of sets. The objective function is the area of the region, whereas the constraints are related to the required confidence level. Explicit expressions for the area and confidence level of a given region are first deduced. An efficient procedure based on minimizing the corresponding Lagrangian function is then presented to solve the nonlinear programming problem. The process is valid when some of the smallest and largest observations have been discarded or censored, i.e., both single (right or left) and double censoring are allowed. The optimal Pareto confidence region is derived by simultaneously solving three (four) nonlinear equations in the right (double) censoring case. In most practical situations, Newton’s method with the balanced set as the starting point only needs a few iterations to find the global solution. In general, the reduction in area of the optimal Pareto region with respect to the balanced set is considerable if the sample size, n, is small or moderately large, which is usual in practice. This reduction is sometimes impressive when n is quite small and the censoring degree is fairly high. Two numerical examples regarding component lifetimes and fire claims are included for illustrative and comparative purposes.     

不等式约束最优化无严格互补条件下的快速收敛序列线性方程组算法

本文讨论无严格互补性的非线性不等式约束最优化问题,建立了一个新的序列线性方程组算法。算法每次迭代只需解一个线性方程组或计算一次广义梯度投影,并不要求Lagrange函数的近似Hessian阵正定。在较弱的假设下,证明了算法的整体收敛性、强收敛性、超线性收敛性及二次收敛速度。还对算法进行了有效的数值试验。     

Unification of Filled Function and Tunnelling Function in Global Optimization

In this paper,two auxiliary functions for global optimization are proposed.These two auxiliaryfunctions possess all characters of tunnelling functions and filled functions under certain general assumptions.Thus,they can be considered as the unification of filled function and tunnelling function.Moreover,the processof tunneling or filling for global optimization can be unified as the minimization of such auxiliary functions.Result of numerical experiments shows that such two auxiliary functions are effective.     

Control synthesis for discrete time systems with control and state bounds in the presence of disturbances

The problem of control in the presence of unknown but limited disturbance for a discrete-time linear system with polyhedral input and state bounds is investigated. Two problems are considered: that of reaching an assigned target set in the state space; and that of keeping the state in a given region using the available controls. In both cases, a solution is given via linear programming. A computational procedure for the control synthesis is proposed which can be implemented to obtain a feedback control.The author thanks Professor G. Leitmann for his helpful suggestions.     

Extreme optics and the search for Earth-like planets

In this paper I describe a new and exciting application of optimization technology. The problem is to design a space telescope capable of imaging Earth-like planets around nearby stars. Because of limitations inherent in the wave nature of light, the design problem is one of diffraction control so as to provide the extremely high contrast needed to image a faint planet positioned very close to its much brighter star. I will describe the mathematics behind the diffraction control problem and explain how modern optimization tools were able to provide unexpected solutions that actually changed NASA’s approach to this problem. The author was supported by a grant from the ONR (N00014-98-1-0036).     

Algorithms for a class of nondifferentiable problems

A nonlinear programming problem with nondifferentiabilities is considered. The nondifferentiabilities are due to terms of the form min(f ₁(x),...,f _n(x)), which may enter nonlinearly in the cost and the constraints. Necessary and sufficient conditions are developed. Two algorithms for solving this problem are described, and their convergence is studied. A duality framework for interpretation of the algorithms is also developed.This work was supported in part by the National Science Foundation under Grant No. ENG-74-19332 and Grant No. ECS-79-19396, in part by the U.S. Air Force under Grant AFOSR-78-3633, and in part by the Joint Services Electronics Program (U.S. Army, U.S. Navy, and U.S. Air Force) under Contract N00014-79-C-0424.     

On Smoothing l1 Exact Penalty Function for Constrained Optimization Problems

This article introduces a smoothing technique to the l₁ exact penalty function. An application of the technique yields a twice continuously differentiable penalty function and a smoothed penalty problem. Under some mild conditions, the optimal solution to the smoothed penalty problem becomes an approximate optimal solution to the original constrained optimization problem. Based on the smoothed penalty problem, we propose an algorithm to solve the constrained optimization problem. Every limit point of the sequence generated by the algorithm is an optimal solution. Several numerical examples are presented to illustrate the performance of the proposed algorithm.     

An Affine Scaling Interior Trust-Region Algorithm Combining Backtracking Line Search with Filter Technique for Nonlinear Constrained Optimization

In this article, an affine scaling interior trust-region algorithm which employs backtracking line search with filter technique is presented for solving nonlinear equality constrained programming with nonnegative constraints on variables. At current iteration, the general full affine scaling trust-region subproblem is decomposed into a pair of trust-region subproblems in vertical and horizontal subspaces, respectively. The trial step is given by the solutions of the pair of trust-region subproblems. Then, the step size is decided by backtracking line search together with filter technique. This is different from traditional trust-region methods and has the advantage of decreasing the number of times that a trust-region subproblem must be resolved in order to determine a new iteration point. Meanwhile, using filter technique instead of merit function to determine a new iteration point can avoid the difficult decisions regarding the choice of penalty parameters. Under some reasonable assumptions, the new method possesses the property of global convergence to the first-order critical point. Preliminary numerical results show the effectiveness of the proposed algorithm.     

Adaptive fuzzy backstepping control design for a class of pure-feedback switched nonlinear systems

In this paper, an adaptive fuzzy output tracking control approach is proposed for a class of single input and single output (SISO) uncertain pure-feedback switched nonlinear systems under arbitrary switchings. Fuzzy logic systems are used to identify the unknown nonlinear system. Under the framework of the backstepping control design and fuzzy adaptive control, a new adaptive fuzzy output tracking control method is developed. It is proved that the proposed control approach can guarantee that all the signals in the closed-loop system are semi-globally uniformly ultimately bounded (SGUUB) and the tracking error remains an adjustable neighborhood of the origin. A numerical example is provided to illustrate the effectiveness of the proposed approach.