Optimal Solutions to Relaxation in Multiple Control Problems of Sobolev Type with Nonlocal Nonlinear Fractional Differential Equations

We introduce the optimality question to the relaxation in multiple control problems described by Sobolev-type nonlinear fractional differential equations with nonlocal control conditions in Banach spaces. Moreover, we consider the minimization problem of multi-integral functionals, with integrands that are not convex in the controls, of control systems with mixed nonconvex constraints on the controls. We prove, under appropriate conditions, that the relaxation problem admits optimal solutions. Furthermore, we show that those optimal solutions are in fact limits of minimizing sequences of systems with respect to the trajectory, multicontrols, and the functional in suitable topologies.     

Interchange of infimum and integral

We prove a new interchange theorem of infimum and integral. Its distinguishing feature is, on the one hand, to establish a general framework to deal with interchange problems for nonconvex integrands and nondecomposable sets, and, on the other hand, to link the theorems of Rockafellar and Hiai-Umegaki with the one of Bouchitté-Valadier. We give an application to relaxation of nonconvex geometric integrals of Calculus of Variations.Received: 20 March 2002, Accepted: 12 March 2003, Published online: 16 May 2003     

New classes of integral functionals for which the integral representation of lower semicontinuous envelopes is valid

M.A. Sychev has recently shown that conditions necessary and sufficient for the lower semicontinuity of integral functionals with p-coercive integrands are W^1,p-quasi-convexity and the so-called matching condition (M). Condition (M) is so general that there is the conjecture that is always holds in the case of continuous integrands. The paper develops relaxation theory (construction of lower semicontinuous envelopes) under the assumption that condition (M) holds. It turns out that, in this case, the theory has very good structure. Applications of general relaxation theory to particular cases, including the theory of strong materials, are also discussed.     

An approximation theory of matrix rank minimization and its application to quadratic equations

Matrix rank minimization problems are gaining plenty of recent attention in both mathematical and engineering fields. This class of problems, arising in various and across-discipline applications, is known to be NP-hard in general. In this paper, we aim at providing an approximation theory for the rank minimization problem, and prove that a rank minimization problem can be approximated to any level of accuracy via continuous optimization (especially, linear and nonlinear semidefinite programming) problems. One of the main results in this paper shows that if the feasible set of the problem has a minimum rank element with the least Frobenius norm, then any accumulation point of solutions to the approximation problem, as the approximation parameter tends to zero, is a minimum rank solution of the original problem. The tractability under certain conditions and convex relaxation of the approximation problem are also discussed. An immediate application of this theory to the system of quadratic equations is presented in this paper. It turns out that the condition for such a system without a nonzero solution can be characterized by a rank minimization problem, and thus the proposed approximation theory can be used to establish some sufficient conditions for the system to possess only zero solution.     

Lower semicontinuity and relaxation for integral functionals with <Emphasis Type="Italic">p</Emphasis>(<Emphasis Type="Italic">x</Emphasis>)- and <Emphasis Type="Italic">p</Emphasis>(<Emphasis Type="Italic">x,u</Emphasis>)-growth

We consider the questions of lower semicontinuity and relaxation for the integral functionals satisfying the p(x)- and p(x, u)-growth conditions. Presently these functionals are actively studied in the theory of elliptic and parabolic problems and in the framework of the calculus of variations. The theory we present rests on the following results: the remarkable result of Kristensen on the characterization of homogeneous p-gradient Young measures by their summability; the earlier result of Zhang on approximating gradient Young measures with compact support; the result of Zhikov on the density in energy of regular functions for integrands with p(x)-growth; on the author’s approach to Young measures as measurable functions with values in a metric space whose metric has integral representation.     

Comparing two methods of resolving homogeneous differential inclusions

Given a compact set we consider the differential inclusion We show how to use the main idea of the method of convex integration [ N], [G], [K] (to control convergence of the gradients of a sequence of approximate solutions by appropriate selection of the sequence) to obtain an optimal existence result. We compare this result with the ones available by the Baire category approach applied to the set of admissible functions with topology. A byproduct of our result is attainment in the minimization problems with integrands L having quasiaffine quasiconvexification that was, in fact, the reason of our interest to differential inclusions. This result can be considered as a first step towards characterization of those minimization problems which are solvable for all boundary data. This problem was solved in [S1] in the scalar case m=1. Received November 5, 1998 / Accepted July 17, 2000 / Published online December 8, 2000     

A complete characterization of strong duality in nonconvex optimization with a single constraint

We first establish sufficient conditions ensuring strong duality for cone constrained nonconvex optimization problems under a generalized Slater-type condition. Such conditions allow us to cover situations where recent results cannot be applied. Afterwards, we provide a new complete characterization of strong duality for a problem with a single constraint: showing, in particular, that strong duality still holds without the standard Slater condition. This yields Lagrange multipliers characterizations of global optimality in case of (not necessarily convex) quadratic homogeneous functions after applying a generalized joint-range convexity result. Furthermore, a result which reduces a constrained minimization problem into one with a single constraint under generalized convexity assumptions, is also presented.     

Regularization of convex variational problems with applications to generalized Newtonian fluids

