Convergence of a strong variational algorithm for relaxed controls involving a class of hyperbolic systems

In this paper, we consider a class of optimal control problems involving linear hyperbolic partial differential equations with Darboux boundary conditions. A strong variational algorithm has been obtained for solving this class of optimal control problems in a previous paper by the third and the first authors. It was also shown that anyL accumulation points of control sequences generated by the algorithm satisfy a necessary condition for optimality. Since such accumulation points need not exist, it is shown in this paper that the control sequences generated by the algorithm always have accumulation points in the sense of control measure, and these accumulation points satisfy a necessary condition for optimality for the corresponding relaxed control problems.This work was partially supported by the Australian Research Grant Committee, and was done during the period when Z. S. Wu and K. G. Choo were Honorary Visiting Fellows in the School of Mathematics at the University of New South Wales, Australia.     

Convergence of a feasible directions algorithm for relaxed controls in time-lag systems

In this paper, we consider a class of time-lag optimal control problems involving control and terminal inequality constraints. A feasible direction algorithm has been obtained by Teo, Wong, and Clements for solving this class of optimal control problems. It was shown that anyL accumulation points of the sequence of controls generated by the algorithm satisfy a necessary condition for optimality. However, suchL accumulation points need not exist. The aim of this paper is to prove a convergence result, which ensures that the sequence of controls generated by the algorithm always has accumulation points in the sense of control measure, and these accumulation points satisfy a necessary condition for optimality for the corresponding relaxed problem.This work was done when the first author was on sabbatical leave at the School of Mathematics, University of New South Wales, Australia.     

An exact penalty function algorithm for optimal control problems with control and terminal equality constraints,part 2

In Part 1 of this paper, implementable and conceptual versions of an algorithm for optimal control problems with control constraints and terminal equality constraints were presented. It was shown that anyL accumulation points of control sequences generated by the algorithms satisfy necessary conditions of optimality. Since such accumulation points need not exist, it is shown in this paper that control sequences generated by the algorithms always have accumulation points in the sense of control measure, and these accumulation points satisfy optimality conditions for the corresponding relaxed control problem.This work was supported by the United Kingdom Science Research Council, by the US Army Research Office, Contract No. DAA-29-73-C-0025, and by the National Science Foundation, Grant No. ENG-73-08214-A01.     

First-order strong variation algorithm for optimal control problems involving hyperbolic systems

This paper considers an optimal control problem involving linear, hyperbolic partial differential equations. A first-order strong variational technique is used to obtain an algorithm for solving the optimal control problem iteratively. It is shown that the accumulation points of the sequence of controls generated by the algorithm (if they exist) satisfy a necessary condition for optimality.     

A conditional gradient method for an optimal control problem involving a class of nonlinear second-order hyperbolic partial differential equations

The aim of this paper is to consider an optimal control problem involving a class of nonlinear hyperbolic partial differential equations. A conditional gradient method is used to obtain an algorithm for solving the optimal control problem iteratively. It is then shown that any accumulation point of the sequence of controls generated by the algorithm (if it exists) satisfies a necessary condition for optimality.     

Mixed Frank–Wolfe Penalty Method with Applications to Nonconvex Optimal Control Problems

We consider a general optimization problem which is an abstract formulation of a broad class of state-constrained optimal control problems in relaxed form. We describe a generalized mixed Frank–Wolfe penalty method for solving the problem and prove that, under appropriate assumptions, accumulation points of sequences constructed by this method satisfy the necessary conditions for optimality. The method is then applied to relaxed optimal control problems involving lumped as well as distributed parameter systems. Numerical examples are given.     

An implementable algorithm for the optimal design centering,tolerancing, and tuning problem

An implementable master algorithm for solving optimal design centering, tolerancing, and tuning problems is presented. This master algorithm decomposes the original nondifferentiable optimization problem into a sequence of ordinary nonlinear programming problems. The master algorithm generates sequences with accumulation points that are feasible and satisfy a new optimality condition, which is shown to be stronger than the one previously used for these problems.This research was sponsored by the National Science Foundation (RANN), Grant No. ENV-76-04264, and by the Joint Services Electronic Program, Contract No. F44620-76-C-0100.     

Necessary and sufficient second order optimality conditions for multiobjective problems with C1 data

