Optimizing a linear function over an efficient set

The problem (P) of optimizing a linear functiond ^T x over the efficient set for a multiple-objective linear program (M) is difficult because the efficient set is typically nonconvex. Given the objective function directiond and the set of domination directionsD, ifd ^T 0 for all nonzero D, then a technique for finding an optimal solution of (P) is presented in Section 2. Otherwise, given a current efficient point , if there is no adjacent efficient edge yielding an increase ind ^T x, then a cutting plane is used to obtain a multiple-objective linear program ( ) with a reduced feasible set and an efficient set . To find a better efficient point, we solve the problem (I_i) of maximizingc _i ^T x over the reduced feasible set in ( ) sequentially fori. If there is a that is an optimal solution of (I_i) for somei and , then we can choosex ⁱ as a current efficient point. Pivoting on the reduced feasible set allows us to find a better efficient point or to show that the current efficient point is optimal for (P). Two algorithms for solving (P) in a finite sequence of pivots are presented along with a numerical example.The authors would like to thank an anonymous referee, H. P. Benson, and P. L. Yu for numerous helpful comments on this paper.     

Generalized Quasi-Variational Inequalities Without Continuities

Given a nonempty set and two multifunctions , we consider the following generalized quasi-variational inequality problem associated with X, : Find such that . We prove several existence results in which the multifunction is not supposed to have any continuity property. Among others, we extend the results obtained in Ref. 1 for the case (x(X.     

Sequential gradient-restoration algorithm for optimal control problems

This paper considers the problem of minimizing a functionalI which depends on the statex(t), the controlu(t), and the parameter . Here,I is a scalar,x ann-vector,u anm-vector, and ap-vector. At the initial point, the state is prescribed. At the final point, the statex and the parameter are required to satisfyq scalar relations. Along the interval of integration, the state, the control, and the parameter are required to satisfyn scalar differential equations. Asequential algorithm composed of the alternate succession of gradient phases and restoration phases is presented. This sequential algorithm is contructed in such a way that the differential equations and boundary conditions are satisfied at the end of each iteration, that is, at the end of a complete gradient-restoration phase; hence, the value of the functional at the end of one iteration is comparable with the value of the functional at the end of any other iteration.In thegradient phase, nominal functionsx(t),u(t), satisfying all the differential equations and boundary conditions are assumed. Variations x(t), u(t), leading to varied functions (t),(t), are determined so that the value of the functional is decreased. These variations are obtained by minimizing the first-order change of the functional subject to the linearized differential equations, the linearized boundary conditions, and a quadratic constraint on the variations of the control and the parameter.Since the constraints are satisfied only to first order during the gradient phase, the functions (t),(t), may violate the differential equations and/or the boundary conditions. This being the case, a restoration phase is needed prior to starting the next gradient phase. In thisrestoration phase, the functions (t),(t), are assumed to be the nominal functions. Variations (t), (t), leading to varied functions (t),û(t), consistent with all the differential equations and boundary conditions are determined. These variations are obtained by requiring the least-square change of the control and the parameter subject to the linearized differential equations and the linearized boundary conditions. Of course, the restoration phase must be performed iteratively until the cumulative error in the differential equations and boundary conditions becomes smaller than some preselected value.If the gradient stepsize is , an order-of-magnitude analysis shows that the gradient corrections are x=O(), u=O(), =O(), while the restoration corrections are . Hence, for sufficiently small, the restoration phase preserves the descent property of the gradient phase: the functionalI decreases between any two successive iterations.Methods to determine the gradient stepsize in an optimal fashion are discussed. Examples are presented for both the fixed-final-time case and the free-final-time case. The numerical results show the rapid convergence characteristics of the sequential gradient-restoration algorithm.The portions of this paper dealing with the fixed-final-time case were presented by the senior author at the 2nd Hawaii International Conference on System Sciences, Honolulu, Hawaii, 1969. The portions of this paper dealing with the free-final-time case were presented by the senior author at the 20th International Astronautical Congress, Mar del Plata, Argentina, 1969. This research, supported by the NASA-Manned Spacecraft Center, Grant No. NGR-44-006-089, Supplement No. 1, is a condensation of the investigations presented in Refs. 1–5. The authors are indebted to Professor H. Y. Huang for helpful discussions.     

Convex programs with an additional reverse convex constraint

A method is presented for solving a class of global optimization problems of the form (P): minimizef(x), subject toxD,g(x)0, whereD is a closed convex subset ofR ⁿ andf,g are convex finite functionsR ⁿ . Under suitable stability hypotheses, it is shown that a feasible point is optimal if and only if 0=max{g(x):xD,f(x)f( )}. On the basis of this optimality criterion, the problem is reduced to a sequence of subproblemsQ _k ,k=1, 2, ..., each of which consists in maximizing the convex functiong(x) over some polyhedronS _k . The method is similar to the outer approximation method for maximizing a convex function over a compact convex set.     

Quadratic Integer Programming with Application to the Chaotic Mappings of Complete Multipartite Graphs

Let be a permutation of the vertex set V(G) of a connected graph G. Define the total relative displacement of in G by be

An existence theorem for generalized quasi-variational inequalities

In this paper, we deal with the following generalized quasi-variational inequality problem: given a closed convex subsetX ⁿ , a multifunction :X 2 ⁿ and a multifunction :X 2 ^X , find a point ( ) X × ⁿ such that We prove an existence theorem in which, in particular, the multifunction is not supposed to be upper semicontinuous.     

On characterizing the solution sets of pseudolinear programs

This paper provides several new and simple characterizations of the solution sets of pseudolinear programs. By means of the basic properties of pseudolinearity, the solution set of a pseudolinear program is characterized, for instance, by the equality that , for each feasible pointx, where is in the solution set. As a consequence, we give characterizations of both the solution set and the boundedness of the solution set of a linear fractional program.     

Book Notices

Given the minimization problem of a real-valued function let A be any algorithm of type with that converges to a local minimum . In this note, new assumptions on f(x) under which A converges linearly to x* are established. These include the ones introduced in the literature which involve the uniform convexity of f(x).     

Stability of Bounded Solutions of Differential Equations with Small Parameter in a Banach Space

For a sectorial operator A with spectrum (A) that acts in a complex Banach space B, we prove that the condition (A) i R = Ø is sufficient for the differential equation where is a small positive parameter, to have a unique bounded solution x for an arbitrary bounded function f: R B that satisfies a certain Hölder condition. We also establish that bounded solutions of these equations converge uniformly on R as 0+ to the unique bounded solution of the differential equation x(t) = Ax(t) + f(t).     

Saddle points of hamiltonian systems in convex problems of Lagrange

In Lagrange problems of the calculus of variations where the LagrangianL(x ), not necessarily differentiable, is convex jointly inx and , optimal arcs can be characterized in terms of a generalized Hamiltonian differential equation, where the HamiltonianH(x, p) is concave inx and convex inp. In this paper, the Hamiltonian system is studied in a neighborhood of a minimax saddle point ofH. It is shown under a strict concavity-convexity assumption onH that the point acts much like a saddle point in the sense of differential equations. At the same time, results are obtained for problems in which the Lagrange integral is minimized over an infinite interval. These results are motivated by questions in theoretical economics.This research was supported in part by Grant No. AFOSR-71-1994.     

Generalized Quasi-Variational Inequalities in Infinite-Dimensional Normed Spaces

In this paper, we deal with the following problem: given a real normed space E with topological dual E*, a closed convex set XE, two multifunctions :X2^X and , find such that We extend to the above problem a result established by Ricceri for the case (x)X, where in particular the multifunction is required only to satisfy the following very general assumption: each set (x) is nonempty, convex, and weakly-star compact, and for each yX–:X the set is compactly closed. Our result also gives a partial affirmative answer to a conjecture raised by Ricceri himself.     

Inertial Gradient-Like Dynamical System Controlled by a Stabilizing Term

Let H be a real Hilbert space and let be a function that we wish to minimize. For any potential and any control function which tends to zero as t+, we study the asymptotic behavior of the trajectories of the following dissipative system:

Self-bounded controlled invariant subspaces: A straightforward approach to constrained controllability

A lattice-type structure is shown to exist in a particular subset of the set of all (A, )-controlled invariants contained in and containing , whereA denotes a linear map inR ⁿ ; , are arbitrary subspaces ofR ⁿ ; andD is an arbitrary subspace ofJ, the maximum (A, )-controlled invariant contained in . In linear system theory, this property can be used for a more direct theoretical and algorithmic approach to constrained controllability and disturbance rejection problems.     

An Intersection Theorem on an Unbounded Set and Its Application to the Fair Allocation Problem

We prove the following theorem. Let m and n be any positive integers with mn, and let be a subset of the n-dimensional Euclidean space ⁿ . For each i=1, . . . , m, there is a class of subsets M _i ^j of ^Tn . Assume that for each i=1, . . . , m, that M _i ^j is nonempty and closed for all i, j, and that there exists a real number B(i, j) such that and its jth component _{xjB(i, j)} imply . Then, there exists a partition of {1, . . . , n} such that for all i and We prove this theorem based upon a generalization of a well-known theorem of Birkhoff and von Neumann. Moreover, we apply this theorem to the fair allocation problem of indivisible objects with money and obtain an existence theorem.     

Moduli of continuity of selections from nonconvex maps

We consider two continuous selection problems related to the differential inclusion F(t, x). Assuming thatF is Hölder or Lipschitz continuous with compact, not necessarily convex values, we provide estimates on the modulus of continuity of these selections.     

Multiple Wick Product Chaos Processes

Let u(x) xR ^q be a symmetric nonnegative definite function which is bounded outside of all neighborhoods of zero but which may have u(0)=. Let p _x, (·) be the density of an R ^q valued canonical normal random variable with mean x and variance and let {G _x, ; (x, )R ^q ×[0,1 ]} be the mean zero Gaussian process with covariance

New Quasi-Newton Equation and Related Methods for Unconstrained Optimization

In unconstrained optimization, the usual quasi-Newton equation is B _k+1 s _k=y _k, where y _k is the difference of the gradients at the last two iterates. In this paper, we propose a new quasi-Newton equation, , in which is based on both the function values and gradients at the last two iterates. The new equation is superior to the old equation in the sense that better approximates ² f(x _k+1)s _k than y _k. Modified quasi-Newton methods based on the new quasi-Newton equation are locally and superlinearly convergent. Extensive numerical experiments have been conducted which show that the new quasi-Newton methods are encouraging.     

Multivariate interpolation in odd-dimensional euclidean spaces using multiquadrics

Let or . Givenf: ⁿ , we establish convergence orders of interpolation where the cardinal functionx withx(j)=_0j is a linear combination of integer shifts, of a fast decaying function

Nonconvergence results for the application of least-squares estimation to Ill-posed problems

One standard approach to solvingf(x)=b is the minimization of f(x)–b² overx in , where corresponds to a parametric representation providing sufficiently good approximation to the true solutionx*. Call the minimizerx=A( ). Take = _N for a sequence { _N } of subspaces becoming dense, and so determine an approximating sequences {x _N A ( _N )}. It is shown, withf linear and one-to-one, that one need not havex _Nx* iff ^–1 is not continuous.This work was supported by the US Army Research Office under Grant No. DAAG-29-77-G-0061. The author is indebted to the late W. C. Chewning for suggesting the topic in connection with computing optimal boundary controls for the heat equation (Ref. 2).     

On the Normal Order of ϕk+1(n)/ϕk(n), where ϕk is the k-Fold Iterate of Euler's Function

Let be the j-fold iterated function of . Let and > 0 be fixed, Q be a prime, and let N _k(Q|x) denote the number of those nx for which Q . We give the asymptotics of N _k(Q|x) in the range .