In the \emph{incremental knapsack problem} ($\IK$), we are given a knapsack whose capacity grows weakly as a function of time. There is a time horizon of $T$ periods and the capacity of the knapsack is $B_t$ in period $t$ for $t = 1, \ldots, T$. We are also given a set $S$ of $N$ items … Read more
The trust-region subproblem minimizes a general quadratic function over an ellipsoid and can be solved in polynomial time using a semidefinite-programming (SDP) relaxation. Intersecting the feasible set with a second ellipsoid results in the two-trust-region subproblem (TTRS). Even though TTRS can also be solved in polynomial-time, existing algorithms do not use SDP. In this paper, … Read more
We study the {\em Celis-Dennis-Tapia (CDT) problem}: minimize a non-convex quadratic function over the intersection of two ellipsoids. In contrast to the well-studied trust region problem where the feasible set is just one ellipsoid, the CDT problem is not yet fully understood. Our main objective in this paper is to narrow the difficulty gap that … Read more
We study the minimum concave cost flow problem over a two-dimensional grid network (CFG), where one dimension represents time ($1\le t\le T$) and the other dimension represents echelons ($1\le l\le L$). The concave function over each arc is given by a value oracle. We give a polynomial-time algorithm for finding the optimal solution when the … Read more
A new computational algorithm is introduced in the present study to solve multimaterial topology optimization problems. It is based on the penalization of the objective functional by the multiphase volume constrained Cahn-Hilliard energy functional. The update procedure is based on the gradient flow of the objective functional by a fractional step projected steepest descent method. … Read more
Constrained global optimization problems can be tackled by using exact penalty approaches. In a preceding paper, we proposed an exact penalty algorithm for constrained problems which combines an unconstrained global minimization technique for minimizing a non-differentiable exact penalty func- tion for given values of the penalty parameter, and an automatic updating of the penalty parameter … Read more
In this paper, we introduce a framework for derivative-free robust optimization based on the use of an efficient derivative-free optimization routine for mixed integer nonlinear problems. The proposed framework is employed to find a robust optimal design of a particular integrated circuit (namely a DC-DC converter commonly used in portable electronic devices). The proposed robust … Read more
It is known that directional differentiability of metric projection onto a closed convex set in a finite dimensional space is not guaranteed. In this paper we discuss sufficient conditions ensuring directional differentiability of such metric projections. The approach is based on a general theory of sensitivity analysis of parameterized optimization problems. ArticleDownload View PDF
Recent research in hybrid optimization shows that a combination of technologies that exploits their complementary strengths can significantly speed up computation. The use of high-level metaconstraints in the problem formulation can achieve a substantial share of these computational gains by better communicating problem structure to the solver. During the solution process, however, metaconstraints give rise … Read more
Quadratic programming problems (QPs) that arise from dynamic optimization problems typically exhibit a very particular structure. We address the ubiquitous case where these QPs are strictly convex and propose a dual Newton strategy that exploits the block-bandedness similarly to an interior-point method. Still, the proposed method features warmstarting capabilities of active-set methods. We give details … Read more