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)

1
vote
1answer
52 views

need help with zero sum game

Tom chooses an integer in {1,2,3} and Bob chooses an integer in {2,3,4}. If the chosen numbers are the same, no money changes hands If the numbers are different the person who picks the bigger number ...
1
vote
1answer
37 views

Optimization of a Sum of Variables

Let there be variables $A$, $B$, $C$, $D$, and $E$ such that a total of $N$ points is allocated among the variables: $A$+$B$+$C$+$D$+$E$=$N$, $N$∈$ℝ$. Let the corresponding point values returned by ...
1
vote
0answers
58 views

How to solve Max under an integral?

This is the first time I come accross a Max function inside an integral. I have looked around online and did not find anything about it. I would like to know the rules of what can I do when I have an ...
1
vote
2answers
62 views

total least squares derivation with matrices

Taken from a computer vision book: "to minimize the sum of the perpendicular distances between points and lines, we need to minimize $$ \sum_i (ax_i + by_i +c)^2$$ subject to $a^2 +b^2 =1$. Now using ...
1
vote
0answers
26 views

Analytic solution for the maxima of a bivariate

I found the maximum of the function $f(x) = \frac{x e^{-x}}{1+1/k-e^{-x}}$ by reducing the first order necessary condition to $ke^{-x}+(1+k)(x-1)=0$, and from there the solution obtained with a ...
1
vote
0answers
123 views

optimization problem minimizing trace of a matrix with inverse

I am trying to solve the following problem $\min_{T} \operatorname{trace} \left( A(T^T M T + N)^{-1}A^T\right)$, where $T$ is the matrix I am solving for and $A$ is given, $M\succ0$ and $N\succ0$. ...
1
vote
1answer
30 views

Linear Optimization Study Material

I've recently enrolled in a linear optimization course, and it's been a while since I've taken linear algebra. I do not yet have access to the book for the course or I would skim it to see what I need ...
1
vote
0answers
29 views

Minimizing the sum of vectors

I have this problem: Given a set of unit vectors $\{ \vec{v_i} \}$, I want to determine another set, $W$, the element of which are in $\{ \vec{v_i} \}$(repeating allowed), so that the module of the ...
1
vote
1answer
62 views

Which Queue to Join at the Super Market

Last night I started wonder about the fastest way to take a shopping trip with my university flat mates and was wonder about how we should queue for the check out. I have a feeling that queue theory ...
1
vote
0answers
28 views

Sufficient condition for Lagrange function to be maximum or minimum

In optimization by Lagrange method, what is the sufficient condition for the Lagrange function to be minimum or maximum? Of course , I do know that in direct replacement method, Hessian matrix being ...
1
vote
2answers
60 views

Compressive Sensing matrix

I am working with compressive sensing recovery with image and I test with various sensing matrices: Case 1: Sensing matrix A of size MxN is i.i.d Gaussian matrix. Case 2: Sensing matrix A is size of ...
1
vote
1answer
60 views

solving a linearly-constrained sparse linear least-squares problem

Given the system of equations $Ax=b$, subject to $Cx\le d$ where $A$ is an $n\times m$ matrix (with $n>m$) and is very large and sparse. As an example $A$ can have $3126250\times 2740$ elements. ...
1
vote
0answers
45 views

Matrix multiplication in game theory doesn't add up? Min y^T*Ax

I'm studying game theory and something seems weird to me. My book says y is the probability of the row player and x is the probability of column player, both x and y are vectors. A = [a$_i$$_j$] is ...
1
vote
0answers
26 views

Constructing Matrix with Normal Distribution

I have a vector given whereby each element of the vector is assumed to be the average of one of a matrix' rows. Now I want to construct the matrix belonging to this vector, whereby the elements of the ...
1
vote
1answer
43 views

Locally minimizing a concave function

What will happen if we minimize a concave function via gradient descent? Where does it get stuck? Intuitively a concave function has more structure than an arbitrary function, and seem to be easier ...
1
vote
1answer
36 views

Complex argument and nyquist plot

I'm trying to sketch the nyquist plot of $$\frac{j\omega-1}{j\omega+1}$$ but can't seem to calculate the argument correctly. I think it should be $$\arctan(-\omega) - \arctan(\omega) = ...
1
vote
0answers
61 views

Infinity norm minimization

I am wondering how to minimize an objective function of the following form: $$\min_{\mathbf{x}\in\mathcal{R}^{MN}} \|\mathbf{x}-\mathbf{y}\|_\infty + \lambda\mathrm{TV}(\mathbf{x})$$ Here, ...
1
vote
1answer
47 views

First derivative test and uniqueness of local extrema

