Search

The inverse radiative transfer problem finds broad applications in medical imaging, atmospheric science, astronomy, and many other areas. This problem intends to recover optical properties, denoted as absorption and the scattering coefficient of the media, through source-measurement pairs. A typical computational approach is to form the inverse problem as a PDE-constraint optimization, with the minimizer being the to-be-recovered coefficients. The method is tested to be efficient in practice, but it lacks analytical justification: there is no guarantee of the existence or uniqueness of the minimizer, and the error is hard to quantify. In this paper, we provide a different algorithm by levering the ideas from singular decomposition analysis. Our approach is to decompose the measurements into three components, two of which encode the information of the two coefficients, respectively. We then split the optimization problem into two subproblems and use those two components to recover the absorption and scattering coefficients separately. In this regard, we prove the well-posedness of the new optimization, and the error could be quantified with better precision. In the end, we incorporate the diffusive scaling and show that the error is harder to control in the diffusive limit. [ABSTRACT FROM AUTHOR]

In the literature, error bound conditions have been widely used to study the linear convergence rates of various first-order algorithms. Most of the literature focuses on how to ensure these error bound conditions, usually posing numerous assumptions or special structures on the model under discussion. In this paper, we focus on the alternating direction method of multipliers (ADMM) and show that the known error bound conditions for studying the ADMM's linear convergence rate can indeed be further weakened if the error bound is studied over the specific iterative sequence it generates. An error bound condition based on ADMM's iterations is thus proposed, and linear convergence under this condition is proved. Furthermore, taking advantage of a specific feature of ADMM's iterative scheme by which part of the perturbation is automatically zero, we propose the so-called partial error bound condition, which is weaker than known error bound conditions in the literature, and we derive the linear convergence rate of ADMM. We further show that this partial error bound condition is useful for interpreting the difference if the two primal variables are updated in different orders when implementing the ADMM. This has been empirically observed in the literature, yet no theory is known. [ABSTRACT FROM AUTHOR]

This paper deals with shape optimization for elastic materials under stochastic loads. It transfers the paradigm of stochastic dominance, which allows for flexible risk aversion via comparison with benchmark random variables, from finite-dimensional stochastic programming to shape optimization. Rather than handling risk aversion in the objective, this enables risk aversion by including dominance constraints that single out subsets of nonanticipative shapes which compare favorably to a chosen stochastic benchmark. This new class of stochastic shape optimization problems arises by optimizing over such feasible sets. The analytical description is built on risk-averse cost measures. The actual optimized cost functional measures the volume and perimeter of the structure. In the implementation, shapes are represented by a phase field which permits an easy estimate of a regularized perimeter. The analytical description and the numerical implementation of dominance constraints are built on risk-averse measures for the cost functional. A suitable numerical discretization is obtained using finite elements both for the displacement and the phase field function. Different numerical experiments demonstrate the potential of the proposed stochastic shape optimization model and in particular the impact of high variability of forces or probabilities in the different realizations. [ABSTRACT FROM AUTHOR]

In this paper we consider a shape optimization problem in which the data in the cost functional and in the state equation may change sign, and so no monotonicity assumption is satisfied. Nevertheless, we are able to prove that an optimal domain exists. We also deduce some necessary conditions of optimality for the optimal domain. The results are applied to show the existence of an optimal domain in the case where the cost functional is completely identified, while the right-hand side in the state equation is only known up to a probability P in the space L2(D). [ABSTRACT FROM AUTHOR]

Cubic-regularization and trust-region methods with worst-case first-order complexity O(ε-3/2) and worst-case second-order complexity O(ε-3/2) have been developed in the last few years. In this paper it is proved that the same complexities are achieved by means of a quadratic-regularization method with a cubic sufficient-descent condition instead of the more usual predicted-reduction based descent. Asymptotic convergence and order of convergence results are also presented. Finally, some numerical experiments comparing the new algorithm with a well-established quadratic regularization method are shown. [ABSTRACT FROM AUTHOR]

The paper considers the problem of absolute stability of systems with time-periodic nonlinear blocks. The approach presented in this paper is based on the so-called quadratic criterion and relies on integral-quadratic inequalities (constraints), which also involve time delays. The results are given in the frequency domain. The paper also includes geometric interpretation and numerical treatment of the new stability criteria. [ABSTRACT FROM AUTHOR]

