Optimization is the process of choosing the "best" value among possible values. They are often formulated as questions on the minimization/maximization of functions, with or without constraints.

learn more… | top users | synonyms (5)

4
votes
2answers
170 views

Minimum of an apparently harmless function of two variables

I would like to prove that the minimum of the function $$ f(x,y):=\frac{(1-\cos(\pi x))(1-\cos (\pi y))\sqrt{x^2+y^2}}{x^2 y^2 \sqrt{(1-\cos(\pi x))(2+\cos(\pi y))+(2+\cos(\pi x))(1-\cos(\pi y))}} $$ ...
0
votes
0answers
20 views

Max Min Problem based on inequalities

I am referring to the problem here I know that statement 2 is sufficient. Because when $ n = 0, p\leq 2.5 $ and when$ p = 0, n\leq 2.2222$ However, how does analyzing just these 2 scenarios (i.e. ...
2
votes
2answers
31 views

Estimating coefficients in a physical system based on observations

I have a physical system which can be modelled as $$Ax+By+C=0$$ I have thousands of measurements of $x$ and $y$ from the physical system (includes some noise). I want to optimize for $A$, $B$, and ...
0
votes
2answers
41 views

Proving inequality using Lagrange multipliers, somehow?

While going over assignments preparing for an upcoming exam, I noticed the question Prove that $x^{4} + y^{4} - 4b^{2}xy \geq -2b^{4} \text{ }\forall\text{ } x,y \in \mathbb{R}$ I had used ...
1
vote
0answers
13 views

Given model determine Least Squares estimate - is my graph correct?

Given the model $\alpha_1 I_k - \alpha_2 I_k^2 = I_{k+1}$ corresponding to measurements shown in the table below $k$ | 1 | 2 | 3 | 4 $I_k$| 0 | 1 | 10 | 80 | Determine the least squares ...
1
vote
1answer
44 views

What's the best way to optimize this energy function, and is it convex?

I have an energy function $E({\bf y})=||\,g({\bf Ay+c})-{\bf d}\,||^2_2 + ||\,{\bf y-e}\,||^2_2 + \alpha\,|{\bf y}|_1$ I need to minimize this with respect to $\bf y$, all other variables being ...
1
vote
0answers
40 views

Minimization of a multivariate quadratic equation

I am interested in the minimum of a general multivariate quadratic equation for non-negative real numbers: $$ \begin{aligned} & \underset{x_i}{\text{minimize}} & & ...
1
vote
1answer
16 views

What is the Dual of this particular Linear Program ( I get a weird Dual)

maximize $x_1-2x_2+3x_3-4x_4$ s.t. $x_1+x_2+x_3+x_4 = 20$ $x_1,x_2,x_3,x_4\geq 0$ The Dual can be found by transposing the constraint matrix and interchanging the objective function with 20 in ...
0
votes
2answers
79 views

Optimisation Problem

I'm given a lattice with particles having charges which have known magnitude but unknown signs. The primary aim is to stabilize the lattice (or decrease the force acting on the system) by assigning ...
1
vote
0answers
36 views

Implementation of EM algorithm for Gaussian Mixture Models using Matlab

Using the EM algorithm, I want to train a Gaussian Mixture model using four components on a given dataset. The set is three dimensional and contains 300 samples. The problem is that after about 6 ...
1
vote
1answer
28 views

L1 minimization linear programming

So suppose we want to minimize the sum of the absolute errors $\sum\limits_{i=1}^m |b_i - \sum\limits_{j=1}^n a_{ij}x_j|$ with respect to $x_k$ where $k=1,...,n$ So to formulate this as a linear ...
0
votes
2answers
114 views

how to check an optimization function is convex or not

This is the sparse coding optimization function: $\operatorname*{argmin}_{B, \alpha} \sum_j \| \bf{x}_j - B\bf{\alpha}_j \|_2^2 + \lambda\sum_j |\bf{\alpha}_j|_1$ I read in the literature that this ...
0
votes
1answer
304 views

optimization of a non-differentiable, component-wise step function

I would like to estimate the (local) minimum of a function $c:R^N \mapsto R^+$ where: $c$ is only differentiable almost everywhere, there exists a component $j$, such that $\frac{\partial ...
1
vote
1answer
25 views

Compute eigenvalues of Hessian = $\begin{bmatrix}a&1\\1&2\end{bmatrix}$ such that function is convex/eigenvalues $\geq 0$

The Hessian matrix is given to be $\begin{bmatrix}a&1\\1&2 \end{bmatrix}$ where $a$ is a real number. EDIT: So to find the eigenvalues I find the determinant which is ad-bc so 2a-1. So in ...
6
votes
2answers
3k views

Show that there's a minimum spanning tree if all edges have different costs

Show that there's a unique minimum spanning tree (MST) in case the edges' weights are pairwise different $(w(e)\neq w(f) \text{ for } e\neq f)$. I thought that the proof can be done for example ...
2
votes
2answers
489 views

Show that a graph has a unique MST if all edges have distinct weights [duplicate]

Prove that if all edge-costs are different, then there is only one cheapest tree (minimum spanning tree or MST). (Use contradiction and make sure to keep track of the costs of the different trees ...
0
votes
0answers
19 views

Quadratic Programming “big M” method

How does the optimization problem $$\min_{x,\eta} \frac{1}{2} x^TGx+x^Tc+M\eta$$ $$ s.t. Ax+\eta-b \geq0$$ $$\eta\geq0$$ look in standard form? What would the KKT look like? The problem is, that ...
0
votes
0answers
17 views

Quadratic optimization problem with quadratic equality constraint

I am trying to solve the following optimization problem: $$ \min_{x \in \mathbf{R}^2} \, x^T A x + b^Tx \quad \text{subject to $x^T J x = 1$} $$ where $A$ is a positive semi-definite $2 \times 2$ ...
0
votes
1answer
472 views

Shortest distance between parallel line and plane

I've been doing questions regarding the shortest distance between lines/planes and points , and I've come across a question asking to find the shortest distance between a line and a plane which are ...
1
vote
0answers
15 views

Optimization formulation for a dynamic system. Constructing constraints for a problem.

I am trying to formulate a problem that goes the following Min $f(.)$ This is a generalized objective function. Subject to, $x_{i}^{(t+1)} = x_{i}^{(t)} + r_{i}^{(t)} - x_{i}^{(t)}z_{i}^{(t)}$ ...
0
votes
0answers
19 views

Minimizing a quadratic form with orthogonality constraints

Suppose $A$ is an $n$-by-$n$ symmetric matrix, and I want to find $x_{1}$ and $x_{2}$ that maximize $x_{1}^{T} A x_{1} + x_{2}^{T} A x_{2}$ subject to the constraint that $x_{i}^{T} x_{j} = ...
0
votes
1answer
30 views

How do you go about solving partial differential equations for finding critical points in general optimization problems?

I was reading about partial second derivative test for optimization problems and I came across the example here. I saw the equations have yielded four critical points, but I wasn't able to find those ...
0
votes
1answer
1k views

How do I construct the Jacobian for use in a Levenberg-Marquardt algorithm.

I am working on a 3D reconstruction system and I am looking to use a Levenberg-marquardt algorithm to do bundle adjustment. I am not too sure about how LM works and what it requires. The model I am ...
1
vote
0answers
30 views

Minimizing sequences and topology (direct method)

To show the importance of the choice of the topology for the direct method we have been assigned the following exercise which I've not been able to solve due to my lack of understanding on how strong ...
1
vote
1answer
49 views

$\frac{1}{x+1}+\frac{1}{y+1} +\frac{1}{z+1}$ minimum value if $xyz$ =k.$x,y,z$ are positive reals.

$\frac{1}{x+1}+\frac{1}{y+1} +\frac{1}{z+1}$ minimum value if $xyz$ =k.$x,y,z$ are positive reals.I think the minimum should be when $x=y=z=k^{1/3}$. How do I show it? I tried to use AM-GM inequality ...
0
votes
3answers
23 views

The minimum of $\sum_{i=1}^m(c_ix-b_i)^2$

We know the minimum of $(c_ix-b_i)^2$ is $$x_i^*=\frac{b_i}{c_i}$$ How to show that the minimum of $\sum_{i=1}^m(c_ix-b_i)^2$ with $c_i \neq0$ is ...
1
vote
0answers
32 views

Need help using matlab optimization tools [closed]

I'm working on some project involving large scale matrix and i need your help to solve an optimization problem with matlab, the problem is the following: $ \min_L \{\alpha Tr(Y^{t}LY) + ...
0
votes
0answers
12 views

Surface fitting: Where to start from?

Often, we deal with identification problems such as identifying the parameters $\alpha_i$ where $z(x) = f_{\alpha_i}(x,y)$, which means simply $z$ is a function of $(x,y)$ and the parameters ...
1
vote
0answers
9 views

Consider $x = A[v]_+ + B[-v]_+$, under what conditions on A & B is there a solution v for every x

Consider the vector equality $$x = A[v]_+ + B[-v]_+$$ where $[v]_+$ is the elementwise rectifier function, i.e. $$[x]_+ = \begin{cases} x &\mbox{if } x > 0, \\ 0 & \mbox{otherwise}. ...
0
votes
0answers
13 views

Single variable optimization

A retail outlet for calculators sells 700 calculators per year. It costs \$2 dollars to store one calculator for a year; to reorder, there is a fixed cost of \$7 dollars plus \$2.25 for each ...
1
vote
1answer
54 views

Max flow on undirected graph with constrained edges

I've been trying for a while to develop an algorithm that counts the maximum number of disjoint vertex paths in a graph, but with an addition of "forced paths". Forced paths are here marked with bold ...
1
vote
1answer
547 views

Efficient Cholesky decomposition of inverse matrix

I want to generate random numbers from a multivariate normal distribution in Matlab. Normally, this is done like: $w = \overline{w} + \text{chol}(\Sigma) \cdot \vec{l}$ But in my case I don't know ...
0
votes
1answer
21 views

How to solve a Robust Linear Program problem?

How to solve a Robust problem? For example if I have the following Robust LP. minimize $\beta$ subject to $3x_1+4x_2 \leq7$ $3x_1 \leq7$ $x_1 \geq 0$ $x_2 \geq 0$ $-x_1+4x_2\leq\beta$ ...
2
votes
1answer
50 views

Is my Lagrange function correct? How can a point be a maximum and minimum?

minimize $3x_1^2+3x_2^2-2x_1x_2-12(x_1+x_2)+36$ s.t. $|x1+x2|=1$ Determine the maximum and minimum of this problem. The Lagrangian can be set up as: $L(x,\lambda)= ...
0
votes
1answer
116 views

Maximization of sum of functions

Let $w,a\in R^n$, and $B\in R^{n\times n}_{++}$ (the set of $n\times n$ positive definite matrices). We know that the following function (which is a specific form of the Rayleigh quotient) has a ...
2
votes
1answer
75 views

Unclear why the highest argument value for cosine function $\cos(x+\frac{\pi}{4})$ is $\frac{\pi}{2}$

The problem to solve is to find the values of $x$ with which the function $\sin(x)+\cos(x)$ will compute to its highest value. I checked the textbook's answers section: it has the function transformed ...
0
votes
1answer
47 views

Minimizing the area of the triangles containing a square of side $1$

This exercise is from a past admission exam to an Italian institute: Among all the triangles that contain a square of side $1$, which ones have minimum area? I have solved it, however I'd like ...
0
votes
0answers
23 views

How to find out if point is local Maximizer or local Minimizer ? Lagrangian is given

The Lagrangian is: $L(x,\lambda) = x_1x_2-2x_1-\lambda (x_1^2-x_2^2)$ Taking the derivatives and setting it equal to zero gives: $x_2-2\lambda x_1-2=0$ $x_1+2\lambda x_2=0$ $x_1^2-x_2^2=0$ The ...
0
votes
0answers
28 views

When exactly are quadratic objective functions polynomial time solvable

I'm considering quadratic programming problems of the form: $$ \max x^tQx+Bx$$ subject to the linear constraint $$ Ax \le b $$ I read that if is the case that $$ x^tQx + Bx \ge 0 \ \forall x$$ or ...
0
votes
1answer
53 views

Find the minimum of a function for only positive values of the vector variable

Let variable vector $\vec{q}$ of size $m\times1$, and its diagonal counterpart $m\times m$ matrix $Q=diag(\vec{q})$, for some $m\in\mathbb{N}$. Define fixed parameter $n\times1$ vectors $\vec{p}, ...
0
votes
2answers
26 views

Finding conditional extrema with trig functions

Find the conditional extrema of $$f(x,y)=\cos^2x+\cos^2y,\quad g(x,y)=x-y+\frac{\pi}{4}=0.$$ I have a problem with finding a solution to this problem. Using Lagrange multipliers i come up with a ...
1
vote
2answers
28 views

Optimization problem: maximise horizontal distance

Fifteen men are placed on a Dead Man's Chest in a rectangular pattern, with each man distant $a$ from his neighbours,thus: The average weight of the men is $w$, and the heaviest man weighs no ...
0
votes
2answers
33 views

Maximum likelihood of fraction

To maximize the log likelihood of my parameters, I need to find the argument that maximizes the following function: $$\sum_{\substack{i,\,j\\ i \neq j}} n_i \log(x_i) + n_j \log(x_j) - (n_i + n_j) ...
1
vote
1answer
26 views

Does given point satisfy FONC?

minimize $4x_1^2+2x_2^2-4x_1x_2-8x_2$ subject to $x_1+x_2\leq 4$ Does the point $(2,2)$ satisfy the FONC for a local minimizer? The gradient of the objective function is $\nabla f = ...
1
vote
1answer
98 views

quantum mechanics violate Bell's inequality

I have this function $$ \begin{aligned} F\big(\theta_a,\theta_b,\phi_a,\phi_b\big) = \ & – \big[\cos \theta_a \cos \theta_b \big] – \big[\sin\theta_a \sin\theta_b \sin\phi_a \sin\phi_b\big] \\ ...
1
vote
1answer
22 views

Is the given function convex? Does the point satisfy the FONC?

minimize $2x_1^2+x_2^2-2x_1x_2-4x_2$ subject to $x_1x_2\leq 4$ Is the objective function convex? Does the point $(1,4)$ satisfy the FONC for a local minimizer? Do optimal solutions of this given ...
0
votes
0answers
29 views

Learning to solve complex inequalities in many variables

below is a very specific inequality problem. I would like to know how to solve it so I can apply it to more complex problems. The equations are as follows: $$3.5x−2.5y−3z=A$$ $$−7.5x+3.75y+5.25z=B$$ ...
4
votes
2answers
122 views

How does one generate recognizable point-patterns on a plane?

I've recently learned that some smartpens (e.g. Livescribe) have a camera in their front part. They film the paper. You have to use special paper which looks as if somebody made a lot of tiny holes ...
0
votes
1answer
16 views

One definition of strong convexity (from textbook of Prof. Bertsekas in 2015)

In strong convexity, there are a few definitions, one of them is: $f$ is strongly convex over $\mathcal{C}$ with coefficient $\sigma$ if $\forall x,y \in \mathcal{C}$ and all $\alpha \in [0,1]$, we ...
1
vote
1answer
326 views

Gradient-descent and Hidden Markov Models

I would like to use gradient-descent to fit the parameters of a simple 2-state HMM. This paper Levinson, S. E., Rabiner, L. R. and Sondhi, M. M. (1983), An Introduction to the Application of the ...