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.9k
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 ...
- 12.4k
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.4k
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 ...
- 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 ...
- 56.2k
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,748
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 ...
- 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{...
- 8,582
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^...
- 56.2k
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 ...
- 18.9k
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 ...
- 10.4k
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 ...
- 1,512
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 ...
- 11.5k
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 ...
- 2,495
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,340
6
votes
Minimum distance from point to surface
You could try with gradient projection, here is a quick implementation in python:
...
- 265
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: ...
- 485
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 {...
- 741
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 $\...
- 2,226
5
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 ...
- 603
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 ...
- 12.4k
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=...
- 56.2k
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 ...
- 18.9k
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 ...
- 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] \...
- 271
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,242
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. \;\...
- 1,512
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 ...
- 56.2k
4
votes
Accepted
Constraints 'exactly/at most one non-zero element' without binary variables
No, this is not possible. There is a standard way of showing this:
The feasible region of your constraints is not convex. For example, $x_{1,1}=1$, $x_{1,2}=0$ is feasible, $x_{1,1}=0$, $x_{1,2}=1$ ...
- 18.9k
4
votes
Nature of stationary points of a Lagrangian fuction
By the very definition of the Lagrangian, the extrema of the original, constrained problem are stationary points of the Lagrangian. That's just how the Lagrangian is defined.
What you are looking for ...
- 56.2k
Only top scored, non community-wiki answers of a minimum length are eligible