Wikipedia:Reference desk/Archives/Computing/2015 December 26

Welcome to the Wikipedia Computing Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

December 26

Quadratic Programming

Hi, I know that quadratic programming (finding the minimum of convex quadratic function under linear constraints) is in $P$. Is the problem of finding the maximum of convex quadratic function under linear constraints (assuming that the problem is both feasible and bounded) also in $P$? How can one solve this problem? 213.8.204.17 (talk) 08:03, 26 December 2015 (UTC)

Multiply the function by -1 and find its minimum - and the problem is reduced to a previously-solved problem. Maybe you should review symmetry in mathematics and other fundamental concepts before tackling more advanced numerical methods. If you're not seeing these fundamental relationships, you're not going to make real sense out of more difficult algorithm analysis topics, like whether the runtime is in P or NP. These aren't just letters for labeling groups of algorithms: to understand them, you need to really appreciate how different types of operations affect problem-complexity. Multiplying by a constant factor, or even rewriting a bunch of constant factors in the solution-method, has only a constant-factor impact on the time complexity of an algorithm. It does not change the complexity class and certainly does not move an algorithm from P into NP. Nimur (talk) 10:50, 26 December 2015 (UTC)

Except that when multiplying by -1 the function is not convex anymore but concave. Finding the maximum of a convex quadratic (or equivalently the minimum of a concave quadratic) certainly is in NP: It does even say so in our article on Quadratic Programming. Maybe user Nimur should read questions carefully before insulting other users. 79.247.226.200 (talk) 23:04, 27 December 2015 (UTC)

No offense is intended to anyone. You may be misunderstanding the word "convex", which in the context of "quadratic programming" refers to convex programming, convex functions, and convex analysis. This is a very different sense of the word, not to be confused with a convex lens. If you want to understand how the geometric concept of convexity does relate to its more abstract sense in mathematical analysis, the relevant articles are convex hull and convex set. The relationship between the two uses of this word - one purely geometric, and one in a more analytical sense, are due to a real mathematical and etymological relationship, but this is non-trivial to describe without using some really hard math. Have a read through our articles to get a feel for this topic.

Multiplying a convex function by a constant factor does not change its convexity; this has nothing to do with, e.g., a concave lens. In actual fact, some very confusing mathematical authors actually use concave as a synonym for convex. Don't get too hung up on this.

Lastly: with respect to whether the solution is in complexity-class P or NP: the article section referenced by 79.247.226.200 states:

"For positive definite Q, the ellipsoid method solves the problem in polynomial time."

If you would like to read more on the relationship between convex functions and positive definite matrices, the most appropriate and authoritative text is Golub's horrible Matrix Computations book; although Boyd's CVX book is now available in its entirety at zero cost. Or, from our article, positive definite matrix § quadratic forms:

"It turns out that the matrix M is positive definite if and only if it is symmetric and its quadratic form is a strictly convex function."

Nimur (talk) 23:17, 27 December 2015 (UTC)

I'm sorry Nimur but you're very wrong on this. You claim that "multiplying a convex function by a constant factor does not change its convexity", but multiplying a function by -1 in general does change the convexity. This is clear from reading just the introductory section of convex function. For the original question about quadratic programming, multiplying the function by -1 and propagating the change to the inputs changes Q to -Q and c to -c. This has the symmetry that it remains a quadratic programming problem, but running time is determined by convexity (whether Q is positive definite) and positive definiteness is not preserved when multiplying by -1. The section Quadratic_programming#Complexity says that the time complexity changes from P to NP-hard. Egnau (talk) 15:26, 28 December 2015 (UTC)

Well, you are welcome to your interpretation; but I do not believe I am wrong on these points. May I again refer you to the books that I linked? For example, page 2 of Boyd's book specifically addresses the issue:

"(We can also think of −f0(x) as representing the value, or utility, of choosing x.) A solution of the optimization problem (1.1) corre- sponds to a choice that has minimum cost (or maximum utility)..."

...specifically in reference to the sign convention. Surely, you don't think it's any more difficult to solve for the extreme point of a parabola if you multiply by negative one?

I'll quote Boyd once again, to back up my earlier assertion: if you're struggling with these elementary operations, you aren't going to stand a chance at understanding the harder details. But if you study the elementals really well, it's worthwhile:

"Developing a working knowledge of convex optimization can be mathematically demanding, especially for the reader interested primarily in applications. In our experience (mostly with graduate students in electrical engineering and computer science), the investment often pays off well, and sometimes very well."

With due respect, User:Egnau, but maybe you should defer your assertion that I have made some comment in error until after you review some of these resources? Numerical optimization theory is a topic with which I have some familiarity. If I am actually wrong, it will be very easy to demonstrate it. In the same spirit, we can show computer code that solves for minima or maxima with identical runtimes... in fact, such codes are provided in the books I referenced - which refutes your claim pretty exactly.

