-
作者：Shtern, Shimrit; Ben-Tal, Aharon
作者单位：Technion Israel Institute of Technology; Tilburg University; Columbia University
摘要：Tracking problems are prevalent in the present day GPS and video systems. The problem of target tracking is a specific case of dynamic linear system estimation with additive noise. The most widely used filter for these systems is the Kalman filter (KF). The optimality of the KF and similar Bayesian filters is guaranteed under particular probabilistic assumptions. However, in practice, and specifically in applications such as tracking, these probabilistic assumptions are not realistic; indeed, ...
-
作者：Kogan, Alexander; Lejeune, Miguel A.; Luedtke, James
作者单位：Rutgers University System; Rutgers University Newark; Rutgers University New Brunswick; George Washington University; University of Wisconsin System; University of Wisconsin Madison
-
作者：Aronna, M. S.; Bonnans, J. F.; Goh, B. S.
作者单位：Getulio Vargas Foundation; Institut Polytechnique de Paris; Ecole Polytechnique; Institut Polytechnique de Paris; ENSTA Paris; Ecole Polytechnique; Curtin University Malaysia
摘要：In this article we establish new second order necessary and sufficient optimality conditions for a class of control-affine problems with a scalar control and a scalar state constraint. These optimality conditions extend to the constrained state framework the Goh transform, which is the classical tool for obtaining an extension of the Legendre condition.
-
作者：Dobre, Cristian; Duer, Mirjam; Frerick, Leonhard; Vallentin, Frank
作者单位：Wageningen University & Research; Universitat Trier; University of Cologne
摘要：In the last decade, copositive formulations have been proposed for a variety of combinatorial optimization problems, for example the stability number (independence number). In this paper, we generalize this approach to infinite graphs and show that the stability number of an infinite graph is the optimal solution of some infinite-dimensional copositive program. For this we develop a duality theory between the primal convex cone of copositive kernels and the dual convex cone of completely posit...
-
作者：Garber, Dan; Hazan, Elad
作者单位：Technion Israel Institute of Technology
摘要：We consider semidefinite optimization in a saddle point formulation where the primal solution is in the spectrahedron and the dual solution is a distribution over affine functions. We present an approximation algorithm for this problem that runs in sublinear time in the size of the data. To the best of our knowledge, this is the first algorithm to achieve this. Our algorithm is also guaranteed to produce low-rank solutions. We further prove lower bounds on the running time of any algorithm for...
-
作者：Protasov, Vladimir Yu.
作者单位：Lomonosov Moscow State University
摘要：We develop an iterative optimization method for finding the maximal and minimal spectral radius of a matrix over a compact set of nonnegative matrices. We consider matrix sets with product structure, i.e., all rows are chosen independently from given compact sets (row uncertainty sets). If all the uncertainty sets are finite or polyhedral, the algorithm finds the matrix with maximal/minimal spectral radius within a few iterations. It is proved that the algorithm avoids cycling and terminates w...
-
作者：Hirai, Hiroshi
作者单位：University of Tokyo
摘要：A -extension of graph is a metric on a set containing the vertex set of such that extends the shortest path metric of and for all there exists a vertex in with . The minimum -extension problem 0-Ext on is: given a set and a nonnegative cost function defined on the set of all pairs of , find a -extension of with minimum. The -extension problem generalizes a number of basic combinatorial optimization problems, such as minimum -cut problem and multiway cut problem. Karzanov proved the polynomial ...
-
作者：Nagarajan, Viswanath; Shi, Cong
作者单位：University of Michigan System; University of Michigan
摘要：We consider the following two deterministic inventory optimization problems with non-stationary demands. Submodular joint replenishment problem. This involves multiple item types and a single retailer who faces demands over a finite planning horizon of T periods. In each time period, any subset of item-types can be ordered incurring a joint ordering cost which is submodular. Moreover, items can be held in inventory while incurring a holding cost. The objective is to find a sequence of orders t...
-
作者：Dorsch, Dominik; Gomez, Walter; Shikhman, Vladimir
作者单位：RWTH Aachen University; Universidad de La Frontera; Universite Catholique Louvain
摘要：We derive a new genericity result for nonlinear semidefinite programming (NLSDP). Namely, almost all linear perturbations of a given NLSDP are shown to be nondegenerate. Here, nondegeneracy for NLSDP refers to the transversality constraint qualification, strict complementarity and second-order sufficient condition. Due to the presence of the second-order sufficient condition, our result is a nontrivial extension of the corresponding results for linear semidefinite programs (SDP) from Alizadeh ...
-
作者：de Oliveira, Welington; Solodov, Mikhail
摘要：We propose a bundle method for minimizing nonsmooth convex functions that combines both the level and the proximal stabilizations. Most bundle algorithms use a cutting-plane model of the objective function to formulate a subproblem whose solution gives the next iterate. Proximal bundle methods employ the model in the objective function of the subproblem, while level methods put the model in the subproblem's constraints. The proposed algorithm defines new iterates by solving a subproblem that e...
