Questions tagged [numerical-optimization]

Numerical methods for continuous optimization.

Filter by
Sorted by
Tagged with
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 ...

1
2 3 4 5
23