Two Error Bounds for Constrained Optimization Problems and Their Applications

This paper presents a global error bound for the projected gradient and a local error bound for the distance from a feasible solution to the optimal solution set of a nonlinear programming problem by using some characteristic quantities such as value function, trust region radius etc., which are appeared in the trust region method. As applications of these error bounds, we obtain sufficient conditions under which a sequence of feasible solutions converges to a stationary point or to an optimal solution, respectively, and a necessary and sufficient condition under which a sequence of feasible solutions converges to a Kuhn–Tucker point. Other applications involve finite termination of a sequence of feasible solutions. For general optimization problems, when the optimal solution set is generalized non-degenerate or gives generalized weak sharp minima, we give a necessary and sufficient condition for a sequence of feasible solutions to terminate finitely at a Kuhn–Tucker point, and a  sufficient condition which guarantees that a sequence of feasible solutions terminates finitely at a stationary point. This research was supported by the National Natural Science Foundation of China (10571106) and CityU Strategic Research Grant.     

The exact condition of the B-spline basis may be hard to determine

The author's conjecture concerning the knot sequence whose associated B-spline sequence has maximum max-norm condition number is disproved. Related condition numbers are explored and the corresponding conjecture concerning the “worst” knot sequence for them is further supported by numerical results.     

A test for legitimate decks

Bondy and Hemminger (Graph reconstruction—a survey, J. Graph Theory 1 (1977) 227–268) give three necessary conditions namely subgraph condition, degree sequence condition and symmetric array condition (of Randic) for Legitimate decks. We have strengthened the degree sequence condition (SDSC) and extended the symmetric array condition (ESAC). We prove that both these are necessary conditions for legitimate decks and ESAC implies SDSC and symmetric array condition. ESAC gives a graph G¹ which has the same degree sequence as the prospective graph determined by the deck and the point deletions of G¹ have the same degree sequence as the given cards. Examples of illegitimate decks satisfying ESAC, legitimate decks giving G¹ with point deletions different from the given deck, deck giving more than one (non isomorphic) G¹ etc. are given. We develop this ESAC to a test to determine whether a deck is legitimate or not. Also we point out how the failure of reconstruction conjecture (if it is so) for (p?1)-point graphs can hamper the characterization of legitimate decks of p-point graphs. We extend these results to colored graphs and digraphs also.     

Interpolating sequences for H∞ in the ball

We give a sufficient condition for a sequence of points in the unit ball of ℂⁿ to be an interpolating sequence for H^∞. This result generalizes Carleson's interpolation theorem in one complex variable, but an example shows that the condition is not necessary when n≥1.     

G-frames and g-frame sequences in Hilbert spaces

In this paper, we first determine the relations among the best bounds A and B of the g-frame, the g-frame operator S and the pre-frame operator Q and give a necessary and sufficient condition for a g-frame with bounds A and B in a complex Hilbert space. We also introduce the definition of a g-frame sequence and obtain a necessary and sufficient condition for a g-frame sequence with bounds A and B in a complex Hilbert space. Lastly, we consider the stability of a g-frame sequence for a complex Hilbert space under perturbation.     

Measure free martingales

We give a necessary and sufficient condition on a sequence of functions on a set Ω under which there is a measure on Ω which renders the given sequence of functions a martingale. Further such a measure is unique if we impose a natural maximum entropy condition on the conditional probabilities.     

On local convergence of sequential quadratically-constrained quadratic-programming type methods,with an extension to variational problems

We consider the class of quadratically-constrained quadratic-programming methods in the framework extended from optimization to more general variational problems. Previously, in the optimization case, Anitescu (SIAM J. Optim. 12, 949–978, 2002) showed superlinear convergence of the primal sequence under the Mangasarian-Fromovitz constraint qualification and the quadratic growth condition. Quadratic convergence of the primal-dual sequence was established by Fukushima, Luo and Tseng (SIAM J. Optim. 13, 1098–1119, 2003) under the assumption of convexity, the Slater constraint qualification, and a strong second-order sufficient condition. We obtain a new local convergence result, which complements the above (it is neither stronger nor weaker): we prove primal-dual quadratic convergence under the linear independence constraint qualification, strict complementarity, and a second-order sufficiency condition. Additionally, our results apply to variational problems beyond the optimization case. Finally, we provide a necessary and sufficient condition for superlinear convergence of the primal sequence under a Dennis-Moré type condition. Research of the second author is partially supported by CNPq Grants 300734/95-6 and 471780/2003-0, by PRONEX–Optimization, and by FAPERJ.     

Score sequences of oriented graphs

We extend Landau's concept of the score structure of a tournament to that of the score sequence of an oriented graph, and give a condition for an arbitrary integer sequence to be a score sequence. The proof is by construction of a specific oriented graph Δ(S) with given score sequence S. It is shown that Δ(S) is transitive and has the minimum number of arcs among the oriented graphs with score sequence S.     

A Linearization Method for Nondegenerate Variational Conditions

We employ recent results about constraint nondegeneracy in variational conditions to design and justify a linearization algorithm for solving such problems. The algorithm solves a sequence of affine variational inequalities, but the variational condition itself need not be a variational inequality: that is, its underlying set need not be convex. However, that set must be given by systems of differentiable nonlinear equations with additional polyhedral constraints. We show that if the variational condition has a solution satisfying nondegeneracy and a standard regularity condition, and if the linearization algorithm is started sufficiently close to that solution, the algorithm will produce a well defined sequence that converges Q-superlinearly to the solution.     

Distributional chaos in a sequence

In this paper we prove a sufficient condition for the continuous map of a compact metric space for being distributively chaotic in a sequence. As an application, it is proved that a continuous map of an interval is chaotic in the Li–Yorke sense if and only if it is distributively chaotic in a sequence.     

