Solving generalized semi-infinite programs by reduction to simpler problems

The article intends to give a unifying treatment of different approaches to solve generalized semi-infinite programs by transformation to simpler problems. In particular dual-, penalty-, discretization-, reduction-, and Karush-Kuhn-Tucker (KKT)-methods are applied to obtain equivalent problems or relaxations of a simpler structure. The relaxations are viewed as a perturbation P _τ of the original problem P, depending on a perturbation parameter τ > 0, and are analyzed by using parametric programming techniques. We give convergence results and results on the rate of convergence for the minimal values and the optimal solutions of P _τ when τ tends toward 0. We review earlier studies and present new ones.     

A method of bi-coordinate variations with tolerances and its convergence

We propose a method of bi-coordinate variations for optimal resource allocation problems, which involve simplex type constraints. It consists in making coordinate-wise steps together with special threshold control and tolerances whose values reduce sequentially. The method is simpler essentially than the usual gradient ones, which enables one to apply it to large dimensional optimization problems. We establish its convergence and rate of convergence under rather mild assumptions.     

Local Convergence Analysis of Projection-Type Algorithms: Unified Approach

In this paper, we use a unified approach to analyze the local convergence behavior of a wide class of projection-type methods for solving variational inequality problems. Under certain conditions, it is shown that, in a finite number of iterations, either the sequence of iterates terminates at a solution of the concerned problem or all iterates enter and remain in the relative interior of the optimal face and, hence, the subproblem reduces to a simpler form.     

Convergence in norm of modified Krasnoselski-Mann iterations for fixed points of demicontractive mappings

This paper deals with fixed points methods related to the general class of demicontractive mappings (including the well-known classes of nonexpansive and quasi-nonexpansive mappings) in Hilbert spaces. Specifically, we point out some historical aspects concerning the concept of demicontactivity and we investigate a regularized variant of the Krasnoselski-Mann iteration that can be alternatively regarded as a simplified form of the inertial iteration (P-E. Maingé, J. Math. Anal. Appl. 344 (2008) 876-887) with non-constant relaxation factors. These two methods ensure the strong convergence of the generated sequence towards the least norm element of the set of fixed-points of demicontractive mappings. However, for convergence, our method does not require anymore the knowledge of some constant related to the involved demicontractive operator. A new and simpler proof is also proposed for its convergence even when involving non-constant relaxation factors. We point out the simplicity of this algorithm (at least from computational point of view) in comparison with other existing methods. We also present some numerical experiments concerning a convex feasibility problem, experiments that emphasize the characteristics of the considered algorithm comparing with a classical cyclic projection-type iteration.     

半无限极大极小问题的极大熵方法

给出了一种求解半无限极大极小问题的极大熵方法，其基本思想是将半无限极大极小问题用有限维的可微无约束优化问题来近似．研究了方法的一些性质，并证明了方法的收敛性．文末的数值结果说明：这种方法是可行的，而算法的构造比已知的算法要容易得多，因而易于在工程设计中推广应用．     

On Unique Solutions of Multiple-State Optimal Design Problems on an Annulus

We study the uniqueness and explicit derivation of the relaxed optimal solutions, corresponding to the minimization of weighted sum of potential energies for a mixture of two isotropic conductive materials on an annulus. Recently, it has been shown by Burazin and Vrdoljak that even for multiple-state problems, if the domain is spherically symmetric, then the proper relaxation of the problem by the homogenization method is equivalent to a simpler relaxed problem, stated only in terms of local proportions of given materials. This enabled explicit calculation of a solution on a ball, while problems on an annulus appeared to be more tedious. In this paper, we discuss the uniqueness of a solution of this simpler relaxed problem, when the domain is an annulus and we use the necessary and sufficient conditions of optimality to present a method for explicit calculation of the unique solution of this simpler proper relaxation, which is demonstrated on an example.     

Coincidence criteria for maximal stable bridges in two game problems of approach

We consider a finite-dimensional conflict-controlled system whose behavior on a finite time interval is described by a vector differential equation. We analyze two game problems of approach in the phase space. In both problems the same terminal set is considered: in the first case, one should guarantee that the phase vector of the system reaches the terminal set at the final instant of time; in the second case, the phase vector should reach the terminal set no later than the final time instant. It is natural to assume that the construction of a solution to the first problem is much simpler than the construction of a solution to the second problem; this fact is confirmed by available experience. The paper is devoted to finding conditions on the system and the terminal set under which the solutions to the above problems coincide. Using these conditions, one can replace the solution of the second problem by the simpler solution of the first problem.     