We study variational problems with convex integrands of very general structure by introducing certain regularizations leading to particular minimizers. In a second part we apply the method to stationary generalized Newtonian fluids which gives the existence of solutions under weak hypotheses on the dissipative potential. In particular the potential is not required to be a strictly convex function.Received: 29 July 2003     

A Modified Relaxation Scheme for Mathematical Programs with Complementarity Constraints

In this paper, we consider a mathematical program with complementarity constraints. We present a modified relaxed program for this problem, which involves less constraints than the relaxation scheme studied by Scholtes (2000). We show that the linear independence constraint qualification holds for the new relaxed problem under some mild conditions. We also consider a limiting behavior of the relaxed problem. We prove that any accumulation point of stationary points of the relaxed problems is C-stationary to the original problem under the MPEC linear independence constraint qualification and, if the Hessian matrices of the Lagrangian functions of the relaxed problems are uniformly bounded below on the corresponding tangent space, it is M-stationary. We also obtain some sufficient conditions of B-stationarity for a feasible point of the original problem. In particular, some conditions described by the eigenvalues of the Hessian matrices mentioned above are new and can be verified easily. This work was supported in part by the Scientific Research Grant-in-Aid from the Ministry of Education, Science, Sports, and Culture of Japan. The authors are grateful to an anonymous referee for critical comments.     

Vectorized adaptive quadrature in MATLAB

Adaptive quadrature codes process a collection of subintervals one at a time. We show how to process them all simultaneously and so exploit vectorization and the use of fast built-in functions and array operations that are so important to efficient computation in MATLAB. Using algebraic transformations we have made it just as easy for users to solve problems on infinite intervals and with moderate end point singularities as problems with finite intervals and smooth integrands. Piecewise-smooth integrands are handled effectively with breakpoints.     

Variational principles with integrands defined through a minimum

We revisit a systematic approach for the computation and analysis of the convex hull of non-convex integrands defined through the minimum of convex densities. It consists in reformulating the non-convex variational problem as a double minimization and exploiting appropriately the nature of optimality of the inner minimization. This requires gradient Young measures in the vector case, even if the initial problem was scalar, as the full problem is recast through the computation of a certain quasiconvexification. We illustrate this strategy by looking at two typical non-convex scalar problems. We hope to address vector problems in the near future.     

Stability of Timoshenko systems with thermal coupling on the bending moment

The Timoshenko system is a distinguished coupled pair of differential equations arising in mathematical elasticity. In the case of constant coefficients, if a damping is added in only one of its equations, it is well‐known that exponential stability holds if and only if the wave speeds of both equations are equal. In the present paper we study both non‐homogeneous and homogeneous thermoelastic problems where the model's coefficients are non‐constant and constants, respectively. Our main stability results are proved by means of a unified approach that combines local estimates of the resolvent equation in the semigroup framework with a recent control‐observability analysis for static systems. Therefore, our results complement all those on the linear case provided in [22], by extending the methodology employed in [4] to the case of Timoshenko systems with thermal coupling on the bending moment.     

Γ-convergence of free-discontinuity problems

We study the Γ-convergence of sequences of free-discontinuity functionals depending on vector-valued functions u which can be discontinuous across hypersurfaces whose shape and location are not known a priori. The main novelty of our result is that we work under very general assumptions on the integrands which, in particular, are not required to be periodic in the space variable. Further, we consider the case of surface integrands which are not bounded from below by the amplitude of the jump of u.We obtain three main results: compactness with respect to Γ-convergence, representation of the Γ-limit in an integral form and identification of its integrands, and homogenisation formulas without periodicity assumptions. In particular, the classical case of periodic homogenisation follows as a by-product of our analysis. Moreover, our result covers also the case of stochastic homogenisation, as we will show in a forthcoming paper.     

Solution of a Ball–Murat problem

A necessary and sufficient condition for the W ^{1, p} -quasi-convexity of integrands to imply the lower semicontinuity of the corresponding integral functionals with respect to the weak convergence of sequences in W ^{1, p} is obtained. It is shown that the absence of the Lavrent’ev phenomenon in minimization problems with linear boundary data is sufficient, under a minor technical assumption, for the lower semicontinuity of integral functionals with quasi-convex integrands.     

Robust solutions of quadratic optimization over single quadratic constraint under interval uncertainty

In this paper we examine non-convex quadratic optimization problems over a quadratic constraint under unknown but bounded interval perturbation of problem data in the constraint and develop criteria for characterizing robust (i.e. uncertainty-immunized) global solutions of classes of non-convex quadratic problems. Firstly, we derive robust solvability results for quadratic inequality systems under parameter uncertainty. Consequently, we obtain characterizations of robust solutions for uncertain homogeneous quadratic problems, including uncertain concave quadratic minimization problems and weighted least squares. Using homogenization, we also derive characterizations of robust solutions for non-homogeneous quadratic problems.     

Heavy traffic approximations of large deviations of feedforward queueing networks

