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)

2
votes
0answers
20 views

Closest line to point after non-linear map

I have a map on a vector space $M(\vec{r})$, defined as below. All components (vectors, matrices, everything) are reals in the unit range $[0,1]$. The map $M(\vec r)$ is defined as the sum of an ...
0
votes
2answers
29 views

Rewrite matrix equation as a quadratic programming problem

Given real-matrix $X_{n\times p}$ how can the problem of minimizing $Tr(X^TA_{n\times n}X)$ under the constraint $Tr(X^TC)=\phi$ be posed as a standard convex quadratic program given by the form: ...
3
votes
3answers
105 views

Which statement “must be false”?

Given a function $f$ continuous on $[-4, 1]$ with its maximum at $(-3, 5)$ and its minimum at $(1/2, -6)$, is it not correct to say that both statements (B) and (D) must be false? (A) The graph of ...
0
votes
2answers
404 views

Optimization, rectangle inscribed inside arch of the curve.

A rectangle is to be inscribed under the arch of the curve $y = 4\cos(0.5x)$ from $x = \pi$ to $x = -\pi$. What are the dimensions of the rectangle with largest area, and what is the largest area? ...
0
votes
2answers
27 views

Minimizing cost for a given volume

288 m3 tank will be made in the form of a rectangular prism. The cost of 1 m2 of top and bottom walls is 40 euros. The cost of 1 m2 of side wall is 30 euros. What should be the edges to be cheap as ...
0
votes
2answers
934 views

Optimal Basic Feasible Solutions

In linear programming, is it true that you can only have at most 2 optimal basic feasible solutions? If so, why?
4
votes
1answer
86 views

Is this a known result?

I heard the following result and I am wondering if anyone can verify its correctness and also provide a source to cite. If the Lagrangian $L(x,\lambda)$ is convex in $x$ at the optimal Lagrange ...
1
vote
2answers
60 views

How does one verify if a vector is really recovered?

In compressed sensing, how to verify if a vector is really recovered or how does one plot the figures on recovery rate? Since in numerical experiments, there is always a difference between the ...
1
vote
2answers
15 views

KKT multipliers sign convention

We all know that if we have an optimization problem of the general form: $$ \min f(x) $$ subject to: $$\begin{align} h(x) &= 0 \\ g(x) &\le 0. \end{align}$$ Then, we have a vector of ...
4
votes
1answer
110 views

Smallest possible triangle to contain a square

I was looking at this stack exchange question* and started thinking about the case of a polygon with 4 sides: a square. The question asks for a program that can take a polygon of N sides and return ...
2
votes
2answers
317 views

Find the sparse representation in matlab

I have a dictionary(Matrix) D and an input(Vector) Y. Now I want to solve this problem: What is the Sparse Representation of input Y according to dictionary D. this problem is an important question ...
0
votes
0answers
32 views

Bilinear Constraint

I would like to formulate the following Optimization problem. My question is focused on the constraint. Given a "typical" objective function, e.g.: $$ \min c^T v $$ s.t. $$ 0 = a_1 v_1 - a_2 v_2 + ...
2
votes
1answer
68 views

Knapsack in graph

This question is from job interview for a software company.   "You are given an undirected connected weighted graph with $n$ nodes. The weight function represents transportation costs. In ...
0
votes
0answers
27 views

Can this problem be a form of Nonlinear Programming?

How we can reformulate blew problem as a form of nonlinear programming problems? $$ \begin{array}{ll} & \min&\frac{1}{x_1}+\frac{1}{x_2}+\cdots+\frac{1}{x_n} &\\ & ...
1
vote
1answer
31 views

Prove the solution $u_i$ of equation $\lambda r_i+\frac{1}{\theta}(u_i-v_i)+\beta \left (\sum_{i=1}^Nu_i-1\right )$

