Questions tagged [numerical-optimization]

Numerical methods for continuous optimization.

470 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
1
vote
0answers
177 views

The 2-norm of inverse of a Hessian matrix

This concerns the convergence of Newton's method in unconstrained optimization. But the question can be taken out of this context. Suppose $f$ is twice differentiable and that the Hessian $\...
1
vote
0answers
33 views

Numerically compact representation of high dimensional phase space maps

I am studying the behavior of a transmission electron microscope lens system numerically. The lens system has only one approximate mirror symmetry. Essentially, I am studying the function taking in 5 ...
1
vote
0answers
104 views

How to generate a large PSD matrix $A \in \mathbb{R}^{n \times n}$, where $\mathcal{O}(n) \sim 10^3$

I would like to generate a large PSD matrix, i.e., $A \in \mathbb{R}^{n \times n}$, where $\mathcal{O}(n) \sim 10^3$. The entries of the matrix should be randomly generated using a standard function ...
1
vote
2answers
66 views

Nesterov's momentum derivation

On page 75 in Sutskever's thesis http://www.cs.utoronto.ca/~ilya/pubs/ilya_sutskever_phd_thesis.pdf In equation (7.5) setting $a_0=1$, $a_{t+1} = (1+\sqrt{4 a_t^2 + 1})/2 $ The author said, "to ...
1
vote
1answer
41 views

What solver can I use to solve the following optimization problem?

Let $\xi_{1},\xi_{2},\ldots,\xi_{N}\in\mathbb{R}^{m}$, $\mu,\varepsilon\in\mathbb{R}$ with $\varepsilon>0$ (These are not variables, they are constant). We consider the following optimization ...
1
vote
0answers
319 views

How to solve this QCQP efficiently?

I'd like to solve the following quadratically constrained quadratic program (QCQP) \begin{equation}\label{bijective} \begin{split} \min_{x} \quad &x^{T}Ax\\ \mathrm{s.t.}\quad &...
1
vote
0answers
35 views

How to characterize objective function in order to choose optimization method?

What are some good quantitative metrics to describe an objective function that may help choose which optimization method will work best? E.g. if there are a lot of local minima we know that we ...
1
vote
0answers
77 views

Is there a stochastic analogue of Zangwill's global convergence theorem for deterministic descent algorithms?

Zangwill's well-known global convergence theorem (Zangwill, W. I. 1969. Nonlinear Programming: a Unified Approach. Englewood-Cliffs, N.J.: Prentice-Hall) provides sufficient conditions under which ...
1
vote
0answers
122 views

When does the nuclear norm fail to minimize rank?

Given $F$ and $G$, I'm solving the following problem: \begin{align} \min_{t} & \quad \mbox{rank}(A) \\ \text{s.t.}& \quad A = \text{diag}(t) F - G \\ \end{align} I used the nuclear norm, $\|...
1
vote
1answer
178 views

stochastic subgradient descent

When using stochastic subgradient descent, the solution $f_{best}(x_k)= \min \{f(x_1),f(x_2),....f(x_k) \}$, i.e., the best "point" over all the steps. As I understand, I should evaluate the function ...
1
vote
0answers
335 views

Learn Numerical methods in Python

Please suggest me some texts that I could use to learn Numerical Methods in Python (irrespective of 2.7 or 3.x). I would like to improve my coding skills with Python along with refreshing my math in ...
1
vote
0answers
59 views

Scaling/nondimensionalization for numerical optimization

I have a numerical optimization problem that I am trying to scale appropriately, in order to allow for the solver to achieve faster and more accurate results. I found a paper here that had a short ...
1
vote
0answers
381 views

Writing an accurate SDP solver in Matlab

As part of a research project I'm supposed to write an semidefinite programming solver in Matlab (similar to SDTP3, MOSEK, SEDUM, etc) except it needs to be able to solve to many significant digits ...
1
vote
1answer
112 views

How to solve this optimization problem analytically (parameter selection problem)?

My problem is as follows: \begin{align} \underset{\boldsymbol{x}}\max \quad & \boldsymbol r^T\boldsymbol x-\boldsymbol t^T\boldsymbol x \\ \text{s.t.} \quad & \boldsymbol1^T\boldsymbol x = N \...
1
vote
2answers
118 views

What is the best way to solve this QP?

I have been studying the following optimization problem in $x_0, \dots, x_{n-1}$ $$\begin{array}{ll} \text{minimize} & \frac{1}{2} \displaystyle\sum_{i=1}^{n-1} \left( x_{i-1} - x_i - y_i \right)^...
1
vote
0answers
395 views

Hessian of Euclidean norm of vector function

I'm not familiar with Matrix algebra. I'm trying to minimize an $\ell_2 $ (Euclidean) norm of vector function. I found out the gradient of the function, using the previous questions and answers in ...
1
vote
0answers
97 views

relation between L-BFGS and BFGS

In BFGS, we apply a rank-2 update to the approximate inverse Hessian ($H \in \mathbb{R}^{n \times n}$) at each iteration. This update adjusts for the curvature found from the change in gradient and ...
1
vote
1answer
64 views

