A Convex Optimization Framework for Almost Budget Balanced Allocation of a Divisible Good

We address the problem of allocating a single divisible good to a number of agents. The agents have concave valuation functions parameterized by a scalar type. The agents report only the type. The goal is to find allocatively efficient, strategy proof, nearly budget balanced mechanisms within the Groves class. Near budget balance is attained by returning as much of the received payments as rebates to agents. Two performance criteria are of interest: the maximum ratio of budget surplus to efficient surplus, and the expected budget surplus, within the class of linear rebate functions. The goal is to minimize them. Assuming that the valuation functions are known, we show that both problems reduce to convex optimization problems, where the convex constraint sets are characterized by a continuum of half-plane constraints parameterized by the vector of reported types. We then propose a randomized relaxation of these problems by sampling constraints. The relaxed problem is a linear programming problem (LP). We then identify the number of samples needed for ``near-feasibility'' of the relaxed constraint set. Under some conditions on the valuation function, we show that value of the approximate LP is close to the optimal value. Simulation results show significant improvements of our proposed method over the Vickrey-Clarke-Groves (VCG) mechanism without rebates. In the special case of indivisible goods, the mechanisms in this paper fall back to those proposed by Moulin, by Guo and Conitzer, and by Gujar and Narahari, without any need for randomization. Extension of the proposed mechanisms to situations when the valuation functions are not known to the central planner are also discussed. Note to Practitioners-Our results will be useful in all resource allocation problems that involve gathering of information privately held by strategic users, where the utilities are any concave function of the allocations, and where the resource planner is not interested in maximizing revenue, but in efficient sharing of the resource. Such situations arise quite often in fair sharing of internet resources, fair sharing of funds across departments within the same parent organization, auctioning of public goods, etc. We study methods to achieve near budget balance by first collecting payments according to the celebrated VCG mechanism, and then returning as much of the collected money as rebates. Our focus on linear rebate functions allows for easy implementation. The resulting convex optimization problem is solved via relaxation to a randomized linear programming problem, for which several efficient solvers exist. This relaxation is enabled by constraint sampling. Keeping practitioners in mind, we identify the number of samples that assures a desired level of ``near-feasibility'' with the desired confidence level. Our methodology will occasionally require subsidy from outside the system. We however demonstrate via simulation that, if the mechanism is repeated several times over independent instances, then past surplus can support the subsidy requirements. We also extend our results to situations where the strategic users' utility functions are not known to the allocating entity, a common situation in the context of internet users and other problems.

An operator-splitting finite element method for the efficient parallel solution of multidimensional population balance systems

A finite element method for solving multidimensional population balance systems is proposed where the balance of fluid velocity, temperature and solute partial density is considered as a two-dimensional system and the balance of particle size distribution as a three-dimensional one. The method is based on a dimensional splitting into physical space and internal property variables. In addition, the operator splitting allows to decouple the equations for temperature, solute partial density and particle size distribution. Further, a nodal point based parallel finite element algorithm for multi-dimensional population balance systems is presented. The method is applied to study a crystallization process assuming, for simplicity, a size independent growth rate and neglecting agglomeration and breakage of particles. Simulations for different wall temperatures are performed to show the effect of cooling on the crystal growth. Although the method is described in detail only for the case of d=2 space and s=1 internal property variables it has the potential to be extendable to d+s variables, d=2, 3 and s >= 1. (C) 2011 Elsevier Ltd. All rights reserved.

Dilations of Gamma-contractions by solving operator equations

For a contraction P and a bounded commutant S of P. we seek a solution X of the operator equation S - S*P = (1 - P* P)(1/2) X (1 - P* P)(1/2) where X is a bounded operator on (Ran) over bar (1 - P* P)(1/2) with numerical radius of X being not greater than 1. A pair of bounded operators (S, P) which has the domain Gamma = {(z(1) + z(2), z(2)): vertical bar z(1)vertical bar < 1, vertical bar z(2)vertical bar <= 1} subset of C-2 as a spectral set, is called a P-contraction in the literature. We show the existence and uniqueness of solution to the operator equation above for a Gamma-contraction (S, P). This allows us to construct an explicit Gamma-isometric dilation of a Gamma-contraction (S, P). We prove the other way too, i.e., for a commuting pair (S, P) with parallel to P parallel to <= 1 and the spectral radius of S being not greater than 2, the existence of a solution to the above equation implies that (S, P) is a Gamma-contraction. We show that for a pure F-contraction (S, P), there is a bounded operator C with numerical radius not greater than 1, such that S = C + C* P. Any Gamma-isometry can be written in this form where P now is an isometry commuting with C and C. Any Gamma-unitary is of this form as well with P and C being commuting unitaries. Examples of Gamma-contractions on reproducing kernel Hilbert spaces and their Gamma-isometric dilations are discussed. (C) 2012 Elsevier Inc. All rights reserved.