We consider a multi-class feedforward queueing network with first come first serve queueing discipline and deterministic services and routing. The large deviation asymptotics of tail probabilities of the distribution of the workload vector can be characterized by convex path space minimization problems with non-linear constraints. So far there exists no numerical algorithm which could solve such minimization problems in a general way. When the queueing network is heavily loaded it can be approximated by a reflected Brownian motion. The large deviation asymptotics of tail probabilities of the distribution of this heavy traffic limit can again be characterized by convex path space minimization problems with non-linear constraints. However, due to their less complicated structure there exist algorithms to solve such minimization problems. In this paper we show that, as the network tends to a heavy traffic limit, the solution of the large deviation minimization problems of the network approaches the solution of the corresponding minimization problems of a reflected Brownian motion. Stated otherwise, we show that large deviation and heavy traffic asymptotics can be interchanged. We prove this result in the case when the network is initially empty. Without proof we state the corresponding result in the stationary case. We present an illuminating example with two queues. This revised version was published online in June 2006 with corrections to the Cover Date.     

Fixed point and Bregman iterative methods for matrix rank minimization

The linearly constrained matrix rank minimization problem is widely applicable in many fields such as control, signal processing and system identification. The tightest convex relaxation of this problem is the linearly constrained nuclear norm minimization. Although the latter can be cast as a semidefinite programming problem, such an approach is computationally expensive to solve when the matrices are large. In this paper, we propose fixed point and Bregman iterative algorithms for solving the nuclear norm minimization problem and prove convergence of the first of these algorithms. By using a homotopy approach together with an approximate singular value decomposition procedure, we get a very fast, robust and powerful algorithm, which we call FPCA (Fixed Point Continuation with Approximate SVD), that can solve very large matrix rank minimization problems (the code can be downloaded from http://www.columbia.edu/~sm2756/FPCA.htm for non-commercial use). Our numerical results on randomly generated and real matrix completion problems demonstrate that this algorithm is much faster and provides much better recoverability than semidefinite programming solvers such as SDPT3. For example, our algorithm can recover 1000 × 1000 matrices of rank 50 with a relative error of 10^?5 in about 3?min by sampling only 20% of the elements. We know of no other method that achieves as good recoverability. Numerical experiments on online recommendation, DNA microarray data set and image inpainting problems demonstrate the effectiveness of our algorithms.     

Nonlinear robust optimization via sequential convex bilevel programming

In this paper, we present a novel sequential convex bilevel programming algorithm for the numerical solution of structured nonlinear min–max problems which arise in the context of semi-infinite programming. Here, our main motivation are nonlinear inequality constrained robust optimization problems. In the first part of the paper, we propose a conservative approximation strategy for such nonlinear and non-convex robust optimization problems: under the assumption that an upper bound for the curvature of the inequality constraints with respect to the uncertainty is given, we show how to formulate a lower-level concave min–max problem which approximates the robust counterpart in a conservative way. This approximation turns out to be exact in some relevant special cases and can be proven to be less conservative than existing approximation techniques that are based on linearization with respect to the uncertainties. In the second part of the paper, we review existing theory on optimality conditions for nonlinear lower-level concave min–max problems which arise in the context of semi-infinite programming. Regarding the optimality conditions for the concave lower level maximization problems as a constraint of the upper level minimization problem, we end up with a structured mathematical program with complementarity constraints (MPCC). The special hierarchical structure of this MPCC can be exploited in a novel sequential convex bilevel programming algorithm. We discuss the surprisingly strong global and locally quadratic convergence properties of this method, which can in this form neither be obtained with existing SQP methods nor with interior point relaxation techniques for general MPCCs. Finally, we discuss the application fields and implementation details of the new method and demonstrate the performance with a numerical example.     

Approximation of rank function and its application to the nearest low-rank correlation matrix

The rank function rank(.) is neither continuous nor convex which brings much difficulty to the solution of rank minimization problems. In this paper, we provide a unified framework to construct the approximation functions of rank(.), and study their favorable properties. Particularly, with two families of approximation functions, we propose a convex relaxation method for the rank minimization problems with positive semidefinite cone constraints, and illustrate its application by computing the nearest low-rank correlation matrix. Numerical results indicate that this convex relaxation method is comparable with the sequential semismooth Newton method (Li and Qi in SIAM J Optim 21:1641–1666, 2011) and the majorized penalty approach (Gao and Sun, 2010) in terms of the quality of solutions.     

Choosing Optimal Parameters in Iterative Processes

We consider the problem of choosing optimal parameters in certain iterative procedures. Specifically, we are interested in finite-step processes for which it is possible to estimate the computational cost and the error relaxation in terms of the process parameters. The problem of finding the optimal process that provides the required error relaxation with a minimal total computational cost is defined and studied. To solve the problem, it is generally necessary to solve a series of mathematical programming problems with rapidly increasing dimension. We suggest two ways to avoid that difficulty. The first is to find a process that is close to the optimal process, by solving only one mathematical programming problem. The second is to define optimal processes in some special cases when this problem can be simplified. We define conditions under which processes with geometrically decreasing error are optimal or asymptotically optimal. The methods of finding parameters of such processes are also provided. We illustrate our ideas with two examples: the bilevel gradient method for unconstrained function minimization and the iterative process for solving an optimal design problem.