We provide Completely Positive and Copositive Programming formulations for the Constrained Fractional Quadratic Problem (CFQP) and Standard Fractional Quadratic Problem (StFQP). Based on these formulations, Semidefinite Programming (SDP) relaxations are derived for finding good lower bounds to these fractional programs, which are used in a global optimization branch-and-bound approach. Applications of the CFQP and StFQP, … Read more
We provide a probabilistic comparison of split and type 1 triangle cuts for mixed-integer programs with two rows and two integer variables. Under a simple probabilistic model of the problem parameters, we show that a simple split cut, i.e. a Gomory cut, is more likely to be better than a type 1 triangle cut in … Read more
In this paper we propose a heuristic approach for the problem of packing equal rectangles within a convex region. The approach is based on an Iterated Local Search scheme (or, using a terminology employed for continuous problems, a Monotonic Basin Hopping), in which the key step is the perturbation move. Different perturbation moves, both combinatorial … Read more
We address bilevel programming problems when the derivatives of both the upper and the lower level objective functions are unavailable. The core algorithms used for both levels are trust-region interpolation-based methods, using minimum Frobenius norm quadratic models when the number of points is smaller than the number of basis components. We take advantage of the … Read more
In this paper we prove that direct search of directional type shares the worst case complexity bound of steepest descent when sufficient decrease is imposed using a quadratic function of the step size parameter. This result is proved under smoothness of the objective function and using a framework of the type of GSS (generating set … Read more
In this paper, we derive explicit characterizations of convex and concave envelopes of several nonlinear functions over various subsets of a hyper-rectangle. These envelopes are obtained by identifying polyhedral subdivisions of the hyper-rectangle over which the envelopes can be constructed easily. In particular, we use these techniques to derive, in closed-form, the concave envelopes of … Read more
In practical applications of optimization it is common to have several conflicting objective functions to optimize. Frequently, these functions are subject to noise or can be of black-box type, preventing the use of derivative-based techniques. We propose a novel multiobjective derivative-free methodology, calling it direct multisearch (DMS), which does not aggregate any of the objective … Read more
Abstract. NCSOStools is a Matlab toolbox for – symbolic computation with polynomials in noncommuting variables; – constructing and solving sum of hermitian squares (with commutators) programs for polynomials in noncommuting variables. It can be used in combination with semidefi nite programming software, such as SeDuMi, SDPA or SDPT3 to solve these constructed programs. This paper provides … Read more
Let S be a subset of integer points that satisfy the property that $conv(S) \cap Z^n = S$. Then a convex set K is called an S-free convex set if $int(K) \cap S = \emptyset$. A maximal S-free convex set is an S-free convex set that is not properly contained in any S-free convex set. … Read more
We develop a natural generalization to the notion of the central path — a notion that lies at the heart of interior-point methods for convex optimization. The generalization is accomplished via the “derivative cones” of a “hyperbolicity cone,” the derivatives being direct and mathematically-appealing relaxations of the underlying (hyperbolic) conic constraint, be it the non-negative … Read more