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 &...
Richard's user avatar
  • 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 ...
Brian Borchers's 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 ...
Daniel Shapero's 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{...
Brian Borchers's user avatar
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 ...
Christian Clason's 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 ...
Remis's 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. ...
Christian Clason's user avatar
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? $$...
GoHokies's user avatar
  • 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 ...
Brian Borchers's 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 ...
Dirk's user avatar
  • 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 ...
Wolfgang Bangerth's 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 ...
Mark L. Stone's 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 ...
Christian Clason's user avatar
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 ...
Mauro Vanzetto's user avatar
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$.
Johan Löfberg's user avatar
6 votes

Minimum distance from point to surface

You could try with gradient projection, here is a quick implementation in python: ...
Marko Lalovic's 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 ...
Nick Alger's user avatar
  • 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 ...
Brian Borchers's user avatar
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 ...
Christian Clason's 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 ...
Johan Löfberg's 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 ...
Stelios's 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 ...
Mark L. Stone's 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 ...
Mark L. Stone's user avatar
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 ...
Mark L. Stone's user avatar
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 ...
Daniel Shapero's user avatar
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 ...
Mark L. Stone's user avatar
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. ...
Mark L. Stone's user avatar
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 ...
Johan Löfberg's user avatar
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 ...
Johan Löfberg's user avatar
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}(...
Brian Borchers's user avatar

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