-
作者：Liu, Hongcheng; Yao, Tao; Li, Runze; Ye, Yinyu
作者单位：Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park; Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park; Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park; Stanford University
摘要：This paper concerns the folded concave penalized sparse linear regression (FCPSLR), a class of popular sparse recovery methods. Although FCPSLR yields desirable recovery performance when solved globally, computing a global solution is NP-complete. Despite some existing statistical performance analyses on local minimizers or on specific FCPSLR-based learning algorithms, it still remains open questions whether local solutions that are known to admit fully polynomial-time approximation schemes (F...
-
作者：Basu, Amitabh; Hildebrand, Robert; Koppe, Matthias
作者单位：Johns Hopkins University; International Business Machines (IBM); IBM USA; University of California System; University of California Davis
摘要：We develop foundational tools for classifying the extreme valid functions for the k-dimensional infinite group problem. In particular, we present the general regular solution to Cauchy's additive functional equation on restricted lower-dimensional convex domains. This provides a k-dimensional generalization of the so-called Interval Lemma, allowing us to deduce affine properties of the function from certain additivity relations. Next, we study the discrete geometry of additivity domains of pie...
-
作者：Sitters, Rene
作者单位：Vrije Universiteit Amsterdam; Centrum Wiskunde & Informatica (CWI)
摘要：We show that minimizing the average job completion time on unrelated machines is -hard if preemption of jobs is allowed. This provides one of the last missing pieces in the complexity classification of machine scheduling with (weighted) sum of completion times objective. The proof is based on a mixed integer linear program. This means that verification of the reduction is partly done by an ILP-solver. This gives a concise proof which is easy to verify. In addition, we give a deterministic 1.69...
-
作者：Le Bodic, Pierre; Nemhauser, George
作者单位：Monash University; University System of Georgia; Georgia Institute of Technology
-
作者：Rosat, Samuel; Elhallaoui, Issmail; Soumis, Francois; Lodi, Andrea
作者单位：Universite de Montreal; Universite de Montreal; Polytechnique Montreal
摘要：This paper concentrates on the addition of cutting planes to the integral simplex using decomposition (ISUD) of Zaghrouti et al. (Oper Res 62(2):435-449, 2014). This method solves the set partitioning problem by iteratively improving an existing feasible solution. We present the algorithm in a primal language and relate it to existing augmenting methods. The resulting theoretical properties, stronger than the ones already known, simplify termination proofs and deepen the geometrical insights o...
-
作者：Modaresi, Sina; Vielma, Juan Pablo
作者单位：Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh; Massachusetts Institute of Technology (MIT)
摘要：In this paper we consider an aggregation technique introduced by YA +/- ldA +/- ran (J Math Control Inf 26:417-450, 2009) to study the convex hull of regions defined by two quadratic inequalities or by a conic quadratic and a quadratic inequality. YA +/- ldA +/- ran (2009) shows how to characterize the convex hull of open sets defined by two strict quadratic inequalities using Linear Matrix Inequalities. We show how this aggregation technique can be easily extended to yield valid conic quadrat...
-
作者：Toriello, Alejandro; Uhan, Nelson A.
作者单位：University System of Georgia; Georgia Institute of Technology; United States Department of Defense; United States Navy; United States Naval Academy
摘要：Motivated by situations in which independent agents wish to cooperate in some uncertain endeavor over time, we study dynamic linear programming games, which generalize classical linear production games to multi-period settings under uncertainty. We specifically consider that players may have risk-averse attitudes towards uncertainty, and model this risk aversion using coherent conditional risk measures. For this setting, we study the strong sequential core, a natural extension of the core to d...
-
作者：Birgin, E. G.; Gardenghi, J. L.; Martinez, J. M.; Santos, S. A.; Toint, Ph. L.
作者单位：Universidade de Sao Paulo; Universidade Estadual de Campinas; University of Namur; University of Namur
摘要：The worst-case evaluation complexity for smooth (possibly nonconvex) unconstrained optimization is considered. It is shown that, if one is willing to use derivatives of the objective function up to order p (for p >= 1) and to assume Lipschitz continuity of the p-th derivative, then an epsilon-approximate first-order critical point can be computed in at most O(epsilon -((p+1)/p)) evaluations of the problem's objective function and its derivatives. This generalizes and subsumes results known for...
-
作者：Consolini, Luca; Locatelli, Marco
作者单位：University of Parma
摘要：The complexity of quadratic programming problems with two quadratic constraints is an open problem. In this paper we show that when one constraint is a ball constraint and the Hessian of the quadratic function defining the other constraint is positive definite, then, under quite general conditions, the problem can be solved in polynomial time in the real-number model of computation through an approach based on the analysis of the dual space of the Lagrange multipliers. However, the degree of t...
-
作者：Schmidt, Mark; Le Roux, Nicolas; Bach, Francis
作者单位：University of British Columbia
