Studying the Complexity of Global Verification for NP-Hard Discrete Optimization Problems

This paper examines the complexity of global verification for MAX-SAT, MAX-k-SAT (for k3), Vertex Cover, and Traveling Salesman Problem. These results are obtained by adaptations of the transformations that prove such problems to be NP-complete. The class of problems PGS is defined to be those discrete optimization problems for which there exists a polynomial time algorithm such that given any solution , either a solution can be found with a better objective function value or it can be concluded that no such solution exists and is a global optimum. This paper demonstrates that if any one of MAX-SAT, MAX-k-SAT (for k3), Vertex Cover, or Traveling Salesman Problem are in PGS, then P=NP.     

Adaptive wavelet schemes for an elliptic control problem with Dirichlet boundary control

An adaptive algorithm based on wavelets is proposed for the fast numerical solution of control problems governed by elliptic boundary value problems with Dirichlet boundary control. A quadratic cost functional representing Sobolev norms of the state and a regularization in terms of the control is to be minimized subject to linear constraints in weak form. In particular, the constraints are formulated as a saddle point problem that allows to handle the varying boundary conditions explicitly. In the framework of (biorthogonal) wavelets, a representer for the functional is derived in terms of ₂-norms of wavelet expansion coefficients and the constraints are written in form of an ₂ automorphism. Standard techniques from optimization are then used to deduce the resulting first order necessary conditions as a (still infinite) system in ₂. Applying the machinery developed in [8,9] which has been extended to control problems in [14], an adaptive method is proposed which can be interpreted as an inexact gradient method for the control. In each iteration step, in turn the primal and the adjoint saddle point system are solved up to a prescribed accuracy by an adaptive iterative Uzawa algorithm for saddle point problems which has been proposed in [10]. Under these premises, it can be shown that the adaptive algorithm containing now three layers of iterations is asymptotically optimal. This means that the convergence rate achieved for computing the solution up to a desired target tolerance is asymptotically the same as the wavelet-best N-term approximation of the solution, and the total computational work is proportional to the number of computational unknowns. AMS subject classification 65K10, 65N99, 93B40Angela Kunoth: This work has been supported partly by the Deutsche Forschungsgemeinschaft (SFB 611) at the Universität Bonn and by the European Communitys Human Potential Programme under contract HPRN-CT-2002-00286 Breaking Complexity.     

The Heat Equation in the Interior of an Equilateral Triangle

We present the solution of the classical problem of the heat equation formulated in the interior of an equilateral triangle with Dirichlet boundary conditions. This solution is expressed as an integral in the complex Fourier space, i.e., the complex k₁ and k₂ planes, involving appropriate integral transforms of the Dirichlet boundary conditions. By choosing Dirichlet data so that their integral transforms can be computed explicitly, we show that the solution is expressed in terms of an integral whose integrand decays exponentially as . Hence, it is possible to evaluate this integral numerically in an efficient and straightforward manner. Other types of boundary value problems, including the Neumman and Robin problems, can be solved similarly.     

A FPTAS for computing a symmetric Leontief competitive economy equilibrium

In this paper, we consider a linear complementarity problem (LCP) arisen from the Nash and Arrow–Debreu competitive economy equilibria where the LCP coefficient matrix is symmetric. We prove that the decision problem, to decide whether or not there exists a complementary solution, is NP-complete. Under certain conditions, an LCP solution is guaranteed to exist and we present a fully polynomial-time approximation scheme (FPTAS) for approximating a complementary solution, although the LCP solution set can be non-convex or non-connected. Our method is based on approximating a quadratic social utility optimization problem (QP) and showing that a certain KKT point of the QP problem is an LCP solution. Then, we further show that such a KKT point can be approximated with a new improved running time complexity ${{O}((\frac{n^4}{\epsilon})\log\log(\frac{1}{\epsilon}))}$ arithmetic operation in accuracy ${\epsilon \in (0,1)}$ . We also report preliminary computational results which show that the method is highly effective. Applications in competitive market model problems with other utility functions are also presented, including global trading and dynamic spectrum management problems.     

