-
作者：Bernauer, Martin K.; Griesse, Roland
作者单位：Technische Universitat Chemnitz
摘要：Unconstrained convex quadratic optimization problems subject to parameter perturbations are considered. A robustification approach is proposed and analyzed which reduces the sensitivity of the optimal function value with respect to the parameter. Since reducing the sensitivity and maintaining a small objective value are competing goals, strategies for balancing these two objectives are discussed. Numerical examples illustrate the approach.
-
作者：Tseng, Paul; Bomze, Immanuel M.; Schachinger, Werner
作者单位：University of Vienna; University of Washington; University of Washington Seattle
摘要：We propose a first-order interior-point method for linearly constrained smooth optimization that unifies and extends first-order affine-scaling method and replicator dynamics method for standard quadratic programming. Global convergence and, in the case of quadratic program, (sub)linear convergence rate and iterate convergence results are derived. Numerical experience on simplex constrained problems with 1000 variables is reported.
-
作者：Ben-Tal, Aharon; Bhadra, Sahely; Bhattacharyya, Chiranjib; Nath, J. Saketha
作者单位：Indian Institute of Science (IISC) - Bangalore; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Bombay
摘要：This paper studies the problem of constructing robust classifiers when the training is plagued with uncertainty. The problem is posed as a Chance-Constrained Program (CCP) which ensures that the uncertain data points are classified correctly with high probability. Unfortunately such a CCP turns out to be intractable. The key novelty is in employing Bernstein bounding schemes to relax the CCP as a convex second order cone program whose solution is guaranteed to satisfy the probabilistic constra...
-
作者：Grippo, Luigi; Palagi, Laura; Piccialli, Veronica
作者单位：University of Rome Tor Vergata; Sapienza University Rome
摘要：In this paper we consider low-rank semidefinite programming (LRSDP) relaxations of combinatorial quadratic problems that are equivalent to the maxcut problem. Using the Gramian representation of a positive semidefinite matrix, the LRSDP problem can be formulated as the nonconvex nonlinear programming problem of minimizing a quadratic function with quadratic equality constraints. For the solution of this problem we propose a continuously differentiable exact merit function that exploits the spe...
-
作者：Cornuejols, G.; Liberti, L.; Nannicini, G.
作者单位：Institut Polytechnique de Paris; Ecole Polytechnique; Carnegie Mellon University; Aix-Marseille Universite
摘要：Within the context of solving Mixed-Integer Linear Programs by a Branch-and-Cut algorithm, we propose a new strategy for branching. Computational experiments show that, on the majority of our test instances, this approach enumerates fewer nodes than traditional branching. On average, on instances that contain both integer and continuous variables the number of nodes in the enumeration tree is reduced by more than a factor of two, and computing time is comparable. On a few instances, the improv...
-
作者：de Klerk, Etienne; Dobre, Cristian; Pasechnik, Dmitrii V.
作者单位：Tilburg University; Tilburg University; Nanyang Technological University
摘要：Semidefinite programming (SDP) is one of the most active areas in mathematical programming, due to varied applications and the availability of interior point algorithms. In this paper we propose a new pre-processing technique for SDP instances that exhibit algebraic symmetry. We present computational results to show that the solution times of certain SDP instances may be greatly reduced via the new approach.
-
作者：Izmailov, A. F.; Solodov, M. V.
作者单位：Instituto Nacional de Matematica Pura e Aplicada (IMPA); Lomonosov Moscow State University
摘要：It has been previously demonstrated that in the case when a Lagrange multiplier associated to a given solution is not unique, Newton iterations [e. g., those of sequential quadratic programming (SQP)] have a tendency to converge to special multipliers, called critical multipliers (when such critical multipliers exist). This fact is of importance because critical multipliers violate the second-order sufficient optimality conditions, and this was shown to be the reason for slow convergence typic...
-
作者：So, Anthony Man-Cho
作者单位：Chinese University of Hong Kong
摘要：In this paper, we consider various moment inequalities for sums of random matrices-which are well-studied in the functional analysis and probability theory literature-and demonstrate how they can be used to obtain the best known performance guarantees for several problems in optimization. First, we show that the validity of a recent conjecture of Nemirovski is actually a direct consequence of the so-called non-commutative Khintchine's inequality in functional analysis. Using this result, we sh...
-
作者：Zanette, Arrigo; Fischetti, Matteo; Balas, Egon
作者单位：University of Padua; Carnegie Mellon University
摘要：We discuss an implementation of the lexicographic version of Gomory's fractional cutting plane method for ILP problems and of two heuristics mimicking the latter. In computational testing on a battery of MIPLIB problems we compare the performance of these variants with that of the standard Gomory algorithm, both in the single-cut and in the multi-cut (rounds of cuts) version, and show that they provide a radical improvement over the standard procedure. In particular, we report the exact soluti...
-
作者：Ames, Brendan P. W.; Vavasis, Stephen A.
作者单位：University of Waterloo
摘要：We consider the problems of finding a maximum clique in a graph and finding a maximum-edge biclique in a bipartite graph. Both problems are NP-hard. We write both problems as matrix-rank minimization and then relax them using the nuclear norm. This technique, which may be regarded as a generalization of compressive sensing, has recently been shown to be an effective way to solve rank optimization problems. In the special case that the input graph has a planted clique or biclique (i.e., a singl...