This is the context in which my question lies. See below for the actual question. Let $f(x)$ be differentiable everywhere and have a minimum at $x^*$. Then for every $x$ in a proper neighbourhood ...
1
vote
0answers
38 views

Euler Lagrange equations

I need to minimise $$\int\limits_\Omega|\nabla H_\epsilon(\phi)|\,dx\,dy$$ with respect to $\phi$. Where $H_\epsilon$ is the regularised Heaviside function, so that it is differentiable. This can be ...
1
vote
0answers
36 views

Non-convexity of an energy functional

How would I go about showing that the following Mumford Shah functional is not convex? $$E_{MS}(u,C)= \int_{\Omega} |u_{0}(x,y) -u(x,y)|^{2}\ dx\ dy + \mu \int_{\Omega \backslash C}|\nabla ...
1
vote
1answer
193 views

Absolute extrema of a multivariable function bounded by an ellipse

I have a function $f(x,y) = 2x + x^2 + y^2$ bounded by the ellipse $x^2 + 4y^2 \leq 24$ I know how to determine the extrema within the ellipse by getting the partial derivatives and setting them to ...
1
vote
0answers
49 views

Minimising waste in a cutting problem.

I have three possible board sizes: $8$, $10$ and $12$ feet long. I want to make some number of cuts to these, say, $3, 2,1,1,1,6,5,3,4,2,1$ feet cuts and I want to minimize waste. I've done a quick ...
1
vote
0answers
18 views

Comparing the hardness of optimizing two similar, but different expressions

Suppose we have binary variables $y_1, ..., y_n$. To make the representation simple, we show the concatenated vector as $\mathbf{y} = (y_1, ..., y_n)$. Consider the two following functions: $$ ...
1
vote
1answer
22 views

minimizing a function involving exponential term

Let $w\ge e$ . I want the following $$ \min_{r\geq0} r(e^r-w) $$ Is there any way to find it. Thanks.
1
vote
0answers
38 views

Interpreting constraints in an optimization problem

I am working on an optimization-based image denoising project in which I have three "flavors" of an optimization problem, one constrained and two unconstrained. They are given as follows: ...
1
vote
1answer
23 views

examination of the function

I need help.. Question An examination of the function $f:\mathbb{R}^2 \to \mathbb{R}$, $f(x,y) = (y-3 x^2)(y-x^2)$ will give an idea of the difficulty of finding conditions that guarantee that a ...
1
vote
1answer
364 views

Smooth approximation of maximum using softmax?

Look at the Wiki page for Softmax function (section "Smooth approximation of maximum"): https://en.wikipedia.org/wiki/Softmax_function It is saying that the following is a smooth approximation to the ...
1
vote
0answers
77 views

Formal definition of convexity for multivariate function?

Let $M\in R^{M\times N}$, a function $f: M\rightarrow R$ is called convex on $M$ if $f\big((1-\lambda)X1+\lambda X2, (1-\lambda)Y1+\lambda Y2\big) \leq (1-\lambda)f(X1,Y1) + \lambda f(X2,Y2)$ For ...
1
vote
0answers
65 views

How to find fitting parameters of the function?

I have the function describing the experimental data - $f(x)$. I also have another function - $g(x, \bar{p})$, which is the theoretical function for the process involved. Here $\bar{p}$ - is the ...
1
vote
0answers
23 views

Optimize profit given complete market information

Assume there are $N$ market participants (on the order of several hundred), and $M$ items (several thousand) being bought and sold on a market. For each participant/item pair, you know how many units ...
1
vote
0answers
33 views

Optimizing over a set of optimization problems

This is my first time asking an optimization question on here, so I am looking forward to see what will happen here. In the lack of a better title, I wrote it as it is. At a high-level, I can perhaps ...
1
vote
1answer
50 views

Convex Functions and Subsets

