22
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 &...
- 3,546
11
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 ...
- 18k
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 ...
- 8,695
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{...
- 18k
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?
$$...
- 2,136
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 ...
- 256
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 ...
- 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. ...
- 12k
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 ...
- 18k
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 ...
- 18k
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 ...
- 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 ...
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 ...
- 2,022
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 \...
- 18k
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.
...
- 12k
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 ...
- 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 ...
- 12k
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 ...
- 12k
6
votes
Accepted
Rewriting quadratically-constrained optimization problem as a semidefinite program
With a factorization such as $HAH = R^TR$ you can apply a Schur complement and use $\begin{pmatrix}tI+\alpha (AH+HA)-A & \alpha R^T\\\alpha R & I\end{pmatrix} \succeq 0$.
- 1,848
6
votes
Minimum distance from point to surface
You could try with gradient projection, here is a quick implementation in python:
...
- 265
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 ...
- 30k
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, ...
- 18k
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.
...
- 18k
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 ...
- 30k
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 ...
- 18k
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 ...
- 3,033
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 ...
- 1,310
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 ...
- 1,848
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 ...
- 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 ...
- 2,022
Only top scored, non community-wiki answers of a minimum length are eligible