The tag has no usage guidance.

learn more… | top users | synonyms

0
votes
0answers
17 views

Global optimization methods where constraints are lipschitz functions

Is there any global optimization methods where objective function is nonlinear (not lipschitz) but constraints are lipschitz functions?
0
votes
1answer
59 views

Optimizing sums of log det

I have a set of points $S$ which have to be clustered into $K$ cluster say, $S_k$, by minimizing the following function: $J = - \sum_{i=1}^{K} \log \det( \mathbf{I} + H_i H_i^T)$, Where $H_i$ is the ...
0
votes
0answers
8 views

Speeding up Conjugate Gradients iterations for Sparse Matrices?

I've been using Conjugate Gradients to minimize linear systems involving sparse matrices. Although many of my sparse matrices are highly specialized - i.e. for any given row it is easy to know which ...
0
votes
0answers
28 views

Maximum volume inscribed ellipsoid inside nonconvex polyhedron

In Convex Optimization (Boyd, Vandenberghe), an algorithm for finding the maximum volume inscribed ellipsoid inside a convex polyhedron is given on p. 414 (8.4.2 Maximum volume inscribed ellipsoid) [I ...
0
votes
0answers
13 views

numerical solution for nash equillibrium

I have the following setup. $\pi_1=f_1(q,r)$ and $\pi_2=f_2(q,r)$ are the real valued payoff/profit functions of the two players. Player 1 gets to pick $q$ and player 2 gets to pick $r$. I also know ...
0
votes
0answers
11 views

Scaling issue with Gradient descent methods

As is the common knowledge that gradient methods are affected by scaling issue of the variables. For example, If minimizing a function of say 2 variables $x_1$, $x_2$. Both variables have different ...
1
vote
1answer
65 views

Maximization of a nasty Gaussian likelihood

I have a Gaussian likelihood function, $$p(y|x) = \mathcal{N}(y; Ax, (x^\top V x + \lambda) \otimes I)$$ where $A,V,\lambda$ is known, and $\otimes$ is the Kronecker product. (the notation indicates ...
0
votes
0answers
17 views

Nonsmooth Gauss-Seidel minimization (coordinate descent)

I have attempted to implement the coordinate descent algorithm for a separably convex problem of the form $$\min \sum f_i(x_i) \\ \text{s.t.} \ Ax = b $$ using the augmented Lagrangian ...
0
votes
4answers
65 views

What does it actually mean if a cost function is differentiable?

I am just learning about optimization, and having trouble understanding the idea behind differentiating cost functions. I have read that for standard optimization problems, the cost function needs to ...
0
votes
1answer
29 views

Gauß-Newton Example with one variable

$$T=f(t):=2 \alpha + \sqrt{\alpha^2+t^2}$$ To estimate $\alpha$ we got the measured values $T_i$ for $t_i$. Formulate the curve fitting problem and show each step in the Gauss-Newton algorithm. My ...
0
votes
0answers
22 views

Non-Linear Constrained Optimisation Over Zonotopes: Reference Request

Background I am investigating, numerically, the problem of a chess team attempting to maximise its probability of winning a team match . Each of our N players independently chooses one of two ...
0
votes
1answer
32 views

Automatic way to have a good initial guess for the iterative methods ( newton method) and for high dimensional nonlinear problems

I am solving a variety class of nonlinear systems where I need to reduce in optimal manner the number of iterations of either the newton or modified newton method. For this end I am trying to figure ...
1
vote
0answers
28 views

Numerical method for wave equation with nonlinear forcing in 1+1 D

I am looking for numerical method to solve the equation $$ \square \phi = \frac{\partial^2 \phi}{\partial x^2} - \frac{\partial^2 \phi}{\partial t^2} = \lambda \phi^3 \, $$ for real $\phi = ...
0
votes
0answers
9 views

Numerically/Computationally estimating parameters

I have a function $f(x)$ and I have an estimating function $\hat f(a,b,c,d;x)$ Say, I also have a scoring function $S(f,\hat f,x)$ (which could very well be mean square error) And I have some ...
0
votes
0answers
30 views

Identification of non-linear functions:polynomial+exponential

Is there a way to perform a non linear least square to identify the following function: $$\alpha_2\cdot x^2 + \alpha_1\cdot x + \alpha_0 + \beta e^{\frac{\gamma}{x}}=Y$$ I aim at identifying the ...
0
votes
1answer
36 views

Local extrema in special directions

I am looking for the extrema of a function $G(y_1,y_2,y_3,y_4)$ subject to the constraint $y_1 = y_4 + y_2y_3.$ We know that $G$ is defined if $(y_2,y_3,y_4)$ is in the cylinder $\mathbb{D} \times ...
1
vote
0answers
16 views

Convergence results for block coordinate descent methods

I am trying to solve the problem minimize $f(x)$ subject to $x_1 \in C_1, x_2\in C_2, ... x_m\in C_m$ where $x_1, ..., x_m$ are block subvectors of $x$, and $C_i$ are each closed convex sets (not ...
0
votes
1answer
21 views

Partial derivative of a matrix multiplied by a vector wrt matrix

Given a matrix $A$ and and two vectors x and b, what is the gradient of $(A\cdot x-b)^2$ with respect to $A$? (I am trying to find the matrix which best sustains a given linear equation using gradient ...
1
vote
0answers
17 views

Integrating over particular grids to obtain Spherical Harmonic coefficients

Theoretically the spherical harmonic expansion coefficients of a function $f$ should be calculated via a continuous integration: $$F_{lm} = \int_{0}^{2\pi}\int_{0}^{\pi} ...
2
votes
0answers
18 views

Reference request for finite difference method

I am trying to use finite difference method to solve the minimizing problem $$ J[u]=\min_{u\in BV(Q)}\{\|u-f\|_{L^1(Q)}+|u|_{BV(Q)}\} $$ where $Q=(0,1)\times (0,1)$ is a uint square and ...
3
votes
2answers
58 views

Lagrange multiplier and minimum variance

Looking into a control variate technique of Monte Carlo simulation I have run into a cost-optimization problem that I'm not quite sure I understand. It seems it has to do with Lagrangian multipliers, ...
0
votes
1answer
42 views

Iterative method to compute only the positive eigenvalue's and corresponding eignevectors of a very large matrix?

I have a very large dense matrix (~10000 X ~10000) which is not full rank . I want to compute only the positive eigenvalues and corresponding eigenvectors instead of computing all of them. I have ...
0
votes
1answer
24 views

Optimization: maximizing nonconvex sum of product of constraints

I'm wondering if there is any way to convexify, approximate, and/or simplify the following problem. $\max. \sum_{k \in K} \prod_{i \in I} (a_{ik} x_{ik} + b_{ik})$ s.t. $x_{ik} \in [0,1]$ where ...
1
vote
2answers
115 views

Solving a matrix equation using numerical optimization

To my knowledge, if $A \in \mathbf{S}^n_{++}$, then given any $b \in \mathbb{R}^n$, the system of linear equations $Ax = b$ has a unique solution $x^* \in \mathbb{R}^n$. Moreover, the solution $x^* ...
1
vote
1answer
35 views

In an ODE dynamic system, is there a convient way or algorithms for estimating the parameters which make the ODE solution satisfing some constraint?

I have construct a ODE dynamic system like this $$molA(t)==sa$$ $$molB'(t)=sb-db\;molB(t)+\frac{kab\;molA(t)\;molB(t)}{molB(t)+Jab}-\frac{kgb\;molG(t)\;molB(t)}{molB(t)+Jgb} $$ $ molC'(t)=sc-dc\ ...
0
votes
1answer
23 views

Minimizing nonsmooth single variable functions?

What options is available if one wants to minimize a nonsmooth convex function of one variable? Subgradients would work, but there has to be some nice way of utilizing that we're only searching in 1d. ...
-2
votes
1answer
22 views

Adjust the data up curve φ(x) = α1e^(α2x) by the method of least squares

Adjust the data up curve φ(x) = α1e^(α2x) by the method of least squares: Here's what I've done so far but I think it is wrong(and sorry for the bad english) --x | 0    | 1    | 2   | 3   | 4   ...
0
votes
0answers
15 views

Lagrangian multiplier vectorial form

When i have this problem: $min f(x)$ $h{_i}(x)=0, i=1,\dots,m$ $g{_j}(x)<=0, j=1,\dots,p$ I can use the Lagrangian multiplier to write function in: $L(x,\lambda,\mu)=f(x)+\sum_{i=1}^{m} ...
0
votes
0answers
33 views

Optimum point of $f(s) = \int_0^{\pi} \frac{ \exp(-s) y \cos(ky)}{s^2+y^2} \,dy $

Is it possible to find optimum point for the following function f(s) (i.e. $df/ds=0$): $$ f(s) = s e^{-s} \int_0^{a} \frac{ y \cos(\frac{\pi}{a} y)}{s^2+y^2} \,dy $$ or $$ f(s) = s e^{-s} ...
0
votes
1answer
42 views

Efficient algorithm to find the maximum of a sum of $m$ sines

Is there an efficient algorithm to find the maximum of a sum of $m$ sines? That is, find an $x \in \mathbb{R}$ such that $$f(x) = \sum_{k=1}^m \sin(\alpha_kx)$$ is maximized? By efficient, we mean an ...
0
votes
1answer
64 views

Complexity of Newton iteration problem for a d-dimensional problem

If we assume that we have $f:\mathbb{R}^{d} \rightarrow \mathbb{R}^{d}$ and we want to use the Newton iteration method to solve $f(x)=0_{\mathbb{R}^{d} }$. Is there any theorem regarding the ...
0
votes
0answers
164 views

Linear - Quadratic optimization for system of objectives

I have two distinct data sets, $\{x^{\mu},J^{\mu}\}$, $\mu=1,\ldots,n$ and $\{x^{\nu},V^{\nu}\}$, $\nu=1,\ldots,m$ that also include uncertainties $\delta J^{\mu}$ and $\delta V^{\nu}$. In these I fit ...
-4
votes
1answer
38 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
33 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
54 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
37 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
29 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
78 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
82 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 ...
1
vote
0answers
29 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
185 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
18 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
33 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
56 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
41 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
77 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
47 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
62 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 ...