Fast Iterative Solution of Saddle Point Problems in Optimal Control Based on Wavelets

In this paper, wavelet techniques are employed for the fast numerical solution of a control problem governed by an elliptic boundary value problem with boundary control. A quadratic cost functional involving natural norms of the state and the control is to be minimized. Firstly the constraint, the elliptic boundary value problem, is formulated in an appropriate weak form that allows to handle varying boundary conditions explicitly: the boundary conditions are treated by Lagrange multipliers, leading to a saddle point problem. This is combined with a fictitious domain approach in order to cover also more complicated boundaries.Deviating from standard approaches, we then use (biorthogonal) wavelets to derive an equivalent infinite discretized control problem which involves only ₂-norms and -operators. Classical methods from optimization yield the corresponding optimality conditions in terms of two weakly coupled (still infinite) saddle point problems for which a unique solution exists. For deriving finite-dimensional systems which are uniformly invertible, stability of the discretizations has to be ensured. This together with the ₂-setting circumvents the problem of preconditioning: all operators have uniformly bounded condition numbers independent of the discretization.In order to numerically solve the resulting (finite-dimensional) linear system of the weakly coupled saddle point problems, a fully iterative method is proposed which can be viewed as an inexact gradient scheme. It consists of a gradient algorithm as an outer iteration which alternatingly picks the two saddle point problems, and an inner iteration to solve each of the saddle point problems, exemplified in terms of the Uzawa algorithm. It is proved here that this strategy converges, provided that the inner systems are solved sufficiently well. Moreover, since the system matrix is well-conditioned, it is shown that in combination with a nested iteration strategy this iteration is asymptotically optimal in the sense that it provides the solution on discretization level J with an overall amount of arithmetic operations that is proportional to the number of unknows N _J on that level.Finally, numerical results are provided.     

Convergence rates of iterated Tikhonov regularized solutions of nonlinear III — posed problems

Summary In this paper we investigate iterated Tikhonov regularization for the solution of nonlinear ill-posed problems. In the case of linear ill-posed problems it is well-known that (under appropriate assumptions) then-th iterated regularized solutions can converge likeO(²² /(2n+1)), where denotes the noise level of the data perturbation. We give conditions that guarantee this convergence rate also for nonlinear ill-posed problems, and motivate these conditions by the mapping degree. The results are derived by a comparison of the iterated regularized solutions of the nonlinear problem with the iterated regularized solutions of its linearization. Numerical examples are presented.Supported by the Austrian Fonds zur Förderung der wissenschaftlichen Forschung,project P-7869 PHY, and by the Christian Doppler Society     

Direct and inverse problems for degenerate differential equations

We are concerned with a general abstract equation that allows to handle various degenerate first and second order differential equations in Banach spaces. We indicate sufficient conditions for existence and uniqueness of a solution. Periodic conditions are assumed to improve previous approaches on the abstract problem to work on \((-\infty ,\infty )\). Related inverse problems are discussed, too. All general results are applied to some systems of partial differential equations. Inverse problems for degenerate evolution integro-differential equations might be described, too.     

A hinged plate equation and iterated Dirichlet Laplace operator on domains with concave corners

Fourth order hinged plate type problems are usually solved via a system of two second order equations. For smooth domains such an approach can be justified. However, when the domain has a concave corner the bi-Laplace problem with Navier boundary conditions may have two different types of solutions, namely u₁ with and . We will compare these two solutions. A striking difference is that in general only the first solution, obtained by decoupling into a system, preserves positivity, that is, a positive source implies that the solution is positive. The other type of solution is more relevant in the context of the hinged plate. We will also address the higher-dimensional case. Our main analytical tools will be the weighted Sobolev spaces that originate from Kondratiev. In two dimensions we will show an alternative that uses conformal transformation. Next to rigorous proofs the results are illustrated by some numerical experiments for planar domains.     

