Questions tagged [numerical-optimization]
Numerical methods for continuous optimization.
1,101
questions
1
vote
2answers
26 views
For continuous optimizations, what is the condition that says an optimal value lies on the boundary and not in the interior?
Suppose I want to solve the problem
\begin{equation}
\min_{x \in \mathcal{X}} f(x)
\end{equation}
where $f$ is assumed to be continuously differentiable, and $\mathcal{X}$ is closed and possibly ...
0
votes
0answers
11 views
Convergence of method of Newton modified with minimizing step size
This is an exercise from Bazaraa's Nonlinear Programming book in Chapter 8.
Given a twice continuously differentiable function $f$ with invertible-everywhere Hessian $H$, and let $x_{k+1}=x_k - t_k H(...
1
vote
0answers
21 views
What is a general condition that ensures all optimizers of a function are located on the boundary of a constraint set?
Let $f: \mathbb{R}^n \to \mathbb{R}$ be a continuous function. We wish to maximize or minimize the function on a constraint set $\mathcal{D}$, which we can assume to be compact (but not necessarily ...
0
votes
0answers
8 views
Verify that the nth direction vector (dk) and the rest (k-1) of the direction vectors are mutually conjugate
In the Polak-Ribiere conjugate gradient algorithm the direction vectors are generated by:
Polak-Ribiere: $d_{k} = -g_{k} +\frac{g_{k}^{T} (g_{k} - g_{k-1})}{g_{k-1}^{T}g_{k-1}}d_{k-1}$
Can someone ...
0
votes
0answers
9 views
Does gradient related implies $\{f(x^k)\}$ is monotonically decreasing?
In Bersetkas's book on nonlinear programing given a sequence $\{x^k\}$ he defines the set of direction $\{d^k\}$ to be gradient related if for every subsequence $\{x^k\}_{\mathcal{K}}$ that converges ...
0
votes
2answers
23 views
Differentiable “Signum” Function or “Step” Function for Gradient Descent
We are working on an optimization problem that involves using thresholds in a real-world decision algorithm. As of right now, my colleague and I are stumped on finding a differentiable mathematical ...
3
votes
4answers
194 views
How to find an optimum distance between 2 lines?
In the below graph there are 4 series of points. These points are symmetric respect to $OX$ axis and also with the $OY$ axis.
I have to create/to draw two parallel lines in order to include all these ...
0
votes
0answers
19 views
Finding Rotation and Translation from 2 known sets of data
As illustrated in the Figure above, I have 2 point clouds $X$ and $X'$ which initially lie on the same plane $\mathcal{P}$. The orientation of $\mathcal{P}$ - i.e. both Rotation $\mathbf{R}_0$ and ...
0
votes
1answer
37 views
Very Weird Optimization Problem.
I want to know methods to get approximate solution for a system of n linear equations in n variables with one extra constraint. Let's consider a simpler case, say n=3. Consider the equations :
2x + y ...
1
vote
1answer
23 views
Finding a minimum set in an optimization scheme.
I tried to formulate a problem as a numerical optimization, but I'm not sure how to solve it or if this is the best way to solve the problem.
Let's say for a given vector $\vec x \in \{-1,1\}^n$ and ...
1
vote
0answers
22 views
Minimize $\vert \vert B^HS BX\vert \vert$ subject to sparsity constraint
Can somebody please tell me if there is any iterative algorithm to solve the following optimization problem:
Given a collection of vectors in a matrix $X =\left\{x_i\right\}_{i=1}^q \in\mathbf{C}^{n\...
0
votes
0answers
17 views
Single objective non-linear optimization with multiple constraints
I am trying to solve a non-linear optimization problem with single objective function $$\operatorname*{min} J(u)+P(f_u)$$ with constraints $$R(u;f_u)=0$$ $$Q(a,u;f_{a})=0$$
Here $J(u)$ is the ...
0
votes
1answer
63 views
How can we show this identity for the material derivative?
Let $T(\;\cdot\;,t)$ be a $C^1$-diffeomorphism on $\mathbb R^d$ for $t\in[0,\tau]$ with $T(\;\cdot\;,0)=\operatorname{id}_{\mathbb R^d}$, $\Omega\subseteq\mathbb R^d$ and $\Omega_t:=T(\Omega,t)$ and $\...
0
votes
0answers
17 views
Lower-bounded non-convex geometric program: Help me figure out how to approach this!
I am trying to solve an optimization problem of the form:
$$\text{variables: } k \in \mathbb{N}, n \in \mathbb{N}^k, m \in \mathbb{N}^{k+1} \text{, indexing $n$ and $m$ from 0}$$
$$\text{constants: } ...
6
votes
0answers
88 views
Solving a nonlinear system of equations involving only products of unknowns
I would like to find a numerical solution of a system of $N$ equations of the form:
$A^i = w_1 F(x^i_k) + w_2 F(x^i_l) + w_3 F(x^i_m) +...$
$A^j = \,\,\,\,\,\,0 \,\,\,\,\ \,\,\ + w_2 F(x^j_l)...
0
votes
2answers
58 views
Solving min-max equations
I'm struggling solving the following systems of equations:
Solve for $x$ and $y$
$$
\min(2x,5y)+\min(3x,-2y)=-50
\\
\max(-3x,2y)+\max(6x,3y)=~~51
$$
I have tried many method however I'm still not ...
0
votes
1answer
26 views
Tolerance in x in Linear Programming
Suppose we have a linear programming problem of the form:
\begin{align*}
& \min_{x}c^{T}x\\
\text{s.t.}\text{: } & Ax=b\text{, }x\geq0
\end{align*}
Generally, the termination condition of the ...
3
votes
1answer
37 views
Gradient descent scaling
If gradient descent converges with a learning rate of 0.1 for f(x), should the same learning rate work for g(x) = f(10x)?
I think that g changes more quickly than f, so want to take smaller steps. ...
0
votes
1answer
27 views
What is the meaning of the word “block” in the Block Successive Minimization Methods (BSUM) for optimization?
What is the mean of the word "block" in the Block Successive Minimization Methods (BSUM) for optimization ?
https://arxiv.org/abs/1511.02746
My guess is that the word block mean act of ...
2
votes
0answers
14 views
Why is the step size for gradient tree boosting with squared error loss = 1?
In his paper on gradient boosting, Friedman proposed the following algorithm.
In section 4.3 of his paper, Friedman considers the special case where each base learner is a $J-$terminal node ...
2
votes
1answer
47 views
ADMM solution for this problem $\text{min}_{x} \frac{1}{2}\left\|Ax - y \right\|_2^2 \ \text{s.t.} \ \|x \|_{1} \leq b$?
How to use ADMM for the problem given below?
\begin{alignat}{2}
\tag{P1}
&\underset{x \in \mathbb{R}^{n \times 1}}{\text{minimize}}&\quad \frac{1}{2}\left\|Ax - r \right\|_2^2\\
&\text{...
0
votes
0answers
42 views
How to find optimal step sizes for gradient descent convergence in convex case?
"Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization", page 14, almost at the bottom (simplified):
$$ \Delta_{t+1} \le (1 - 2 \eta_t \lambda) \Delta_t + \eta_t^2,$$
...
0
votes
0answers
34 views
Is this equation solvable with Lambert function or some other way?
I'm new to Lambert function and was wondering if this was the correct method of solving the following equation. I have generalized it to
$e^{\frac{a+bx}{cx^2}}(x^2+d_1x+ d_2)= k$
If it can't be solved ...
1
vote
0answers
234 views
MaxMin of Sum of Fractionals Optimization Problem
Let $\mathbf{x}^{(1)},\ldots,\mathbf{x}^{(L)}$ be $L$ vectors of $N$ variables. Then, how can I solve the following optimization problem?
\begin{align}
\max_{\mathbf{x}^{(1)},\ldots,\mathbf{x}^{(L)}}&...
0
votes
0answers
16 views
a property of Amijo-type line search algorithm
I am reading
L. Grippo and M. Sciandrone. "On the convergence of the block nonlinear GaussāSeidel method under convex constraints." Operations Research Letters (2000).
And have some ...
0
votes
0answers
14 views
Conjugate Gradient: A-orthogonality under quadratic form implies “regular” orthogonality under special mapping…
I have been reading through an article on the method of conjugate gradients (in solving a system $\textbf{A}x=b$). You can find the article here.
In the article, we consider the quadratic form $f(x)= \...
2
votes
1answer
50 views
Convexifying Optimization Problem
Let $\mathbf{V} \in \mathbb{R}_{+}^{n \times m}$ and $\mathbf{E} \in \mathbb{R}_{+}^{n \times m}$.
I am trying to convexify the following program which solves for $\mathbf{X} \in \mathbb{R}^{n \times ...
4
votes
0answers
56 views
Shape derivative of a boundary integral with a continuously differentiable function on a “tubular neighborhood”
Let $d\in\mathbb N$. I want to compute the shape derivative of a shape functional$^1$ $$\mathcal F(\Omega):=\int_{\partial\Omega}f\:{\rm d}\sigma_{\partial\Omega}\;\;\;\text{for }\Omega\in\mathcal A$$ ...
0
votes
1answer
25 views
Identify the regions in $(\alpha_{1},\ \alpha_{2})$ plane for which $f_{\alpha_{1},\ \alpha_{2}}$ is a convex or concave function
A family of functions. For constants $\alpha_{1}$ $\alpha_{2}$,
let $f_{\alpha_{1},\alpha_{2}}:R^{2}_{+} \rightarrow R_{+}$ be defined as:
$\hspace{4 cm}$ $f_{\alpha_{1},\alpha_{2}}(x_{1},\ x_{2})= x_{...
1
vote
0answers
38 views
A simple shape derivative example
Let $d\in\mathbb N$, $\tau>0$, $U\subseteq\mathbb R^d$ be open and $T_t$ be a $C^1$-diffeomorphism from $U$ onto an open subset of $\mathbb R^d$ for $t\in[0,\tau)$ with $T_0=\operatorname{id}_U$. ...
1
vote
1answer
43 views
How does topological properties of sets (openness, closed, compactness) matter in practical algorithm design for optimization problems?
In optimization problems, one places great emphasizes the properties of the constraint set
$$\min_{x \in \mathcal{C}} f(x)$$
For instance, when $\mathcal{C}$ is compact, we have the existence of an ...
1
vote
1answer
33 views
Proximal Gradient of absolute value of linear function
I am working through
https://www.ipol.im/pub/art/2013/26/article.pdf
This is an attempt at simplyfying deriving (13) from (9).
One of the posed problems can be written as,
\begin{equation}
\min_{\...
0
votes
0answers
12 views
Finding one of several close local minima
I have a function which looks like this:
The function is a kind of error metric from another optimisation, which itself uses input data which is changing over time. I don't have an analytic ...
0
votes
0answers
94 views
Show that the perturbation of identity satisfies certain continuity and Lipschitz properties
Let $d\in\mathbb N$, $u\in C^{0,\:1}(\mathbb R^d,\mathbb R^d)$ and $c:=|u|_{C^{0,\:1}(\mathbb R^d,\:\mathbb R^d)}$ (the semi-norm given by the Lipschitz constant).
I would like to show that there is a ...
0
votes
0answers
10 views
Any optimizing constraints available to limit the positon of non-zero elements?
For the model $\mathbf{M} = \mathbf{K_2SK_1^T}$ (data was attached here!),$\mathbf{K_2}\in R^{18000\times 64}$,$\mathbf{K_1}\in R^{21 \times 64}$ and $\mathbf{M} \in R^{18000\times 21}$ were given. ...
0
votes
0answers
42 views
Prove gradient descent converges to a local minimum
I would like to have a proof that indeed, the gradient descent converges to a local minimum if it exists, for a differentiable function with Lipschitz continuous derivative $f:\mathbb R \rightarrow \...
0
votes
0answers
50 views
Solving Linear System of Equation in Polynomial Time
Let $ \mathbf{b} \in \mathbb{R}_+^n$, $\mathbf{E} \in \mathbb{R}_+^{n \times m}$, $\mathbf{V} \in \mathbb{R}_+^{n \times m}$ with $\mathbf{E}^T \mathbf{1}_n = \mathbf{1}_m$ and $\mathbf{V} \mathbf{1}...
1
vote
2answers
69 views
Parameter scaling in optimization
I'm currently working on an iterative approach to solving an optimization problem. The implementation seems to be calculating biased directions so a colleague suggested I look into parameter scaling. ...
1
vote
0answers
62 views
Inverse a sparse matrix
I have a sparse singular matrix W where I want to find its inverse Q. My current method is to use $W*Q = I$ for an optimization process of approximating the convergence of cost function norm($I-W*Q$).
...
1
vote
1answer
31 views
Steepest-descent optimization procedure with step size given by harmonic sequence
Here is a minimization procedure I've "dreamed up." I'm hoping to gain a better understanding of its mathematical properties and practical efficiency.
Given a (locally) convex function $f(x):...
1
vote
0answers
12 views
Hessian Boundedness for Continuously Differentiable Function
While reading Numerical Optimization 2ed by Nocedal & Wright, on page 23, it says
$$\begin{align}\nabla f(x+p) &= \nabla f(x) + \nabla^2 f(x)p - \nabla^2 f(x)p + \int_0^1 \nabla^2 f(x+tp) p \,...
0
votes
0answers
23 views
How to Reconstruct a curves from coordinate points? How to detect curves?
I have extracted the coordinate points of a diagram using edge detection in opencv.
With these coordinates I wanted to reconstruct the diagram in question, with lines and curves in separate canvas i.e ...
0
votes
0answers
25 views
Derivation of Broyden's Method
I'm currently struggling with the drivation of the Broyden's method [1]. I get the point where the Jacobian $J$ is approximated via a (kind of) Secand method $A$ and has to fulfill the following ...
0
votes
0answers
27 views
Euler Lagrange equation with optimal quadratic function
Let $\lambda \in [0,1]$, $c \geq 0$. I want to find the quadratic functions $P: \mathbb{R}\rightarrow \mathbb{R}$ with $P(0)=0$ for which there exist $\bar{q}_P, \hat{q}_P \geq 0$ such that $P'(\bar{q}...
0
votes
1answer
33 views
What is the relationship between linear convergence in gradient descent and linear convergence in real analysis?
In undergraduate analysis/calculus courses, we often learn about linear convergence of a sequence: a sequence $x_n\rightarrow x_\infty$ in $\mathbb{R}^n$ linearly if there exists $r\in (0,1)$ such ...
0
votes
1answer
19 views
pentadiagonal matrix vector multiplication
I have a pentadiagonal symmetric matrix , with elements on the diagonal, on the 1st upper-diagonal and 1st lower-diagonal and at the n-th upper and lower diagonal.
( n changes values from one matrix ...
0
votes
0answers
12 views
Efficient intersection of linear subspaces? How to solve a big nonlinear least squares with linear constraints?
Problem:
I want to solve a big linearly constrained nonlinear least squares problem. The number of unknowns is between millions and billions. In terms of cost functions, the Hessian would be pretty ...
0
votes
0answers
40 views
How to avoid overflow when evaluating the exponential smoothing function?
The exponential smoothing function is $f:\Bbb R^n\to \Bbb R$ defined as
$$f(x):= \log\left(\sum_{i=1}^{n}e^{x_i}\right).$$ Obviously, when $x_i$ is large for some $i$, the term inside the logarithmic ...
0
votes
0answers
31 views
Example of convex function with global min that is Lipschitz but does not have Lipschitz gradients
In gradient descent, when optimizing a convex function with a global minimum, one often assumes either that
the function is Lipschitz, or
that its gradients are Lipschitz.
There are examples where ...
1
vote
1answer
65 views
Accelerated Randomized Coordinate Descent
This paper is by a famous professor. It has several hundreds of citations. There must be someone who understands this paper. If someone out there is experienced in optimization, please have a look at ...