An operator-splitting Galerkin/SUPG finite element method for population balance equations : stability and convergence

We present a heterogeneous finite element method for the solution of a high-dimensional population balance equation, which depends both the physical and the internal property coordinates. The proposed scheme tackles the two main difficulties in the finite element solution of population balance equation: (i) spatial discretization with the standard finite elements, when the dimension of the equation is more than three, (ii) spurious oscillations in the solution induced by standard Galerkin approximation due to pure advection in the internal property coordinates. The key idea is to split the high-dimensional population balance equation into two low-dimensional equations, and discretize the low-dimensional equations separately. In the proposed splitting scheme, the shape of the physical domain can be arbitrary, and different discretizations can be applied to the low-dimensional equations. In particular, we discretize the physical and internal spaces with the standard Galerkin and Streamline Upwind Petrov Galerkin (SUPG) finite elements, respectively. The stability and error estimates of the Galerkin/SUPG finite element discretization of the population balance equation are derived. It is shown that a slightly more regularity, i.e. the mixed partial derivatives of the solution has to be bounded, is necessary for the optimal order of convergence. Numerical results are presented to support the analysis.

Operator-splitting finite element algorithms for computations of high-dimensional parabolic problems

An operator-splitting finite element method for solving high-dimensional parabolic equations is presented. The stability and the error estimates are derived for the proposed numerical scheme. Furthermore, two variants of fully-practical operator-splitting finite element algorithms based on the quadrature points and the nodal points, respectively, are presented. Both the quadrature and the nodal point based operator-splitting algorithms are validated using a three-dimensional (3D) test problem. The numerical results obtained with the full 3D computations and the operator-split 2D + 1D computations are found to be in a good agreement with the analytical solution. Further, the optimal order of convergence is obtained in both variants of the operator-splitting algorithms. (C) 2012 Elsevier Inc. All rights reserved.

On the dynamic contact angle in simulation of impinging droplets with sharp interface methods

Effects of dynamic contact angle models on the flow dynamics of an impinging droplet in sharp interface simulations are presented in this article. In the considered finite element scheme, the free surface is tracked using the arbitrary Lagrangian-Eulerian approach. The contact angle is incorporated into the model by replacing the curvature with the Laplace-Beltrami operator and integration by parts. Further, the Navier-slip with friction boundary condition is used to avoid stress singularities at the contact line. Our study demonstrates that the contact angle models have almost no influence on the flow dynamics of the non-wetting droplets. In computations of the wetting and partially wetting droplets, different contact angle models induce different flow dynamics, especially during recoiling. It is shown that a large value for the slip number has to be used in computations of the wetting and partially wetting droplets in order to reduce the effects of the contact angle models. Among all models, the equilibrium model is simple and easy to implement. Further, the equilibrium model also incorporates the contact angle hysteresis. Thus, the equilibrium contact angle model is preferred in sharp interface numerical schemes.

Riesz transforms and multipliers for the Grushin operator

We show that Riesz transforms associated to the Grushin operator G = -Delta - |x|(2 similar to) (t) (2) are bounded on L (p) (a''e (n+1)). We also establish an analogue of the Hormander-Mihlin Multiplier Theorem and study Bochner-Riesz means associated to the Grushin operator. The main tools used are Littlewood-Paley theory and an operator-valued Fourier multiplier theorem due to L. Weis.

Adiabatic eigenfunction-based approach for coherent excitation transfer: An almost analytical treatment of the Fenna-Matthews-Olson complex

We suggest a method of studying coherence in finite-level systems coupled to the environment and use it for the Hamiltonian that has been used to describe the light-harvesting pigment-protein complex. The method works with the adiabatic states and transforms the Hamiltonian to a form in which the terms responsible for decoherence and population relaxation are separated out. Decoherence is then accounted for nonperturbatively and population relaxation using a Markovian master equation. Almost analytical results can be obtained for the seven-level system, and the calculations are very simple for systems with more levels. We apply the treatment to the seven-level system, and the results are in excellent agreement with the exact numerical results of Nalbach et al. Nalbach, Braun, and Thorwart, Phys. Rev. E 84, 041926 (2011)]. Our approach is able to account for decoherence and population relaxation separately. It is found that decoherence causes only damping of oscillations and does not lead to transfer to the reaction center. Population relaxation is necessary for efficient transfer to the reaction center, in agreement with earlier findings. Our results show that the transformation to the adiabatic basis followed by a Redfield type of approach leads to results in good agreement with exact simulation.

Improved quasiparticle wave functions and mean field for G(0)W(0) calculations: Initialization with the COHSEX operator