Blow-up,global existence and exponential decay estimates for a class of quasilinear parabolic problems

This paper deals with a class of nonlinear parabolic problems in divergence form whose solutions, without appropriate data restrictions, might blow up at some finite time. The purpose of this paper is to establish conditions on the data sufficient to guarantee blow-up of solution at some finite time τ$\tau$, conditions to ensure that the solution remains bounded as well as conditions to derive some explicit exponential decay bounds for the solution and its derivatives.     

Wavelet–Galerkin solutions of one dimensional elliptic problems

Daubechies wavelet bases are used for numerical solution of partial differential equations of one dimension by Galerkin method. Galerkin bases are constructed from Daubechies functions which are compactly supported and which constitute an orthonormal basis of L²(R)$L^2(\mathbb{R})$. Theoretical and numerical results are obtained for elliptic problems of second order with different types of boundary conditions. Optimal error estimates are also obtained. Comparison of solutions with simple finite difference method suggests that for this class of problems, the present method will provide a better alternative to other classical methods. The methodology can be generalized to multidimensional problems by taking care of some technical facts.     

Construction of Carleman formulas by using mixed problems with parameter-dependent boundary conditions

Let D be an open connected subset of the complex plane C with sufficiently smooth boundary ?D. Perturbing the Cauchy problem for the Cauchy–Riemann system ??u = f in D with boundary data on a closed subset S ? ?D, we obtain a family of mixed problems of the Zaremba-type for the Laplace equation depending on a small parameter ε ∈ (0, 1] in the boundary condition. Despite the fact that the mixed problems include noncoercive boundary conditions on ?D\S, each of them has a unique solution in some appropriate Hilbert space H ⁺(D) densely embedded in the Lebesgue space L ₂(?D) and the Sobolev–Slobodetski? space H ^1/2?δ(D) for every δ > 0. The corresponding family of the solutions {u _ε} converges to a solution to the Cauchy problem in H ⁺(D) (if the latter exists). Moreover, the existence of a solution to the Cauchy problem in H ⁺(D) is equivalent to boundedness of the family {u _ε} in this space. Thus, we propose solvability conditions for the Cauchy problem and an effective method of constructing a solution in the form of Carleman-type formulas.     

KKT Conditions for Rank-Deficient Nonlinear Least-Square Problems with Rank-Deficient Nonlinear Constraints

In nonlinear least-square problems with nonlinear constraints, the function , where f ₂ is a nonlinear vector function, is to be minimized subject to the nonlinear constraints f ₁(x)=0. This problem is ill-posed if the first-order KKT conditions do not define a locally unique solution. We show that the problem is ill-posed if either the Jacobian of f ₁ or the Jacobian of J is rank-deficient (i.e., not of full rank) in a neighborhood of a solution satisfying the first-order KKT conditions. Either of these ill-posed cases makes it impossible to use a standard Gauss–Newton method. Therefore, we formulate a constrained least-norm problem that can be used when either of these ill-posed cases occur. By using the constant-rank theorem, we derive the necessary and sufficient conditions for a local minimum of this minimum-norm problem. The results given here are crucial for deriving methods solving the rank-deficient problem.     

Existence and multiplicity of solutions to 2mth-order ordinary differential equations

In this paper, the existence and multiplicity of solutions are obtained for the 2mth-order ordinary differential equation two-point boundary value problems u(2(m−i))(t)=f(t,u(t)) for all t∈[0,1] subject to Dirichlet, Neumann, mixed and periodic boundary value conditions, respectively, where f is continuous, ai∈R for all i=1,2,…,m. Since these four boundary value problems have some common properties and they can be transformed into the integral equation of form , we firstly deal with this nonlinear integral equation. By using the strongly monotone operator principle and the critical point theory, we establish some conditions on f which are able to guarantee that the integral equation has a unique solution, at least one nonzero solution, and infinitely many solutions. Furthermore, we apply the abstract results on the integral equation to the above four 2mth-order two-point boundary problems and successfully resolve the existence and multiplicity of their solutions.     

