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.
3,032 questions
1
vote
0
answers
46
views
A cute game with ratios
Given two integers $N$, and $K$. Two players A and B play a game on a grid of size $1\cdot K$. Each player has $N$ token.
We define a good sequence $c = [c_1,c_2,...,c_K]$ as a sequence of non ...
- 21
0
votes
0
answers
38
views
Is there a correction algorithm for Newton-Raphson method to find global minimum instead of local?
I have a case of single-variable function minimization where a "simple" Newton-Raphson algorithm works perfectly in most cases, except the edge case when the function has several local ...
- 32.2k
1
vote
2
answers
32
views
Exponential regression with three terms.
I was told to solve this by Least squares regression:
$$p(t) = a_{0} \exp(-1.5t) + a_{1}\exp(-0.3t) + a_{2}\exp(-0.05t)$$
along with some data for $t$ and $p(t)$.
I'm not sure how to proceed in this ...
- 11
0
votes
0
answers
17
views
Derivation of Dual problem from Primal problem with Lagrange
I'm currently preparing for test in non-linear optimization, and are trying to learn how to derive the dual problem from primal problem using Lagrange relaxation. The answer I get ends up being the ...
- 593
1
vote
0
answers
19
views
Is the limit of the constrained maximima of a sequence of smooth functions equal to the maximum of the limit of those functions?
Context: Trying to figure out how to find exact solutions to non-smooth optimization problems. Here is an earlier question.
Suppose we have a parameterized family of functions $f_r:\mathbb R \to \...
- 12.3k
0
votes
0
answers
17
views
Looking for general advice for finding collection of evenly spaced vectors as determined by absolute cosine similarity
I have a problem where I'm trying to find a collection of $N$ unit vectors, $V = \left\{ \hat{v}_1,\hat{v}_2,...,\hat{v}_N\right\}$, on the half-sphere in $\mathbb{R}^3$ such that such for $\hat{v}_i=(...
- 364
0
votes
0
answers
16
views
Proof of Convergence Rate for Steepest Descent with Exact Line Search
I am trying to understand a theorem about the convergence rate of the steepest descent method with exact line searches. The theorem states:
**Suppose
$𝑓:𝑅^𝑛→𝑅$ is twice continuously differentiable,...
- 11
0
votes
1
answer
25
views
On the relationship between relative interior and core of a set in convex analysis
I encountered what seems to be the same theorem about the relationship between the relative interior and core of a set in two different books:
In "First-Order Methods in Optimization" by ...
- 11
2
votes
0
answers
103
views
Similar SVMs with only different misclassification weights!
I am working on understanding the relationship between the solutions of two related SVM optimization problems, defined as follows:
Problem 1:
\begin{equation}
\min \frac{1}{2} \|w\|^2 + C \sum_{i=...
- 381
2
votes
0
answers
132
views
What is the generic method to find closed-form maxima given non-differentiable functions?
Suppose we have a problem:
$$\max_x f(x) \quad \text{s.t.} \quad g(x)\leq 0.$$
Assume $f$ and $g$ are both continuous. Assume now the following cases:
that $g(x)$ is not differentiable. We can assume ...
- 12.3k
0
votes
0
answers
37
views
Is this production/transportation problem solvable?
I am trying to solve the following problem.
Consider a scenario with $m$ factories producing a product and $n$ customers. Production at factory $i=1,\dots,m$ costs $c_i\geq 0$ per unit of product, as ...
- 14.1k
1
vote
0
answers
30
views
Effect of relaxing RHS of constraints in a convex optimization problem
I have a convex optimization problem of the form:
\begin{align}
\min\limits_{x\in\mathbb{R}^n} \quad&f(x)\\
\text{s.t. } \quad & g_i(x) \leq b_i, \forall i\in [m]
\end{align}
Let the primal-...
- 11
0
votes
0
answers
24
views
Least squares minimization of a set $m$ n-dimensional ellipsoidal equations
I have a set of $m$ ellipsoid like equations of the type:
$$f(x_i, .., x_n) = \sum_{i=1}^{n}\frac{(x_i-p_i)^2}{a_{i}^2}=1$$
I would to find the vector $x_i, .., x_n$ that minimizes the squared sum of ...
- 101
0
votes
0
answers
29
views
What is the correct Dual form of this exercise?
Consider the problem to minimize:
$z = -2x_1 + 8x_2 + x_1x_2 + x_1^2+6x_2^2$
subject to restrictions:
$\displaystyle ( x_1 + 2x_2 \leq 4 )\\
( 2x_1 + x_2 \leq 5 )\\
( x_1, x_2 \geq 0 )$
Derive the ...
- 405
1
vote
0
answers
32
views
How to maximize $l_1$ norm?
I have a problem of the form
\begin{align*}
\max \sum |a_i^T x + c_i| \text{ s.t. } x \in S
\end{align*}
My idea was to introduce auxiliary variables to remove the absolute value in the objective and ...
- 777
0
votes
1
answer
25
views
KKT-conditions of $\min t$ such that $t-x\geq0, t+x \geq 0, x^2 -4x + 4 = 0$
I want to solve
\begin{align*}
\min_{t,x} t\\
\text{s.t. } t-x &\geq 0 \\
t+x &\geq 0 \\
x^2 -4x + 4 &= 0
\end{align*}
with the help of KKT conditions. Obviously, the solution is given by $...
- 777
3
votes
0
answers
51
views
Maximizing a linear combination of logistic functions
Fix $a$ and $b$ in $\mathbb{R}^n$. Consider the mapping $h: \mathbb{R}^n \to \mathbb{R}$ defined as
$$
h(x, y) = \sum_{i=1}^n b_i \sigma(a_i x + y)
$$
where $\sigma$ is the logistic function, i.e. $\...
- 962
1
vote
1
answer
45
views
Optimal fractional betting strategy to maximize expected wealth
Suppose I start with a bankroll $X_0 = 1$ and for $n$ rounds I wager a fraction $f$ of my wealth in a favorable game with symmetric odds. That is to say, I seek an optimal betting rule $f^*$ to ...
- 1,316
0
votes
1
answer
37
views
Solving $\max |c^Tx+d|$ such that $c_i(x) = 0\;\forall i = \mathcal{E}$, and $c_i(x) \geq 0\;\forall i \in \mathcal{I}$
I want to solve $\max |c^Tx+d|$ such that $c_i(x) = 0\;\forall i = \mathcal{E}$, and $c_i(x) \geq 0\;\forall i \in \mathcal{I}$.
My idea is to split the absolute value. So, on the one hand, solve
$$\...
- 777
0
votes
0
answers
16
views
Does the solutions yielded by augmented Lagrange function fulfill equality constraints?
Consider the following optimization problem,
\begin{equation}
\begin{aligned}
\min_{x}\ & f(x),\\
s.t.\ &g(x)=0,
\end{aligned}
\end{equation}
with the smooth functions~$f(x),g(x)$,
which can ...
- 11
0
votes
0
answers
20
views
Do we need LICQ for SOSC in KKT points?
I am currently reading Numerical Optimization by Wright and Nocedal.
I stumbled upon the second-order necessary and sufficient conditions.
and
What confuses me is that LICQ is apparently not needed ...
- 777
0
votes
0
answers
22
views
The meaning of Lagrange multipliers with a constant objective function
In the method of Lagrange multipliers, it is well known that the meaning of a Lagrange multiplier $\lambda$ is the rate at which the extremal value changes with respect to the constraint. That is,
$$(\...
- 364
1
vote
1
answer
32
views
Solve $\min -x_1-x_2$ such that $x_1+2x_2 = 0, \| x\|^2 \leq 125$ with KKT conditions.
Given the following problem
\begin{align*}
\min -x_1-x_2 \\
\text{s.t.} x_1+2x_2=0 \\
\| x\|² \leq 125
\end{align*}
From the equality it follows that $x_1=-2x_2$. Plugging this into the norm ...
- 777
2
votes
0
answers
81
views
Minimizing the Distance Between Rotated Coordinate Frames with Axis Constraints
I am trying to find the optimal rotations for two coordinate frames, $F_1,F_2\in SO(3)$, to make them as close as possible to each other, subject to the constraint that each frame can only rotate ...
- 107
1
vote
0
answers
26
views
How to convert this non-convex constraint into a convex bound using successive convex optimization?
The constraint is shown as follows,
$$\LARGE \|\mathbf{AA}^H\|_{F} \leq c$$
where $\mathbf{A}$ is a matrix with dimension $K \times N$, $c$ is a given constant and the norm is $F$-norm. This ...
- 21
1
vote
0
answers
60
views
Approximation of the Set of LQR feedbacks for parameter-varying system matrix
Consider the classical continuous-time LQR case with infinite control horizon.
One entry of the system matrix $A$ is represented through the scalar parameter $a\in[\underline{a},\overline{a}]=\mathcal{...
- 127
1
vote
0
answers
64
views
How to tell if cost function (a sum of quadratics) is convex?
I have a mixed integer nonlinear programming optimization problem with the following characteristics:
All the constraints are linear
The cost function (which I want to minimize) is a sum of ...
- 226
0
votes
0
answers
15
views
Determine of value is optimal using sub-gradient method
Im currently trying to determine if my given value $x^*$ is an optimal value from the given information about subgradients at that point, and would like some help.
So the exercise is the following:
...
- 593
0
votes
0
answers
41
views
Why "continously differentiable" in optimization results?
In many results in Optimization, the function to minimize is often required to be continuously differentiable.
For example, the 1st-order necessary condition says that
If $x^{\ast}$ is a local ...
- 31
0
votes
0
answers
19
views
Gaussian variable estimation with asymmetric loss
Is it possible to get an explicit expression for $a$ in terms of $\mu$ and $\sigma$ such that this is satisfied?
$$100 \cdot\int_{-\infty}^a(a-x)\exp\left(-\frac{(x-\mu)^2}{2\sigma^2}\right)dx = \int_{...
0
votes
0
answers
42
views
Transform a matrix optimization problem into a semidefinite programming
I am working on a matrix optimization problem, and the constraints are difficult to handle.
The constraints are in the following form,
\begin{align}
\text{Given: } &b \in \mathbb{R}^n \text{ , and ...
- 17
0
votes
0
answers
14
views
transformation of parameter vector in constrained optimization using Hessian basis
Consider an unconstrained optimization problem, where the parameter vector $ \mathbf{x} $ can be thought of as a linear combination of unit vectors:
$
\mathbf{x} = \sum_{i=1}^{n} \alpha_i \mathbf{e}_i ...
0
votes
0
answers
47
views
Minimum distance from a point to a set
If $S=\{(x,y,z)|x^2+y^2+z^2 \leq 4, x^2-4y \leq 0\}$ and $w=(1,0,2)^t$. Find the minimum distance of $w$ to $S$, the unique minimizing point and the separating plane.
Solve without using KKT ...
- 77
2
votes
2
answers
75
views
Existence of a minimizer for the Thomas-Fermi-type model
I am looking for the following minimization problem
$$
\inf\left\{\int_{\mathbb R^d}f^3-\int_{\mathbb R^d}f^2:0\leq f \in L^1\cap L^3(\mathbb R^d), \int_{\mathbb R^d}f = 1\right\}
$$
where $d$ denoted ...
- 1,523
1
vote
0
answers
56
views
Complex integration and root-finding algorithms
I try to evaluate an integral of the form
\begin{equation}
I(R) = \int_{-R}^{R}\frac{1}{\left(f(x)+e^{i\phi(x)}\right)\left(f(x)+e^{-i\phi(x)}\right)}\,\mathrm{d}x
\end{equation}
where $f\in\mathbb{R}...
- 313
0
votes
0
answers
37
views
Optimization of affine invariant metric
Notations:
$\theta$: Rotation angle
$s$: Scale factor
$t = (t_x, t_y)$: Translation vector
$R(\theta) = \begin{bmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{bmatrix}$: ...
- 51
0
votes
0
answers
63
views
How to simplify this nonlinear integer programming
The situation is :
There are n bulbs and m power sources. The j-th power source has a failure probability of $P_j$. Each bulb is connected to 3 power sources, and only $\frac{3n}{m}$ bulbs can be ...
- 33
1
vote
0
answers
35
views
Fiting Damped Sine with high Correlation
I want to fit the function
$$f_t(x_1,x_2,x_3) = -x_1\exp \left(-\frac{t}{x_2} \right)\sin(2\pi x_3t)$$
which is basically a damped sine. This works quite well with non-linear LSQ. However, $x_1$ and $...
- 143
0
votes
0
answers
28
views
What is the alternative to condition number as a cost function for a NLP
My problem description.
I have robot manipulator dynamics with $n$ degree of freedoms:
$$
\tau = \xi(q, \dot{q}, \ddot{q}) \cdot \chi,
$$
where $\tau, q, \dot{q}, \ddot{q} \in \mathbb{R}^n $ are ...
0
votes
0
answers
15
views
Global optima of sigmoid functions
Consider a linear combination of multi-variate sigmoid function $f(x) = \sum_{i=1}^{n} c_i \sigma(<a,x> - b_i)$. I would like to know the locations of all local optima.
For the univariate case, ...
- 1
1
vote
1
answer
87
views
How to solve this $\min_{V} \sum_k \|Y_k - A_k V \|_F^2$ subject to $V^T V= I$?
How to solve this
\begin{aligned}
&\underset{V \in \mathbb{R}^{n \times n}}{\text{minimize}}
& & \sum_k \|Y_k - A_k V \|_F^2 \\
&\text{subject to}
& & V^T V = I,
\end{aligned}
...
- 713
0
votes
1
answer
28
views
Convexity of function, Hessian
Im trying to understand convexity of a given function $$f(x)=x_1^2+x_2^2+3x_1x_2+10x_1-11x_2+5.$$
My initial thought was to only take the second derivatives and check that $f_{xx} \geq 0$, and $f_{yy} ...
- 593
0
votes
0
answers
51
views
Are second-order conditions in optimization really needed?
I’m participating in optimization course and a lot of time is spent proving second-order conditions for unconstrained and constrained problems. To me these conditions feel rather unnecessary since I ...
- 339
1
vote
2
answers
116
views
An optimization problem and proof of necessity
The problem is formulated as follows
$
\max f\left( x_k,y_k \right) =\log _2\left( 1+Ax_1y_{1}^{2} \right) +\log _2\left( 1+Ax_2y_{2}^{2} \right) -\log_2 \left( 1+ACD^2 \right)
\\
s.t\,\,x_1+x_2=C,
\...
- 31
1
vote
1
answer
49
views
How to reformulate negative power of posynomial as a geometric programming constraint?
Currently, I am working as a network optimization engineer. From what I see, most of my optimization task can be fulfil effectively by using Geometric Programming (GP). However, I am running into a ...
0
votes
2
answers
111
views
Solve $ y'' + \lambda y^2 = 0$
Solve $ y'' + \lambda y^2 = 0$
Attempt 1 : if $\lambda =0 $ .then it's trivial to solve.
If $ \lambda <0 $ ,then $y '' \ge 0$
In particular when $y '' > 0 $ for some interval .
Let $ y''= e^{u(...
- 2,991
0
votes
0
answers
42
views
Bound on the min of the sum of cosines at two rationally related frequencies
I am interested in the minima of the sum of two frequencies:
\begin{equation}
\Delta = \min_t\left[\cos(t) + \delta \cos\left(\frac{p}{q}t+\phi\right)\right]
\end{equation}
$\phi, \delta\in\mathbb{R}$,...
- 177
0
votes
0
answers
51
views
Maximisation of a function involving the ratio of quadratic and linear forms
I have a function to maximise
$\boldsymbol{x}'A\boldsymbol{a} - \frac{\boldsymbol{x}'B\boldsymbol{x}}{\boldsymbol{x}'\boldsymbol{b}} - \frac{\boldsymbol{x}'C\boldsymbol{x}}{\boldsymbol{x}'\boldsymbol{...
- 83
0
votes
0
answers
35
views
Using Block Coordinate Descent for Convex Optimization with Quadratic Constraints
In solving the optimization problem $$min _{X, Y} f(X, Y) $$ $$\text { s.t. } \operatorname{tr}\left(X X^T\right)+\operatorname{tr}\left(Y Y^T\right) \leq P$$
, where both $f_X(Y)$
and $f_Y(X)$
are ...
0
votes
0
answers
36
views
Nonlinear KKT Optimization Problem
Check whether the 1st-order necessary conditions for
optimality hold at the optimum point (1, 0) of the following NLP:
$$min \; f(x) := -x_1$$
$$s.t. \;g_1(x) := -(1-x_1)^3 + x_2 \leq 0$$
$$g_2(x) := -...
- 152