The object of this paper is to revisit the results of Bernhard [J. Optim. Theory Appl., 27 (1979), pp. 51-69] on two-person zero-sum linear quadratic differential games and generalize them to utility functions without positivity assumptions on the matrices acting on the state variable and to linear dynamics with bounded measurable data matrices. Our paper specializes to state feedback via Lebesgue measurable affine closed loop strategies with possible non-L2-integrable singularities. After sharpening the recent results of Delfour [SIAM J. Control Optim., 46 (2007), pp. 750-774] on the characterization of the open loop lower and upper values of the game, it first deals with L2-integrable closed loop strategies and then with the larger family of strategies that may have non-L2-integrable singularities. A new conceptually meaningful and mathematically precise definition of a closed loop saddle point is introduced to simultaneously handle state feedbacks of the L2 type and smooth locally bounded ones, except at most in the neighborhood of finitely many instants of time. A necessary and sufficient condition is that the free end problem be normalizable almost everywhere. This relaxation of the classical notion allows singularities in the feedback law at an infinite number of instants, including accumulation points that are not isolated. A complete classification of closed loop saddle points is given in terms of the convexity/concavity properties of the utility function, and connections are given with the open loop lower value, upper value, and value of the game. [ABSTRACT FROM AUTHOR]

This paper analyzes a class of singular control problems for which value functions are not necessarily smooth. Necessary and sufficient conditions for the well-known smooth fit principle, along with the regularity of the value functions, are given. Explicit solutions for the optimal policy and for the value functions are provided. In particular, when payoff functions satisfy the usual Inada conditions, the boundaries between action and continuation regions are smooth and strictly monotonic, as postulated and exploited in the existing literature (see [A. K. Dixit and R. S. Pindyck, Investment under Uncertainty, Princeton University Press, Princeton, NJ, 1994]; [M. H. A. Davis et al., Adv. in Appl. Probab., 19 (1987), pp. 156-176]; [T. Ø. Kobila, Stochastics Stochastics Rep., 43 (1993), pp. 29-63]; [A. B. Abel and J. C. Eberly, J. Econom. Dynam. Control, 21 (1997), pp. 831-852]; [A. Øksendal, Finance Stoch., 4 (2000), pp. 223-250]; [J. A. Scheinkman and T. Zariphopoulou, J. Econom. Theory, 96 (2001), pp. 180-207]; [A. Merhi and M. Zervos, SIAM J. Control Optim., 46 (2007), pp. 839-876]; and [L. H. Alvarez, A General Theory of Optimal Capacity Accumulation under Price Uncertainty and Costly Reversibility, Working Paper, Helsinki Center of Economic Research, Helsinski, Finland, 2006]). Illustrative examples for both smooth and nonsmooth cases are discussed to emphasize the pitfall of solving singular control problems with a priori smoothness assumptions. [ABSTRACT FROM AUTHOR]

Dissipative systems have played an important role in the analysis and synthesis of dynamical systems. The commonly used definition of dissipativity often requires an assumption on the controllability of the system. In this paper we use a definition of dissipativity that is slightly different (and less often used in the literature) to study a linear, time-invariant, possibly uncontrollable dynamical system. We provide a necessary and sufficient condition for an uncontrollable system to be strictly dissipative with respect to a supply rate under the assumption that the uncontrollable poles are not "mixed"; i.e., no pair of uncontrollable poles is symmetric about the imaginary axis. This condition is known to be related to the solvability of a Lyapunov equation; we link Lyapunov functions for autonomous systems to storage functions of an uncontrollable system. The set of storage functions for a controllable system has been shown to be a convex bounded polytope in the literature. We show that for an uncontrollable system the set of storage functions is unbounded, and that the unboundedness arises precisely due to the set of Lyapunov functions for an autonomous linear system being unbounded. Further, we show that stabilizability of a system results in this unbounded set becoming bounded from below. Positivity of storage functions is known to be very important for stability considerations because the maximum stored energy that can be drawn out is bounded when the storage function is positive. In this paper we establish the link between stabilizability of an uncontrollable system and existence of positive definite storage functions. In most of the results in this paper, we assume that no pair of the uncontrollable poles of the system is symmetric about the imaginary axis; we explore the extent of necessity of this assumption and also prove some results for the case of single output systems regarding this necessity. [ABSTRACT FROM AUTHOR]

This paper presents applications of an optimization-based multigrid method to state constrained aerodynamic shape optimization problems. The one-shot simultaneous pseudo-timestepping method has been applied successfully to such problems, reducing the cost of computation up to 70% from that of a traditional gradient method. However, the number of optimization iterations is comparatively large in this method since we update the design parameters in each time-step of state and costate runs. In this paper we use an optimization-based multigrid strategy to reduce the total number of optimization iterations while keeping the idea of the one-shot pseudo-time-stepping method. Design examples of drag reduction with constant lift, together with geometrical constraints, for an RAE2822 airfoil are included. The total effort required for convergence of the optimization problem is between four and six times that of forward simulation runs depending on computational grid size. [ABSTRACT FROM AUTHOR]

