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,921
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 ...
- 18.5k
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 ...
- 10.1k
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{...
- 18.5k
8
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 ...
- 12.2k
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. ...
- 12.2k
8
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,176
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 ...
- 18.5k
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,738
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 ...
- 54.1k
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,192
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 ...
- 12.2k
6
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,330
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
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,133
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 ...
- 18.5k
5
votes
Second-order derivative condition for convexity
Consolidating my comments (so that they can be cleaned up): This is a misunderstanding.
A twice (continuously!) differentiable function $f:\mathbb{R}^n\to \mathbb{R}$ is convex if and only if the ...
- 12.2k
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,192
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 ...
- 2,192
5
votes
Accepted
SCP (Sequential Convex Programming) vs SQP (Sequential Quadratic Programming)
In SCP (a.k.a. SCA), at each outer iteration:
Objective function is replaced by a convex approximation, not necessarily quadratic.
Nonlinear inequality constraints are replaced by convex ...
- 2,192
5
votes
Accepted
continuous analogues of Newton's method
No, it is not possible to use higher-order ODE integration methods on the Newton dynamical system to do better than vanilla Newton with some globalization strategy.
Brezinski (2001) gives a negative ...
- 10.1k
5
votes
Accepted
Convex optimization: what is atom library?
Adding new functions to the CVX atom library just means adding new functions which can accept CVX variables and expressions as input, as described in the section Adding new functions to the atom ...
- 2,192
4
votes
Best platform for complex SDPs with n and m around 5-15K?
You can try using SCS, either the direct or indirect solver. SCS uses first-order methods, and hence may be able to solve larger problems than second-order solvers such as SDPT3, SeDuMi, MOSEK, etc. ...
- 2,192
4
votes
How to solve a constrained optimization problem using minFunc or minConf
Adding another answer, as I just realized that the problem is easily solved as a linear SDP. Let $Q=S^TS$ and you have the objective $\mathrm{trace}~Q + \mathrm{trace}~Q^{-2}$. Introduce an upper ...
- 1,848
4
votes
How to solve a constrained optimization problem using minFunc or minConf
Not a direct answer to your title question, but I think you are better off attacking this problem from the semidefinite domain instead. Trivial approach is to linearize the objective at some initial ...
- 1,848
4
votes
Accepted
What method do you suggest to solve this minimax, quadratic in both variables problem?
You can write your inner problem as
$
\max_{x} x^{T}y - x^{T}Cx
$
subject to
$
x \in [l,u]
$
where $C=\mathrm{diag}(y)B\mathrm{diag}(y)$. This is a box constrained QP.
Since $C=\mathrm{diag}(...
- 18.5k
Only top scored, non community-wiki answers of a minimum length are eligible