In recent years, optimization theory has been greatly impacted by the advent of sum of squares (SOS) optimization. The reliance of this technique on large-scale semidefinite programs however, has limited the scale of problems to which it can be applied. In this paper, we introduce DSOS and SDSOS optimization as linear programming and second-order cone … Read more
We present a logarithmic barrier interior-point method for solving a second-order cone programming problem. Newton’s method is used to compute the descent direction, and majorant functions are used as an efficient alternative to line search methods to determine the displacement step along the direction. The efficiency of our method is shown by presenting numerical experiments. … Read more
In this paper, a primal-dual interior-point method equipped with various selections of the displacement step are derived for solving second-order cone programming problems. We first establish the existence and uniqueness of the optimal solution of the corresponding perturbed problem and then demonstrate its convergence to the optimal solution of the original problem. Next, we present … Read more
Interior point methods (IPM) are the most popular approaches to solve Second Order Cone Optimization (SOCO) problems, due to their theoretical polynomial complexity and practical performance. In this paper, we present a warm-start method for primal-dual IPMs to reduce the number of IPM steps needed to solve SOCO problems that appear in a Branch and … Read more
We study stochastic programs where the decision-maker cannot observe the distribution of the exogenous uncertainties but has access to a finite set of independent samples from this distribution. In this setting, the goal is to find a procedure that transforms the data to an estimate of the expected cost function under the unknown data-generating distribution, … Read more
For a given triangle $\triangle ABC$, Pierre de Fermat posed around 1640 the problem of finding a point $P$ minimizing the sum $s_P$ of the Euclidean distances from $P$ to the vertices $A$, $B$, $C$. Based on geometrical arguments this problem was first solved by Torricelli shortly after, by Simpson in 1750, and by several … Read more
Recently, Chubanov proposed an interesting new polynomial-time algorithm for linear program. In this paper, we extend his algorithm to second-order cone programming. ArticleDownload View PDF
We study the convex hull of the intersection of a disjunctive set defined by parallel hyperplanes and the feasible set of a mixed integer second order cone optimization problem. We extend our prior work on disjunctive conic cuts, which has thus far been restricted to the case in which the intersection of the hyperplanes and … Read more
We consider chance-constrained binary programs, where each row of the inequalities that involve uncertainty needs to be satis ed probabilistically. Only the information of the mean and covariance matrix is available, and we solve distributionally robust chance-constrained binary programs (DCBP). Using two different ambiguity sets, we equivalently reformulate the DCBPs as 0-1 second-order cone (SOC) programs. … Read more
We study the trust region subproblem (TRS) of minimizing a nonconvex quadratic function over the unit ball with additional conic constraints. Despite having a nonconvex objective, it is known that the TRS and a number of its variants are polynomial-time solvable. In this paper, we follow a second-order cone based approach to derive an exact … Read more