Skip to main content
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
Accepted

Looking for name of optimization problem in form $\min \mathrm x^T \mathrm A \mathrm x$ subject to $\|\mathrm x\| = 1$

Since the optimization problem has a well-known closed-form solution, it is rarely used in itself and hence usually not given a name. The objective function $x^TAx$ (using $\|x\|=1$), however, is ...
Christian Clason's user avatar
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

Can this simple quadratic optimization problem be turned into a simple eigenvalue problem?

At least for the second question the answer is yes. See for example Mattheij, Robert MM, and Gustaf Söderlind. "On inhomogeneous eigenvalue problems. I." Linear Algebra and its Applications ...
Aage's user avatar
  • 188
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

Looking for name of optimization problem in form $\min \mathrm x^T \mathrm A \mathrm x$ subject to $\|\mathrm x\| = 1$

I know this should be a comment but I do not have enough reputation to comment. I just want to point out that for an arbitrary $A$ with real entries the solution (minimum) to this problem is the ...
platypus's user avatar
  • 101
7 votes
Accepted

Solvers for Quadratically Constrained Quadratic Programs (QCQP) with complex variables

Let's consider the following minimization problem \begin{align} & \text{minimize} && \tfrac12 z^\mathrm{H} P_0 z + q_0^\mathrm{H} z\\ & \text{subject to} && \tfrac12 z^\mathrm{...
nicoguaro's user avatar
  • 8,510
7 votes

Why would BFGS converge to a local minima of a non-convex function but maintain a large gradient?

For a bounds-constrained problem to minimize $f(x)$ subject to $h(x)\ge 0$, there is no reason for $\nabla f(x^\ast)$ to be small at the optimum $x^\ast$. All the theory guarantees is that $\nabla f(x^...
Wolfgang Bangerth's user avatar
7 votes
Accepted

Optimization with the constraint of rank=1

You can parameterize your rank-1 matrix $A$ as $A=xs^{T}$ where $x$ and $s$ are the unknown $n$ by $1$ column vectors. You then have an unconstrained problem $\min f(x,s)$. Depending on the ...
Brian Borchers's user avatar
7 votes
Accepted

The nitty-gritty details of augmented Lagrangian methods

My favorite reference on this is Constrained Optimization and Lagrange Multiplier Methods by Bertsekas. It's a little old (1982) but I haven't seen any other reference that describes many of the ...
Daniel Shapero's user avatar
6 votes
Accepted

How to create an optimal pizza delivery plan and how to visualize it

Problem Formulation I can't guarantee that this is a perfect (or smallest-possible) formulation of the problem, but maybe it will help guide a better one. The road network is a directed graph ...
Tyler Olsen's user avatar
  • 1,522
6 votes
Accepted

Intersections of supports constraint

Suppose that $\mathbf{x}\ge0$ and $\mathbf{y}\ge0$. Then a necessary and sufficient condition for $\mathrm{supp}\{\mathbf{x}\}\cap\mathrm{supp}\{\mathbf{y}\}=\emptyset$ is for the two vectors to be ...
Richard Zhang'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

Scaling/nondimensionalization for numerical optimization

One thing that makes your non-dimensionalized ODE confusing is that you use the same symbols for dimensionalized and nondimensionalized variables, even though they are different variables. Consider ...
Kirill's user avatar
  • 11.4k
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
6 votes
Accepted

Why does `scipy.optimize.minimize(...)` fail with this toy constrained minimisation case?

The problem is that you are passing the constraint list as a positional argument, but it should be a keyword argument: ...
user9794's user avatar
  • 465
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
Accepted

Checking the feasibility of a system of inequalities

You can check feasibility of a set of linear inequalities by constructing a linear programming (LP) problem with a "dummy" objective, e.g., $$ \begin{align} \max_{\{x_i\}_{i=1}^n} &\;0\\ \text {...
Stelios's user avatar
  • 731
5 votes
Accepted

adjoint method for reaction-diffusion problem

Some remarks: Notation: $[t_1,t_2]$: the time interval; $\Omega$: the spatial domain; $\bar{u}^i(x)$: the known tumour profile at $t_i$; $\left\| \cdot \right\|_\Omega$: a suitably chosen norm on $\...
GoHokies's user avatar
  • 2,216
5 votes
Accepted

Simulation-based Optimization vs PDE-constrained Optimization

Both approaches apply to the same problem (numerical minimization of functionals which involve the solution of a PDE, although both extend to a larger class of problems). The difficulty is that for ...
Christian Clason's user avatar
5 votes
Accepted

sum of absolute difference constraint in optimization problem

The way to deal with this kind of constraint is to add "slack variables" to your system. In your case, let us say that you want to solve the problem $$ \min_a c^T a \\ \text{subject to}\; \sum_{i=...
Wolfgang Bangerth's user avatar
5 votes
Accepted

Maximize a function of an orthogonal matrix

There are specialized methods for the minimization of a differentiable function $f(X)$ subject to the orthogonality constraint $X^{T}X=I$. See for example: Lai, Rongjie, and Stanley Osher. “A ...
Brian Borchers's user avatar
5 votes
Accepted

How to solve calculus of variations problems numerically?

In the specific problem you ask about (unlike Richard's more general answer), it turns out that you can relax the $=$ constraint into a $\leq$ without changing the optimal value, and that the ...
cdipaolo's user avatar
  • 402
5 votes

How can I deal with optimization problems that have a sum of functions of Z as a constraint when Z is the quantity to be minimized?

This is just an NLP (Non-Linear Programming) model. You can rewrite it as: $$\begin{align}\min \>& Z \\ & \sum_i w_i = 1 \\ & \sum_i f_i(w_i\cdot Z)\ge k\cdot Z \\ & w_i \in [0,1] \...
Erwin Kalvelagen'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
4 votes
Accepted

limiting function as cost function: logistic function between -a and +a

Tangens Hyperbolicus behaves as you want.
PatrickS's user avatar
  • 156
4 votes

Checking the feasibility of a system of inequalities

I agree with Stelios' answer, but it could use some fleshing out. This problem is called the "Phase One" problem. First, convert your problem into "standard form". \begin{align*} \min_x 0 \\ s.t. \;\...
Tyler Olsen's user avatar
  • 1,522
4 votes
Accepted

Optimisation of purely integer quantity with bound-constraints for a 1D expensive function whose analytical form is not available

@Stellos already gave the correct answer, but let me try to back it up with a bit of intuition: Think of your function $f(x)$ as a function that would actually make sense for any real-valued argument ...
Wolfgang Bangerth's user avatar
4 votes

Constrained simulated annealing

Simulated annealing comes from computations in statistical mechanics. When I think of simulated annealing, I very much think in terms of physics: I want to minimize some potential energy function that ...
doetoe's user avatar
  • 593

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