I have an cost function such as $$E(U)=\lambda \sum_{i=1}^{N} \int_{\Omega}r_iu_idx+\frac{1}{2\theta}\sum_{i=1}^{N} \int_{\Omega}(v_i-u_i)^2dx+ \frac{\beta}{2} \int_{\Omega}\left ( ...
0
votes
0answers
15 views

Jointly learning with dependences

I am looking for some directions/opinions regarding the following problem. I am new to this domain and although I searched in the web, I am totally lost on which direction to take. I have $n$ ...
2
votes
1answer
38 views

Optimization with Calculus

This one has me bugged big time. An architect needs to design a rectangular room with an area of 89ft^2. What dimensions should he use in order to minimize the perimeter? Round to the nearest ...
0
votes
1answer
16 views

Optimizing a positive definite quadratic form with inequality constraints.

I have a positive definite, multidimensional quadratic form: $(x-x_o)^t M (x-x_o)$, where the "${}^t$" indicates transpose and $M$ is a positive definite matrix (in fact, it is a multidimensional ...
0
votes
0answers
22 views

Transformation between two optimization problems.

Problem $1$ is as follows: \begin{equation} \max_{1{\le}i{\le}N}\min_{\{v_i\}_{i=1}^N\in\textbf{V}_{\gamma}}\left[\lambda_i - v_i\right] \end{equation} Problem $2$ is as follows: \begin{eqnarray} ...
3
votes
1answer
30 views

Proof that $\min_{b\in B} u(a,b)\leq \min_{b\in B}\max_{a\in A}u(a,b)$

So I have two finite sets $A,B$ and $u:A\times B\rightarrow \mathbb{R}$ a utility function. I am asked to give a certain proof but I don't need help with the whole thing, I just need help figuring ...
0
votes
0answers
22 views

Is there a solution/algorithm for a one-directional stable marriage problem?

I'm working on an application to assign summer camp kids to activities. The program input is a list of campers, and a ranked list of each camper's preferred activities. For example, Alice might rank ...
0
votes
0answers
20 views

Do the higher-order Frechet derivatives can be used in optimization?

I am working on inverse problem in seismics. In our community, we use 1-order and 2-order Frechet derivatives a lot to solve the inverse problems being posed. However, some seismologist verified that ...
0
votes
0answers
19 views

Newton-Raphson convergence for function $f(\gamma)$ with $\gamma \geq0$ constraint.

I am reading an (engineering) paper that in the part of their solution, They propose a 2-step iterative solution based on Newton-Raphson method for concave function $f$ as below : ...
1
vote
1answer
25 views

Game Theory (continuous utility, pure strategy)

I have a game in which two players, 1 and 2, choose a non-negative real number level of effort $e_1,e_2$ respectively. Their cost for this choice is $ce_i$ for $i=1,2$ where $c>0$ is the same for ...
1
vote
2answers
460 views

Prove that if all edge-costs are different, then there is only one cheapest tree.

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

Optimization by Symmetry?

Let $$f(x,y,a,b) := \frac{xa+yb}{\sqrt{xa^2+yb^2}},$$ where $x,y,a,b$ are all positive. Define $$g(a,b) = \min_{x+y=1,\,x,y\ge 0}f(x,y,a,b).$$ How would one solve for $g(a,b)$? I have solved this by ...
0
votes
0answers
11 views

How can we constrain lagrange multipliers in svm dual by adding constraints in primal problem?

Consider svm-dual,i.e., \begin{align} &\text{maximize} \sum_{i=1}^n \alpha_i-\frac{1}{2\lambda} \sum_{i,j=1}^n \alpha_i \alpha_j y_i y_j K(x_i,x_j)\cr &\text{subject to, } 0\leq \alpha_i ...
0
votes
2answers
26 views

Using optimization for a logarithmic function

Question: A tangent line is drawn on the graph of $y=\ln x$ for $0\lt x\lt 1$. A right triangle is thus formed in the fourth quadrant. If we regard the area of this triangle has a positive value, ...
9
votes
1answer
124 views

gradient flow on $SU(n)$

Define the following cost functions $f_1, f_2 :SU(n) \rightarrow \mathbb{R}$ by $f_1(U) = Re \left( \text{Tr}\left(G^{\dagger} U \right) \right)$ and $f_2(U) = \left| \left( \text{Tr}\left(G^{\dagger} ...
0
votes
1answer
29 views

Am I headed in the right direction with this area optimization question?

Question: A fence will create a rectangular area with one side being formed by an existing building (and hence, the fence only needs 3 sides). One side will be created using Redwood fencing and the ...
1
vote
1answer
12 views

Multi objective optimization: Ideal vector

I'm going to consider the two problem distinctly. Now I want to calculate $z_1^{id}$ and $z_2^{id}$ and $x_1^{id}$ and $x_2^{id}$ where $z_1^{id} = min(x)$ $z_2^{id} = max(y)$ $z_1^{id}$ is the ...
0
votes
0answers
11 views

Is this a Combinatorial Optimization problem with Multiple Constraint Satisfaction?

Given n-dimensional data consisting of over 20000 samples with 200 dimensions, using this as an example: ...
3
votes
0answers
49 views

Auction Design : Multiple lots, one win max per bidder, not regret

This is a real life game theory problem. I have to organize an auction. There is a finite number of lots, which are not equivalent. There is a finite number of bidders; the number of bidders is ...
1
vote
2answers
23 views

Bivariate optimal density

Consider any feasible $p:[0,1]^2\to [0,1]$ that allows discontinuities and the problem $$\min_{p(.)} \int_0^1\int_0^1 p(x,y)^2 dF(x) dG(y)$$ s.t. $$\int_0^1 p(x,y)dG(y)=k\phantom{0} for \phantom{0} ...
0
votes
1answer
37 views

Maximum number of teams of three people such that each team is built in one of two ways

A coach picks team members in two ways:   A. The team of three people should consist of one experienced participant and two newbies. Thus, each experienced participant can share the ...
-1
votes
0answers
20 views

How to transform this problem to a matrix optimization problem?

I wonder how can I loose the following set of equations to an optimization problem ? Suppose given three real vectors $w_0$, $f$ and $\delta$, and a positive entry vector $c$, such that for every ...
1
vote
1answer
432 views

Absolute extrema

Find the absolute extrema of the function $f(x,y)=2xy-x-y$ over the region of the xy-plane bounded by the parabola $y=x^2$ and the line $y=4$ I was wondering if I needed to use Lagrange multipliers to ...
4
votes
1answer
36 views

Why lower semicontinuity?

I'm reading a proof on the existence of a solution to a minimisation problem, but I'm stuck. I give a brief summary of the arguments up to the point at which I'm stuck(at the yellow box). ...
0
votes
1answer
56 views

Area of the figure within the circle and outside a polygon

For which values of the parameter $c \in \mathbb{R}$, the area $S$ of the figure $F$, consisting of the points $(x,y)$ such that $$\begin{gathered} \max \{ \left| x \right|,y\} \geqslant 2c \hfill ...
1
vote
2answers
55 views

is there a problem in the answer? finiding an angle

Can you tell me if there's an error in the answer ? Given isosceles $\triangle ABC$ ($AB=AC$) and $AB=b$. $BD$ is perpendicular to $AC$ and $DE$ is perpendicular to $BC$. $\angle BAC=2x$. The ...
2
votes
1answer
201 views

Regarding Nesterov's smooth minimization

I am currently studying this Nesterov's paper for project purposes, and I am trying to figure out how the smoothing and the minimization algorithm works I have tried looking at the example ...
0
votes
3answers
89 views

Find the function $\hat{g}$ that maximizes $\int_0^1 x^2g(x)dx$ over the set of all functions that satisfy the following conditions:

Find the function $\hat{g}$ that maximizes $\int_0^1 x^2g(x)dx$ over the set of all functions that satisfy the following conditions: $\int_0^1 |g(x)|^2dx =1$, $\int_0^1 g(x)dx=0$, and ...
2
votes
2answers
37 views

Differential equation for finding closest point on surface.

Inspired by this question I got to think about a more general case. Say I have any discretized surface and want to find closest point from each point outside of surface to the surface. Say that I can ...
4
votes
2answers
372 views

Derivation of Euler-Lagrange equation

Here is a simple (probably trivial) step in the derivation of the Euler-Lagrange equation. If we denote $Y(x) = y(x) + \epsilon \eta(x) $, I want to know why is $\dfrac{\partial ...
2
votes
1answer
40 views

An optimization problem, in the form of a word problem,

The manager of a $1000$ seat concert hall knows from experience that all seats will be occupied if the ticket price is $50$ dollars. A market survey indicates that $10$ additional seats will remain ...
2
votes
1answer
38 views

How come $Ax\le b$ and $c^Tx\ge \alpha +\epsilon$ has NO nonnegative solution.

Let $\alpha=c^Tx^*$ be the optimum value of the standard form of (LP)(= max $c^Tx$ subject to $Ax\le b$ and $x\ge0$ in $\mathbf{R^n}$) Then we know: $Ax\le b$ and $c^Tx\ge \alpha$ has a nonnegative ...
0
votes
1answer
13 views

Is there a name for this type of online optimization problem?

I have a sequence of items $1\leq i \leq n$ that arrive to me one at a time. Each item has a weight $w_j\geq 0$. If I pick up one item, I will not be allowed to pick up any of the next $k$ items ...
2
votes
3answers
121 views

How can I find the minimum value for $F(x,y,z,w)=x^2+y^2+z^2+w^2+xy+zw-xz-yw-yz$

Let $x,y,z,w$ be integer numbers,and $xw=yz+1$ Find this minimum of the value $$x^2+y^2+z^2+w^2+xy+zw-xz-yw-yz$$ This is how did it and I would like to know if I made a mistake Let ...
0
votes
0answers
22 views

Matrix Factorization with Arbitrary Dimensions

Continuation of a previous question here. Suppose I have a $n\times m$ matrix $A$. I choose some $k$, and want to find a factorization $A=XY$ where $X$ is $n\times k$ and $Y$ is $k\times m$. In ...
1
vote
2answers
28 views

Would like some help formulating an optimization problem

I have a function $f$ that takes $n \geq 1$ positive real-valued arguments $\mathbf{a} \in R^n_+$. This function is defined for all amounts of inputs (e.g. $f(1)$ and $f(3, \pi, 17)$ are both valid) ...