An Augmented Lagrangian Method for a Class of Inverse Quadratic Programming Problems

We consider an inverse quadratic programming (QP) problem in which the parameters in the objective function of a given QP problem are adjusted as little as possible so that a known feasible solution becomes the optimal one. We formulate this problem as a minimization problem with a positive semidefinite cone constraint and its dual is a linearly constrained semismoothly differentiable (SC¹) convex programming problem with fewer variables than the original one. We demonstrate the global convergence of the augmented Lagrangian method for the dual problem and prove that the convergence rate of primal iterates, generated by the augmented Lagrange method, is proportional to 1/r, and the rate of multiplier iterates is proportional to  $1/\sqrt{r}$ , where r is the penalty parameter in the augmented Lagrangian. As the objective function of the dual problem is a SC¹ function involving the projection operator onto the cone of symmetrically semi-definite matrices, the analysis requires extensive tools such as the singular value decomposition of matrices, an implicit function theorem for semismooth functions, and properties of the projection operator in the symmetric-matrix space. Furthermore, the semismooth Newton method with Armijo line search is applied to solve the subproblems in the augmented Lagrange approach, which is proven to have global convergence and local quadratic rate. Finally numerical results, implemented by the augmented Lagrangian method, are reported.     

On the convergence of a smoothed penalty algorithm for semi-infinite programming

For semi-infinite programming (SIP), we consider a class of smoothed penalty functions, which approximate the exact $l_\rho (0<\rho \le 1)$ penalty functions. On base of the smoothed penalty function, we present a feasible penalty algorithm for solving SIP. Without any boundedness condition or coercive condition, we establish the global convergence theorem. Then we present a perturbation theorem for this algorithm and obtain a necessary and sufficient condition for the convergence to the optimal value of SIP. Under Mangasarian–Fromovitz constrained qualification condition, we further discuss the convergence properties for the algorithm based upon a subclass of smooth approximations to the exact $l_\rho $ penalty function. Finally, numerical results are given.     

Cutting Plane Algorithms for Nonlinear Semi-Definite Programming Problems with Applications

We will propose an outer-approximation (cutting plane) method for minimizing a function f X subject to semi-definite constraints on the variables XR ⁿ. A number of efficient algorithms have been proposed when the objective function is linear. However, there are very few practical algorithms when the objective function is nonlinear. An algorithm to be proposed here is a kind of outer-approximation(cutting plane) method, which has been successfully applied to several low rank global optimization problems including generalized convex multiplicative programming problems and generalized linear fractional programming problems, etc. We will show that this algorithm works well when f is convex and n is relatively small. Also, we will provide the proof of its convergence under various technical assumptions.     

An implicit function theorem

Suppose thatF:DR ⁿ×R^mRⁿ, withF(x ⁰,y ⁰)=0. The classical implicit function theorem requires thatF is differentiable with respect tox and moreover that ₁ F(x ⁰,y ⁰) is nonsingular. We strengthen this theorem by removing the nonsingularity and differentiability requirements and by replacing them with a one-to-one condition onF as a function ofx.     

Numerical experiments in semi-infinite programming

A quasi-Newton algorithm for semi-infinite programming using an L exact penalty function is described, and numerical results are presented. Comparisons with three Newton algorithms and one other quasi-Newton algorithm show that the algorithm is very promising in practice.     

Absolute convergence of Fourier series in eigenfunctions of an elliptic operator

In this article we investigate absolute convergence of Fourier series in eigenfunctions of an m-th order elliptic operator on functions in the Besov class B _2, ^N/2 . We show that in terms of Besov classes the theorem of Peetre on absolute convergence of series in eigenfunctions in the class B _2,1 ^N/2 is best possible. We construct a function in B _2, ^N/2 whose Fourier series is absolutely divergent at any preassigned point.Translated from Matematicheskie Zametki, Vol. 19, No. 3, pp. 435–448, March, 1976.In conclusion, the author thanks Sh. A. Alimov for guiding this work.     

Derivation of Vector-Valued Boolean Functions

The notion of Jacobi matrix is introduced for B ^m B ⁿ mappings. The chain rule, the inverse function theorem and the implicit function theorem are proved. The meaning of functional dependence in the context of Boolean functions is discussed. Parallel is drawn with usual calculus.     

Trust region algorithms for the nonlinear least distance problem

The nonlinear least distance problem is a special case of equality constrained optimization. Let a curve or surface be given in implicit form via the equationf(x)=0,x R ^d , and letz R ^d be a fixed data point. We discuss two algorithms for solving the following problem:Find a point x ^* such that f(x ^* )=0and z–x ^*₂ is minimal among all such x. The algorithms presented use thetrust region approach in which, at each iteration, an, approximation to the objective function or merit function is minimized in a given neighborhood (the trust region) of the current iterate. Among other things, this allows one to prove global convergence of the algorithm.Both authors were supported in part by the Deutsche Forschungsgemeinschaft, SFB 350.     