Suppose that $f, g: \mathbb R^n \to \mathbb R $ are $C^1$ convex functions. Show that $C = ${$\mathbf x \mid g(\mathbf x) \leq 0$} is a convex subset of $\mathbb R^n$. Show that if $\nabla f(\mathbf ...
1
vote
0answers
69 views

Linear Programming, Optimal Solutions

I posted the whole question to give some context, but my problem lies with (iv). I think you're meant to use a formula for the generalization of the optimal solution, but I'm not really sure what ...
1
vote
0answers
51 views

Optimization issue, how to obtain the maximal value?

$ max f(\beta)=\frac{\beta}{1+\beta}\cdot \left(1- \frac{\binom{N+B}{B}\cdot\beta^B} {\sum_{i=0}^B {\binom{N+i}{i} \cdot \beta^i}} \right)$ where $\beta\in[0,\infty)$, $N$ and $B$ are identified ...
1
vote
0answers
43 views

Inequality optimization, KKT condition.

So we have the problem: maximize $x^2+y^2$ subject to $x^2-y \leq3$ and $y\leq 1$. And I sorted out the KKT conditions for the problem (is here where the problem is?): $2x=\lambda _12x$, ...
1
vote
0answers
38 views

Understanding optimization on non-compact region

Say we have $f(x,y) = x^2 e^{-x^2 - y^2}$ and we want to optimize it over $\mathbb{R}^2$. The minimum value is $0$ since $f(x,y) \geqslant 0$; the question is whether a maximum value exists or not. ...
1
vote
0answers
52 views

How to find the maximizer in the Legendre transform of cumulant generating function?

Cramer's theorem in the large deviations theory gives the rate function $\sup_{\boldsymbol{\lambda}} \left<\boldsymbol{\lambda},\,\mathbf{b}\right>-\log\int_{\mathbb{R}^n} ...
1
vote
0answers
41 views

Quickly checking if an inequality holds on a convex region

Let $C$ be a given convex polygon in $\mathbb{R}^2$ containing the origin and let $a$, $\mathbf{b}$, and $Q\succeq0$ be a given scalar, vector, and matrix respectively. Is there a fast way to verify ...
1
vote
1answer
41 views

Reverse engineering the objective function

If there is a finite iteration algorithm can we find a function that this algorithm optimizes, in hindsight? Edit: Suppose there is a set of functions $f_i(x)$, where $x\in \mathbb R^n$, ...
1
vote
0answers
31 views

Optimization non-compact region

I've unsuccessfully been looking all over the web for examples on optimizing multivariable, real-valued functions over non-compact regions. As I've understood it, such optimizations are essentially ...
1
vote
0answers
43 views

Finding a minimization problem corresponding to a PDE

I was trying to find an equivalent minimization problem to the following PDE in $\Omega \subset \mathbb{R}^2$ $$ \Delta^2 u-\nabla \cdot (k(x,y) \nabla u)+\lambda u = f(x,y) $$ where $\lambda >0 $ ...
1
vote
0answers
36 views

Finding 'closest' function subject to constraints on derivatives

Suppose I have a real-valued function $f(t)$ for $t\in[0,T]$ s.t. $f'''(t)$ is defined as piecewise constant values: $$ f'''(t) = \begin{cases} k_0, & 0 < t \le t_0 \\ k_1, & t_0 < t ...
1
vote
0answers
51 views

Conjugate Gradient Method Near Exact Line Search

Unlike Newton-type methods, there is no natural step-length value $\alpha _k$ in conjugate gradient methods. Because of this, why do we need to use a near exact line search if we are to expect rapid ...
1
vote
0answers
57 views

Minimizing distance between 2 arrays (or points)

I would like to get a solution or receive guidance on how I can solve the optimisation problem below. Let's say I have two arrays of length N , say A and B, and I want to find 2 coefficients $k_1$ ...
1
vote
0answers
35 views

Finding coordinates of nodes in a graph

I have a complete graph in which the edges represent the euclidean distance between the nodes which is known. Assuming a node to be (0,0), I want to find (approximately) the coordinates of other ...
1
vote
1answer
32 views

$\max_x \max_y f(x,y) = \max_y \max_x f(x,y)?$

Just come across a question regarding sequential maximization and simultaneous maximization, and I do not recall whether there are any established conditions for the equivalence. Anyone has some idea? ...
1
vote
0answers
73 views

Finding minimum value of trigonometric function

Find the minimum value of $$\displaystyle \frac{2\cos^{-1}(x)}{\pi(1 - x)} , x \in [-1,+1) $$
1
vote
1answer
89 views

Minimize the minimum - Linear programming

Consider an optimization problem with variables $x_1, x_2, \dots, x_n \in \mathbb{R}$ (maybe subject to some linear constraints), and linear functions $\{f_i(x_1, \dots, x_n)\}_{1\leq i\leq m}$. We ...
1
vote
0answers
31 views

Optimization that involves inverse operation.

$\newcommand{\diag}{\operatorname{diag}}$ I have the following optimization problem: \begin{align} \mathop{\arg\min}_\beta & \frac{1}{2} a' [ M + \diag( \beta ) \otimes I_d ]^{-1} a + ...
1
vote
2answers
122 views

steepest descent with quadratic form converge in 1 iteration

Well I'm stuck on an exercise given: The steepest descent method is applied to the quadratic form $$Q(\mathbf{x}) = \tfrac{1}{2}\mathbf{x}^TA\mathbf{x} - \mathbf{b}^T\mathbf{x} + c$$ where $A$, ...