Well-Posed Boundary Value Problems for Integrable Evolution Equations on a Finite Interval

We consider boundary value problems posed on an interval [0,L] for an arbitrary linear evolution equation in one space dimension with spatial derivatives of order n. We characterize a class of such problems that admit a unique solution and are well posed in this sense. Such well-posed boundary value problems are obtained by prescribing N conditions at x=0 and n–N conditions at x=L, where N depends on n and on the sign of the highest-degree coefficient _n in the dispersion relation of the equation. For the problems in this class, we give a spectrally decomposed integral representation of the solution; moreover, we show that these are the only problems that admit such a representation. These results can be used to establish the well-posedness, at least locally in time, of some physically relevant nonlinear evolution equations in one space dimension.     

Uniform grid approximation of nonsmooth solutions to the mixed boundary value problem for a singularly perturbed reaction-diffusion equation in a rectangle

A mixed boundary value problem for a singularly perturbed reaction-diffusion equation in a square is considered. A Neumann condition is specified on one side of the square, and a Dirichlet condition is set on the other three. It is assumed that the coefficient of the equation, its right-hand side, and the boundary values of the desired solution or its normal derivative on the sides of the square are smooth enough to ensure the required smoothness of the solution in a closed domain outside the neighborhoods of the corner points. No compatibility conditions are assumed to hold at the corner points. Under these assumptions, the desired solution in the entire closed domain is of limited smoothness: it belongs only to the Hölder class C ^μ, where μ ∈ (0, 1) is arbitrary. In the domain, a nonuniform rectangular mesh is introduced that is refined in the boundary domain and depends on a small parameter. The numerical solution to the problem is based on the classical five-point approximation of the equation and a four-point approximation of the Neumann boundary condition. A mesh refinement rule is described under which the approximate solution converges to the exact one uniformly with respect to the small parameter in the L _∞ ^h norm. The convergence rate is O(N ^?2ln² N), where N is the number of mesh nodes in each coordinate direction. The parameter-uniform convergence of difference schemes for mixed problems without compatibility conditions at corner points was not previously analyzed.     

Iterative continuation and the solution of nonlinear two-point boundary value problems

In this paper we present a unified function theoretic approach for the numerical solution of a wide class of two-point boundary value problems. The approach generates a class of continuous analog iterative methods which are designed to overcome some of the essential difficulties encountered in the numerical treatment of two-point problems. It is shown that the methods produce convergent sequences of iterates in cases where the initial iterate (guess),x ₀, is far from the desired solution. The results of some numerical experiments using the methods on various boundary value problems are presented in a forthcoming paper.     

Strict Feasibility Conditions in Nonlinear Complementarity Problems

Strict feasibility plays an important role in the development of the theoryand algorithms of complementarity problems. In this paper, we establishsufficient conditions to ensure strict feasibility of a nonlinearcomplementarity problem. Our analysis method, based on a newly introducedconcept of -exceptional sequence, can be viewed as a unified approachfor proving the existence of a strictly feasible point. Some equivalentconditions of strict feasibility are also developed for certaincomplementarity problems. In particular, we show that aP_*-complementarity problem is strictly feasible if and only ifits solution set is nonempty and bounded.     

On a Priori Energy Estimates for Characteristic Boundary Value Problems

Motivated by the study of certain non linear free-boundary value problems for hyperbolic systems of partial differential equations arising in Magneto-Hydrodynamics, in this paper we show that an a priori estimate of the solution to certain boundary value problems, in the conormal Sobolev space \(H^1_{ tan}\) , can be transformed into an \(L^2\) a priori estimate of the same problem.