Find $\alpha$ from the equations below.

I need to find $\alpha$ from the equations in below. Having the following constants: $C$, $K$, $N_k (1\le k \le K)$ and $\lambda_{k,i}(1\le k \le K, 1 \le i \le N_k)$. What would be $\alpha$ if: \...
1
vote
3answers
167 views

Algorithms For Lp Regression

So I know that L2 regression problems can be solved by simple autocorrelations and matrix inversions. Similarly, L1 and L$_{\infty}$ problems can be solved by linear programs. But what about Lp, ...
1
vote
0answers
43 views

Is there any method for gradient descent that achieves acceleration while moving always in the opposite direction of the gradient?

I'm studying gradient descent methods, in particular Nesterov's methods and others that achieve a better complexity (in terms of access to the gradient oracle) than regular gradient descent. In ...
1
vote
0answers
32 views

Optimization with probability constrain

Is there a clever way (analitically or nummerically) to minimize following objective function $$ L(W, W_{in}, W_1, W_2) = \sum_{t=0}^T (W + W_{in}W_{out})\vec{x}(t) \cdot (W_1+W_2 W_{out})\vec{x}(t) ...
1
vote
0answers
98 views

Find boundary of a set (interval), What to use?

So directly I will State my problem: Given $\epsilon >0$ and some function $f$, required to find $\epsilon_1, \epsilon_2 >0$ such that, for any $x_1, x_2 \in \mathbb{R}$ we have $$ |x_1|\leq \...
1
vote
0answers
30 views

Maximum likelihood of a non-injective transformation

Problem: Let $g(z|a,b,c,d) = a + bz + cz^2 + dz^3$ be a polynomial function of degree 3. Clearly, $g$ is not monotone increasing for all values of $a,b,c,d$. Suppose I observe data $Y_1, \cdots, Y_n$ ...
1
vote
0answers
23 views

Designing non-local polynomials for function approximation (spec. trig fun).

In the process of investigating this problem I encountered the following $\log_2$-plots of bitwise errors of the Taylor expressions of growing number of significant terms: By these plots it's quite ...
1
vote
1answer
44 views

Best approximation in the motivation of the GMRES method