An implicit shift bidiagonalization algorithm for ill-posed systems

Iterative methods based on Lanczos bidiagonalization with full reorthogonalization (LBDR) are considered for solving large-scale discrete ill-posed linear least-squares problems of the form min _x Ax–b₂. Methods for regularization in the Krylov subspaces are discussed which use generalized cross validation (GCV) for determining the regularization parameter. These methods have the advantage that no a priori information about the noise level is required. To improve convergence of the Lanczos process we apply a variant of the implicitly restarted Lanczos algorithm by Sorensen using zero shifts. Although this restarted method simply corresponds to using LBDR with a starting vector (AA ^T) ^p b, it is shown that carrying out the process implicitly is essential for numerical stability. An LBDR algorithm is presented which incorporates implicit restarts to ensure that the global minimum of the CGV curve corresponds to a minimum on the curve for the truncated SVD solution. Numerical results are given comparing the performance of this algorithm with non-restarted LBDR.This work was partially supported by DARPA under grant 60NANB2D1272 and by the National Science Foundation under grant CCR-9209349.     

Whitney type inequalities for local anisotropic polynomial approximation

We prove a multivariate Whitney type theorem for the local anisotropic polynomial approximation in L_p(Q) with 1≤p≤∞. Here Q is a d-parallelepiped in R^d with sides parallel to the coordinate axes. We consider the error of best approximation of a function f by algebraic polynomials of fixed degree at most r_i−1 in variable , and relate it to a so-called total mixed modulus of smoothness appropriate to characterizing the convergence rate of the approximation error. This theorem is derived from a Johnen type theorem on equivalence between a certain K-functional and the total mixed modulus of smoothness which is proved in the present paper.     

A Perturbation approach for an inverse quadratic programming problem

We consider an inverse quadratic programming (QP) problem in which the parameters in both the objective function and the constraint set of a given QP problem need to be adjusted as little as possible so that a known feasible solution becomes the optimal one. We formulate this problem as a linear complementarity constrained minimization problem with a positive semidefinite cone constraint. With the help of duality theory, we reformulate this problem as a linear complementarity constrained semismoothly differentiable (SC¹) optimization problem with fewer variables than the original one. We propose a perturbation approach to solve the reformulated problem and demonstrate its global convergence. An inexact Newton method is constructed to solve the perturbed problem and its global convergence and local quadratic convergence rate are shown. As the objective function of the problem is a SC¹ function involving the projection operator onto the cone of positively semi-definite symmetric matrices, the analysis requires an implicit function theorem for semismooth functions as well as properties of the projection operator in the symmetric-matrix space. Since an approximate proximal point is required in the inexact Newton method, we also give a Newton method to obtain it. Finally we report our numerical results showing that the proposed approach is quite effective.     

A one-phase algorithm for semi-infinite linear programming

We present an algorithm for solving a large class of semi-infinite linear programming problems. This algorithm has several advantages: it handles feasibility and optimality together; it has very weak restrictions on the constraints; it allows cuts that are not near the most violated cut; and it solves the primal and the dual problems simultaneously. We prove the convergence of this algorithm in two steps. First, we show that the algorithm can find an-optimal solution after finitely many iterations. Then, we use this result to show that it can find an optimal solution in the limit. We also estimate how good an-optimal solution is compared to an optimal solution and give an upper bound on the total number of iterations needed for finding an-optimal solution under some assumptions. This algorithm is generalized to solve a class of nonlinear semi-infinite programming problems. Applications to convex programming are discussed.     

The Central Approximation Theorems for the Method of Left Gamma Quasi-Interpolants in L p spaces

The optimal degree of approximation of the method of Gammaoperators G _n in L _p spaces is O(n ^-1). In order to obtain much faster convergence, quasi-interpolants G _n ^(k) of G _n in the sense of Sablonnière are considered. We show that for fixed k the operator-norms G _n ^(k) _p are uniformly bounded in n. In addition to this, for the first time in the theory of quasi-interpolants, all central problems for approximation methods (direct theorem, inverse theorem, equivalence theorem) could be solved completely for the L _p metric. Left Gamma quasi-interpolants turn out to be as powerful as linear combinations of Gammaoperators [6].     

An inexact algorithm for composite nondifferentiable optimization

