The tag has no usage guidance.

learn more… | top users | synonyms

1
vote
1answer
33 views

LASSO with equivalent quadratic costs

Is there any fundamental difference between the solutions obtained by minimizing following LASSO cost functions, if any? ( $A_{N \times n }$ and $ N >> n$) $ J=\Vert y-Ax \Vert_{2}^{2} + \...
0
votes
1answer
27 views

What's the relationship between automatic differentiation and gradient method?

I'm learning about shape optimization and in the numerical methods of shape optimization I've seen the terms automatic differentiation and gradient method. Doing a Google search gives an impression ...
2
votes
0answers
41 views

Convex optimization with $\ell_0$ “norm”

I have an optimization problem of the form $$\begin{align*}\text{minimize }\;&f(x)\\ \text{subject to }\;&||x||_0 \le t,\end{align*}$$ where $t$ is a given constant and $f:\mathbb{R}^d \to \...
1
vote
0answers
24 views

Explicit least-squares method for horizontal shifts of a function

I have a sequence of $N$ strictly positive real values $y_n$. They form some kind of peak; for simplicity, let's assume $f(x, \mu) = A \exp^{-(x-\mu)^2}$ is the shape, with $A$ and $\mu$ real (in the ...
1
vote
2answers
45 views

Optimization with L_infinity norm regularization

I'm trying to solve an optimization problem of the form $$\text{minimize } \; f(x) + \|x\|_\infty$$ where $x$ ranges over all of $\mathbb{R}^n$ and $f:\mathbb{R}^n \to \mathbb{R}$ is a nice, smooth, ...
3
votes
0answers
35 views

how to find the the maximum of an implicit function

