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
5answers
147 views

Maximum value of $ x^2 + y^2 $ given $4 x^4 + 9 y^4 = 64$ [closed]

It is given that $4 x^4 + 9 y^4 = 64$. Then what will be the maximum value of $x^2 + y^2$? I have done it using the sides of a right-angled triangle be $2x , 3y $ and hypotenuse as 8 .
1
vote
1answer
45 views

how to find the solution of this cost function?

I have the following cost function. $J = \sum_{i=1}^N a\, Trace(W^TX_iW) - b\, Trace(W^TY_iW)$ Where $X_i$ and $Y_i$ are symmetric matrices, $a$ and $b$ are scalars. How can I find W?
1
vote
1answer
114 views

Maximization under Kronecker product vectors

I need some hints to solve the optimization problem on $\mathbf{x}$ and $\mathbf{y}$ \begin{equation} \begin{array}{c} \text{max} \hspace{4mm} (\mathbf{x}\otimes \mathbf{y})^TA(\mathbf{x}\otimes ...
1
vote
3answers
385 views

Local optimality of a KKT point.

Consider the problem \begin{equation} \min_x f(x)~~~{\rm s.t.}~~~ g_i(x)\leq 0,~~i=1,\dots,I, \end{equation} where $x$ is the optimization parameter vector, $f(x)$ is the objective function and ...
1
vote
1answer
167 views

Solving a Non-linear Multivariable System of equations

How would I go about solving a system of nonlinear equations where the highest degree is two? For example: $$f_1(x) = f_1(x_1, x_2,\dots, x_n) = 0,$$ $$f_2(x) = f_2(x_1, x_2,\dots, x_n) = 0,$$ ...
1
vote
1answer
266 views

Formulate the Marriage Problem into a Maximum-flow problem (Graph theory)

Suppose I have $M=\{1,\ldots, n\}$ men and $W = \{1, \ldots, n\}$ women and $B =\{1, \ldots, m\}$ brokers, such that each broker knows a subset of $M \times W$ and for each pair in this subset a ...
1
vote
3answers
131 views

Confounding Lagrange multiplier problem

Optimize $f(x,y,z) = 4x^2 + 3y^2 + 5z^2$ over $g(x,y,z) = xy + 2yz + 3xz = 6$ According to the theorem the gradients must be parallell, $\nabla f = \lambda \nabla g$, so their cross product must ...
1
vote
1answer
556 views

Find the ellipse inscribed in a triangle having the maximum area

If we have a triangle of sides $a,b,c$, there are infinite ellipsis inscribed in the triangle. How can I find that having the maximum area? Is this ellipse the circle, or in what cases the maximum ...
1
vote
1answer
58 views

$AB$ is a chord of a circle $C$. Let there be another point $P$ on the circumference of the circle, optimize $PA.PB$ and $PA+PB$

$AB$ is a chord of a circle $C$. (a) Find a point $P$ on the circumference of $C$ such that $PA.PB$ is the maximum. (b) Find a point $P$ on the circumference of $C$ which maximizes $PA+PB$. My ...
1
vote
1answer
163 views

Free software or algorithm for Second-Order Cone Program

I need to solve the following optimization problem: $$ \mathbf{x}^\ast = \operatorname{argmin}_{\mathbf{x}} \Vert \mathbf{Rx} \Vert_2^2 \;\;\; \mathrm{s.t.} \;\;\; \mathbf{s}^\mathrm{H} \mathbf{x} = ...
1
vote
2answers
363 views

Value minimizing mean absolute percentage error

What value for $c$ would minimize the formula: $$\frac{1}{n}\;\sum^{n}_{i=1}\left | \frac{y_i-c}{y_i}\right|$$ given the values $y_1, ..., y_n$. For example in the mean squared error we have the ...
1
vote
0answers
113 views

extreme value of increasing or decreasing function

From the three problems: one, two and three, it seems that if $f(x)$ is decreasing function with $a+b+c=abc$ or $a + b + c + a b + b c + c a = 1 + a b c$ then the maximum value of $f(a)+f(b)+f(c)$ ...
1
vote
2answers
531 views

Determine all the extrema of a function subject to a non-linear constraint.

QUESTION Determine all extrema of the function $$f(x,y) = x+ 2y $$ subject to $$x^2 + y^2 - 80 = 0$$ ATTEMPT I don't think I understand what I'm supposed to do. This was in a test and I ended up ...
1
vote
1answer
2k views

“Box With No Top” Optimization

I am having some trouble with this problem, A box with no top is to be constructed from a piece of cardboard of dimensions $A$ by $B$ by cutting out squares of length $h$ from the corners and ...
1
vote
2answers
658 views

Sign restriction on the Lagrange multiplier? Why?

Say we are given a linear program where the goal is to minimize $c^Tx$ with the constraints $Ax\ge b$. Why is there a sign restriction on the Lagrange multiplier associated with the active constraints ...
1
vote
0answers
461 views

Notation for limit points of a minimizing sequence: $\arg \inf$

Could you tell me what is the accepted notation for the set of limit points of a minimizing sequence. For example, if I have a function $f(x)$ and a sequence $x_t$ such that $\lim f(x_t) = \inf ...
1
vote
1answer
380 views

Sudoku mathematically, MILP?

My homework contains a word (freely-translated) "target-function" that I should generate somehow for 9x9 sudoku solver with some MILP problem. But I am bit lost what they mean. I have sofar described ...
1
vote
1answer
274 views

Questions about weak duality theorem

Following are some corollaries regarding the weak duality theorem. Consider a constrained problem, $\min_{x \in X} f(x),$ subject to $g(x) \leq 0$ and $h(x) =0$. Its dual problem is $\sup_{u \geq ...
0
votes
1answer
44 views

Travelling salesman problem as an integer linear program

So the travelling salesman problem is a problem wherein a salesman has to travel through all cities in a way that the total travelling distance is minimal. You can rewrite this as an integer linear ...
0
votes
2answers
30 views

How to design a closed rectangular box of minimum cost using Lagrange Multipliers

Suppose the box is to be of volume $V_0$ cubic cm; and the cost of material for the front and back sides is $b$ dollars per square cm, $c$ dollars per square cm for the left and right two sides, ...
0
votes
2answers
30 views

By using slack(free) variable, solutions of both min and max problems

$$F(x,y)= 2x^2-3y^2-2x$$. $$\text{s.t.} \ \ \ \ \ \ x^2+y^2\le 1$$ By using slack variable (free variable,), I want to solve minimum and maximum problems. I want to solve this problem for maximum ...
0
votes
1answer
82 views

Why are the quantities equal to 0?

I am looking at the general form of the Simplex algorithm with the use of tableaux. $\overline{x_0}$ is a basic non degenarate feasible solution and thus the columns $P_1, \dots, P_m$ are linearly ...
0
votes
1answer
55 views

Find $\min x^TAy+b^Tx+c^Ty$ subject to $1^Tx=1^Ty=1,x\ge 0,y\ge 0$

The problem seems to be easy but I can't find a solution :( Problem: Given $A\in\mathbb{R}^{m\times n}, A\ge 0, b\in\mathbb{R}^{m}, c\in\mathbb{R}^{n}$. Minimize $f(x,y) = x^TAy+b^Tx+c^Ty$ subject to ...
0
votes
1answer
70 views

Distribute small number of points on a disc

Firstly I strongly know how many similar questions there are here. It's about sets of evenly distributed points inside a circle. If we need a big set of such points, good solutions are: Isocell ...
0
votes
2answers
181 views

The maximum volume of Tetrahedron

A optimization problem: Get the maximum volume of a tetrahedron its 4 vertices on the surface of cube whose edge length is 1 . From the geometrical intutition ,we can get : Selecting ...
0
votes
0answers
68 views

Can a polygon with minimal perimeter self-intersect?

Recipe. Do the following. Throw $N$ random points $(x_0,y_0),(x_1,y_1),x_2,y_2),\cdots,(x_{N-1},y_{N-1})$ in the plane.Define $(x_N,y_N)=(x_0,y_0)$ : enumeration is $\mod N$ . These points are joined ...
0
votes
1answer
206 views

Maximizing the volume of a box using Lagrange multipliers

We are given a box of surface area $64$. As such, I wish to maximize $f(x,y,z) = xyz$ subject to $g(x,y,z) = 2(xy+xz+yz) - 64$. If I have understood in correctly, I am to find the critical points of ...
0
votes
1answer
24 views

Are there known patterns among minimal expressions?

Let $R = F[z_1, z_2, \dots]$ be the finite-degree polynomials in a countable number of variables. Let $\mathcal{E}(R)$ be the set of all expressions of polynomials. Note that there could be an ...
0
votes
1answer
87 views

Homogeneous function has its derivative homogeneous of one less degree

This is from Simon and Blume's Mathematics for Economists: But, for LHS, applying Chain rule goes:$$\dfrac{\partial f}{\partial(tx_1)}(tx_1,\dots,tx_n)\cdot\dfrac{\partial(tx_1)}{\partial ...
0
votes
1answer
39 views

Proving an inequality involving multiple constraints

Let $R$ be a discrete set and let $f:{\left[ {0,1} \right]^{\left| R \right|}} \times {\left[ {0,1} \right]^{\left| R \right|}} \to \mathbb{R}$ be defined as $f\left( {{\mathbf{x}},{\mathbf{y}}} ...
0
votes
1answer
1k views

Local extreme value & saddle point: multi variable calculus

I am asked to find all local extreme values & saddle points of $$f(x,y) = 2x^2 + y^2 - xy - 7y + 8$$ $$f_x(x, y) = 4x-y, \qquad f_y(x,y) = 2y-x-7$$ $$f_x(x,y) = 0, \qquad y = 4x$$ $$f_y(x,y) ...
-1
votes
1answer
101 views

Lp optimal solution question

i have a general question. if there is a general LP problem $c^Tx$ s.t $A\cdot x \le b$, and $x \ge 0$ and assuming that the components of $c$ are non-zero entries then how can I prove that when $x$ ...
-2
votes
2answers
4k views

Minimum ladder over wall optimization

A fence 6 feet tall runs parallel to a tall building at a distance of 2 feet from the building. We want to find the the length of the shortest ladder that will reach from the ground over the fence to ...
7
votes
1answer
6k views

Split a set of numbers into 2 sets, where the sum of each set is as close to one another as possible

Given a set of numbers, I'd like to split this set into 2 sets, where the sum of each set is as close to equal as possible. How would I go about doing this in a programmatic way? Thanks in advance ...
7
votes
0answers
216 views

Optimization of relative entropy

Wondering if my following question is an application of information theory: Lets say we have a factory and ship boxes of stuff outside. If a competitor stands outside my factory, observes the stream ...
5
votes
1answer
398 views

Find extremes of function $f(x,y,z) = x^2y + y^2z + x - z$

I am preparing for an exam tuesday morning and I would like to ask you, if someone could please review my solution for the following excercise. I don't have the correct answer so I am unable to check ...
5
votes
1answer
593 views

Find minimum in a constrained three-variable equation

After my last question I have worked through the math quite a bit and now I'm stuck again. This time my question is less wordy. I have two equations for $t$, one with respect to each $a_{x}$ and ...
4
votes
1answer
281 views

Minimize Frobenius norm with unitary constraint

I am trying to find a unitary tramsformation, $M$, that minimizes $\Vert MA-B \Vert_F^2$ where $A$ and $B$ are $N\times L,\;L\ge N$. I know how to solve it without the unitary constraint. I thought ...
4
votes
0answers
309 views

Optimizing non linear programs of two variables

The scenario is; We've got $n$ stationary 360$^{\circ}$ sensors in an confined area (each sensor is located at some arbitrary $\left(x,y\right) = \left(x_{n},y_{n}\right)$), once a unit $t$ enters ...
4
votes
4answers
632 views

Approximate a function over the interval $[0, 1]$ by a polynomial of degree $n$ (or less).

To approximate a function $G$ over the interval $[0,1]$ by a polynomial $P$ of degree $n$ (or less), we minimize the function $f:R^{n+1} \to R$ given by $F(a) = \int_0^1 (G(x) - P_a(x))^2\,dx$, where ...
4
votes
3answers
3k views

Prove $ax - x\log(x)$ is convex?

How do you prove a function like $ax - x\log(x)$ is convex? The definition doesn't seem to work easily due to the non-linearity of the log function. Any ideas?
4
votes
1answer
241 views

Computing the volume of a set efficiently

Given a set of vectors $\mathbf v_i$ for $i=1,\dots,k$, $\mathbf v_i \in \{0,1\}^n$, is that possible to efficiently find the volume of the set, $$\left\{\mathbf x \in [0,1]^n:\mathbf x \le ...
4
votes
1answer
93 views

Is $f(t)=t^\alpha$ for $\alpha\in(0,1)$ a sub-additive function? [duplicate]

Possible Duplicate: Does $|x|^p$ with $0<p<1$ satisfy the triangular inequality on $\mathbb{R}$? Is the function $$f(t)= t^{\alpha},\quad \alpha\in (0,1)$$ a subadditive ...
4
votes
2answers
1k views

Minimizing weighted sum of distances

given a set of coordinates and the following function: cost = $\sum \sqrt{(x_i−X)^2+(y_i−Y)^2}w_i$ I would like to find the point (X, Y) for which this function is minimal. A simple example shows ...
4
votes
1answer
671 views

Question about the simplex method complexity

So I know that in general the simplex method for linear and convex quadratic programming can require exponential time. But assuming a positive semidefinite quadratic program that is solvable by the ...
4
votes
3answers
702 views

Optimally combining samples to estimate averages

Suppose I have two tables, each of unknown size, and I'd like to estimate the average of their true sizes. I hire 2 contractors: one guarantees good precision (i.e., her measurement ...
3
votes
1answer
135 views

binary quadratic optimization problem

I am trying to solve the following binary quadratic program. $$ \min_{\Delta} \Delta^T H \Delta + c^T\Delta \\ \text{Such that:} ~~~\Delta\in \{0,1\}^n ~~\text{and}~~ \sum_{i=1}^n \Delta_i \leq \Gamma ...
3
votes
0answers
52 views

Online stochastic convex optimization.

I need to find/approximate the argument that minimizes a stochastic convex function $F(\theta, Z)$: $$ {\arg\min_{\theta}} E_{Z}[ F(\theta, Z) ]$$ Where $Z$ is some random variable (we could assume ...
3
votes
2answers
480 views

How to maximize area of two circles inside a rectangle without overlapping?

Two circles have to be drawn inside a rectangle of dimensions $W\times H$ such that the area of both circles is to be as large as possible without overlapping. Let the radii of the circles be $r_1$ ...
3
votes
3answers
358 views

A primitive function of $ e^{x^{2}} $

I made some efforts to set a closed form of primitive function of $ e^{x^{2}} $ i find this function : $ f(x)=\frac{x}{2x^{2}-1}e^{x^{2}} $ where : $f'(x)=(\frac{x}{2x^{2}-1}e^{x^{2}})'$= ...