Nonlinear Optimization

A Block Coordinate Descent Method for Regularized Multi-Convex Optimization with Applications to Nonnegative Tensor Factorization and Completion

Categories Constrained Nonlinear Optimization, Data-Mining, Nonsmooth Optimization Tags , , , , , , ,

This paper considers regularized block multi-convex optimization, where the feasible set and objective function are generally non-convex but convex in each block of variables. We review some of its interesting examples and propose a generalized block coordinate descent method. (Using proximal updates, we further allow non-convexity over some blocks.) Under certain conditions, we show that … Read more

Bounds on Eigenvalues of Matrices Arising from Interior-Point Methods

Categories Convex Optimization, Quadratic Programming Tags , , , , , , ,

Interior-point methods feature prominently among numerical methods for inequality-constrained optimization problems, and involve the need to solve a sequence of linear systems that typically become increasingly ill-conditioned with the iterations. To solve these systems, whose original form has a nonsymmetric 3×3 block structure, it is common practice to perform block Gaussian elimination and either solve … Read more

A method for weighted projections to the positive definite cone

Categories Biomedical Applications, Quadratic Programming, Semi-definite Programming Tags , , , ,

We study the numerical solution of the problem $\min_{X \ge 0} \|BX-c\|2$, where $X$ is a symmetric square matrix, and $B$ a linear operator, such that $B^*B$ is invertible. With $\rho$ the desired fractional duality gap, we prove $O(\sqrt{m}\log\rho^{-1})$ iteration complexity for a simple primal-dual interior point method directly based on those for linear programs … Read more

Complexity Analysis of Interior Point Algorithms for Non-Lipschitz and Nonconvex Minimization

Categories Applications - Science and Engineering, Constrained Nonlinear Optimization, Nonsmooth Optimization

We propose a first order interior point algorithm for a class of non-Lipschitz and nonconvex minimization problems with box constraints, which arise from applications in variable selection and regularized optimization. The objective functions of these problems are continuously differentiable typically at interior points of the feasible set. Our algorithm is easy to implement and the … Read more

A QCQP Approach to Triangulation

Categories Convex Optimization, Quadratic Programming Tags , , ,

Triangulation of a three-dimensional point from $n\ge 2$ two-dimensional images can be formulated as a quadratically constrained quadratic program. We propose an algorithm to extract candidate solutions to this problem from its semidefinite programming relaxations. We then describe a sufficient condition and a polynomial time test for certifying when such a solution is optimal. This … Read more

Superiorization: An optimization heuristic for medical physics

Categories Biomedical Applications, Constrained Nonlinear Optimization Tags , , , ,

Purpose: To describe and mathematically validate the superiorization methodology, which is a recently-developed heuristic approach to optimization, and to discuss its applicability to medical physics problem formulations that specify the desired solution (of physically given or otherwise obtained constraints) by an optimization criterion. Methods: The superiorization methodology is presented as a heuristic solver for a … Read more

Optimality conditions for the nonlinear programming problems on Riemannian manifolds

Categories Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , , , ,

In recent years, many traditional optimization methods have been successfully generalized to minimize objective functions on manifolds. In this paper, we first extend the general traditional constrained optimization problem to a nonlinear programming problem built upon a general Riemannian manifold $\mathcal{M}$, and discuss the first-order and the second-order optimality conditions. By exploiting the differential geometry … Read more

Aubin Property and Uniqueness of Solutions in Cone Constrained Optimization

Categories Complementarity and Variational Inequalities, Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , ,

We discuss conditions for the Aubin property of solutions to perturbed cone constrained programs, by using and refining results given in \cite{KlaKum02}. In particular, we show that constraint nondegeneracy and hence uniqueness of the multiplier is necessary for the Aubin property of the critical point map. Moreover, we give conditions under which the critical point … Read more

Deriving robust counterparts of nonlinear uncertain inequalities

Categories Constrained Nonlinear Optimization, Linear, Cone and Semidefinite Programming, Robust Optimization Tags , , , ,

In this paper we provide a systematic way to construct the robust counterpart of a nonlinear uncertain inequality that is concave in the uncertain parameters. We use convex analysis (support functions, conjugate functions, Fenchel duality) and conic duality in order to convert the robust counterpart into an explicit and computationally tractable set of constraints. It … Read more