Questions tagged [nonlinear-optimization]
A non-linear optimization problem includes an objective function (to be minimized or maximized) and some number of equality and/or inequality constraints where the objective or some of the constraints are non-linear. Use this tag for questions related to the theory of solving such problems or for trying to solve particular problems.
2,950
questions
0
votes
0
answers
24
views
On Extreme points of unit ball in $\mathbb{R}^n$ with respect to the max norm
I was trying to solve the following problem for my non-linear optimization class from the book by Amir Beck.
Let $S=\{ x \in \mathbb{R}^n \colon \|x\|_{\infty}\leq 1\}$. Show that
$$ext(S)=\{x \in \...
0
votes
0
answers
9
views
Gradient Descent Over the Set of Complex Symmetric Matrices
In the course of my research (somewhat related to compressive sensing), I am trying to determine a complex, symmetric matrix $L$ (i.e. $L = L^T$) through the following optimization formulation:
$$ \...
-1
votes
0
answers
13
views
How to solve this optimization problem corresponding to sparsity? [closed]
\begin{equation}
\begin{aligned}
\min_{ \mathbf{h}_s } & \ \sum_{i=1}^s h_i^2 \\
\text { s.t. } &\ \sum_{i=1}^N h_i^2 = 1\\
&\ \sum_{i=1}^...
-1
votes
0
answers
42
views
Given a point in the 3D brain, and given blood vasculature in the brain, find a path to drill through the brain farthest from the vasculature. [closed]
The specific context for this problem is placement of electrodes in the brain.
You know the specific point where you want to place the electrode in the brain, and assume you know where the blood ...
0
votes
0
answers
18
views
Solve Minimax Rules in Finite Case
Let $\Theta = \{\theta_1, \cdots, \theta_n\}$ be the space of parameters and $D = \{d_1, \cdots, d_m\}$ be the space of decisions (that is, they are arbitrary finite sets with at least two elements). ...
0
votes
0
answers
26
views
Does Cutting Plane method always converge in case of Integer Linear Programming?
I learned that the Cutting plane algorithm using Gromory's cut helps in finally reaching an optimum solution in integer linear programming.
But I also observed that in the simplex tableau, if the ...
3
votes
2
answers
123
views
Why having a global convex upper bound is considered as an advantage for the convex-concave procedure?
I am reading this paper "Variations and extension of the convex–concave procedure" and on page 5/25, second paragraph, the authors state that "Another advantage of CCP is that the over ...
1
vote
1
answer
90
views
"Sandwich" Quadratic majorizer of even convex function
Assume $f : R \to R$ is strictly convex, differentiable, even and $f(0)=0$. Further assume that there exist quadratic functions above f.
I want to prove that for any quadratic function $ax^2 + bx + c \...
0
votes
0
answers
26
views
Optimal choice of tires in race
Formula 1 started this weekend. And I have been trying to figure out how they calculate the optimum choice of tires to finish the race fastest.
While in the real F1 race there are many factors ...
0
votes
0
answers
15
views
what constraints should I use when optimizing ellipsoid function
I'm using an ellipsoid $f = x^a + |y|^b + |z|^c - 1 = 0$ to fit some data (a failure envelope), where $x \in [0, 1]$, $y \in [-1, 1]$, and $z \in [-1, 1]$ are all normalized variables and $a$, $b$, $c$...
1
vote
0
answers
20
views
Can a function be converted into a Voronoi diagram of its local extremum points and basins of convergence?
Let's say I know the position $e \in \mathbb{R}^N$ of a local extremum point of a non-convex function $f: \mathbb{R}^N \mapsto \mathbb{R}$. Is there an efficient method for finding $K$ closest "...
0
votes
1
answer
23
views
How to solve $\min(x^2+y^2)$, $x\ge1, y\ge-2$, using the KKT conditions?
I'm trying to understand better optimisation problems and in particular the KKT conditions. To this end, consider the minimisation problem
$\min(x^2+y^2)$ subject to $x\ge1$ and $y\ge -2$.
It's clear ...
-1
votes
0
answers
28
views
Minimization of the ratio of quadratic forms with constraints [duplicate]
I don't want to re-invent the wheel so I was wondering if anything is known about this problem
$$
\begin{equation}
\begin{aligned}
\min_{x\in\mathbb{R}^d} \quad & \frac{x^\top A x}{x^\top B x} ...
0
votes
0
answers
10
views
Finding parameters for function approximation
I am working on some project in Matlab, where I defined some function $R(x, h, H, L, N)$ and I want to find such $h, H, L, N$ such that $R(x, h, H, L, N)$ is approximated by some sine wave in other ...
2
votes
0
answers
59
views
+50
Scaling and Adding Mathematical Programs
I understand the notion of Linearity typically applied to define Linear Programs (here I will capitalize "Linear" when and only when I use it in this sense). In contrast, this question is ...
1
vote
0
answers
50
views
What is truncated Levenberg-Marquardt and how does it work?
I am currently trying to understand the Levenberg-Marquardt implementation that (Fetzer et al. 2020) used in their solution.
(The paper is publicly accessible here). After reading it, I'm stuck at the ...
0
votes
0
answers
35
views
Approximating a rational number in a subset of Q defined by limited prime factors
I'm wondering if there is an efficient (or good enough for small numbers) algorithm for the following problem:
Suppose I have a rational number in the form of its prime factorization:
$k = p_0^{x_0}...
1
vote
1
answer
50
views
Solving a convex problem with quasiconvexity with CVXPY?
I have a question regarding quasiconvexity and its usage in CVXPY.
I have the following optimization problem.
\begin{equation*}
\begin{aligned}
\min_{x} \quad & \sqrt x\\
\textrm{subject to:} \...
2
votes
1
answer
42
views
Convex optimization with some cubic and quartic constraint?
I am an engineer who is currently working with some network optimization problem. In my work, I encounter a strange optimization problem that seems to be convex but it has some cubic and quartic ...
0
votes
0
answers
23
views
Maximizing a function involving a linear combination of the positive and negative part
Let $u:\mathbb{R}_+ \rightarrow \mathbb{R}$ be a differentiable and strictly concave function satisfying $\lim_{x \to 0^+} u(x)=\infty$ and $\lim_{x \to \infty} u(x)=0$, and let $a,b,c \in \mathbb{R}$ ...
0
votes
0
answers
23
views
Can geometric programming be considered as a special case of second order cone programming?
From the Mosek cookbook, it is clear that by using the log-sum-exp transformation and some extra variable $u_k$, a geometric programing problem can be transform into a exponential cone presentation.
...
0
votes
1
answer
32
views
An optimisation problem involving a special class of polynomials
I'm currently working on an interesting problem in function approximation thta just came to mind and am seeking insights or methodologies that might aid in approaching it. The problem is as follows:
...
0
votes
0
answers
32
views
Quadratic programming problem with additional non-linear term
I am familiar with methods for solving quadratic programming problems of the form
$$\max_{x\in C} \mu^T x- 0.5x^T \Sigma x,$$
where
$$C = \{x\in \mathbb{R}^d: 1^Tx = 1, x\succeq 0\}.$$
For example the ...
0
votes
1
answer
40
views
Why am I getting a constant for alpha when I take the derivative of my objective function?
I am trying to solve this simple optimization problem:
Minimize $f(x,y)=x^2+y^2$ over $\frac{1}{4}x^2+\frac{1}{9}y^2-1=0$
I get
$L = x^2+y^2+\alpha(\frac{1}{4}x^2+\frac{1}{9}y^2-1)$
then
$0=\frac{\...
0
votes
0
answers
32
views
coordinatewise gauss-newton algorithm
I'm considering Gauss-Newton algorithm to minimize $\left\Vert \mathbf{f}\left( \mathbf{z}\right) \right\Vert ^{2}=\left\Vert \mathbf{f}\left( \mathbf{x},\mathbf{y}\right) \right\Vert ^{2}=\left\Vert \...
1
vote
0
answers
48
views
Solving a non-linear program using Python
New to optimization, trying to understand the characteristics of a problem I am in the process of modelling, and looking to solve in Python. Given is a decision variable k,the sum of N other decision ...
3
votes
1
answer
97
views
A trajectory optimization problem [closed]
The following problem comes from information theory. Specifically, for an impossibility bound I need to supply the decoder with side information and the answer will say what policy gives the tightest ...
1
vote
0
answers
115
views
Penalty method and the question of equivalence in a specific optimization problem
I encountered an interesting problem in “Practical Methods of Optimization” by R. Fletcher, which utilizes the penalty method to solve the following constrained optimization problem
\begin{align}
{\...
5
votes
1
answer
189
views
Optimality condition inspired by subdifferential of square root: $y\in \text{argmin}(g(x)-a^Tx ) \Rightarrow y\in \text{argmin}(g^2(x)-2g(y)a^Tx).$
Let $f:\mathbb R^d\to\mathbb R\cup\{+\infty\}$ be a proper convex lower semicontinuous function. Suppose that $f$ is bounded by below, and for simplicity that $\inf f = 0$. Set $\varphi:\mathbb R^d\to\...
2
votes
0
answers
53
views
Request for help understanding a solution in a research paper
I am having difficulty understanding a particular solution in a research paper I am reading.
Title: "Analysis of nonlinear duopoly game with
heterogeneous players"(2006)
Authors: Jixiang ...
2
votes
1
answer
88
views
Is it true that a function is $c$-strongly convex if $f - c\|x\|^2_p$ is convex for ANY norm $\|x\|_p$?
It is a common knowledge that a function is $c$-strongly convex if $f - c\|x\|^2_2$ is convex.
However, can we replace $\|x\|_2$ with any norm $\|x\|_p$? I strongly suspect this holds, but from ...
0
votes
1
answer
76
views
Linear programming with $XX^T=Identity$ constraint
I have the following system of equations
$$X R a - c_1 = 0$$
$$X a - c_2 = 0$$
$$X X^T=Identity$$
where $X\in\mathbb{R}^{3x3}$, $a,c_1,c_2\in\mathbb{R}^{3x1}$, $R\in\mathbb{R}^{3,3}$ is a rotation ...
0
votes
1
answer
35
views
Farkas lemma query
I had a query related to Farkas's lemma. As i understand as per the lemma the following two statements are equivalent:
For a matrix $A \in \mathbb{R}^{m \times n}$,and vector $c \in \mathbb{R}^{n}$ ...
0
votes
0
answers
15
views
conjugate duality involving sum of convex functions
Consider the primal problem
$$
\min_x \{f(x):G(x)\in Y\}\tag{$P$}
$$
rewritten as
$$
\nu(P^\prime) = \min_x \{f(x):y\in Y,\;y=G(x)\}\tag{$P^\prime$}
$$
where $G:\mathbb{R}^n\to \mathbb{R}^m$ with $G(x)...
1
vote
0
answers
73
views
Does anyone have experience with this multidimensional optimization algorithm
I recently stumbled across what looks like a very interesting paper concerning a simplex-based bisection algorithm for multidimensional optimization.
The authors provide results from their own MATLAB ...
0
votes
0
answers
39
views
Are there practical problems in optimization where its dual problem is computationally easier to solve?
In a class I learned that optimization problems can have "dual counterparts"
For example, a problem of the type
$$\min_{x} f(x) + g(x)$$
has a "Fenchel" dual problem:
$$\max_{y} -f^...
0
votes
0
answers
18
views
Finding the real roots of a set of multivariate polynomial in an interval
Problem: I have a set of $m$ multivariate polynomials over $k$ variables, with an upper bound on the degrees $n$:
$$
\{f_i(x_1,x_2...x_k)\}_{i=1}^{m}
$$
My goal is to find if there's a real root such ...
1
vote
1
answer
65
views
An integral-formula multivariate Talyor's theorem for twice differentiable function
In [1], I encounter the following statement:
For $ f: \mathbb{R}^{d} \rightarrow \mathbb{R} $ that is twice differentiable,
$ \nabla f (x + p) - \nabla f (x) = \int_{0}^{1} \nabla^{2} f (x + t p) ~ p ~...
0
votes
0
answers
53
views
How to capture low-rankness of a symmetric matrix using its components (not eigenvalues)?
Suppose I have an optimization model (P1) which its decision variable is a symmetric matrix $W$ (but not necessarily negative/positive semidefinite). In my case, this model can be converted to a ...
1
vote
1
answer
67
views
Minimizing symmetric convex functions of eigenvalues
I am stuck with the following problem.
Prove that the optimal value to the SDP
\begin{align}
\text{minimize} \quad &\operatorname{tr}(V)
\end{align}
\begin{align}
\text{subject to} \quad &\...
2
votes
1
answer
53
views
Prove that the following function is firmly non expansive
Let $T(x)=\frac{x}{\sqrt{1+x^2}}$ be a function from $R$ to $R$. Prove that the function is firmly non-expansive.
Definition:
$$||Tx-Ty||^2 + ||(Id-T)x-(Id-T)y||^2 \leq ||x-y||^2$$
If the space is ...
1
vote
0
answers
47
views
Parameterizing matrices whose rows and columns sum to a constant
I have a constrained optimization problem for a matrix $A \in \mathbb{R}^{m \times n}$. The objective doesn't matter, and the constraint is that
for some scalars $\alpha, \beta \in \mathbb{R}$, we ...
0
votes
1
answer
89
views
Route to maximize number of visited partitions in a weighted graph for given distance [closed]
How can I find a route through a partitioned weighted graph that visits as many of the partitions as possible, for a given maximum distance? Start and end anywhere.
A real-world example could be to ...
0
votes
0
answers
150
views
Evaluating the ratio of minimum to maximum norm
Consider a square grid in $Y-Z$ plane consisting of $(L+1)^2$ points ($L$ is an even integer) centered around origin. The points in the square grid are:
$\vec{s}_{mn}= (0,md,nd)^T ,$ where $ -L/2 \...
0
votes
0
answers
38
views
fractional optimization problem with equality constraints
I have the following optimization problem
\begin{equation}
\begin{aligned}
\max_{\mathbf{x}} & \ |d-\sum_{n=1}^{N}\frac{c_n}{f_n+x_n} |^2 \\ \quad
\text{subject to} \quad & \sum_{n=1}^{N} \...
0
votes
0
answers
15
views
Information optimization
Is there a field/subfield of mathematics dealing with the following type of optimisation problem; if so, what is it called?
-If every word in a language has a unique sign, a writer in that language ...
0
votes
2
answers
51
views
Relation between Moore-penrose pseudoinverse and $A^T$?
I have the following question:
If $Ax=b$ where $A \in R^{m \times n}$, then we can get $x = A'b$ where $A'$ is the moore-pensrose psuedoinverse. Is it true that $x$ is unique if $x^Ty = 0 \forall y \...
0
votes
0
answers
10
views
Proofing Slater's condtion iterative?
If I have a convex optimisation problem for an engineering application of the standard form:
$$
\begin{equation*}
\begin{aligned}
\min_{x} \quad & f(x)\\
\textrm{s.t.} \quad & g_i(x) \leq 0 \\
...
1
vote
1
answer
89
views
Non-linear optimization programming, with step function in constraint
I want to optimize a non-linear function $f(x)$, $f: \mathcal{R}^{n} \to \mathcal{R}$ (being a log-likelihood over $m$ observations, i.e. $i$ being the observation index) under constraints numerically,...
1
vote
0
answers
28
views
How to determine the infimum with linear and logarithm term to dualise a convex problem?
I wanted to try and dualise an optimisation problem but I am struggling with the infimum.
The problem looks as follows:
$$
\begin{equation}
\begin{aligned}
\min_{x} \quad & 3x\\
\textrm{s.t.} \...