Lower bounds and duality in the optimal control of distributed systems

We develop a duality theory for problems of minimization of a convex functional on a convex set and apply this theory to optimal control problems with non-differentiable functional and state as well as control constraints. The dual problem is sometimes found to be simpler than the primal problem. The equivalence of the primal and the dual problem is established for problems in which the functional is strongly convex. A posteriori error are also given for such problems.     

Asymmetric variational inequality problems over product sets: Applications and iterative methods

In this paper, we (i) describe how several equilibrium problems can be uniformly modelled by a finite-dimensional asymmetric variational inequality defined over a Cartesian product of sets, and (ii) investigate the local and global convergence of various iterative methods for solving such a variational inequality problem. Because of the special Cartesian product structure, these iterative methods decompose the original variational inequality problem into a sequence of simpler variational inequality subproblems in lower dimensions. The resulting decomposition schemes often have a natural interpretation as some adjustment processes. This research was based on work supported by the National Science Foundation under grant ECS 811–4571.     

On the convergence of constrained minima

We characterize the convergence of values and Lagrange multipliers for minimum problems of perturbed quadratic functionals in Banach spaces subject to a fixed linear operator constraint with finite-dimensional range. We obtain sufficient conditions for the convergence of the solutions. Examples show the different behaviour of the continuous dependence problem for the analogous unconstrained minimizations, where the gamma-type variational convergences are relevant. Such convergence conditions are extended here to the con strained problems.     

无穷小延伸定理的推广及其应用

本文在饱和的非标准模型中把无穷小延伸定理推广到网的情形,做为应用,利用推广了的无穷小延伸定理给出拓扑空间中连续泛函的一个重要性质的离散化证明.     

On the approximation and the optimization of plates

This work is devoted to the study of simply supported and of clamped plates together with related variational inequalitiesand optimization problems. We introduce a new unitary approach based on distributed optimal control problems governed by second order elliptic boundary value problems and their penalization. This approach gives the possibility to approximate the solution via piecewise linear continuous finite elements and is simpler than other methods considered in the literature.The convergence with respect to the penalization parameter (?) is proved under very general assumptions.

In order to solve the obtained control problems, optimization procedures of steepest descent type are considered. Relevantnumerical examples illustrate the applicability of the proposed methods.     

On the proximal point method for equilibrium problems in Hilbert spaces

We analyse a proximal point method for equilibrium problems in Hilbert spaces, improving upon previously known convergence results. We prove global weak convergence of the generated sequence to a solution of the problem, assuming existence of solutions and rather mild monotonicity properties of the bifunction which defines the equilibrium problem, and we establish existence of solutions of the proximal subproblems. We also present a new reformulation of equilibrium problems as variational inequalities ones.     

Exact Solutions in Optimal Design Problems for Stationary Diffusion Equation

We consider two-phase multiple state optimal design problems for stationary diffusion equation. Both phases are taken to be isotropic, and the goal is to find the optimal distribution of materials within domain, with prescribed amounts, that minimizes a weighted sum of energies. In the case of one state equation, it is known that the proper relaxation of the problem via the homogenization theory is equivalent to a simpler relaxed problem, stated only in terms of the local proportion of given materials.

We prove an analogous result for multiple state problems if the number of states is less than the space dimension. In spherically symmetric case, the result holds for arbitrary number of states, and the optimality conditions of a simpler relaxation problem, which are necessary and sufficient, enable us to explicitly calculate the unique solution of proper relaxation for some examples. In contrary to maximization problems, these solutions are not classical.

     

Approximation of solutions of the two-dimensional wave equation with variable velocity and localized right-hand side using some “simple” solutions

Asymptotic solutions based on the characteristics and the modified Maslov canonical operator of the two-dimensional wave equation with variable coefficients and right-hand side corresponding to: (a) an instantaneous source; (b) a rapidly acting, but “time spread,” source, are compared. An algorithm for approximating a (more complicated) solution of problem (b) by linear combinations of the derivatives of the (simpler) solution of problem (a) is proposed. Numerical calculations showing the accuracy of this approximation are presented. The replacement of the solutions of problem (b) by those of problem (a) becomes especially important in the case where the wave equation is considered in the domain with boundary on which the velocity of the wave equation vanishes. Then the characteristics of the problem become singular (nonstandard) and solutions of type (a) generalize to the case referred to above in a much simpler and effective way than solutions of type (b). Such a situation arises in problems where long waves (for example, tsunami waves) are incident on a sloping seashore.     