I have an implicit function and I would like to find the value of $h$ that maximizes $R$, i.e, I want to find $h$ that satisfies $\frac{\partial R}{\partial h} = 0$. The function is, $C=\frac{A}{1+\...
2
votes
0answers
24 views

Does converting an inequality constraint to an equality one have any major impact on an optimization solver?

In an optimization problem, I have an inequality constraint, say $\begin{array}{c} {\min\limits_x~} c(x)\\ {s.t.~}g(x)\le 0 \end{array}$ The function $g(x)$ in general is unknown. So, numerical ...
0
votes
0answers
24 views

Sequential versus simultaneous optimization of multivariate problems

Suppose we have the bivariate function $f(x,y)$. I want to solve the following problem: \begin{equation} \min\limits_{(x,y)} \; \; f(x,y) \end{equation} I want to prove theoretically that ...
0
votes
2answers
29 views

Optimization of the function of two variables

I have two functions $f(x,y)$ and $g(x,y)$. I want to minimize the sum of these functions w.r.t $x,y \in (0,1)$. I know that for fixed values of $x$, $f(.,y)$ is a decreasing function while $g(.,y)$ ...
-1
votes
1answer
16 views

Sum of convex and decreasing function

I have a sum of decreasing function and a convex function over some domain. Can I say that the sum is also a convex function (i.e. there exists a unique minimum)?
1
vote
1answer
34 views

Quasi-newton methods: SR1 and BFGS inverse update

In Numerical Optimization by Nocedal and Wright, (http://home.agh.edu.pl/~pba/pdfdoc/Numerical_Optimization.pdf) Chapter 2 on unconstrained optimization, page 25 top, the authors claim that "The ...
0
votes
1answer
19 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 ...
0
votes
0answers
23 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 ...
4
votes
1answer
60 views

Prove $\int_\Omega f(x) \,dx=f(x_B) \int_\Omega1 dx+ \mathcal O(\int_\Omega1 dx \cdot \sup_{x,y\in\Omega}\|x-y\|_2^2)$?

Let $\Omega \subset \Bbb R^n$ be a convex domain and $f: \Omega \to \Bbb R $ and $f \in \mathcal C^2(\Omega)$. Let $x_B $ be the barycentre of $\Omega$ with $$x_B:= \frac{\int_\Omega x \,dx}{\int_\...
4
votes
2answers
145 views

Proving a contraction mapping is a Cauchy sequence

Let $\phi(x):[a,b]\rightarrow [a,b]$ be a continuous function. Show that if $\phi(x)$ is a contraction mapping on $[a,b]$ then the sequence $\{x^{(k)}\}$ defined by $x^{(k+1)} = \phi(x^{(k)})$ is a ...
1
vote
0answers
23 views

Gradient Descent and Scale of Data and Objective Function

One way to tune step size in gradient descent is via backtracking line search. backtracking line search (with parameters α ∈ (0, 1/2), β ∈ (0, 1)) starting at $t = 1$, repeat $t := \beta t$ ...
0
votes
0answers
14 views

Multi-objective optimization or single objective optimization?

I have this function: A(x)= P(x) / B(x) Firstly I thought about doing an multi-objective optimization, maximizing A(x) and minimizing B(x) because this two values are very important. But if I just ...
0
votes
0answers
12 views

Optimized placing of same-size squares into rectangles

Suppose that we have several squares of the same size. We want to draw n rectangles (red and yellow rectangles here) to contain these squares. The goal is to have ...
0
votes
0answers
21 views

Non linear functional optimization under constraints

For some given positive functions $l(t)>0$ and $h(t)>0$, such that $h(t)>l(t)$, I want to solve this functional optimization problem on $a(t)$: $\min_a\int_0^T[l(t)\cdot\min(a(t),0) + h(t)\...
0
votes
1answer
26 views

Exact line search in convex optimization

For a convex function $f$ what do we know about convexity of the exact line search problem? $$\min_{\alpha \ge 0} f(x+ \alpha p_k)$$ I think because the function is convex and is linear in variable, ...
1
vote
0answers
14 views

Numerical Method for fitting parameters of an explicit integration to actual data

I have a heat transfer system described by, $$\{\dot{T}\} = [C^{-1}]\left([K]\{T\} + \{F\} \right)$$ where ${T}$ is a vector of the nodal temperatures of the system. From initial conditions I am able ...
0
votes
1answer
54 views

Check numerically the definite-positiveness on linear subspaces

I have a given matrix $W\in \mathbb{R}^n$ with known fixed entries. I would like to check the definite-positiveness of $W$ on appropriate linear subspaces. Typically I would like to show (...
0
votes
0answers
24 views

Interplanetary Optimisation using a simulator with PyGMO or SciPy

I am currently trying to use a N-body gravity simulator to model a spacecraft trajectory and using the simulator as a BlackBox to optimise the trajectory. I am thinking of using basin hopping/ ...
1
vote
2answers
100 views

Decrease in the size of gradient in gradient descent

Gradient descent reduces the value of the objective function in each iteration. This is repeated until convergence happens. The question is if the norm of gradient has to decrease as well in every ...
1
vote
1answer
20 views

Matrix similar and unitarily diagonalizable

Let $A,B \in R^{n \ x \ n} $ similar and unitarily diagonalizable. Prove that there $Q$ unitarily such that $Q^{H}AQ=B$
0
votes
0answers
47 views

How can I solve this optimization problem?

How do I solve this optimisation problem? $$W = \left(\frac{n(X-Y-Z)p}{Zq}\right)^{1/a},\, a>0$$ $\operatorname{Max}\{ W\}$, subject to $0\leq n \leq 1$, $0\leq Y \leq X$ and $Z \leq Z_{max}$ ...
1
vote
1answer
25 views

Can someone help me understand using the Jacobian matrix with Newton's Method for finding zeros?

I'm struggling to understand approximating solutions to non linear equations using a Jacobian matrix. I understand intermediate steps, but I'm unsure how everything comes together. I want to use ...
0
votes
1answer
26 views

Does convergence of iterates imply convergence of function values?

The question came to my find when I was reading convergence of gradient descent. However, my question is general and does not necessarily stick to GD. Concretely,my question is: \begin{equation} \|x^k-...
0
votes
1answer
25 views

Rate of Convergence vs Tolerance

I have this confusion that if I know that a numerical method has a rate of convergence equal to $O(c^k)$ (see this link, page no .8), then how to find the number of iterations to reach a tolerance of $...
2
votes
0answers
35 views

Index of a stationary point of constrained optimization

For an unconstrained optimization problem with objective function $F(x,y,z)$ the index of a stationary point is well-defined: If $(x^*, y^*, z^*)$ is a point where the gradient of $F(x,y,z)$ vanishes, ...
0
votes
0answers
17 views

Converting a sum over squared norms to Quadratic Programming problem

I'm trying to minimize the following function which is a function of a set of vectors $\vec{x}_i \in \mathbb{R}^2$, and is parametrized by the fixed parameters $\alpha, \beta,\gamma_i,\vec{u}_i$ where ...
1
vote
0answers
27 views

Computational complexity of conjugate gradient method for a positive semidefinite Hermitian matrix

Let us assume that we want to solve the linear system: $$\mathbf{A}\mathbf{x} = \mathbf{b}$$ with the conjugate gradient method. $\mathbf{A}$ is a positive semi-definite Hermitian matrix. The ...
1
vote
1answer
35 views

Calculating block diagonalization / canonical bases with linear optimization?

Edit Even though I have started answering my own question I am still eager to hear any feedback and new ideas. So feel free to tell me if you come to think of anything. In Linear Algebra there are ...
1
vote
0answers
27 views

Find the “optimal” placement of $n$ points in a polygon

I was hoping someone could help me with a question I've been pondering the past few days. I searched the usual places (google, journals, texts, etc) but couldn't find anything that fit the bill, but ...
0
votes
0answers
8 views

what is an efficient way to accomodate squares on an irregular big area?

I'm trying to use efficiently the space in this ship, there are 3x3 guns and 1x1 guns, the best guns are 3x3 so having more is better. Is there an algorithm or a program which help me find the best ...
0
votes
0answers
30 views

Parameter estimation with polynomial cost function

I am working on a model that can be written in its simplest form as $$ \mathbf{d_1}=a\,\mathbf{d_2}+b\,\mathbf{d_3}+ab\,\mathbf{d_4}, $$ where $\mathbf{d_i}$ are some data columns and $a,b$ are ...
0
votes
0answers
18 views

How to numerically evaluate a integral whose limits are functions of x (using Gauss quadrature rule)?

I am trying to numerically evaluate an integral $\int_q^1 \ln (\sum_i \alpha_ix_i) dq$, in which $\ln (\sum_i \alpha_i x_i)$ is related to $q$ via the following: $z_i=(1-q)\frac{\alpha_ix_i}{\ln (\...
1
vote
0answers
27 views

Numerical stability of computational results

Let z be a function of a finite number of variables i.e. z=f(a,b,c,...). If we have the mathematical formula connecting z and the variables, we can determine how the value of z varies with a change ...
0
votes
0answers
13 views

Why is it that if a numeric method has quadratic rate of convergence then it can reach d digits of precision in logd iterations?

I was trying to understand why a method with quadratic convergence can get close to a good solution in $\log d$ iterations. Assume we have a method that has the property that the number of digits of ...
0
votes
1answer
19 views

Correct formulation of equality and non-negativity constrained non-linear minimization problem

I am trying to minimize a non-linear function with both equality and non-negativity constraints numerically (not analytically) using gradient based methods and without software packages. $f(x)=x_1^2+...
1
vote
0answers
36 views

How does one rigorously prove that gradient descent indeed decreases the function in question locally i.e. show $f(x^{(t+1)}) \leq f(x^{(t)})$?

How does one prove that gradient descent indeed decreases the function in question locally? In other words if we take a step in the negative of the gradient as in: $$ x^{(t+1)} = x^{(t)} - \eta \...
1
vote
0answers
34 views

Minimize/Maximze a function against its approximation.

Let $f \in C^{\infty}[1,2]$ be a function we would like to approximate, let be $g$ such approximation, you can assume $g$ is a spline function (at least quadratic). In literature I have seen that a ...
0
votes
0answers
13 views

Quasi Newton updation matrix

How to prove that Quasi Newton updation matrix $B_{k}$ is positive definite for every iteration and it converges to $H^{*}$ ?
0
votes
0answers
7 views

Testing an SR1 update for approximate Hessian

I have written a function in MATLAB to run an SR1 update for an iteration of a Trust Region method to find a new approximate Hessian and its inverse, but I need to test it to check it works. Are ...
0
votes
0answers
12 views

Which are the alternative approaches to stochastic (online) gradient descend for online optimization?

I'm looking for some alternative approaches to online\stochastic gradient descent for online optimization such that 1) there exists some proof about the convergence of the parameters to some compact ...
0
votes
0answers
14 views

Equality constraints into inequalities constraints through elimination

I read here in Section 10.1.2 of this text that a way to eliminate linear equality constraints of the type $$Ax = b$$ in convex optimization problems is to parameterize the related affine space as a ...
0
votes
0answers
29 views

equality constraints and conic constraints in Sedumi (SOCP)

I´m starting playing with Sedumi. I want to solve a problem in the form $$ \min c_0' x $$ s.t. $$ A_1 x = b_1$$ $$ ||A_2 x + b_2|| <= c_2'x+d_2 $$ where $x \in R^n$, $ A_1 \in R^{m_1,n}$, $ ...
2
votes
0answers
44 views

Isotonic regression like

I have 2 ordered sets $$X=\{X_1<\dots<X_n\}$$ and $$Y=\{Y_1<\dots<Y_m\}$$ with $X_1<Y_1$ and and $X_n<Y_m$. I wish to approximate an increasing continuous function $g$ by piecewise ...
0
votes
0answers
19 views

Exact line Search in Steepest descent

I wanted to clarify the idea of the exact line search in steepest descent method. An exact line search involves starting with a relatively large step size ($\alpha$) for movement along the search ...
0
votes
0answers
14 views

Scaled gradient descent

Consider the unconstrained minimization \begin{align*} \min_{x\in\mathbb{R}^n}f(x) \end{align*} One iterative approach to obtaining a solution is to use the gradient descent algorithm. This algorithm ...