The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
10 views

Analysis of Optimizatiointechniques: Regret Analysis vs. Direct convergence? [on hold]

When it comes to convergence rate analysis of optimization algorithms (like gradient descent and its family), there seems to be to be two main: Direct analysis, i.e. bound on $$ |f(x_t) - f(x^*)| ...
-2
votes
1answer
30 views

Linear Algebra - minimal polynomial, polynomial

the minimal polynomial of $A$ is $(x−1)(x+1)$. Let $f(x)=4x^{2008} − 8x^{597} + 10x + 6$ show $f(A) = \alpha I + \beta A$ $\alpha=?\ \beta=?$ So I worked on a bit, and I got this far $A = ...
1
vote
0answers
17 views

Do quasi-Newton methods check the second-order optimality condition?

I have a practical question about quasi-Newton methods. In quasi-Newton methods, Hessian matrix is approximated. It seems to be impossible for them to check the second optimality condition. In ...
2
votes
2answers
38 views

Why a convex cone cannot have more than one extreme point?

The way I define an extreme point is : A point which cannot be defined as a convex combination of two distinct points. I'm not able to extend this and show why a convex cone cannot have more than ...
1
vote
1answer
29 views

Problem with Broyden update: Divide by a matrix?

I am implementing a maximum likelihood method (the EM algorithm) for which I'm using Broyden's method at each iteration. Here is the formula: $\Delta A = \frac{(\Delta \theta - A ...
1
vote
1answer
20 views

Showing that a given function is convex.

I am trying to show that the function $f(x,\vec{y})=\alpha\ln(1+\exp(x+\vec{y}\cdot \vec{z}))+(1-\alpha)\ln(1+\exp(-x-\vec{y}\cdot\vec{z}))$ is a convex function of $(x,\vec{y})$ (where ...
7
votes
1answer
70 views

Singularity of a positive linear combination of rank one matrices

Given a set of rank one matrices $A_1,..,A_n$, we need to find out if there exists $x \in \mathbb R^n$ with $x\gg 0$ (i.e, positive) such that $$ \sum_{i=1}^n x_i A_i = x_1 A_1 + .... + x_n A_n $$ ...
1
vote
1answer
37 views

Augmented Lagrangian Method for Inequality Constraints

Augmented Lagrangian Method can be used with inequality constraints. The question is how. One approach (according to Numerical Optimization Book by Nocedal and Wright; page 522), is linearly ...
0
votes
0answers
24 views

bound on Lagrange multipliers [closed]

Under what conditions is it possible to bound the Lagrange multipliers in a given optimiztion with constrains problem?
1
vote
0answers
24 views

Importance sampling estimate

Suppose that one is interested in estimating the tail probability $$ P(Z \ge b) $$ for $$Z \sim N(0,1)$$ and a large threshold b. What is the expression for the importance sampling estimate with ...
1
vote
0answers
174 views

Global and local maxima in a weighted sum of logarithms of linear functionals?

Is is possible to describe, and locate efficiently, the maxima of the function below in the parameters $\mathbf{x}$ $$\sum_{i} p_i \log( N + \sum_j x_j[B_j +(A_j-B_j)\delta_{ij} + min(A_j,B_j) ]) ...
0
votes
0answers
16 views

Minimizing a function known to have a unique local and global minimum

Quasi-convex functions are a class of functions known to have a unique local and global minimum, which can minimized over convex sets using numerical methods with convergence guarantees. A function is ...
0
votes
1answer
18 views

Steepest descent method and how to find the weighting factor [duplicate]

I am trying to understand the numerical method of finding a minimum, the steepest descent method. \begin{equation} x_1 = x_0 - \alpha \frac{df}{dx} \end{equation} I understand the idea behind it and ...
1
vote
1answer
43 views

how to write largest circle inscribed inside a triangle as an optimization problem?

can someone show me how to write this problem as a convex optimization problem.Find the largest disk that can be bounded by $X \geq 0$ , $Y \geq0$ and $X+2Y\leq1$. My institution is to cast to ...
0
votes
0answers
22 views

Best set of subgraphs of a weighted complete bipartite graph

Consider a weighted complete bipartite graph, i.e. consider the graph $G=(V,E)$, with $V=X \cup Y$, $X \cap Y = \emptyset$ and $E = X \times Y$, and a set of weights $W=\{w_i : i \in E\}$. Now we ...
1
vote
0answers
29 views

Good convergence criterion for stochastic optimization?

This is a question that has bothered me quite long, as I have faced it many different optimization and equation solving problems. The basic idea is that one wishes to minimize $F(x)$ and has one ...
1
vote
2answers
65 views

How to solve a matrix equation for a scalar?

Given matrices $Q, P \succeq 0$, a vector $q$, a real number $\gamma$. How can one solve the equation $ q^T (Q+\lambda P)^{-T}P(Q+\lambda P)^{-1} q = \gamma$ for the scalar $\lambda$ in an efficient ...
0
votes
0answers
28 views

Numeric solution for a non-linear system

It has been a while I have not practiced mathematics but I should have enough background to get your answers if well detailed. I have an n-by-n matrix, let's call it D, where dij represents the ...
0
votes
1answer
32 views

Advice to solve a system of 8th order univariate polynomials

I am struggling to solve a least square problem in which the tedious part is the initialization. Grid search methods are out of question. The initial problem I've stated my problem in a previous ...
0
votes
1answer
43 views

Getting an improved upper bound for a finite geometric series

The title says it all. For an infinite geometric series, we know that if $|x| < 1$, then $$\sum_{i=0}^{\infty}{x^i} = \frac{1}{1 - x}.$$ On the other hand, if $|x| \geq 1$, then the the infinite ...
1
vote
2answers
65 views

Newtons's Method

If when you are using Newton's method and your results are just going back and forth between two values, say $0$ and $1$. It is $f(x)=x^3 -2x+2$ starting with $x=1$. What is the reasoning behind ...
1
vote
0answers
36 views

Powell vs Levmar

I'm learning about the application of numerical optimization, and noticed that in one of the programs that I'm using it uses Powell's method to get parameters of a piece-wise function, and Levmar if ...
1
vote
0answers
20 views

Levenberg-Marquardt - What is preferable (A + mu.I) or (A + mu.diag[A])?

The step size is computed by solving (A + mu I) h = -g I could find in some literature that one can compute the step size by solving (A + mu A') h = -g where, A' = diagonal(A) It is said that ...
0
votes
0answers
17 views

Rationale for extrapolation and interpolation in line search

I am studying for an exam right now and I need to know the rationale for the extrapolation and interpolation mechanisms in line search. I understand the line search algorithm but I do not know what ...
0
votes
1answer
25 views

Comparison of augmented and standard Lagrangian methods

I understand that augmented Lagrangian methods, add penalty terms to standard Lagrangian method. The question is what is wrong with original standard Lagrangian method, that made people add a ...
2
votes
1answer
31 views

A Variant of Gradient Descent

Suppose I have some objective function $f(\beta)$ which I would like to minimize for $\beta$. A standard gradient descent would be $\beta^{(t+1)}=\beta^{(t)}-\alpha \nabla f(\beta^{(t)})$, where ...
0
votes
0answers
54 views

Nonsmooth optimization

Now I have a chance taking a course in nonsmooth optimization, the course outline writes: convex analysis, subdifferential calculus and proximal mapping. various numerical algorithms to solve ...
1
vote
0answers
18 views

Numerical optimization in function space

I'm new to calculus of variations. I'm curious about how to apply simple numerical optimization techniques in function space. Consider the classical problem: finding the shortest path between two ...
0
votes
0answers
5 views

showing something supposedly obvious in the proof of the fletcher-powell algorithm

I read the paper below and understand most of it. But there is one statement that I don't follow that I guess is straightforward to show. It's not necessary to look at the paper but it has to do with ...
1
vote
0answers
31 views

Efficient method for refining parameters in nonlinear curve fitting

I have time-series electrical current data $i(t)$ with transient steps in it which are convoluted with the hardware filter used in data acquisition. As a result, the real steps in current, which would ...
1
vote
1answer
23 views

why not handle box-constraints with a transformation

I have a question that I've always wondered about concerning the "L-BFGS-B" algorithm. I am not familar with the details of the algorithm except for the fact that it optimizes a non-linear function ...
0
votes
0answers
26 views

integration rule for singular function

It is well known that for sufficiently smooth function $f(t)$, error bounds for midpoint are $$ \int_{t_i}^{t_{i+1}} f(s)ds=hf(t_{i+1/2})+\frac{h^3}{24}\frac{d^2 f(s)}{ds^2}|_{s=t_i} +O(h^5). $$ where ...
1
vote
1answer
68 views

Why easier to numerically minimize than to maximize a function

Is it easier, in terms of coputational complexity or speed, to numerically minimize a function $f$ than to maximize $-f$? Why is that so? I have noticed that most optimization algorithms in Matlab are ...
1
vote
0answers
39 views

saddle point versus local extermum

Suppose a function $f$ from $\mathbb{R}^n \to \mathbb{R}$, is differentiable. We know that $c$ is a critical point of $f$, i.e. $\nabla f(c) = 0$. Our goal is to find out if $c$ is a local extremum, ...
3
votes
2answers
89 views

Good Textbook in Numerical PDEs?

I am currently taking a course on Numerical PDE. The course covers the following topics listed below. Chapter 1: Solutions to Partial Dierential Equations: Chapter 2: Introduction to Finite ...
0
votes
1answer
33 views

Finding the basis functions given the boundary values and values of derivatives at the boundary

Given an interval $I=[a,b]$ we define $$P_3(I):=\{v:I\rightarrow\mathbb{R}\mid v \text{ is a polynomial of degree} \leq 3 \text{ i.e } \\v=a_3x^3+a_2x^2+a_1x+a_0 \text{ for } a_i\in\mathbb{R}\}.$$ How ...
0
votes
0answers
19 views

How to choose a proper numerical optimisation method

Given a problem in numerical analysis in finance/econometrics, how to decide whther to choose Monte Carlo, Newton Raphson , Finite Difference , Gradient descent? I had this silly misconception that ...
0
votes
0answers
35 views

What does coordinate descent actually do?

We've done a bunch of theoretical stuff in my optimization class, but basically no time for the actual implementation details. I'm trying to get an understanding of coordinate descent, which if I'm ...
2
votes
0answers
21 views

discrete nonlinear convex optimization relaxation over a dense set

Be a discrete nonlinear convex optimization problem $P$ \begin{align} \underset{x\in \mathrm{C}^n}{\mathrm{min}} \ \ \ f(x) \\ Ax=b \\ c \leq x \leq d \end{align} $C$ is a dense in $F$. Is solving ...
1
vote
1answer
41 views

What does 'the level set is bounded' exactly want to tell?

'The level set is bounded.' occurs in many theorems and other places. I think I can understand the definition of 'level set' but I don't know what does 'it's bounded' want to tell me exactly in ...
1
vote
1answer
152 views

Finding minimum point of banana function using Newton's Method

I am using the banana function $F(x_1,x_2)=(1-x_1)^2+100(x_2-x_1^2)^2$ over $x_1,x_1 \in \Re$. I am using $f_1(x_1,x_2)=0, f_2(x_1,x_2)=0$ to find the minimum point of $F$ which it is (1,1). Now I ...
2
votes
0answers
146 views

Direct multiple shooting (numerical optimal control)

please, Iam currently implementing direct multiple shooting method* and I need one simple but fundamental concept answered: When I want to provide not only objective funtion value (result of ODE ...
0
votes
1answer
57 views

Distributed Newton methods for large scale problems

I am keen to know about the literature landscape for distributed convex optimization methods which use second order information like the Newton step. This is as such a less evolved area compared to ...
0
votes
0answers
21 views

How to approach this optimization problem with “sorted” constraint

I have formulated an optimization problem and I'm not sure how to go about solving it intelligently. I have three vectors $ a, p, n$, all with the same number of elements. I know what $p$ and $n$ are ...
0
votes
1answer
36 views

Nearest-neighbor interpolation

I read in a book that the nearest-neighbor interpolation results in a function whose derivative is either zero or undefined. Can anyone explain what does it mean when the derivative of a function is ...
1
vote
0answers
87 views

Solution of equations involving determinant and matrix inverse

$x$ and $y$ are two scalar unknowns. The two equations are $$|\mathbf{I}+x\mathbf{h}_1\mathbf{h}'_1+y\mathbf{h}_2\mathbf{h}'_2|=R$$ and ...
7
votes
3answers
284 views

The Integral of Multiple Tangent Functions

I need help to find the numerical values to the precision at least $50$ digits (the closed forms if possible) for the following integrals \begin{equation} ...
0
votes
0answers
42 views

How can be a conservative field constraint be efficiently implemented in a continuous optimization problem?

Suppose we have the following continuous optimization problem: $$ \underset{x}{\mathrm{minimize}}f\left(x\right) $$ subject to $$ \exists X:\nabla X=Jac\left(X\right)=x $$ where $f$ is a function ...
0
votes
0answers
30 views

constraint optimization: sparsity with non zero constraints

I have an obtimization problem in the following form. $\min f(x)\\ s.t \|x_i\|_0\leq\lambda\\ x_i \geq0\\ \sum_i x_i = 1$ where $f(x)$ is convex. What is the easy way to optimize it as I have a ...
0
votes
1answer
35 views

A question on a nonnegative quadratic form

Denote $x,y,z$ as variables, and $a,b,c$ as coefficients. Suppose $a\leq b\leq 0\leq c$ and $a+b+c=0$. Could anyone help me prove whether the following quadratic form positive semi-definite? ...