Let $n\in\mathbb N$ $A\in\mathbb C^{n\times n}$ be invertible $b\in\mathbb C^n$ $x_0\in\mathbb C^n$ $r_0:=Ax_0-b$ Moreover, let $$\mathcal K_i:=\operatorname{span}\left\{A^0r_0,\ldots,A^{i-1}r_0\...
1
vote
0answers
474 views

Minimizing sum of two functions, minimize one and maximize the other.

I'm new in optimization and I have a problem involving minimizing the sum of two functions f(x) and g(x). The objective function must be in such a way that f(x) has to be minimized and g(x) maximized, ...
1
vote
0answers
39 views

A nonlinear optimization problem: numerical solution fails

I am working on a practical problem which requires a theoretical analysis. Specifically, the problem is: Given a list of items, each enclosed in a rectangular box and with a given weight, and given ...
1
vote
1answer
329 views

How to show that the method of steepest descent does not converge in a finite number of steps?

I have a function, $$f(\mathbf{x})=x_1^2+4x_2^2-4x_1-8x_2,$$ which can also be expressed as $$f(\mathbf{x})=(x_1-2)^2+4(x_2-1)^2-8.$$ I've deduced the minimizer $\mathbf{x^*}$ as $(2,1)$ with $f^*=-8$...
1
vote
0answers
177 views

numerical optimization algorithm with approximate Gradient and Hessian only!

Suppose I have a energy functional E depending on X, where X is a N-dimensional real value vector and N could be very large (~=2000). I assume that there exists (at least) a (local) minimizer for E. ...
1
vote
1answer
39 views

Understanding a bound in numerical optimization

I'm reading through the deepest descent method, and I'm struggling to understand a specific bound. I'll try to be as much clear as I can, but the notation used is a bit messy. It is basically ...
1
vote
0answers
372 views

Numerical - Optimization : Gauss-seidel implementation?

Reading through a book of numerical optimization the very first algorithm explained is the Gauss-Seidel one. Suppose we want to solve the problem $$ \min_{x \in \mathbb{R}^n} f(x) $$ Assume $f : \...
1
vote
1answer
80 views

Maximizing the logarithm of a rational function over a polytope

Which optimization technique/algorithm can be used to solve such problems? I want to know the name of a technique because some problems I need to solve are more complex than this one. \begin{align} \...
1
vote
0answers
26 views

H^1-Seminorm of nodal basis bounded

My question comes from the topic of Finite Elements (and domain-composition-algorithms). Consider the following setting: We have some domain $\Omega = (0,1)^2$ which is decomposed into rectangular ...
1
vote
0answers
62 views

Determine whether the nonconvex problem has a unique global minimum or not

The original optimization problem is in the constrained least square form as follows: $$\min\limits_{x_1,x_2,x_3,x_4,x_5,x_6\in \mathbb{R}} \left(\left(x_2^2+x_3^2+2 x_1-x_4+x_5-3 x_6\right)^2+\left(-...
1
vote
0answers
34 views

is this optimization formulation correct?

I define an optimization problem for the following scenario: Let $S={V_1,...,V_L}$ be a set of real valued variables, defined in domain $\ [0,1]$. I have constraints as follows. 1) I want sum of ...
1
vote
0answers
54 views

Minimize function over graph weights

I have given an absorbing Markov chain $P_t$ dependent on the transition probabilities $t:V \times V \rightarrow [0,1]$ for $V$ the states of the chain. Given is also a initial vector $x$ and a vector ...
1
vote
0answers
74 views

Minimization of a convex smooth function with implicit constraints

My goal is to minimize twice differentiable convex function $f(x):\mathbb{R}^n \to \mathbb{R}$ subject to constraints $x \in C_1$ and $x \in C_2$. However I have an issue with formulating $C_2$ as I ...
1
vote
1answer
649 views

Optimal Control/Runge-Kutta-4

I'm working through Lenhart and Workman's Optimal Control Applied to Biological Models, and I'm trying to apply the Forward-Backward Sweep Method w/ Runge-Kutta-4 as the DE solver to solve $$\max_{u}\...
1
vote
0answers
112 views

Is this algorithm for solving an inverse problem similar to any known algorithms?

The short version of my question is: I designed this algorithm for finding a solution for an inverse problem. Based on my research it is a new algorithm, does anyone know a similar algorithm? My ...
1
vote
0answers
187 views

Prove the steepest descent algorithm for solving $Ax = b$

Prove that the steepest descent algorithm for solving $Ax = b$, where $A$ is symmetric and positive definite, can be rewritten as follows: Compute the residual at the $k^{\text{th}}$ step: $r_k = b − ...
1
vote
0answers
55 views

Can this nonconvex optimization problem be tranformed into a convex problem?

I’m trying to solve the following optimization problem. Minimize M subject to $0=t_{1,1}\prec t_{1,2}=t_{2,1}\prec t_{1,3}\prec t_{2,2}=t_{3,1}\prec t_{3,2}\prec t_{2,3}\prec t_{3,3}=M$, $t_{j,k}=...
1
vote
1answer
156 views

Element-wise upper bound by rank-1 matrix

I would like to solve the following optimization problem for vectors $\mathbf{u} \in \mathbb{R}^m$ and $\mathbf{v} \in \mathbb{R}^n$, given a matrix $\mathbf{h} \in \mathbb{R}_{\geq 0}^{m \times n}$ ...
1
vote
0answers
423 views

Convergence of gradient descent method with non Lipschitz gradient

I would like to study the convergence of the gradient descent method applied to the function $$f(x)=|x-1|^3$$ In order to do that, I was thinking about using the following theorem: Assume that $...
1
vote
0answers
99 views

Numeric solution to summation with Hadamard product of vectors

I need to solve: $$\vec a_i\circ \vec b_i=\sum_{j}^n\alpha_{ij}\vec c_j\circ(\vec d_j-2\pi\tau_{ij})$$ For $\vec d_j$ and $\tau_{ij}$ when $\circ$ denotes the Hadamard product and $\vec a_i,\vec b_i,\...
1
vote
0answers
38 views

Optimisation problem: connectors

Suppose there are $n$ distinct points in the $\mathbb{R}^3$ space, namely $P_1,P_2,\ldots,P_n$. Define the distance matrix $M:=(d_{ij})_{n\times n}$, where $d_{ij}$ denotes the distance of line ...
1
vote
0answers
67 views

Finding zero of a matrix function via trust region subproblem

I have an issue with some steps carried out in a paper (https://arxiv.org/abs/1508.07497 sec 9.2.2) In order to perform a gradient descent step, we need to solve the following equation for the square ...
1
vote
0answers
96 views

Closed form solution to the Digamma recurrence relation?

The difference between two digamma function can be written using the following recurrence relation: $\psi(n+z) - \psi(z) = \sum_{i=0}^{n} \frac{1}{i + z}$ My question is, is there a closed form ...
1
vote
0answers
37 views

Expectation of Value Function

I am not sure whether this is the right place to ask this. I have solved a standard Bellman equation problem. The Value Function $V$ depends on 3 state variables: $K_t$, $X_t$, $Z_t$. The variables ...
1
vote
1answer
315 views

Why does Frobenius norm make BFGS scale-invariant?

On slide 11 here it is claimed that the weighted Frobenius norm leads to a scale-invariant optimization method. Similar claims about this norm can be found throughout the literature see 1,2,3. In ...
1
vote
0answers
459 views

Steepest descent method - proof in Nocedal and Wright

In Numerical Optimization by Nocedal and Wright, Chapter 2 on Unconstrained Optimization, (http://home.agh.edu.pl/~pba/pdfdoc/Numerical_Optimization.pdf) beginning on page 20, they verify that the ...