-
作者：Levi, Retsef; Shmoys, David B.; Swamy, Chaitanya
作者单位：Massachusetts Institute of Technology (MIT); Cornell University; Cornell University; University of Waterloo
摘要：In the capacitated facility location problem with hard capacities, we are given a set of facilities, F, and a set of clients D in a common metric space. Each facility i has a facility opening cost f(i) and capacity u(i) that specifies the maximum number of clients that may be assigned to this facility. We want to open some facilities from the set F and assign each client to an open facility so that at most ui clients are assigned to any open facility i. The cost of assigning client j to facili...
-
作者：Royset, J. O.
作者单位：United States Department of Defense; United States Navy; Naval Postgraduate School
摘要：Optimality functions define stationarity in nonlinear programming, semi-infinite optimization, and optimal control in some sense. In this paper, we consider optimality functions for stochastic programs with nonlinear, possibly nonconvex, expected value objective and constraint functions. We show that an optimality function directly relates to the difference in function values at a candidate point and a local minimizer. We construct confidence intervals for the value of the optimality function ...
-
作者：Hu, Jing; Mitchell, John E.; Pang, Jong-Shi
作者单位：Rensselaer Polytechnic Institute; University of Illinois System; University of Illinois Urbana-Champaign
摘要：Filling a gap in nonconvex quadratic programming, this paper shows that the global resolution of a feasible quadratic program (QP), which is not known to be bounded or unbounded below, can be accomplished in finite time by solving two linear programs with linear complementarity constraints, i.e., LPCCs. Specifically, this task can be divided into two LPCCs: the first confirms whether the QP is bounded below on the feasible set and, if not, computes a feasible ray on which the QP is unbounded; ...
-
作者：Fletcher, Roger
作者单位：University of Dundee
摘要：The possibilities inherent in steepest descent methods have been considerably amplified by the introduction of the Barzilai-Borwein choice of step-size, and other related ideas. These methods have proved to be competitive with conjugate gradient methods for the minimization of large dimension unconstrained minimization problems. This paper suggests a method which is able to take advantage of the availability of a few additional 'long' vectors of storage to achieve a significant improvement in ...
-
作者：Wiesemann, Wolfram; Kuhn, Daniel; Rustem, Berc
作者单位：Imperial College London
摘要：Temporal networks describe workflows of time-consuming tasks whose processing order is constrained by precedence relations. In many cases, the durations of the network tasks can be influenced by the assignment of resources. This leads to the problem of selecting an 'optimal' resource allocation, where optimality is measured by network characteristics such as the makespan (i.e., the time required to complete all tasks). In this paper we study a robust resource allocation problem where the task ...
-
作者：Liu, Yong-Jin; Sun, Defeng; Toh, Kim-Chuan
作者单位：National University of Singapore; National University of Singapore; Shenyang Aerospace University; Nanyang Technological University; Massachusetts Institute of Technology (MIT); Singapore-MIT Alliance for Research & Technology Centre (SMART)
摘要：The nuclear norm minimization problem is to find a matrix with the minimum nuclear norm subject to linear and second order cone constraints. Such a problem often arises from the convex relaxation of a rank minimization problem with noisy data, and arises in many fields of engineering and science. In this paper, we study inexact proximal point algorithms in the primal, dual and primal-dual forms for solving the nuclear norm minimization with linear equality and second order cone constraints. We...
-
作者：Agnetis, Alessandro; Grande, Enrico; Pacifici, Andrea
作者单位：University of Rome Tor Vergata; University of Siena
摘要：We address the exact resolution of a Mixed Integer Non Linear Programming model where resources can be activated in order to satisfy a demand (a covering constraint) while minimizing total cost. For each resource, there is a fixed activation cost and a variable cost, expressed by means of latency functions. We prove that this problem is NP-hard even for linear latency functions. A branch and bound algorithm is devised, having two important features. First, a dual bound (equal to that obtained ...
-
作者：Dostal, Zdenk; Kozubek, Toma
作者单位：Technical University of Ostrava
摘要：We propose a modification of our MPGP algorithm for the solution of bound constrained quadratic programming problems so that it can be used for minimization of a strictly convex quadratic function subject to separable convex constraints. Our active set based algorithm explores the faces by conjugate gradients and changes the active sets and active variables by gradient projections, possibly with the superrelaxation steplength. The error estimate in terms of extreme eigenvalues guarantees that ...
-
作者：Iiduka, Hideaki
摘要：We discuss the variational inequality problem for a continuous operator over the fixed point set of a nonexpansive mapping. One application of this problem is a power control for a direct-sequence code-division multiple-access data network. For such a power control, each user terminal has to be able to quickly transmit at an ideal power level such that it can get a sufficient signal-to-interference-plus-noise ratio and achieve the required quality of service. Iterative algorithms to solve this...
-
作者：Sager, Sebastian; Bock, Hans Georg; Diehl, Moritz
作者单位：Ruprecht Karls University Heidelberg; KU Leuven
摘要：We extend recent work on nonlinear optimal control problems with integer restrictions on some of the control functions (mixed-integer optimal control problems, MIOCP). We improve a theorem (Sager et al. in Math Program 118(1): 109-149, 2009) that states that the solution of a relaxed and convexified problem can be approximated with arbitrary precision by a solution fulfilling the integer requirements. Unlike in previous publications the new proof avoids the usage of the Krein-Milman theorem, w...