In this paper, we obtain necessary and sufficient second order optimality conditions for multiobjective problems using second order directional derivatives. We propose the notion of second order KT-pseudoinvex problems and we prove that this class of problems has the following property: a problem is second order KT-pseudoinvex if and only if all its points that satisfy the second order necessary optimality condition are weakly efficient. Also we obtain second order sufficient conditions for efficiency.     

Trust region affine scaling algorithms for linearly constrained convex and concave programs

We study a trust region affine scaling algorithm for solving the linearly constrained convex or concave programming problem. Under primal nondegeneracy assumption, we prove that every accumulation point of the sequence generated by the algorithm satisfies the first order necessary condition for optimality of the problem. For a special class of convex or concave functions satisfying a certain invariance condition on their Hessians, it is shown that the sequences of iterates and objective function values generated by the algorithm convergeR-linearly andQ-linearly, respectively. Moreover, under primal nondegeneracy and for this class of objective functions, it is shown that the limit point of the sequence of iterates satisfies the first and second order necessary conditions for optimality of the problem. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.The work of these authors was based on research supported by the National Science Foundation under grant INT-9600343 and the Office of Naval Research under grants N00014-93-1-0234 and N00014-94-1-0340.     

Sufficient Optimality Conditions for Optimal Control Problems with State Constraints

It is well-known in optimal control theory that the maximum principle, in general, furnishes only necessary optimality conditions for an admissible process to be an optimal one. It is also well-known that if a process satisfies the maximum principle in a problem with convex data, the maximum principle turns to be likewise a sufficient condition. Here an invexity type condition for state constrained optimal control problems is defined and shown to be a sufficient optimality condition. Further, it is demonstrated that all optimal control problems where all extremal processes are optimal necessarily obey this invexity condition. Thus optimal control problems which satisfy such a condition constitute the most general class of problems where the maximum principle becomes automatically a set of sufficient optimality conditions.     

Convergence bounds for nonlinear programming algorithms

Bounds on convergence are given for a general class of nonlinear programming algorithms. Methods in this class generate at each interation both constraint multipliers and approximate solutions such that, under certain specified assumptions, accumulation points of the multiplier and solution sequences satisfy the Fritz John or the Kuhn—Tucker optimality conditions. Under stronger assumptions, convergence bounds are derived for the sequences of approximate solution, multiplier and objective function values. The theory is applied to an interior—exterior penalty function algorithm modified to allow for inexact subproblem solutions. An entirely new convergence bound in terms of the square root of the penalty controlling parameter is given for this algorithm.     

On an optimal control problem involving first order hyperbolic systems with boundary controls

In this paper, we consider an optimal control problem involving a class of first order hyperbolic systems with boundary controls. A computational algorithm which generates minimizing sequences of controls is devised and the convergence properties of the algorithm are investigated. Moreover, a necessary and sufficient condition for optimality is derived and a result on the existence of optimal controls is obtained.     

一类变结构动态系统的非光滑最优性条件

研究了一类事件驱动的变结构动态系统的非光滑最优性条件. 通过引入一个新的时间变量, 将变结构动态系统的最优性问题转化为古典动态系统的最优性问题. 基于广义微分和古典动态系统的最优性理论, 得到了该系统的Frechet上微分形式的必要性条件, 推广了已有文献的相关结论. 结果表明, 在系统的连续运行过程中, 控制变量、协态变量和状态变量满足最小值原理和协态方程. 在系统的运行模型发生改变时, 协态变量产生一定的跳跃, 哈密尔顿函数连续. 最后通过一个算例说明了该结论的有效性.     

Rates of convergence for a method of centers algorithm

Convergence of a method of centers algorithm for solving nonlinear programming problems is considered. The algorithm is defined so that the subproblems that must be solved during its execution may be solved by finite-step procedures. Conditions are given under which the algorithm generates sequences of feasible points and constraint multiplier vectors that have accumulation points satisfying the Fritz John or the Kuhn-Tucker optimality conditions. Under stronger assumptions, linear convergence rates are established for the sequences of objective function, constraint function, feasible point, and multiplier values.This work was supported in part by the National Aeronautics and Space Administration, Predoctoral Traineeship No. NsG(T)-117, and by the National Science Foundation, Grants No. GP-25081 and No. GK-32710.The author wishes to thank Donald M. Topkis for his valuable criticism of an earlier version of this paper and a referee for his helpful comments.     