A convergent simplicial algorithm with ω-subdivision and ω-bisection strategies

The simplicial algorithm is a kind of branch-and-bound method for computing a globally optimal solution of a convex maximization problem. Its convergence under the ω-subdivision strategy was an open question for some decades until Locatelli and Raber proved it (J Optim Theory Appl 107:69–79, 2000). In this paper, we modify their linear programming relaxation and give a different and simpler proof of the convergence. We also develop a new convergent subdivision strategy, and report numerical results of comparing it with existing strategies.     

Numerical methods for controlled and uncontrolled multiplexing and queueing systems

We deal with a very useful numerical method for both controlled and uncontrolled queuing and multiplexing type systems. The basic idea starts with a heavy traffic approximation, but it is shown that the results are very good even when working far from the heavy traffic regime. The underlying numerical method is a version of what is known as the Markov chain approximation method. It is a powerful methodology for controlled and uncontrolled stochastic systems, which can be approximated by diffusion or reflected diffusion type systems, and has been used with success on many other problems in stochastic control. We give a complete development of the relevant details, with an emphasis on multiplexing and particular queueing systems. The approximating process is a controlled or uncontrolled Markov chain which retains certain essential features of the original problem. This problem is generally substantially simpler than the original physical problem, and there are associated convergence theorems. The non-classical associated ergodic cost problem is derived, and put into a form such that reliable and good numerical algorithms, based on multigrid type ideas, can be used. Data for both controlled and uncontrolled problems shows the value of the method.Supported by ARO contract DAAL-03-92-G-0115, AFOSR contract F49620-92-J-0081, and DARPA contract AFOSR-91-0375.Formerly at Brown University. Supported by DARPA contract AFOSR-91-0375.     

Column Generation Algorithms for Nonlinear Optimization,I: Convergence Analysis

Column generation is an increasingly popular basic tool for the solution of large-scale mathematical programming problems. As problems being solved grow bigger, column generation may however become less efficient in its present form, where columns typically are not optimizing, and finding an optimal solution instead entails finding an optimal convex combination of a huge number of them. We present a class of column generation algorithms in which the columns defining the restricted master problem may be chosen to be optimizing in the limit, thereby reducing the total number of columns needed. This first article is devoted to the convergence properties of the algorithm class, and includes global (asymptotic) convergence results for differentiable minimization, finite convergence results with respect to the optimal face and the optimal solution, and extensions of these results to variational inequality problems. An illustration of its possibilities is made on a nonlinear network flow model, contrasting its convergence characteristics to that of the restricted simplicial decomposition (RSD) algorithm.     

Numerical solution of quasi-variational inequalities arising in stochastic game theory

We study the finite-difference approximation for the quasi-variational inequalities for a stochastic game involving discrete actions of the players and continuous and discrete payoff. We prove convergence of iterative schemes for the solution of the discretized quasi-variational inequalities, with estimates of the rate of convergence (via contraction mappings) in two particular cases. Further, we prove stability of the finite-difference schemes, and convergence of the solution of the discrete problems to the solution of the continuous problem as the discretization mesh goes to zero. We provide a direct interpretation of the discrete problems in terms of finite-state, continuous-time Markov processes.     

Intelligent Initialization and Adaptive Thresholding for Iterative Matrix Completion: Some Statistical and Algorithmic Theory for Adaptive-Impute

Over the past decade, various matrix completion algorithms have been developed. Thresholded singular value decomposition (SVD) is a popular technique in implementing many of them. A sizable number of studies have shown its theoretical and empirical excellence, but choosing the right threshold level still remains as a key empirical difficulty. This article proposes a novel matrix completion algorithm which iterates thresholded SVD with theoretically justified and data-dependent values of thresholding parameters. The estimate of the proposed algorithm enjoys the minimax error rate and shows outstanding empirical performances. The thresholding scheme that we use can be viewed as a solution to a nonconvex optimization problem, understanding of whose theoretical convergence guarantee is known to be limited. We investigate this problem by introducing a simpler algorithm, generalized- softImpute, analyzing its convergence behavior, and connecting it to the proposed algorithm.