The GW approximation to the electron self-energy has become a standard method for ab initio calculation of excited-state properties of condensed-matter systems. In many calculations, the G W self-energy operator, E, is taken to be diagonal in the density functional theory (DFT) Kohn-Sham basis within the G0 W0 scheme. However, there are known situations in which this diagonal Go Wo approximation starting from DFT is inadequate. We present two schemes to resolve such problems. The first, which we called sc-COHSEX-PG W, involves construction of an improved mean field using the static limit of GW, known as COHSEX (Coulomb hole and screened exchange), which is significantly simpler to treat than GW W. In this scheme, frequency-dependent self energy E(N), is constructed and taken to be diagonal in the COHSEX orbitals after the system is solved self-consistently within this formalism. The second method is called off diagonal-COHSEX G W (od-COHSEX-PG W). In this method, one does not self-consistently change the mean-field starting point but diagonalizes the COHSEX Hamiltonian within the Kohn-Sham basis to obtain quasiparticle wave functions and uses the resulting orbitals to construct the G W E in the diagonal form. We apply both methods to a molecular system, silane, and to two bulk systems, Si and Ge under pressure. For silane, both methods give good quasiparticle wave functions and energies. Both methods give good band gaps for bulk silicon and maintain good agreement with experiment. Further, the sc-COHSEX-PGW method solves the qualitatively incorrect DFT mean-field starting point (having a band overlap) in bulk Ge under pressure.

DIMENSION FREE BOUNDEDNESS OF RIESZ TRANSFORMS FOR THE GRUSHIN OPERATOR

Let G = -Delta(xi) - vertical bar xi vertical bar(2) partial derivative(2)/partial derivative eta(2) be the Grushin operator on R-n x R. We prove that the Riesz transforms associated to this operator are bounded on L-p(Rn+1), 1 < p < infinity, and their norms are independent of dimension n.

Identifying functionally important cis-peptide containing segments in proteins and their utility in molecular function annotation

Cis-peptide embedded segments are rare in proteins but often highlight their important role in molecular function when they do occur. The high evolutionary conservation of these segments illustrates this observation almost universally, although no attempt has been made to systematically use this information for the purpose of function annotation. In the present study, we demonstrate how geometric clustering and level-specific Gene Ontology molecular-function terms (also known as annotations) can be used in a statistically significant manner to identify cis-embedded segments in a protein linked to its molecular function. The present study identifies novel cis-peptide fragments, which are subsequently used for fragment-based function annotation. Annotation recall benchmarks interpreted using the receiver-operator characteristic plot returned an area-under-curve >0.9, corroborating the utility of the annotation method. In addition, we identified cis-peptide fragments occurring in conjunction with functionally important trans-peptide fragments, providing additional insights into molecular function. We further illustrate the applicability of our method in function annotation where homology-based annotation transfer is not possible. The findings of the present study add to the repertoire of function annotation approaches and also facilitate engineering, design and allied studies around the cis-peptide neighborhood of proteins.

Monopoles, Dirac operator, and index theory for fuzzy SU(3) / (U(1) x U(1))

The intersection of the ten-dimensional fuzzy conifold Y-F(10) with S-F(5) x S-F(5) is the compact eight-dimensional fuzzy space X-F(8). We show that X-F(8) is (the analogue of) a principal U(1) x U(1) bundle over fuzzy SU(3) / U(1) x U(1)) ( M-F(6)). We construct M-F(6) using the Gell-Mann matrices by adapting Schwinger's construction. The space M-F(6) is of relevance in higher dimensional quantum Hall effect and matrix models of D-branes. Further we show that the sections of the monopole bundle can be expressed in the basis of SU(3) eigenvectors. We construct the Dirac operator on M-F(6) from the Ginsparg-Wilson algebra on this space. Finally, we show that the index of the Dirac operator correctly reproduces the known results in the continuum.

An interior penalty method for distributed optimal control problems governed by the biharmonic operator

In this paper, a C-0 interior penalty method has been proposed and analyzed for distributed optimal control problems governed by the biharmonic operator. The state and adjoint variables are discretized using continuous piecewise quadratic finite elements while the control variable is discretized using piecewise constant approximations. A priori and a posteriori error estimates are derived for the state, adjoint and control variables under minimal regularity assumptions. Numerical results justify the theoretical results obtained. The a posteriori error estimators are useful in adaptive finite element approximation and the numerical results indicate that the sharp error estimators work efficiently in guiding the mesh refinement. (C) 2014 Elsevier Ltd. All rights reserved.

L-p estimates for the wave equation associated to the Grushin operator

We prove that the solution of the wave equation associated to the Grushin operator G = -Delta -vertical bar x vertical bar(2)partial derivative(2)(t) is bounded on L-P (Rn+1), with 1 < p < infinity, when vertical bar 1/p - 1/2 vertical bar < 1/n+2.