Skip to main content
23 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,971
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
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? $$...
GoHokies's user avatar
  • 2,216
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
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

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

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
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
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

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

Reformulate a strictly convex QP problem containing absolute value term

$$\begin{align} \text{Minimize}\quad&\frac{1}{2} x^T Q x + a^T x + c^T|x| \\ \text{subject to}\quad&Gx \leq b \end{align}$$ where $Q$ is positive definite matrix, $c^T \gt 0$ (element-wise) ...
Zero's user avatar
  • 191
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,143
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 efficiently solve a QCQP with "dynamic" constraints in Python?

In order for a QCQP to be convex, the quadratic terms needs be be convex. Linear terms are always convex. With regard to your specific problem, the objective function is convex because it is linear. ...
Mark L. Stone'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
Accepted

Largest hypercuboid inside a polyhedron

It turns out that the problem has quite an elegant solution. Let the hypercuboid be defined by $\mathbf{l} \leq \mathbf{x} \leq \mathbf{u}$ instead of using the more cumbersome $\mathbf{x_{0}}$ and $\...
gpavanb's user avatar
  • 572
4 votes
Accepted

Determine image of hypercube under linear map

I eventually found an answer. The image of a hypercube in $\Bbb R^3$ under a linear map is called a zonohedron. They can be calculated efficiently, for example using the algorithm in An Efficient ...
Oscar Cunningham's user avatar
4 votes

Disciplined convex programming expression of $x\sqrt{1-x}$

I don't think you can represent this as a concave function in the (cvxpy-)DCP sense: import cvxpy as cp x=cp.Variable() a=x*cp.sqrt(1-x) a.curvature 'UNKNOWN' ...
Richard's user avatar
  • 3,971
4 votes

In which cases does the nonlinear conjugate gradient method take more than $n$ steps?

The nonlinear conjugate gradient method will converge for a quadratic function in $N$ steps at most. You do not have a quadratic function, and have no guarantees on convergence. It can be helpful to ...
EMP's user avatar
  • 2,089

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