Nimur (talk) 16:57, 28 December 2015 (UTC)

I have already demonstrated that you are wrong about multiplying a convex function by a constant factor but you chose to ignore it in your reply. Do you agree that x² is a convex function and that -x² is not a convex function? Your Boyd book snippet is saying that you can minimize f0(x) or maximize -f0(x) because they are equivalent. It doesn't support your claim that maximizing f0(x) is equivalent. Finding the minimum of x² over an interval is easier than finding the minimum of -x² over an interval because there is only one local minimum to investigate instead of two. It's not a big deal in 1 dimension, but in higher dimensions when you minimize the negative of a convex function over a hypercube, there can be an exponential number of local minima because every hypercube corner can be one. This is essentially why the problem is so much harder compared to the unnegated version. Egnau (talk) 04:16, 29 December 2015 (UTC)

Syncing problems with bookmarks in Chrome

I have used Chrome's synchronized bookmarks feature on both a desktop computer and a laptop. Recently, however, when I have added a bookmark in Chrome on either computer it has not appeared on the other. Past bookmarks still appear on both, but for some reason new ones are not synced. I have tried signing out and logging in again, but that didn't help. Does anyone have any suggestions about how to re-synchronize my bookmarks? Eddie Blick (talk) 16:37, 26 December 2015 (UTC)

Are you synced through an account or a passphrase? --Cahrlework (talk) 21:37, 29 December 2015 (UTC)

Is installing latest chipset driver updates BIOS?

When someone installs the latest chipset driver for his CPU, is it also updating the BIOS? Can a BIOS update even be made from the Operating system layer? Thanks, Ben-Yeudith (talk) 22:21, 26 December 2015 (UTC)

The so-called chipset doesn't include the CPU, although particular chipsets are normally used with particular CPUs from the same era. If the chipset software you're talking about is this, for example, that's not a BIOS update. It's purely a Windows update, and not even a driver update; it seems to just add some product name strings so Windows will display the correct name for various Intel hardware.

There's no theoretical reason why you'd have to reboot into a bare-bones operating system to upgrade the BIOS, except that it's a more predictable environment, so it's slightly less likely that the machine will crash mid-upgrade. I think that many BIOS updaters from major vendors run under Windows now. -- BenRG (talk) 00:56, 27 December 2015 (UTC)

It's actually often been possible for nearly 15 years now. I remember a Windows flashing utility (Either AMI or Award) back in 1999-2001 supporting Windows 9x. Nowadays of course most BIOS/EFIs have built in updaters removing the need for fussing our around a boot disk, although you still generally have to have a partition somewhere with FAT/32 as they often don't read NTFS or anything else. Nil Einne (talk) 03:19, 27 December 2015 (UTC)

For Linux (and a range of other OSes, including Windows to some degree) there is the open source utility Flashrom, which will allow updates to BIOS/UEFI firmware flash devices on the motherboard (and on some adaptor cards too). It does it from the OS level, without reboots or FreeDOS or floppies or the like. It only requires that it be run as root, because it needs untrammelled access to memory. The central part of it is flashchips.c, which lists the devices it supports, their memory maps and control registers, and the method used to update them. For most BIOSes, the device appears in ordinary address space (for adapter cards the device usually has to be mapped into the PCI address space with a call to the PCI driver). Then a the flash can be written by setting some magic values in the device's control registers and streaming update data into it. -- Finlay McWalterᚠTalk 20:29, 27 December 2015 (UTC)

Flashing the BIOS is updating its firmware by writing it into the flash memory. Be careful, flashing a wrong firmware or interrupting the write procedure by reset or power lost by turning off or power failure causes failure of the firmware, making the next startup impossible. The wrong BIOS on a mainboard causes no picture on the screen. The BIOS for an other version of the mainboard causes failures in initializing optional components or hang the startup due try to initialize the changed hardware devices if this are the changes of the hardware revision like mutli-I/O devices including the PS-mouse and keyboard controller. When hardware becomes programmable like using FPGAs, drivers may do a temporary reprogramming of this device. In the next start the default programing is applied. Drivers initialize the peripheral device and filter or convert the input and output to the operating systems procedures. A printer driver is a output filter for the printed information. An ohter solution of programmable hardware was reprogramming the Code Morphing Software of Transmeta CPUs. These CPUs are a permanent emulator by the morphing code. Optimizing it was reprogramming the mophing code to utilize the CPUs circuits more efficiently. --Hans Haase (有问题吗) 12:34, 31 December 2015 (UTC)