An Optimization Problem with a Separable Non-Convex Objective Function and a Linear Constraint

For a class of global optimization (maximization) problems, with a separable non-concave objective function and a linear constraint a computationally efficient heuristic has been developed.The concave relaxation of a global optimization problem is introduced. An algorithm for solving this problem to optimality is presented. The optimal solution of the relaxation problem is shown to provide an upper bound for the optimal value of the objective function of the original global optimization problem. An easily checked sufficient optimality condition is formulated under which the optimal solution of concave relaxation problem is optimal for the corresponding non-concave problem. An heuristic algorithm for solving the considered global optimization problem is developed.The considered global optimization problem models a wide class of optimal distribution of a unidimensional resource over subsystems to provide maximum total output in a multicomponent systems.In the presented computational experiments the developed heuristic algorithm generated solutions, which either met optimality conditions or had objective function values with a negligible deviation from optimality (less than 1/10 of a percent over entire range of problems tested).     

Optimality conditions with state constraints for semilinear systems determined by operator valued measures

In this paper we develop the necessary conditions of optimality for a class of distributed parameter systems (partial differential equations) determined by operator valued measures and controlled by vector measures. Based on some recent results on existence of optimal controls from the space of vector measures, we develop necessary conditions of optimality for a class of control problems. The main results are the necessary conditions of optimality for problems without state constraints and those with state constraints. Also, a conceptual algorithm along with a brief discussion of its convergence is presented.     

A tutorial on the deterministic Impulse Control Maximum Principle: Necessary and sufficient optimality conditions

This paper considers a class of optimal control problems that allows jumps in the state variable. We present the necessary optimality conditions of the Impulse Control Maximum Principle based on the current value formulation. By reviewing the existing impulse control models in the literature, we point out that meaningful problems do not satisfy the sufficiency conditions. In particular, such problems either have a concave cost function, contain a fixed cost, or have a control-state interaction, which have in common that they each violate the concavity hypotheses used in the sufficiency theorem. The implication is that the corresponding problem in principle has multiple solutions that satisfy the necessary optimality conditions. Moreover, we argue that problems with fixed cost do not satisfy the conditions under which the necessary optimality conditions can be applied. However, we design a transformation, which ensures that the application of the Impulse Control Maximum Principle still provides the optimal solution. Finally, we show for the first time that for some existing models in the literature no optimal solution exists.     

Global optimality condition and fixed point continuation algorithm for non-Lipschitz ?_p regularized matrix minimization

Regularized minimization problems with nonconvex, nonsmooth, even non-Lipschitz penalty functions have attracted much attention in recent years, owing to their wide applications in statistics, control,system identification and machine learning. In this paper, the non-Lipschitz ?_p(0 p 1) regularized matrix minimization problem is studied. A global necessary optimality condition for this non-Lipschitz optimization problem is firstly obtained, specifically, the global optimal solutions for the problem are fixed points of the so-called p-thresholding operator which is matrix-valued and set-valued. Then a fixed point iterative scheme for the non-Lipschitz model is proposed, and the convergence analysis is also addressed in detail. Moreover,some acceleration techniques are adopted to improve the performance of this algorithm. The effectiveness of the proposed p-thresholding fixed point continuation(p-FPC) algorithm is demonstrated by numerical experiments on randomly generated and real matrix completion problems.     

Global optimality condition and fixed point continuation algorithm for non-Lipschitz ℓ<Subscript><Emphasis Type="Italic">p</Emphasis></Subscript> regularized matrix minimization

Regularized minimization problems with nonconvex, nonsmooth, even non-Lipschitz penalty functions have attracted much attention in recent years, owing to their wide applications in statistics, control, system identification and machine learning. In this paper, the non-Lipschitz ? _p (0 < p < 1) regularized matrix minimization problem is studied. A global necessary optimality condition for this non-Lipschitz optimization problem is firstly obtained, specifically, the global optimal solutions for the problem are fixed points of the so-called p-thresholding operator which is matrix-valued and set-valued. Then a fixed point iterative scheme for the non-Lipschitz model is proposed, and the convergence analysis is also addressed in detail. Moreover, some acceleration techniques are adopted to improve the performance of this algorithm. The effectiveness of the proposed p-thresholding fixed point continuation (p-FPC) algorithm is demonstrated by numerical experiments on randomly generated and real matrix completion problems.