We describe an inexact version of Fletcher's QL algorithm with second-order corrections for minimizing composite nonsmooth functions. The method is shown to retain the global and local convergence properties of the original version, if the parameters are chosen appropriately. It is shown how the inexact method can be implemented, for the case in which the function to be minimized is an exact penalty function arising from the standard nonlinear programming problem. The method can also be applied to the problems of nonlinearl ₁ - andl -approximation.This research supported in part by the National Science Foundation under Grant DMS-8619903, and by the Air Force Office of Scientific Research under Grant AFOSR-ISSA-870092.     

A Projected Indefinite Dogleg Path Method for Equality Constrained Optimization

In this paper, we propose a 2-step trust region indefinite dogleg path method for the solution of nonlinear equality constrained optimization problems. The method is a globally convergent modification of the locally convergent Fontecilla method and an indefinite dogleg path method is proposed to get approximate solutions of quadratic programming subproblems even if the Hessian in the model is indefinite. The dogleg paths lie in the null space of the Jacobian matrix of the constraints. An ₁ exact penalty function is used in the method to determine if a trial point is accepted. The global convergence and the local two-step superlinear convergence rate are proved. Some numerical results are presented.     

A spectral Galerkin approximation of the Orr-Sommerfeld eigenvalue problem in a semi-infinite domain

Summary The convergence of a Galerkin approximation of the Orr-Sommerfeld eigenvalue problem, which is defined in a semi-infinite domain, is studied theoretically. In case the system of trial functions is based on a composite of Jacobi polynomials and an exponential transform of the semi-infinite domain, the error of the Galerkin approximation is estimated in terms of the transformation parametera and the numberN of trial functions. Finite or infinite-order convergence of the spectral Galerkin method is obtained depending on how the transformation parameter is chosen. If the transformation parameter is fixed, then convergence is of finite order only. However, ifa is varied proportional to 1/N with an exponent 0<<1, then the approximate eigenvalue converges faster than any finite power of 1/N asN. Some numerical examles are given.     

Dini-Verbände mit fast gut frisiertem Dualkegel

Summary We prove a theorem which is a generalisation of a theorem due to Goullet de Rugy: LetE be a locally convex vector lattice such that the structure spaces of the principal ideals ofE are universally measurable in their Stone-ech-compactifications respectively. Then, ifE is infrabarrelled or its topology is finer than the topology of compact convergence,E is a Dini lattice iffE ₊ is nearly well-capped.     

The distance between the Kac process and the Wiener process with applications to generalized telegraph equations

In this note we obtain a local central limit theorem and an expansion of length two for the Kac processY (t) that describes the position of a particle at timet after collisions. In particular, we obtain a rate of convergence for the distance of total variation for the distributions oft ^–1/2 Y (t) and the Wiener process at timet. The results apply to the probabilistic solutions of abstract telegraph and heat equations which heavily rely on the Kac and Wiener processes. Under very mild assumptions we establish a rate of convergence for a singular perturbation problem of an abstract heat equation.     

Convergence of distorted Brownian motions and singular Hamiltonians

We prove a convergence theorem for sequences of Diffusion Processes corresponding to Dirichlet Forms of the kind .We obtain convergence in total variation norm of the corresponding probability measures on the path space C(₊;^d) under hypotheses which, for example, are satisfied in the case of H _loc ¹ ( ^d )-convergence of the 's, but we can allow more singular situations as regards the approximating sequences. We use then these results to give a criterion of convergence for generalized Schrödinger operators in which the potential function should not necessarily exists as a measurable function. We obtain convergence not only in strong resolvent sense, but we also obtain convergence in the uniform operator topology up to sets of arbitrarily small Lebesgue measure. Applications to the problem of the approximation of ordinary Schrödinger operators by generalized ones corresponding to zero-range interactions are given.     

Amorphe Potenzen kompakter Räume

A set is amorphous, if it is not a union of two disjoint infinite subsets. The following variants of the Tychonoff product theorem are investigated in the hierarchy of weak choice principles. TA1: An amorphous power of a compactT ₂ space is compact. TA2: An amorphous power of a compactT ₂ space which as a set is wellorderable is compact. In ZF⁰TA1 is equivalent to the assertion, that amorphous sets are finite. RT is Ramsey's theorem, that every finite colouring of the set ofn-element subsets of an infinite set has an infinite homogeneous subset and PW is Rubin's axiom, that the power set of an ordinal is wellorderable. In ZF⁰RT+PW implies TA2. Since RT+PW is compatible with the existence of infinite amorphous sets, TA2 does not imply TA1 in ZF⁰. But TA2 cannot be proved in ZF⁰ alone. As an application, we prove a theorem of Stone, using a weak wellordering axiomD ₃ (a set is wellorderable, if each of its infinite subsets is structured) together with RT.

Diese Arbeit ist Teil der Habilitationsschrift des Verfassers im Fachgebiet Mathematische Analysis an der Technischen Universität Wien.