一类一维的辐射流体力学方程组激波的存在性

该文主要讨论一维空间中一类辐射流体力学方程组的激波. 由Rankine-Hugoniot条件及熵条件得此问题可表述为关于辐射流体力学方程组带自由边界的初边值问题. 首先通过变量代换, 将其自由边界转换为固定边界, 然后研究关于此非线性方程组的一个初边值问题解的存在唯一性. 为此先构造了此问题的一个近似解, 然后分别通过Picard迭代与Newton迭代对此非线性问题构造近似解序列. 通过一系列估计与紧性理论得到此近似解序列的收敛性, 其极限即为原辐射热力学方程组的一个激波.     

度量空间上具有变系数的收缩条件的两个集值映射的公共不动点

在完备的度量空间上利用满足具有某种变系数的收缩条件或φ-收缩条件的两个集值映射构造了一个收敛序列,然后证明了该序列的唯一极限就是两个映射的公共不动点并给出了映射族存在唯一公共不动点的充分条件,同时给出了几个特殊结果.所得结果推广和改进了一些已有的结论.     

NA序列部分和的矩完全收敛性

讨论了NA序列部分和的矩完全收敛性,在一定条件下获得了NA序列矩完全收敛的充要条件,显示了矩完全收敛和矩条件之间的关系,将独立同分布随机变量序列矩完全收敛的结果推广到NA序列,得到了与独立随机变量序列情形类似的结果.     

A heuristic algorithm for nonlinear programming

In this paper, a heuristic algorithm for nonlinear programming is presented. The algorithm uses two search directions, and the Hessian of the Lagrangian function is approximated with the BFGS secant update. We show that the sequence of iterates convergeq-superlinearly if the sequence of approximating matrices satisfies a particular condition. Numerical results are presented.     

A condition under which slow oscillation of a sequence follows from Cesàro summability of its generator sequence

In this paper we retrieve slow oscillation of a real sequence from Cesàro summability of its generator sequence under some one-sided condition.     

New Condition Characterizing the Solutions of Variational Inequality Problems

This paper is devoted to the study of a new necessary condition in variational inequality problems: approximated gradient projection (AGP). A feasible point satisfies such condition if it is the limit of a sequence of the approximated solutions of approximations of the variational problem. This condition comes from optimization where the error in the approximated solution is measured by the projected gradient onto the approximated feasible set, which is obtained from a linearization of the constraints with slack variables to make the current point feasible. We state the AGP condition for variational inequality problems and show that it is necessary for a point being a solution even without constraint qualifications (e.g., Abadie’s). Moreover, the AGP condition is sufficient in convex variational inequalities. Sufficiency also holds for variational inequalities involving maximal monotone operators subject to the boundedness of the vectors in the image of the operator (playing the role of the gradients). Since AGP is a condition verified by a sequence, it is particularly interesting for iterative methods. Research of R. Gárciga Otero was partially supported by CNPq, FAPERJ/Cientistas do Nosso Estado, and PRONEX Optimization. Research of B.F. Svaiter was partially supported by CNPq Grants 300755/2005-8 and 475647/2006-8 and by PRONEX Optimization.     

Lipschitzianity of optimal trajectories for the Bolza optimal control problem

In this paper we investigate Lipschitz continuity of optimal solutions for the Bolza optimal control problem under Tonelli’s type growth condition. Such regularity being a consequence of normal necessary conditions for optimality, we propose new sufficient conditions for normality of state-constrained nonsmooth maximum principles for absolutely continuous optimal trajectories. Furthermore we show that for unconstrained problems any minimizing sequence of controls can be slightly modified to get a new minimizing sequence with nice boundedness properties. Finally, we provide a sufficient condition for Lipschitzianity of optimal trajectories for Bolza optimal control problems with end point constraints and extend a result from (J. Math. Anal. Appl. 143, 301–316, 1989) on Lipschitzianity of minimizers for a classical problem of the calculus of variations with discontinuous Lagrangian to the nonautonomous case.     

On n-term approximation with positive coefficients

In this paper, we consider algorithms for constructing n-terms approximations with nonnegative coefficients. The convergence theorem is proved for a “positive” analog of the Pure Greedy Algorithm. We establish a condition on the sequence of weakness coefficients which is sufficient for the convergence of the Positive Weak Greedy Algorithm. This condition is also necessary for the class of monotone sequences.     

Dual Convergence for Penalty Algorithms in Convex Programming

Algorithms for convex programming, based on penalty methods, can be designed to have good primal convergence properties even without uniqueness of optimal solutions. Taking primal convergence for granted, in this paper we investigate the asymptotic behavior of an appropriate dual sequence obtained directly from primal iterates. First, under mild hypotheses, which include the standard Slater condition but neither strict complementarity nor second-order conditions, we show that this dual sequence is bounded and also, each cluster point belongs to the set of Karush–Kuhn–Tucker multipliers. Then we identify a general condition on the behavior of the generated primal objective values that ensures the full convergence of the dual sequence to a specific multiplier. This dual limit depends only on the particular penalty scheme used by the algorithm. Finally, we apply this approach to prove the first general dual convergence result of this kind for penalty-proximal algorithms in a nonlinear setting.     

Concentration-cancellation phenomena for the velocity fields in incompressible fluid flows

A more intuitive sufficient condition is given for the concentration cancellation phenomena in 2- or 3-D incompressible fluid flows; that is, if the projection of concentration set of the weak-star defect measure associated with the approximate solution sequence onto space ℝ^π _x (n = 2, 3) is a set with Hausdorff dimension less than 1, then the weak-L ² limit of the approximate solution sequence is a classical weak solution of Euler equation. Using this condition, an example is given to elucidate concentration-cancellation phenomena.