In this paper the authors study a model for the optimal operation of a bank or insurance company which was recently introduced by Peura and Keppo. The model generalizes a previous one of Milne and Robertson by allowing the bank to raise capital as well as to pay out dividends. Optimal operation of the bank is determined by solving an optimal control problem. In this paper it is shown that the solution of the optimal control problem proposed by Peura and Keppo exists for all values of the parameters and is unique. [ABSTRACT FROM AUTHOR]

Relaxed controls have proved to be very useful in studying the existence of optimal controls in optimal control theory. Many positive results have been obtained in the literature. However, negative results have also made their rare appearances. The optimal control problem considered in this paper looks quite simple. Yet, by treating such a problem, we can get interesting results, substantiating our idea as to whether an optimal control exists or not. In our opinion, the method used in the paper can be applied to more generalized cases. [ABSTRACT FROM AUTHOR]

This paper considers an extension of the Merton optimal investment problem to the case where the risky asset is subject to transaction costs and capital gains taxes. We derive the dynamic programming equation in the sense of constrained viscosity solutions. We next introduce a family of functions (Vϵ)ϵ>0, which converges to our value function uniformly on compact subsets, and which is characterized as the unique constrained viscosity solution of an approximation of our dynamic programming equation. In particular, this result justifies the numerical results reported in the accompanying paper [I. Ben Tahar, H. M. Soner, and N. Touzi (2005), Modeling Continuous-Time Financial Markets with Capital Gains Taxes, preprint, http://www.cmap.polytechnique.fr/~touzi/bst06.pdf]. [ABSTRACT FROM AUTHOR]

In this paper, we study some optimal control problems governed by certain semilinear parabolic equations with K-approximate periodic solutions. We first prove the existence and uniqueness theorems for K-approximate periodic solutions of the equations. We then use these results to establish the qualified Pontryagin maximum principle. The existence for such optimal controls is also investigated in the paper. [ABSTRACT FROM AUTHOR]

This paper deals with a problem of guaranteed (robust) financial decision-making under model uncertainty. An efficient method is proposed for determining optimal robust portfolios of risky financial instruments in the presence of ambiguity (uncertainty) on the probabilistic model of the returns. Specifically, it is assumed that a nominal discrete return distribution is given, while the true distribution is only known to lie within a distance d from the nominal one, where the distance is measured according to the Kullback-Leibler divergence. The goal in this setting is to compute portfolios that are worst-case optimal in the mean-risk sense, that is, to determine portfolios that minimize the maximum with respect to all the allowable distributions of a weighted risk-mean objective. The analysis in the paper considers both the standard variance measure of risk and the absolute deviation measure. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of minimization of a nonsmooth function under general nonsmooth constraints when no derivatives of the objective or constraint functions are available. We introduce the mesh adaptive direct search (MADS) class of algorithms which extends the generalized pattern search (GPS) class by allowing local exploration, called polling, in an asymptotically dense set of directions in the space of optimization variables. This means that under certain hypotheses, including a weak constraint qualification due to Rockafellar, MADS can treat constraints by the extreme barrier approach of setting the objective to infinity for infeasible points and treating the problem as unconstrained. The main GPS convergence result is to identify limit points x0302;, where the Clarke generalized derivatives are nonnegative in a finite set of directions, called refining directions. Although in the unconstrained case, nonnegative combinations of these directions span the whole space, the fact that there can only be finitely many GPS refining directions limits rigorous justification of the barrier approach to finitely many linear constraints for GPS. The main result of this paper is that the general MADS framework is flexible enough to allow the generation of an asymptotically dense set of refining directions along which the Clarke derivatives are nonnegative. We propose an instance of MADS for which the refining directions are dense in the hypertangent cone at x0302; with probability 1 whenever the iterates associated with the refining directions converge to a single x0302;. The instance of MADS is compared to versions of GPS on some test problems. We also illustrate the limitation of our results with examples. [ABSTRACT FROM AUTHOR]

In this paper we use the penalty approach to study three constrained minimization problems. A penalty function is said to have the exact penalty property [J.-B. Hiriart-Urruty and C. Lemarechal, Convex Analysis and Minimization Algorithms, 2 vols., Springer-Verlag, Berlin, 1993] if there exists a penalty coefficient for which a solution of an unconstrained penalized problem is a solution of the corresponding constrained problem. In this paper we establish a very simple sufficient condition for the exact penalty property. [ABSTRACT FROM AUTHOR]

This paper presents a new verified optimization method for the problem of finding the densest packings of nonoverlapping equal circles in a square. In order to provide reliable numerical results, the developed algorithm is based on interval analysis. As one of the most efficient parts of the algorithm, an interval-based version of a previous elimination procedure is introduced. This method represents the remaining areas still of interest as polygons fully calculated in a reliable way. Currently the most promising strategy of finding optimal circle packing configurations is to partition the original problem into subproblems. Still, as a result of the highly increasing number of subproblems, earlier computer-aided methods were not able to solve problem instances where the number of circles was greater than 27. The present paper provides a carefully developed technique resolving this difficulty by eliminating large groups of subproblems together. As a demonstration of the capabilities of the new algorithm the problems of packing 28, 29, and 30 circles were solved within very tight tolerance values. Our verified procedure decreased the uncertainty in the location of the optimal packings by more than 700 orders of magnitude in all cases. [ABSTRACT FROM AUTHOR]

The focal point of this paper is the probabilistically constrained linear program (PCLP) and how it can be applied to control system, design under risk constraints. The PCLP is the counterpart of the classical linear program, where it is assumed that there is random uncertainty in the constraints and, therefore, the deterministic constraints are replaced by probabilistic ones. It is shown that for a wide class of probability density functions, called log-concave symmetric densities, the PCLP is a convex program. An equivalent formulation of the PCLP is also presented which provides insight into numerical implementation. This concept is applied to control system design. It is shown how the results in this paper can be applied to the design of controllers for discrete-time systems to obtain a closed loop system with a well-defined risk of violating the so-called property of svperstability. Furthermore, we address the problem of risk-adjusted pole placement. [ABSTRACT FROM AUTHOR]

This paper contains a new convergence analysis for the Lewis and Torczon generalized pattern search (GPS) class of methods for unconstrained and linearly constrained optimization. This analysis is motivated by a desire to understand the successful behavior of the algorithm under hypotheses that are satisfied by many practical problems. Specifically, even if the objective function is discontinuous or extended-valued, the methods find a limit point with some minimizing properties. Simple examples show that the strength of the optimality conditions at a limit point depends not only on the algorithm, but also on the directions it uses and on the smoothness of the objective at the limit point in question. The contribution of this paper is to provide a simple convergence analysis that supplies detail about the relation of optimality conditions to objective smoothness properties and to the defining directions for the algorithm, and it gives previous results as corollaries. [ABSTRACT FROM AUTHOR]

Gauge functions significantly generalize the notion of a norm, and gauge optimization, as defined by [R. M. Freund, Math. Programming, 38 (1987), pp. 47-67], seeks the element of a convex set that is minimal with respect to a gauge function. This conceptually simple problem can be used to model a remarkable array of useful problems, including a special case of conic optimization, and related problems that arise in machine learning and signal processing. The gauge structure of these problems allows for a special kind of duality framework. This paper explores the duality framework proposed by Freund, and proposes a particular form of the problem that exposes some useful properties of the gauge optimization framework (such as the variational properties of its value function), and yet maintains most of the generality of the abstract form of gauge optimization. [ABSTRACT FROM AUTHOR]

The multiobjective optimization model studied in this paper deals with simultaneous minimization of finitely many linear functions subject to an arbitrary number of uncertain linear constraints. We first provide a radius of robust feasibility guaranteeing the feasibility of the robust counterpart under affine data parametrization. We then establish dual characterizations of robust solutions of our model that are immunized against data uncertainty by way of characterizing corresponding solutions of robust counterpart of the model. Consequently, we present robust duality theorems relating the value of the robust model with the corresponding value of its dual problem. [ABSTRACT FROM AUTHOR]

This paper deals with first- and second-order necessary optimality conditions for a class of optimal control problems governed by semilinear elliptic partial differential equations with mixed pointwise state-control constraints. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to examine whether the presence of singular configurations poses an obstruction to the small-time local controllability (STLC) and stabilizability of the attitude dynamics of a spacecraft actuated by single-gimbal control moment gyroscopes (CMGs). We identify a class of singular CMG configurations called critically singular configurations, at which the linearized dynamics fail to be controllable. Linear controllability, and hence STLC and stabilizability, hold at equilibria in which the CMG array is in a nonsingular or singular, but not critically singular, configuration. We give sufficient conditions and necessary conditions on critically singular configurations for STLC to hold. In particular, we show that STLC and stabilizability fail to hold at an equilibrium if the magnitude of the total spin angular momentum of the CMG array has a local maximum at the equilibrium. [ABSTRACT FROM AUTHOR]

This paper discusses asymptotic analysis and adaptive design of convex estimators over the Hölder class under the sup-norm risk and the pointwise risk using constrained optimization and asymptotic statistical techniques. Specifically, convex B-spline estimators are proposed to achieve uniform optimal convergence rates and adaptive procedures. The presence of the convex shape constraint complicates asymptotic performance analysis, particularly uniform convergence analysis. This in turn requires deep understanding of a family of size varying constrained optimization problems on spline coeficients. To address these issues, we establish the uniform Lipschitz property of optimal spline coeficients in the l∞-norm by exploiting the structure of underlying constrained optimization 8 problems. By using this property, polyhedral theory, and statistical techniques, we show that the convex B-spline estimator attains uniform consistency and optimal rates of convergence on the entire interval of interest over the Hölder class under the sup-norm risk and the pointwise risk. In addition, adaptive estimates are constructed under both risks when the Hölder exponent is between one and two. These estimates achieve a maximal risk within a constant factor of the minimax risk over the Hölder class. [ABSTRACT FROM AUTHOR]

Preconditioned gradient iterations for very large eigenvalue problems are efficient solvers with growing popularity. However, only for the simplest preconditioned eigensolver, namely the preconditioned gradient iteration (or preconditioned inverse iteration) with fixed step size, are sharp nonasymptotic convergence estimates known. These estimates require a properly scaled pre-conditioner. In this paper a new sharp convergence estimate is derived for the preconditioned steepest descent iteration which combines the preconditioned gradient iteration with the Rayleigh--Ritz procedure for optimal line search convergence acceleration. The new estimate always improves that of the fixed-step-size iteration. The practical importance of this new estimate is that arbitrarily scaled preconditioners can be used. The Rayleigh--Ritz procedure implicitly computes the optimal scaling constant. [ABSTRACT FROM AUTHOR]

In this paper we investigate a passivity approach to collective coordination and synchronization problems in the presence of quantized measurements and show that coordination tasks can be achieved in a practical sense for a large class of passive systems. [ABSTRACT FROM AUTHOR]

In this paper, we extend the notion of person-by-person (pbp) optimization to binary decision spaces. The novelty of our approach is the adaptation to a dynamic team context of notions borrowed from the pseudo-boolean optimization field as completely local-global or unimodal functions and submodularity. We also generalize the concept of pbp optimization to the case where groups of m decisions makers make joint decisions sequentially, which we refer to as mbm optimization. The main contribution is a description of sufficient conditions, verifiable in polynomial time, under which a pbp or an mbm optimization algorithm converges to the team-optimum. As a second contribution, we present a local and greedy algorithm characterized by approximate decision strategies (i.e., strategies based on a local state vector) that return the same decisions as in the complete information framework (where strategies are based on full state vector). As a last contribution, we also show that there exists a subclass of submodular team problems, recognizable in polynomial time, for which the pbp optimization converges for at least an opportune initialization of the algorithm. [ABSTRACT FROM AUTHOR]

This paper presents a time optimal control problem with control constraints of the rectangular type for internally controlled heat equations. An existence result of time optimal controls for such a problem is established. The rectangular type of control constraints originates from the study of time optinial control problems for ordinary differential equations. In the finite dimensional case, there is no difference between such problems with control constraints of the rectangular type and those of the ball type, from the perspective of the study on the existence of optimal controls. Interestingly, in the infinite dimensional case, the problem with control constraints of the rectangular type differs essentially from that with control constraints of the ball type. For infinite dimensional systems, the existence for time optimal controls with constraints of the ball type has already been discussed in the literature, while the study of the rectangular type has not been touched upon as far as we know. [ABSTRACT FROM AUTHOR]

This paper proposes two new constraint qualification conditions (CQs) which are useful for a unified study of CQs from both a convex analysis and a nonsmooth analysis point of view. Our CQs cover the existing CQs of Mangasarian–Fromovitz and Farkas–Minkowski types. Some sufficient conditions for the validity of the new CQs are given. Under these CQs, we derive formulae for computing and/or estimating the (basic and singular) subdifferentials of marginal/optimal value function in semi-infinite programming from some results of modern variational analysis and generalized differentiation. Examples are given to illustrate the obtained formulae. [ABSTRACT FROM AUTHOR]

The paper proposes a general theory for the treatment of a class of optimization problems that arise as a consequence of a search for the optimal replenishment schedule for finite time horizon inventory models. The decision variables in these optimization problems consist of the number of replenishment periods and the lengths of the periods. When the number of replenishment periods is fixed, it is shown that the optimization problems have a unique solution under some partial differential inequalities. Furthermore, the minimal value is convex as a function of the number of replenishment periods. This leads to a simple procedure for determining the optimal control policy. [ABSTRACT FROM AUTHOR]

We study graph properties that are testable for bounded-degree graphs in time independent of the input size. Our goal is to distinguish between graphs having a predetermined graph property and graphs that are far from every graph having that property. It is well known that in the bounded-degree graph model (where two graphs are considered "far" if they differ in ϵn edges for a positive constant ϵ), many graph properties cannot be tested even with a constant or even with a polylogarithmic number of queries. Therefore in this paper we focus our attention on testing graph properties for special classes of graphs. Specifically, we show that every hereditary graph property is testable with a constant number of queries provided that every sufficiently large induced subgraph of the input graph has poor expansion. This result implies that, for example, any hereditary property (e.g., k-colorability, H-freeness, etc.) is testable in the bounded-degree graph model for planar graphs, graphs with bounded genus, interval graphs, etc. No such results have been known before, and prior to our work, very few graph properties have been known to be testable with a constant number of queries for general graph classes in the bounded-degree graph model. [ABSTRACT FROM AUTHOR]

In this paper we study some second order conditions that may be added to the first order nessessary optimality condition 0 ∈ ∂p&fnop;(¯X) (with ∂pƒ denoting the proximal subdifferential) in order to obtain a sufficient condition for a strict local minimum for extended--real-valued, nonsmooth functions. Three different types of second order conditions are investigated, all based on a different second order subdifferential. Namely, the subhessian, the graphical derivative, and the (contingent) coderivative to the proximal subdifferential. [ABSTRACT FROM AUTHOR]

The question of determining strong convex underestimators for nonlinear functions is theoretically and practically of major interest. Unfortunately, results along these lines are quite limited as very few general procedures are at hand that can be applied to general classes of functions. In this paper we show how to reduce the question of determining a convex envelope to lower-dimensional optimization problems when the underlying function is indefinite and (n-1)-convex. Our structural result about this reduction technique enables us to give descriptions for the convex envelope of a variety of two-dimensional functions. [ABSTRACT FROM AUTHOR]

In this paper, we study one kind of stochastic recursive optimal control problem with the obstacle constraint for the cost functional described by the solution of a reflected backward stochastic differential equation. We give the dynamic programming principle for this kind of optimal control problem and show that the value function is the unique viscosity solution of the obstacle problem for the corresponding Hamilton–Jacobi–Bellman equation. [ABSTRACT FROM AUTHOR]

This paper proposes a method for finding the global infimum of a multivariate polynomial f via sum of squares (SOS) relaxation over its truncated tangency variety. This variety is truncated of the set of all points x ∈ Rn where the level sets of f are tangent to the sphere in Rn centered in the origin and with radius x. It is demonstrated that: • The infimum of f on Rn and on its truncated tangency variety coincide. • A sums of squares certificate for nonnegativity of f on its truncated tangency variety. These facts imply that we can find a natural sequence of semidefinite programs whose optimal values converge monotonically, increasing to the infimum of f. This opens up the possibility of solving previously intractable polynomial optimization problems. [ABSTRACT FROM AUTHOR]

The recently introduced proximal average of two convex functions is a convex function with many useful properties. In this paper, we introduce and systematically study the proximal average for finitely many convex functions. The basic properties of the proximal average with respect to the standard convex-analytical notions (domain, Fenchel conjugate, subdifferential, proximal mapping, epi-continuity, and others) are provided and illustrated by several examples. [ABSTRACT FROM AUTHOR]

In this paper we discuss the issue of solving stochastic optimization problems by means of sample average approximations. Our focus is on rates of convergence of estimators of optimal solutions and optimal values with respect to the sample size. This is a well-studied problem in case the samples are independent and identically distributed (i.e., when standard Monte Carlo simulation is used); here we study the case where that assumption is dropped. Broadly speaking, our results show that, under appropriate assumptions, the rates of convergence for pointwise estimators under a sampling scheme carry over to the optimization case, in the sense that convergence of approximating optimal solutions and optimal values to their true counterparts has the same rates as in pointwise estimation. We apply our results to two well-established sampling schemes, namely, Latin hypercube sampling and randomized quasi-Monte Carlo (QMC). The novelty of our work arises from the fact that, while there has been some work on the use of variance reduction techniques and QMC methods in stochastic optimization, none of the existing work--to the best of our knowledge--has provided a theoretical study on the effect of these techniques on rates of convergence for the optimization problem. We present numerical results for some two-stage stochastic programs from the literature to illustrate the discussed ideas. [ABSTRACT FROM AUTHOR]

This paper studies the relationship between the optimal value of a homogeneous quadratic optimization problem and its semidefinite programming (SDP) relaxation. We consider two quadratic optimization models: (1) min{x*Cx | x *Akx≥ 1, k = 0, 1,. . ., m, x ∈ Fn} and (2) max {x*Cx | x*Akχ ≤ 1, k = 0, 1,. . ., m, x ∈ 픞n}, where F is either the real field ℝ or the complex field ℂ, and Ak, C are symmetric matrices. For the minimization model (1), we prove that if the matrix C and all but one of the Ak's are positive semidefinite, then the ratio between the optimal value of (1) and its SDP relaxation is upper bounded by O(m²) when 픞 = ℝ, and by O(m) when 픞 = ℂ. Moreover, when two or more of the Ak's are indefinite, this ratio can be arbitrarily large. For the maximization model (2), we show that if C and at most one of the Ak's are indefinite while other Ak's are positive semidefinite, then the ratio between the optimal value of (2) and its SDP relaxation is bounded from below by O(1/ logm) for both the real and the complex case. This result improves the bound based on the so-called approximate S-Lemma of Ben-Tal, Nemirovski, and Roos [SIAM J. Optim., 13 (2002), pp. 535-560]. When two or more of the Ak's in (2) are indefinite, we derive a general bound in terms of the problem data and the SDP solution. For both optimization models, we present examples to show that the derived approximation bounds are essentially tight. [ABSTRACT FROM AUTHOR]

The dogleg method is a classical trust-region technique for globalizing Newton's method. While it is widely used in optimization, including large-scale optimization via truncated- Newton approaches, its implementation in general inexact Newton methods for systems of nonlinear equations can be problematic. In this paper, we first outline a very general dogleg method suitable for the general inexact Newton context and provide a global convergence analysis for it. We then discuss certain issues that may arise with the standard dogleg implementational strategy and propose modified strategies that address them. Newton-Krylov methods have provided important motivation for this work, and we conclude with a report on numerical experiments involving a Newton-GMRES dogleg method applied to benchmark CFD problems. [ABSTRACT FROM AUTHOR]

The effective resistance between two nodes of a weighted graph is the electrical resistance seen between the nodes of a resistor network with branch conductances given by the edge weights. The effective resistance comes up in many applications and fields in addition to electrical network analysis, including, for example, Markov chains and continuous-time averaging networks. In this paper we study the problem of allocating edge weights on a given graph in order to minimize the total effective resistance, i.e., the sum of the resistances between all pairs of nodes. We show that this is a convex optimization problem and can be solved efficiently either numerically or, in some cases, analytically. We show that optimal allocation of the edge weights can reduce the total effective resistance of the graph (compared to uniform weights) by a factor that grows unboundedly with the size of the graph. We show that among all graphs with n nodes, the path has the largest value of optimal total effective resistance and the complete graph has the least. [ABSTRACT FROM AUTHOR]

In this paper, we consider the Lagrangian-dual problem of a class of convex optimization problems. We first discuss the semismoothness of the Lagrangian-dual function φ. This property is then used to investigate the second-order properties of the Moreau--Yosida regularization ? of the function φ, e.g., the semismoothness of the gradient g of the regularized function ?. We show that φ and g are piecewise C² and semismooth, respectively, for certain instances of the optimization problem. We establish a relationship between the original problem and the Fenchel conjugate of the regularization of the corresponding Lagrangian dual problem. We also find some instances of the optimization problem whose Lagrangian-dual function φ is not piecewise smooth. However, its regularized function still possesses nice second-order properties. Finally, we provide an alternative way to study the semismoothness of the gradient under the structure of the epigraph of the dual function. [ABSTRACT FROM AUTHOR]

The effective resistance between two nodes of a weighted graph is the electrical resistance seen between the nodes of a resistor network with branch conductances given by the edge weights. The effective resistance comes up in many applications and fields in addition to electrical network analysis, including, for example, Markov chains and continuous-time averaging networks. In this paper we study the problem of allocating edge weights on a given graph in order to minimize the total effective resistance, i.e., the sum of the resistances between all pairs of nodes. We show that this is a convex optimization problem and can be solved efficiently either numerically or, in some cases, analytically. We show that optimal allocation of the edge weights can reduce the total effective resistance of the graph (compared to uniform weights) by a factor that grows unboundedly with the size of the graph. We show that among all graphs with n nodes, the path has the largest value of optimal total effective resistance and the complete graph has the least. [ABSTRACT FROM AUTHOR]

This papers analyzes a class of nonlinear additive-increase multiplicative-decrease (AIMD) protocols that are widely deployed in communication networks. It is demonstrated that the use of these protocols guarantees that the system has a unique stable outcome to which it converges geometrically under all starting points. The development is based on a contraction argument and the derivation of explicit bounds on the contraction coefficient of corresponding operators in terms of the network parameters. In particular, bounds on the corresponding rate of convergence are obtained, improving upon known bounds for standard (linear) AIMD networks. [ABSTRACT FROM AUTHOR]

In this paper we establish the local exact internal controllability for the twodimensional magnetohydrodynamic equations. The needed Carleman estimate for the adjoint linearized magnetohydrodynamic equations is also obtained here. [ABSTRACT FROM AUTHOR]

The goal of this paper is to give a rigorous justification for the Hessian-constrained problems introduced in [G. Bouchitté and I. Fragal`a, Arch. Ration. Mech. Anal., 184 (2007), pp. 257-284] and to show how they are linked to the optimal design of thin plates. To that aim, we study the asymptotic behavior of a sequence of optimal elastic compliance problems in the double limit when both the maximal height of the design region and the total volume of the material tend to zero. In the vanishing volume limit, a sequence of linear constrained first order vector problems is obtained, which in turn-in the vanishing thickness limit-produces a new linear constrained problem where both first and second order gradients appear. When the load is orthogonal to the plate, only the Hessian constraint is active, and we recover as a particular case the optimization problem studied in [G. Bouchitté and I. Fragal`a, Arch. Ration. Mech. Anal., 184 (2007), pp. 257-284] (see also [T. Lewinski and J. J. Telega, Arch. Mech. (Arch. Mech. Stos.), 53 (2001), pp. 457-485]). [ABSTRACT FROM AUTHOR]

In this paper we discuss the polynomiality of a feasible version of Mehrotra's predictor-corrector algorithm whose variants have been widely used in several interior point method (IPM)-based optimization packages. A numerical example is given that shows that the adaptive choice of centering parameter and correction terms in this algorithm may lead to small steps being taken in order to keep the iterates in a large neighborhood of the central path, which is important for proving polynomial complexity properties of this method. Motivated by this example, we introduce a safeguard in Mehrotra's algorithm that keeps the iterates in the prescribed neighborhood and allows us to obtain a positive lower bound on the step size. This safeguard strategy is also used when the affine scaling direction performs poorly. We prove that the safeguarded algorithm will terminate after at most O(n2log(x°}T s° /e) iterations. By modestly modifying the corrector direction, we reduce the iteration complexity to O(nlog(x°}T s° /e). To ensure fast asymptotic convergence of the algorithm, we changed Mehrotra's updating scheme of the centering parameter slightly while keeping the safeguard. The new algorithms have the same order of iteration complexity as the safeguarded algorithms but enjoy superlinear convergence as well. Numerical results using the McIPM and LIPSOL software packages are reported. [ABSTRACT FROM AUTHOR]

In this paper, we present new convergence properties of the primal-dual method based on four types of augmented Lagrangian functions in the context of constrained global optimization. Convergence to a global optimal solution is first established for a basic primal-dual scheme under standard conditions. We then prove this convergence property for a modified augmented Lagrangian method using a safeguarding strategy without appealing to the boundedness assumption of the multiplier sequence. We further show that, under the same weaker conditions, the convergence to a global optimal solution can still be achieved by either modifying the multiplier updating rule or normalizing the multipliers in augmented Lagrangian methods. [ABSTRACT FROM AUTHOR]

This paper is concerned with the Lipschitzian behavior of the optimal set of convex semi-infinite optimization problems under continuous perturbations of the right-hand side of the constraints and linear perturbations of the objective function. In this framework we provide a sufficient condition for the metric regularity of the inverse of the optimal set mapping. This condition consists of the Slater constraint qualification, together with a certain additional requirement in the Karush-Kuhn-Tucker conditions. For linear problems this sufficient condition turns out to be also necessary for the metric regularity, and it is equivalent to some well-known stability concepts. [ABSTRACT FROM AUTHOR]

In this paper we derive a posteriori error estimates for space-time finite element discretizations of parabolic optimization problems. The provided error estimates assess the discretization error with respect to a given quantity of interest and separate the influences of different parts of the discretization (time, space, and control discretization). This allows us to set up an efficient adaptive algorithm which successively improves the accuracy of the computed solution by construction of locally refined meshes for time and space discretizations. [ABSTRACT FROM AUTHOR]