21 votes
Accepted

How do I find the minimum-area ellipse that encloses a set of points?

Theory The 1997 paper "Smallest Enclosing Ellipses -- Fast and Exact" by Gärtner and Schönherr addresses this question. The same authors provide a C++ implementation in their 1998 paper &...
user avatar
  • 3,091
12 votes

What is required of the objective function in order to use Gauss Newton method?

Just to clarify notation, I'll be discussing the Gauss-Newton method for the problem $\min \phi(x)=(1/2) \| F(x) \|_{2}^{2}$ with the search direction $p$ computed as the solution to the linear ...
user avatar
10 votes

How do I find the minimum-area ellipse that encloses a set of points?

With your formulation of the constraints, you can only produce ellipses where the semi-major and semi-minor axes are aligned with the coordinate axes, but it's clear from the figure that you attached ...
user avatar
9 votes
Accepted

numerical solution of an under-determined linear equation in high dimensions

You want to minimize $\min \| Ax -y \|_{2}^{2} + x^{T}B^{T}Bx=\| Ax -y \|_{2}^{2} + \| Bx \|_{2}^{2}$ Recall that $\| u \|_{2}^{2} + \| v \|_{2}^{2}= \left\| \left[ \begin{array}{c} u \\ v \end{...
user avatar
9 votes
Accepted

Convexity of Sum of $k$-smallest Eigenvalue

Given $A \in {\bf S}^n$ (a positive definite matrix) with eigenvalues $\lambda_1 \leq \lambda_2 \leq \ldots \leq \lambda_n $, then: $\displaystyle f_k(A)=\sum_{i=1}^{k} \lambda_i$ is concave. Why? $$...
user avatar
  • 2,096
8 votes

Do they use semidefinite programming in industry?

From my own limited experience in the power industry, no one is solving SDPs at that sort of scale. I have some limited knowledge of what the New England ISO is doing, and I think they are more ...
user avatar
8 votes

What is the most appropriate derivative free optimization algorithm

As the "No Free Lunch Theorems for Search" [1] states that there is no one particular optimization algorithm that works best for every problem, i.e., citing the authors: all algorithms that search ...
user avatar
  • 201
8 votes
Accepted

How do I check if a loss function can achieve its minimum?

TL;DR: The property you are looking for is coercivity. This is satisfied for the example in your question (as are properties 1 and 3 below), and hence yes, the penalized objective attains its minimum. ...
user avatar
7 votes

Do they use semidefinite programming in industry?

Semidefinite programming and second order cone programming have not been adopted as rapidly in practice as many of us hoped. I've been involved in this for the last 20 years, and it has been very ...
user avatar
7 votes

Why are convex problems easy to optimize?

You can try to apply a convex optimization algorithm to a non-convex optimization problem, and it might even converge to a local minimum, but having only local information about the function, you'll ...
user avatar
7 votes

How to debug a constrained optimization algorithm?

Writing an optimization routine is like writing any other not too simple program and involves a fair amount of debugging. All things you mention in your question are good checks (i.e. taking care that ...
user avatar
  • 1,728
7 votes

How to debug a constrained optimization algorithm?

In addition to the things that @Dirk already states, run your algorithm on a problem that is simple enough that you can do each step of the algorithm exactly on a piece of paper. Then compare what ...
user avatar
7 votes
Accepted

Imposing special structure on Positive Semi-Definite matrix

The whole point is that you do NOT include the constraint $U = uu^T$ . That constraint is non-convex. Instead you include the constraint that $Z_j$ is (positive) semi-definite. This constraint is ...
user avatar
6 votes
Accepted

Nearest positive semidefinite matrix to a symmetric matrix in the spectral norm

There's no need to use the Schur complement here because $A$ and $S$ are already symmetric. The conventional formulation of this problem as an SDP is $$\min t \quad\text{ subject to}\\ A-S+tI \...
user avatar
6 votes
Accepted

beta in Nesterov's first method for piece wise linear convex optimization problem

A piecewise linear function is not differentiable (except in the trivial case), so as you noticed this method cannot be applied - the gradient does not exist, let alone its Lipschitz constant beta. ...
user avatar
6 votes
Accepted

How to determine whether two cylinders intersect or not?

David Eberly has a good description of the solution (with pseudocode) here: http://www.geometrictools.com/Documentation/IntersectionOfCylinders.pdf The short summary: like most convex-convex ...
user avatar
  • 331
6 votes
Accepted

Subgradients of non-convex functions

The fact that $x^*$ is a (global!) minimizer of $f$ if and only if $0\in\partial f(x^*)$ is already fully explained in the notes you linked to -- it's really that simple, but here's the argument again ...
user avatar
6 votes

On Boyd et al.'s convergence analysis of ADMM: Why do we need the convexity assumption?

To consolidate my comments: The proof of inequality (A.2) rests on the fact that the solutions $x^{k+1}$ and $z^{k+1}$ of the substeps (3.2) and (3.3), respectively, are global minimizers, so you can ...
user avatar
5 votes
Accepted

Converting convex quadratic constraint to linear matrix inequality (LMI)

One option here is to use the pseudoinverse of $\Sigma$ rather than the actual inverse. Appendix A of Boyd and Vandenberghe discusses a version of the Schur complement that includes this case. ...
user avatar
5 votes

Do they use semidefinite programming in industry?

Most of the work I'm aware of at labs for power flow problems is on stochastic optimization also, focusing mostly on MILPs. In chemical engineering, they are interested in MINLPs, and the classic ...
user avatar
5 votes

Looking for open source numerical solver

IPOPT is a good interior point method solver for convex nonlinear problems, and has a MATLAB interface, although I haven't used the MATLAB interface. (The solver, called from GAMS, is very good.) CVX ...
user avatar
5 votes
Accepted

Solve $AX = B$ where $X^T X = C$

Your problem is related to low rank approximation problems, about which there has been a lot of research in recent years. Are you looking for a solution in which $X$ has a specified number of rows, ...
user avatar
5 votes
Accepted

How to understand what's going wrong in a code for solving a problem with augmented lagrangian?

It's very difficult to provide a useful answer to this question because you haven't provided enough details about your problem and what you have already tried. There are various conditions under ...
user avatar
5 votes
Accepted

Why are convex problems easy to optimize?

Most of the best modern methods for large-scale optimization involve making a local quadratic approximation to the objective function, moving towards the critical point of that approximation, then ...
user avatar
  • 3,003
5 votes
Accepted

How to debug a constrained optimization algorithm?

You can use a Test Driven Development (TDD), the ideas behind are: before write code you write the test with the expected result; every line of code (almost all lines) is under test so when you ...
user avatar
5 votes
Accepted

Quadratic programs with rank deficient positive semidefinite matrices

To ensure this does not drown in the comments, I make it an answer. The solver used is not SeDuMi, as claimed in the question. The solver used is quadprog, and that solver (or more specifically, a ...
user avatar
5 votes
Accepted

How to transform this SOCP to the format required by cvxopt

Instead of direclty answering your question, I will propose to use a, so called, modeling language for optimization problems, which allows to formulate your problem in a natural way, and have the ...
user avatar
  • 731
5 votes
Accepted

Why am I getting this DCPError when my matrix is PSD?

Because the matrix KK is not PSD. It has minimum eigenvalue of -1. It is indefinite. Perhaps you are under the misapprehension that a symmetric matrix with all elements positive is PSD. As this ...
user avatar
5 votes

Reformulating a convex optimization problem with $x \mapsto \max(x,0)$ in the constraint

Because you say the losses are convex, I will presume that all $c_i \ge 0$, which means that max is used in a convex fashion. Given that, this problem can be formulated as a Linear Programming problem ...
user avatar
4 votes

Non-linear root finding with positive definite Jacobian

You could consider $d=1$ and $$ f(x) = e^x, \qquad y=0. $$ I don't think a function's derivative being positive everywhere implies that the function's range is all of $\mathbb{R}$. It does imply, ...
user avatar
  • 11.4k

Only top scored, non community-wiki answers of a minimum length are eligible